Como se mencionó en la pista, lo primero que va a generalizar la cuestión de la siguiente forma. Los enteros $1, \ldots, mn$ están dispuestas en un $m\times n$ matriz. En cada fila, el $r \le n$ números más grandes son de color rojo, y en cada columna, el $b \le m$ números más grandes son de color azul. Demostrar que hay al menos $rb$ números de color púrpura.
La prueba de esto es por la fuerte inducción en $m+n+r+b.$ Base de los casos son fáciles de comprobar, así que voy a saltar por encima de ellos. Ahora, considere el más grande de un solo color número $x$ (si no existe tal número, entonces obviamente la vamos a hacer). Sin pérdida de generalidad, supongamos $x$ es de color rojo. La columna que contiene este número ha $b$ números de color azul, ninguno de los cuales se $x,$ desde $x$ es de un solo color. Pero esto significa que todos los $b$ de estos números es mayor que $x,$ donde todos ellos deben ser de color rojo, por supuesto. Por lo tanto, esta columna contiene $b$ números morados.
La eliminación de esta columna, se obtiene un $m\times (n-1)$ matriz donde cada fila, al menos $r-1$ de los números más grandes son de color rojo, y el $b$ números más grandes son de color azul en cada columna. Por inducción, esto produce que, al menos, $(r-1)b$ números morados, por lo que la adición en el original $b$ da $rb,$ como se desee.
Comentario: Algunos de ustedes pueden notar que el problema generalizado en realidad no dar de inmediato el resultado en el último párrafo, ya que en el subarray, no estamos mirando los números de $1,\ldots, m(n-1).$ Esto se puede remediar fácilmente mediante la modificación de la declaración de $mn$ distintos números reales.
