Retículas equilibradas

Enunciado

Retícula equilibrada

Este es un bonito problema que no tiene un método de ataque estándar, es decir, que hay que buscar un patrón mediante la observación de casos aislados y probar después que es correcto.

Si tratamos con retículas pequeñas, rápidamente encontramos retículas equilibradas cuadradas, es decir, en los casos en que n = m, por el sencillo método de pintar todos los puntos de la retícula del mismo color (blanco o negro), pero también con otras tramas. Se sugiere empezar con la (2, 2) y hacer una demostración rápida.

Podemos extraer bastante información del estudio de las cuadrículas (2, 3), (2, 4) y (2, 5).

En el caso (2, 3) descubrimos con bastante rapidez que es imposible que esté equilibrada. Pensemos en una distribución de colores que la equilibre. En una fila (de tres puntos) habrá dos puntos del mismo color (no puede haber tres, porque las columnas sólo tienen dos puntos). Como en cada una de esas columnas, habrá dos puntos de ese color, todos serán del mismo. Por tanto, en la otra fila también habrá dos puntos, que serán exactamente esos. Luego la columna restante, debe ser del otro color. Sin embargo, hay dos puntos en esa columna del mismo color, y en cada fila sólo hay uno. Luego no está equilibrada.

En el caso (2, 4) podemos descubrir muy rápido una retícula equilibrada, pintando la mitad de columnas de un color, y la mitad de otro.

En el caso (2, 5) también podemos probar rápidamente que no hay retículas equilibradas, en este caso de forma muy rápida, ya que en cualquier fila habrá más de dos de un mismo color, por lo que no podrá haber la misma cantidad de puntos de ese color en ninguna de las columnas, luego no estará equilibrada.

Después de este breve estudio, vamos a probar que sólo pueden existir retículas equilibradas en el caso de que los dos valores sean iguales, o bien el mayor sea exactamente doble que el menor.

Está claro que una retícula cuadrada puede ser equilibrada, así que veamos qué sucede si no lo es. Sin pérdida de generalidad, podemos suponer que (n, m) es más ancha que alta (es decir, n < m), ya que en caso contrario se puede realizar el mismo razonamiento cambiando filas por columnas y viceversa.

Si m > 2n, el razonamiento es idéntico al de (2, 5). Puesto que en cada fila hay más de 2n puntos, de uno de los dos colores habrá más de n, por lo que en un punto de ese color no puede haber la misma cantidad de puntos de ese color en la columna, ya que ésta tiene sólo n puntos.

Si m = 2n, podemos encontrar una retícula equilibrada pintando la mitad de las columnas de un color y la mitad de otro. De esta forma, en cada punto hay exactamente n puntos en la fila y en la columna de ese color.

Si n < m < 2n, el razonamiento es un poco más complicado. Supongamos que hay una retícula equilibrada de ese tamaño y lleguemos a un absurdo. Es evidente que en ninguna fila puede haber más de n puntos del mismo color. Busquemos la fila en que más puntos del mismo color haya. Si la cantidad de puntos de ese color es s y s es menor que n, en esa columna habrá s puntos del mismo color, es decir, habrá n - s puntos del otro color (pero habrá alguno, si s es menor que n). Si nos fijamos en uno de los puntos de otro color, en esa misma fila habrá n - s puntos del otro color, y por tanto habrá m - n + s puntos del color inicial, lo que representa un número más grande que s (porque m es mayor que n). Esto es una contradicción, porque hemos supuesto que s es la mayor cantidad posible con puntos de un mismo color.

Luego debe haber una fila con n puntos del mismo color. En cada uno de ellos, esa columna es de ese color, ya que debe haber n puntos del mismo color. Y, como en cada una de las filas debe haber exactamente n puntos de ese color, para que sea equilibrada, serán los n puntos de las n columnas que hemos descubierto que son de ese color. Es decir, que las m - n columnas restantes deben ser enteras del otro color, y tienen n puntos de ese color. Sin embargo, en una cualquiera de las filas no puede haber n puntos de cada color, porque m < 2n. Luego es absurdo.

En resumen, que sólo pueden darse retículas equilibradas cuando uno de las dos medidas es igual a, o exactamente el doble que la otra.