Cada mañana puedes abrir una puerta. Cada noche, el gato cambia de habitación. Necesitas un plan que no dependa de la suerte.
El gato nocturno
Enunciado
Hay siete habitaciones en fila, numeradas del 1 al 7. Un gato se esconde en una de ellas.
Cada día puedes abrir una sola habitación. Si el gato está dentro, lo encuentras. Si no está, cierras la puerta sin obtener ninguna otra información.
Cada noche el gato se mueve obligatoriamente a una habitación vecina: de la 4 puede pasar a la 3 o a la 5; desde los extremos sólo puede avanzar hacia el interior. Nunca se queda quieto ni salta habitaciones.
¿Puedes diseñar un plan que garantice encontrarlo, haga lo que haga el gato? Explica por qué funciona.
Ver solución
Solución
Un plan que garantiza encontrarlo en diez días como máximo es:
2, 3, 4, 5, 6, 6, 5, 4, 3, 2.
No hace falta abrir los extremos.
Primer recorrido: gatos que empiezan en una habitación par.
Durante los cinco primeros días abrimos 2, 3, 4, 5 y 6.
Si el gato empieza en una habitación par, la habitación inspeccionada y la del gato tienen la misma paridad cada día: ambos cambian de paridad de un día al siguiente.
Llamemos xₜ a la posición del gato el día t, antes de abrir, y qₜ=t+1 a nuestra elección. La diferencia
dₜ=xₜ-qₜ
es par. Empieza siendo no negativa, porque x₁ es 2, 4 o 6.
De un día al siguiente, nuestra posición avanza una habitación y la del gato cambia en +1 o -1. Por tanto, dₜ cambia en 0 o en -2.
El quinto día el gato está en una habitación par, como máximo la 6, y nosotros abrimos la 6. Así que d₅ ≤ 0.
Una cantidad par que empieza siendo no negativa y termina siendo no positiva, disminuyendo únicamente de dos en dos, tiene que pasar por cero. Ese día coincidimos con el gato.
Segundo recorrido: gatos que empiezan en una habitación impar.
Si el gato no ha sido encontrado, empezó en una habitación impar. Tras cinco movimientos nocturnos, el sexto día está en una habitación par.
Ese día volvemos a abrir la 6 y empezamos el recorrido inverso: 6, 5, 4, 3, 2.
Ahora consideramos qₜ-xₜ. Empieza siendo no negativa, cambia en 0 o en -2, y el décimo día es no positiva: nosotros estamos en la 2 y el gato está en una habitación par, como mínimo la 2.
Tiene que volver a pasar por cero.
La repetición de la habitación 6 es deliberada: transcurre otra noche y el gato se mueve, aunque nosotros repitamos puerta.