Rompecabezas | El vecino

Sahil tiene un problema de desafío de su amigo Akhil. Sahil tiene que encontrar todos los valores de n para los que se puede llenar una tabla n × n con + y – (uno por celda) para que cada celda tenga exactamente un vecino con el signo opuesto. Dos celdas se consideran vecinas si están en la misma fila o en la misma columna. ¿Puedes ayudar a Sahil a encontrar tales valores de n?

Solución:
El rompecabezas tiene solución si n es par, y no tiene solución si n es impar. Si n es par, uno puede llenar la fila superior con más, las filas 2 y 3 con menos, las filas 4 y 5 con más nuevamente, y así sucesivamente, hasta que la última fila se llene con más. Bajo este esquema, cada celda tendrá exactamente un vecino con el signo opuesto arriba o debajo de la celda en cuestión. Por supuesto, como soluciones alternativas, se pueden intercambiar las ventajas y desventajas de la solución anterior o hacer que todas las columnas, en lugar de todas las filas, contengan el mismo signo. Como ejemplo, si tomamos una mesa de 6 x 6, entonces las posibles soluciones pueden ser:

EXPLICACIÓN:
1). Si se pone un más en la esquina superior izquierda, tenemos que poner un más y un menos en las celdas vecinas, ya que cada celda tendrá exactamente un vecino con el signo opuesto.
2). Considere el caso cuando se coloca un signo más en su vecino de fila y un signo menos en su vecino de columna; el otro caso es simétrico.
3). Por lo tanto, demostremos que si se colocan signos positivos en las dos primeras celdas de la fila 1 y un signo negativo en la primera celda de la fila 2, tendremos que llenar las celdas restantes de la fila 1 con signos positivos y las celdas restantes de la fila 2 con desventajas
4). Dado que la primera celda de la segunda fila ya tiene un vecino con un signo más arriba, la segunda celda de la fila 2 tendrá que contener un signo menos. Pero entonces la tercera celda en la fila 1 tendrá que contener un signo más ya que la segunda celda en la fila 1 ya tiene un vecino con un signo menos debajo.
5). Por el mismo argumento, todas las celdas restantes de la fila 1 deberán contener un signo más, y todas las celdas restantes de la fila 2 deberán contener un signo menos.
6). Pero entonces todas las celdas en la fila 3 deben contener menos porque sus vecinas en la fila 2 ya tienen las vecinas positivas en la fila 1.
7). Esto implica que la fila 3 no puede ser la última, sino que debe ir seguida de la fila 4 con todas las ventajas. La fila 4 puede ser la última o debe ir seguida de la fila de todos los más, y así sucesivamente.

Esto prueba que cuando n es par, el rompecabezas no tiene otras soluciones que las descritas anteriormente. Y no tiene solución cuando n es impar.

Referencias: Rompecabezas algorítmicos – Anany Levitin, Maria Levitin