Edificios

Edificios es un problema lógico clásico cuyo planteo es el siguiente: en un tablero cuadrado de n x n hay que colocar números de 1 a n; en cada casilla va exactamente un número y no puede haber dos números iguales en una misma fila o columna. Alrededor del tablero hay pistas que indican cómo deben ser colocados esos números, para entenderlas hay que imaginar que cada uno de los números a colocar representa la altura de un edificio; las pistas nos dicen cuántos edificios ve una persona que esté parada en esa posición si se coloca mirando hacia el tablero, bajo la suposición de que cada edificio oculta a todos los que estén detrás de él y que sean a la vez más bajos que él, pero que no oculta a los que sean más altos. Un ejemplo con su solución:

Una de las condiciones que todo buen problema de lógica debe cumplir es que su solución sea única, es decir, no puede haber dos formas diferentes de completar el tablero respetando a la vez todas las pistas. A veces sucede que este objetivo se logra con una cantidad menor de pistas. Por ejemplo, en el problema anterior hay, en efecto, pistas redundantes. Éste problema, con menos pistas, también tiene solución única:

En su charla en el Tercer Encuentro por Martin Gardner y Jaime Poniachik, Ivan Skvarca (autor del excelente blog aquí enlazado) planteó estas dos preguntas:

1) ¿Siempre es posible, no importa cuál sea el valor de n, plantear un problema de Edificios en un tablero de n x n que tenga solución única? ¿O para valores "grandes" de n esto es imposible?

2) ¿Cuál es la mínima cantidad de pistas que pueden ponerse de modo que la solución sea única?

Mi intención en esta entrada es responder a la primera pregunta y hacer un aporte para la segunda.

1) En una primera aproximación podríamos creer que la respuesta es que para valores suficientemente grandes de n se llega a un punto en que es imposible garantizar que la solución sea única. Después de todo, la cantidad de pistas de las que disponemos crece linealmente con n, mientras que la cantidad de números a colocar crece cuadráticamente (por así decir, hay muchas más incógnitas que datos). Pero este razonamiento es falaz porque no toma en cuenta que hay una pista "global": en cada fila y columna no puede haber dos números iguales.

La respuesta en realidad es que para cualquier valor de n siempre es posible plantear al menos un problema de Edificios de n x n con solución única. El siguiente dibujo da idea de cómo hacerlo si n es mayor o igual que 6:

2) El mismo dibujo nos da una cota para la cantidad mínima de pistas que pueden colocarse en un problema de Edificios de modo que la solución sea única. Vemos que, para n mayor o igual que 6, esto puede lograrse con 2n - 6 pistas; la pregunta que queda ahora planteada es si puede lograrse con una cantidad menor.