En cada casilla de un tablero de $n\times n$ se escribe un número de forma tal que no haya dos filas exactamente idénticas. Probar que se puede sacar una columna de forma que en el nuevo tablero no haya dos filas exactamente idénticas.
Aclaración: Dos filas son exactamente idénticas si tienen en cada posición el mismo número.
Supongamos lo contrario, es decir, que sin importar que columna quitemos, entonces hay dos filas que nos quedan exactamente idénticas.
Vamos a armarnos un grafo $G$ de $n$ vértices, en donde el vértice número $i$ va a representar la $i$-ésima fila.
Para cada una de las $n$ columnas, sabemos que quitandolas nos quedan dos filas completamente idénticas. Consideremos la $k$-ésima columna y supongamos que al quitarla las filas $i$ y $j$ quedan idénticas (si hay mas de un par, nos quedamos con solo uno). Entonces en $G$ unimos mediante una arista el vértice $i$ con el vértice $j$.
Notemos entonces que nos quedan $n$ aristas en $G$, una por cada columna. Voy a utilizar el siguiente lema (que no demostrare):
Lema: En todo grafo de $n$ vértices con $n$ aristas, hay al menos un ciclo.
Utilizando el lema en $G$, obtenemos un ciclo que llamaremos $i_1,i_2,\ldots,i_m$ con $m \geq 2$. Sin perdida de generalidad, la arista que une a $i_1$ con $i_2$ proviene de la primera columna. Entonces $i_2,i_3,\ldots,i_m$ tienen el mismo valor en la primera columna. Pero $i_m$ con $i_1$ también, o sea que $i_1$ y $i_2$ tienen el mismo valor en la primera columna. Esto es una contradicción, porque entonces las filas $i_1$ y $i_2$ serian idénticas.
El absurdo provino de suponer que el enunciado era falso, por lo que debe ser verdadero.
Vamos a proceder por el absurdo y vamos a suponer que no puedo sacar una columna y lograr que en el nuevo
tablero no haya dos filas exactamente idénticas. Luego, para cada elección de columna que saque, va a haber al menos dos filas que sean exactamente idénticas en el nuevo tablero. Sean $f_1, f_2,..., f_n$ las filas, vamos a definir $f_i \equiv f_j(m)$ si al quitar la columna $m$ la fila $i$ y la fila $j$ son exactamente idénticas $(i \neq j)$. Vamos a definir además $f_i(k)$ a el número que se encuentra en la posición $k$ de la fila $i$.
Vamos a hacer un par de observaciones:
La primera observación, si $f_i \equiv f_j(m)$, entonces $f_i(a)=f_j(a)$ para todo $a$ entero positivo entre $1$ y $n$, salvo para $m$. Luego, si además $f_i \equiv f_j(k)$ y $k \neq m$ entonces también $f_i(a)=f_j(a)$ para todo $a$ entero positivo entre $1$ y $n$, salvo para $k$, pero combinando ambas congruencias llegamos a que $f_i(a)=f_j(a)$ para todo $a$ entero positivo entre $1$ y $n$, por lo que ambas filas deben ser iguales, contradiciendo el enunciado, luego, no puede suceder eso.
La segunda observación, sean $i_1, i_2,..., i_x$, $m_1, m_2,..., m_x$ dos sucesiones de elementos distintos del conjunto $1,2,...,n$ tales que, $f_{i_1} \equiv f_{i_2}(m_1)$, $f_{i_2} \equiv f_{i_3}(m_2)$, ..., $f_{i_x} \equiv f_{i_1}(m_x)$. Esta serie de congruencias lo que nos dicen es lo siguiente:
$f_{i_1}(a)=f_{i_2}(a)$ para todo $a$ entero positivo entre $1$ y $n$ salvo para $m_1$
$f_{i_2}(a)=f_{i_3}(a)$ para todo $a$ entero positivo entre $1$ y $n$ salvo para $m_2$
...
$f_{i_x-1}(a)=f_{i_x}(a)$ para todo $a$ entero positivo entre $1$ y $n$ salvo para $m_{x-1}$
$f_{i_x}(a)=f_{i_1}(a)$ para todo $a$ entero positivo entre $1$ y $n$ salvo para $m_x$
Combinando lo primero con lo segundo llegamos a que $f_{i_1}(a)=f_{i_3}(a)$ para todo $a$ entero positivo entre $1$ y $n$ salvo para $m_1$ y $m_2$.
Combinando este resultado, con lo tercero llegamos a que $f_{i_1}(a)=f_{i_3}(a)$ para todo $a$ entero positivo entre $1$ y $n$ salvo para $m_1$, $m_2$ y $m_3$.
Iterando este proceso hasta llegar al anteúltimo renglón llegamos a que $f_{i_1}(a)=f_{i_x}(a)$ para todo $a$ entero positivo entre $1$ y $n$ salvo para $m_1$, $m_2$, ..., $m_{x-1}$. Pero lo último nos dice que $f_{i_x} \equiv f_{i_1}(m_x)$, es decir que $f_{i_1}(a)=f_{i_x}(a)$ para todo $a$ entero positivo entre $1$ y $n$ salvo para $m_x$, pero esto contradice lo que habíamos concluído antes, luego es imposible que existan $i_1, i_2,..., i_x$, $m_1, m_2,..., m_x$ cumpliendo lo pedido.
Si nuestro tablero cumple que existen dos sucesiones $i_1, i_2,..., i_x$, $m_1, m_2,..., m_x$ que cumplen lo anterior, concluímos que no puede pasar que no haya dos filas exactamente idénticas. Si existen dos sucesiones cumpliendo lo anterior, decimos que nuestro tablero tiene un ciclo.
Ahora bien, vamos a armarnos un grafo, donde cada nodo representa una fila, y dos nodos $i$ y $j$ están conectados por un arista si existe un entero positivo $m$ tal que $f_i \equiv f_j(m)$. Si nuestro grafo no fuera simple, entonces existen $i$ y $j$ tales que $f_i \equiv f_j(m)$ y $f_i \equiv f_j(k)$ y además $m \neq k$, luego, por nuestra primera observación las filas $f_i$ y $f_j$ serían iguales, contradiciendo el enunciado. Concluímos entonces que nuestro grafo es simple. Si nuestro grafo tuviera algún ciclo, entonces existiría una secuencia de nodos $i_1, i_2,..., i_x$ y una secuencia de enteros positivos $m_1, m_2,..., m_x$ tales que $f_{i_1} \equiv f_{i_2}(m_1)$, $f_{i_2} \equiv f_{i_3}(m_2)$, ..., $f_{i_x} \equiv f_{i_1}(m_x)$, luego nuestro tablero tendría un ciclo, pero ya vimos que si nuestro tablero tiene un ciclo se contradice el enunciado, luego nuestro grafo tampoco tiene ciclos, por lo que nuestro grafo es o bien un árbol o bien un bosque, en ambos casos se da que, si $f(G)$ representa la cantidad de aristas de nuestro grafo, $f(G) \leq n-1$ (por definición misma de grafo árbol). Pero por otro lado, para cada entero positivo $m$ entre $1$ y $n$ existen al menos dos filas congruentes módulo $m$, ya que si no existieran dichas filas, al quitar la columna $m$ se cumpliría nuestro objetivo, pero entonces, cada $m$ entre $1$ y $n$ agrega como mínimo una arista al grafo, luego $f(G) \geq n$, absurdo, llegamos una contradicción, por lo que es imposible que un tablero cumpliendo el enunciado cumpla también que para cualquier elección de columna, al quitarla del tablero, en el tablero resultante existan dos filas que sean exactamente idénticas.
Esta parte es para que no suene tan chocante el hecho de usar un grafo. Un grafo no es más que un conjunto de puntitos y lineas que los unen. Con grafos se pueden modelar un montón de problemas de matemática. La idea es que para armar un grafo uno tiene que definir que van a ser sus nodos (los puntitos) y cuando dos nodos van a estar unidos entre si (va a haber una arista entre ellos). Por ejemplo, si tenemos una reunión entre personas y están charlando, los nodos podrían ser las personas, y dos personas estarían conectadas si están formando parte de la misma charla. Está bueno tenerlo presente como herramienta.
Segunda cuestión, un grafo es simple si para cada par de nodos, entre ellos o bien hay una arista que las une, o bien no hay ninguna. Por otra parte, un grafo NO ES SIMPLE cuando hay algunos nodos que hay más de una arista que los conecta.
Tercera cuestión, decimos que un grafo tiene un ciclo, dicho en criollo, cuando hay algún nodo del que podemos partir, recorrer algunos otros nodos moviendonos por las aristas y volver al nodo del que empezamos sin pasar dos veces por el mismo nodo ni por la misma arista. Es como decir que hay un caminito, que empieza en ese nodo, doy una vuelta, y vuelvo a caer en ese nodo.
Por último, un grafo es un árbol si no tiene ciclos, y además, desde cada nodo hay un camino que puedo recorrer por aristas hasta llegar a cualquier otro nodo. Si el grafo es un árbol y tiene $n$ nodos, entonces podemos afirmar que tiene $n-1$ aristas. Un bosque es una unión de varios árboles, que no están unidos entre si, es decir que son disjuntos. Como el bosque está compuesto por varios árboles, si en el bosque hay $n$ nodos y $k$ árboles, podemos afirmar que en el grafo hay exactamente $n-k$ aristas.
Espero que esto sirva como un acercamiento a un tema tan lindo como son los grafos, que muchas veces tiene ideas muy copadas y muy intuitivas, y el grafo no es más que una manera de darle forma a esas ideas.
Supongamos lo contrario, es decir que para cualquier columna que sacamos existen 2 filas identicas.
Si las filas son $1,2,..,n$ viendolo como un grafo para cada columna tendremos una pareja de filas tal que al retirar esta columna las filas son idénticas y es claro que estas parejas no pueden ser iguales para 2 columnas distintas pues sino estas 2 filas serian identicas entonces para cada columna unimos una de estas parejas(pueden haber mas pero solo unimos 1) entonces tendremos un grafo de grado $n$ y es conocido que como tiene $n$ vertices entonces tiene un ciclo y en este ciclo de filas $f_1,f_2,...,f_m$ donde cada uno esta unido con su anterior, tendremos que $f_1,f_2$ difieren en una casilla de una culumna(pues no pueden ser identicas y si le quitas esa columna lo son) y por como esta construido el grafo ninguna de las otras parejas "pertenece" a esta columna,entonces el numero de esta columna de$f_2$ debe ser el mismo que el de $f_3$ y asi sucesivamente hasta $f_m$ y entonces $f_m$ y $f_1$ difieren en exactamente 1 y difieren en la columna que difiere $f_1$ con $f_2$ lo cual es una contradiccion.
Para $n=1$ el problema es verdadero, pues tenemos un tablero de $1\times 1$, y al retirar una columna, retiramos la única casilla que hay, por lo que no hay filas, en particular, no hay dos filas exactamente idénticas. Para $n=2$, la segunda fila puede tener a lo sumo un número igual y en la misma posición que la primera, por lo que retirando la columna a la que pertenecen tenemos lo pedido (si no tienen ningún número igual y en la misma posición, retiramos cualquier columna y tenemos lo pedido). De ahora en adelante suponemos $n\geqslant 3$. Denotamos $(p,q)$ al número en la fila $p$ y columna $q$ (todas las variables que representan el número de una fila o de una columna pertenecen al conjunto $\{1,2,\ldots ,n\}$).
Si al sacar alguna de las primeras $n-1$ columnas resulta que no hay dos filas exactamente idénticas, estamos. Supongamos entonces que al sacar cualquiera de las primeras $n-1$ columnas siempre hay al menos dos filas exactamente idénticas, en particular siempre hay dos casillas iguales en la última columna (las que corresponden a las filas exactamente idénticas).
Notemos que si al retirar dos columnas distintas (digamos $i$ y $j$) ocurre las dos veces que las mismas filas sin una casilla son exactamente idénticas (digamos $a$ y $b$) entonces $a$ y $b$ son exactamente idénticas pues $(a,k)=(b,k)\forall k\neq i$ al sacar la columna $i$ y $(a,k)=(b,k)\forall k\neq j$ al sacar la columna $j$, en particular $(a,i)=(b,i)$, luego $(a,k)=(b,k)\forall k$, por lo que son exactamente idénticas. Entonces al retirar dos columnas distintas del tablero obtenemos pares (no ordenados) distintos de filas exactamente idénticas. Es decir, obtenemos pares (no ordenados) distintos de casillas iguales en la última columna. (*)
Afirmo que si dadas $3$ filas $a,b,c$ al retirar las columnas $i,j$ obtenemos (sin pérdida de generalidad) que las filas $a,b$ y las filas $b,c$ son exactamente idénticas, no podemos obtener al retirar la columna $k$ que las filas $a,c$ son exactamente idénticas. En efecto, supongamos que las filas $a,c$ son exactamente idénticas al retirar la columna $k$, luego $(a,t)=(c,t)\forall t\neq k$, como además tenemos $(a,t)=(b,t)\forall t\neq i$ y $(b,t)=(c,t)\forall t\neq j$, resulta $(a,k)=(b,k)$ y $(b,k)=(c,k)$, por lo $(a,k)=(c,k)$ y $(a,t)=(c,t)\forall t$, entonces las filas $a,c$ son exactamente idénticas. Absurdo pues contradice el enunciado. El absurdo provino de suponer que las filas $a,c$ son exactamente idénticas al retirar la columna $k$, luego, esto no ocurre. (**)
Ahora, todas las casillas de la última columna originalmente están sin pintar, y cada vez que obtenemos que dos casillas son iguales por retirar alguna columna, las pintamos del mismo color (si pintamos una casilla que ya estaba pintada, entonces pintamos todas las casillas que eran del mismo color con el nuevo color). De esta forma, todas las casillas que sabemos que son iguales están pintadas con el mismo color al terminar el proceso. De (*) tenemos que al retirar dos columnas no volvemos a pintar el mismo par de casillas, de (**) tenemos que si una casilla está pintada de un color, no la volvemos a pintar de ese color.
Supongamos que pintamos la última columna con $k$ colores. Como retiramos $n-1$ columnas, pintamos $n-1$ veces, además, cada vez que usamos un nuevo color, pintamos dos casillas. Luego, entre los $k$ pasos que usamos un nuevo color, pintamos $2k$ casillas, en los restantes $n-1-k$ pasos pintamos $n-1-k$ casillas, en total pintamos $n-1-k+2k=n-1+k$ casillas.
Veamos por inducción en $k$ que esto significa que todas las casillas están pintadas de un mismo color.
Como caso base tenemos $k=1$, entonces usamos un único color y pintamos $n-1+1=n$ casillas, por lo tanto (como no pintamos una casilla dos veces de un mismo color), todas las casillas de la última columna están pintadas, y son del mismo color.
Supongamos como hipótesis inductiva que vale para $k=g$ (para cualquier valor de $n$), y veamos que vale para $g+1$.
Veamos primero qué forma tiene el caso $k=g$. Al pintar por primera vez con cada uno de los $g$ colores, pintamos en total $2g$ casillas (en $g$ pasos), entonces nos quedan $n-1-g$ pasos y $n-2g$ casillas para pintar.
Al pintar por primera vez con cada uno de los $g+1$ colores, pintamos en total $2g+2$ casillas (en $g+1$ pasos), además, pintamos en total $x$ casillas del color $1$ (en $x-2$ pasos, pues el primero ya lo contamos antes), en total usamos $g+1+x-2=g+x-1$ pasos, por lo que nos quedan $n-1-(g+x-1)=n-g-x$ pasos y $n-2g-x$ casillas para pintar. Si no pintamos ninguna casilla de color $1$ con una de otro color, entonces tomando $n'=n-x$ resulta que nos quedan $n'-g$ pasos y $n'-2g$ casillas para pintar (pues no volvemos a pintar ninguna casilla de color $1$), pero por hipótesis inductiva, sabemos que con $n'-1-g$ pasos, pintamos las $n'-2g$ casillas restantes y todas las $n'$ casillas son del mismo color (digamos el color $2$), nos queda $n'-2g-(n'-1-2g)=1$ paso, y como no podemos pintar de nuevo un par de casillas de color $1$ ni un par de casillas de color $2$ (y no quedan casillas sin pintar, pues pintamos todas), debemos pintar una casilla de color $1$ y una casilla de color $2$, entonces ambas pasan a tener el color $3$, por lo que todas las casillas de color $1$ y todas las casillas de color $2$ tienen color $3$ ahora, entonces todas las casillas de la última fila tienen el color $3$.
Si volviésemos a pintar alguna casilla de las que originalmente eran de color $1$ o cualquiera de las que son de su mismo color y una de otro color, tenemos un caso parecido al anterior pero con una cantidad mayor o igual de pasos disponibles al final, porque cuando pintamos algún grupo de casillas de otro color para que tengan el color $1$, pintamos al menos $2$ casillas en un paso (si pintamos exactamente dos casillas, como ya habían sido pintadas de una vez en un paso anterior, tenemos igualdad), mientras que en los casos anteriores pintamos a lo sumo $1$ casilla por paso hasta haber coloreado todas las casillas de color $1$ (o sea que pintamos la misma cantidad de casillas con una cantidad menor o igual de pasos, por lo que para cada cantidad de casillas nos queda una cantidad mayor o igual de pasos respecto al caso anterior). Entonces en este caso tenemos más pasos disponibles cuando ya no vamos a pintar ninguna casilla que tenga color $1$, por lo que todas las casillas de la última columna terminan pintadas del mismo color
Habiendo visto que vale para $g+1$ (para cualquier valor de $n$) en todos los casos, la inducción está completa.
Luego, para cualquier cantidad de colores con los que pintemos originalmente la última columna, terminaremos teniendo todas las casillas del mismo color, es decir, todos los números de la última columna serán iguales.
Veamos ahora que quitando la última columna no pueden quedar dos filas exactamente idénticas. En efecto, supongamos lo contrario, luego existen al menos dos filas $a,b$ tales que $(a,t)=(b,t)\forall t\neq n$, pero además $(a,n)=(b,n)$ pues todos los números de la última columna son iguales, luego $(a,t)=(b,t)\forall t$, por lo que $a,b$ son exactamente idénticas. Absurdo pues contradice el enunciado. El absurdo provino de suponer que quitando la última columna quedan al menos dos filas exactamente idénticas, luego esto no ocurre y quitando la última columna logramos lo que pide el enunciado.
Decimos que dos filas están conectadas por una columna si al quitar esa columna las filas son exactamente idénticas.
Si hay dos conexiones formadas por la misma columna vamos a ignorar completamente una y podemos afirmar que cada columna genera una conexión. (1)
Si tenemos un conjunto de filas, $f_{a_1}, f_{a_2},...,f_{a_k}$ tales que $f_{a_i}$ está conectada con $f_{a_{i+1}}$ y $f_{a_k}$ está conectada con $f_{a_1}$ entonces $f_{a_1}$ y $f_{a_k}$ son exactamente iguales. (2)
Llamamos $c_{b_i}$ a la columna que conecta a $f_{a_i}$ con $f_{a_{i+1}}$ y $c_{b_k}$ a la que conecta a $f_{a_1}$ y $f_{a_k}$.
Podemos permutar las filas y las columnas para que nos quede así.
WhatsApp Image 2019-01-22 at 14.46.34.jpeg
Hay dos $f_{a_1}$ para una mejor representación.
Las líneas negras significan que esas dos filas son exactamente iguales excepto por las casillas en la que está la línea negra.
Notemos que gracias a la conexión entre $f_{a_k}$ y $f_{a_1}$ las dos filas son iguales excepto por las casillas de $c_{b_k}$, en el dibujo se ve claramente que la casilla de la columna $c_{b_k}$ es la misma para las filas que están por arriba de $f_{a_k}$ pero eso incluye $f_{a_1}$ por lo que las dos filas antes mencionadas son exactamente iguales.
Ahora pasemos el problema a un grafo donde cada fila está representada por un vértice y la conexión entre dos filas por una arista que conecta los vértices que representan esas dos filas, por (1) este grafo tiene $n$ aristas y por (2) el grafo no tiene ciclos.
Si un vértice no se une con ningún otro lo sacamos.
Como el grafo no tiene ciclos no contiene ningún subgrafo isomorfo a una subdivisión elemental de $K_5$ o $K_{3,3}$ (Ya que estos grafos contienen ciclos), por lo que por el Teorema de Kuratowsky el grafo es plano, como el grafo es plano hay un grafo isomorfo en el cual las aristas no se cortan y en este nuevo grafo se cumple la Formula de Euler $C-A+V=2\leq C-n+n=C$.
Como hay al menos 2 caras hay al menos un ciclo pero por (2) esto conduce a dos filas exactamente idénticas.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
Decimos que dos filas están conectadas por una columna si al quitar esa columna las filas son exactamente idénticas.
Si hay dos conexiones formadas por la misma columna vamos a ignorar completamente una y podemos afirmar que cada columna genera una conexión. (1)
Si tenemos un conjunto de filas, $f_{a_1}, f_{a_2},...,f_{a_k}$ tales que $f_{a_i}$ está conectada con $f_{a_{i+1}}$ y $f_{a_k}$ está conectada con $f_{a_1}$ entonces $f_{a_1}$ y $f_{a_k}$ son exactamente iguales. (2)
Llamamos $c_{b_i}$ a la columna que conecta a $f_{a_i}$ con $f_{a_{i+1}}$ y $c_{b_k}$ a la que conecta a $f_{a_1}$ y $f_{a_k}$.
Podemos permutar las filas y las columnas para que nos quede así.
WhatsApp Image 2019-01-22 at 14.46.34.jpeg
Hay dos $f_{a_1}$ para una mejor representación.
Las líneas negras significan que esas dos filas son exactamente iguales excepto por las casillas en la que está la línea negra.
Notemos que gracias a la conexión entre $f_{a_k}$ y $f_{a_1}$ las dos filas son iguales excepto por las casillas de $c_{b_k}$, en el dibujo se ve claramente que la casilla de la columna $c_{b_k}$ es la misma para las filas que están por arriba de $f_{a_k}$ pero eso incluye $f_{a_1}$ por lo que las dos filas antes mencionadas son exactamente iguales.
Ahora pasemos el problema a un grafo donde cada fila está representada por un vértice y la conexión entre dos filas por una arista que conecta los vértices que representan esas dos filas, por (1) este grafo tiene $n$ aristas y por (2) el grafo no tiene ciclos.
Si un vértice no se une con ningún otro lo sacamos.
Como el grafo no tiene ciclos no contiene ningún subgrafo isomorfo a una subdivisión elemental de $K_5$ o $K_{3,3}$ (Ya que estos grafos contienen ciclos), por lo que por el Teorema de Kuratowsky el grafo es plano, como el grafo es plano hay un grafo isomorfo en el cual las aristas no se cortan y en este nuevo grafo se cumple la Formula de Euler $C-A+V=2\leq C-n+n=C$.
Como hay al menos 2 caras hay al menos un ciclo pero por (2) esto conduce a dos filas exactamente idénticas.
Hola @Joacoini , te hago una consulta, podrías pasarme el software con el que realizás los tableros? Desde ya muchas gracias
Para un tablero de $1×1$ es trivial que es cierto el problema. Asumamos que $n \geq 2$.
Ahora, demostraremos por inducción que lo siguiente es cierto, lo cual implica lo que nos pide el problema:
Si un tablero de $n$ filas y $m$ columnas, con $m \geq n$, no tiene dos filas exactamente idénticas, entonces es posible borrar una columna de manera tal que el nuevo tablero no tenga dos filas exactamente idénticas.
Caso base: tablero de $n=2$ filas y $m\geq 2$ columnas:
Si $n=2$, es claro que las dos filas difieren en al menos una columna. Luego, simplemente borramos cualquiera de las otras columnas, por lo que el tablero que queda cumple que no tiene dos filas exactamente iguales ya que siguen siendo distintas en la columna que no borramos.
Paso inductivo:
Supongamos que es cierto para un tablero de $n$ filas y $m$ columnas, siendo $n$ un número natural fijo y para todo $m\geq n$.
Luego, consideremos un tablero de $(n+1)$ filas y $k\geq (n+1)$ columnas, sin dos filas exactamente idénticas. Borremos una fila cualquiera (digamos la última), luego el tablero que nos queda tiene $n$ filas y $k>n$ columnas y sigue cumpliendo que no tiene dos filas exactamente idénticas. Entonces, por hipótesis inductiva, podemos eliminar una columna de manera tal que el tablero que quede no tenga dos filas exactamente idénticas. Sea $A$ esta columna (digamos la última).
Ahora, el tablero que nos quedó es de $n$ filas y $k-1\geq n$ columnas, por lo que nuevamente, por hipótesis inductiva, podemos borrar una columna de manera que el nuevo tablero de $n$ filas y $k-2$ columnas no tenga dos filas exactamente idénticas. Sea $B$ esta columna (digamos la anteúltima).
Volviendo al tablero original, es claro que si eliminamos la columna $A$ y el tablero que nos queda cumple, ya estamos. Luego, supongamos que esto no ocurre. Luego, esto quiere decir que la última fila (sin la columna A) es exactamente idéntica a una de las filas superiores y sólo a una (digamos la primera), ya que sabemos que todas las filas superiores son distintas entre sí.
Luego, borramos la columna $B$ y dejamos la $A$. Sabemos que las filas superiores son todas distintas entre sí y que difieren en una columna distinta de $A$. Cómo la última fila era exactamente idéntica a la primera cuando eliminábamos $A$, entonces al eliminar $B$ esta última fila será distinta a todas las superiores, y también será distinta a la primera fila en la columna $A$, ya que, en caso contrario, la primera y la última fila serían exactamente idénticas en el tablero original. Luego, al eliminar la columna $B$, obtenemos lo pedido. Por lo que queda demostrado.
