Rusia 2016 Combinatoria

[sfreghy]

Se colorean las casillas del tablero de [math]100\times 100 de color blanco y negro, una coloración se llama admisible, si en cada fila y columna hay de [math]50 a [math]60 casillas negras. Una operación permitida es cambiar el color de una de las casillas siempre que la coloración resultante sea admisible. Demuestre que mediante tales operaciones se puede obtener cualquier coloración admisible a partir de cualquier otra.

[Gianni De Rico]

Hint 1:

Spoiler: mostrar

Fijate que de cada coloración con [math]x cantidad de casillas negras podés llegar a todas las coloraciones con [math]x casillas negras.

Hint 2:

Spoiler: mostrar

Fijate que de cada coloración con [math]x casillas negras podés llegar a una coloración con [math]x+1 casillas negras.

Hint 3: (TE QUEMA MUCHO EL PROBLEMA)

Spoiler: mostrar

Fijate que la operación es reversible, es decir que si llegaste desde una coloración hasta otra podés volver haciendo los pasos en orden inverso. Esto probablemente sea el hint más trivial, pero es bastante fuerte para el problema.

[Lean]

Spoiler: mostrar

Un tablero admisible debe tener mínimo $50×100$ casillas negras, es decir mínimos $50$ en cada columna o fila. Y máximo $60×100$ casillas negras por la misma razón.

Desde un tablero admisible puedo llegar a otro tablero admisible siempre. Esto ya que siempre puedo quitar o agregar alguna casilla negra para conseguir otro admisible. Si no pudiera hacer esto, significaría que me estaría pasando con las casillas, ya que excedo el límite agregando, o me quedo corto, ya que tengo menos de $5000$. Pero yo puedo agregar si justo tengo $5000$ o quitar si tengo justo $6000$.

Ahora debo comprobar que desde un admisible puedo llegar a todos los admisibles.

Suponiendo que esto fuera imposible, tendría una cantidad $X$ de tableros a los que podría conseguir con mis operaciones y una cantidad $Y$ a la que no pueda conseguir con mi tablero inicial.

Como cada operación agrega o quita a lo sumo una casilla, podemos decir que entre un tablero admisible de $X$ y uno de $Y$, diferentes en la coloración de una sola casilla, hay una "barrera" que impide que uno llegue a otro. Pero esto es absurdo, ya que puedo pasar de un tablero a otro agregando o quitando una casilla, ya que esto cumple con lo pedido.

Entonces, si me es posible pasar de un $X$ a un $Y$, podemos pensar de la misma forma con los siguientes. De forma que no importa cómo, siempre puedo llegar desde cualquier tablero admisible a otro admisible.

Edit: Fue una mentira, pero me gustaria saber si la idea lleva a algo