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.
