Sea $n$ un entero positivo. Se tiene un tablero de $(2n)\times (2n)$, donde $3n$ de sus casillas están marcadas. Probar que es posible eliminar todas las casillas marcadas, eliminando $n$ filas y $n$ columnas.
Llamemos "vacías" y "unitarias" a las filas/columnas con ninguna y sólo una casilla marcada, respectivamente.
Ahora bien, la configuración para obtener el mayor $n$ de filas y columnas que sea necesario eliminar, es la que tendrá en cada fila y columna marcada al menos una casilla.
Para ello, cada casilla a marcar será aquella que haga que una fila y una columna vacías se conviertan en unitarias. Por esto mismo, la cantidad de casillas a marcar será $2n$ (una configuración posible podría ser $a_{11}, a_{22}, a_{33},..., a_{(2n)(2n)}$), siendo $a_{bc}$ la casilla ubicada en la fila $b$ y columna $c$ del tablero.
Por tener el tablero cuadrado $2n$ de lado y $3n$ casillas pintadas, por el principio del palomar tendremos que las filas/columnas no serán todas unitarias, y por ser $3n-2n=n$, como máximo se tendrán $n$ filas y $n$ columnas no unitarias, pues cada una de las $n$ casillas que falten marcar, se repartirán en -a lo sumo- $n$ filas y $n$ columnas (razonamiento ya expuesto en el 2º párrafo)
Para comenzar a eliminar, decidimos comenzar con las filas $f$ que no sean unitarias. Esto es posible, pues $f\leq n$. El caso $f=n$ sería el de $n$ filas con $2$ casillas marcadas. En caso de ser $f\leq n$, se tacharán luego $n-f$ filas unitarias, para completar las $n$ filas tachadas. De esta manera, al eliminar $n$ filas, también habremos eliminado $n$ columnas (al menos una de ellas no unitaria ($m$), tal que $1\leq m\leq n$), con lo que sólo restará eliminar $n$ columnas, las que a lo sumo podrán tener $n$ casillas marcadas, y por lo tanto a lo sumo ser $n$ columnas no vacías (unitarias), lo cual implica que tachando estas $n$ columnas ya no quedarán casillas marcadas sin eliminar. Se tiene entonces que será posible eliminar todas las casillas marcadas del cuadrado, tachando como máximo $n$ filas y $n$ columnas ($Q.E.D.$)
