Rompecabezas | Planificación de una exposición

Rompecabezas: Un museo tiene un espacio expositivo de 16 salas. Hay una puerta entre cada par de habitaciones adyacentes horizontal y verticalmente. Además, cada habitación en el lado norte y sur del edificio tiene una puerta que da al exterior. Al planificar una nueva exposición, el curador debe decidir cuál de las puertas debe estar abierta, de modo que un visitante pueda ingresar a la exposición por la puerta del lado norte, visitar todas y cada una de las habitaciones exactamente una vez y salir por una puerta. en el lado sur. Además, el número de puertas abiertas debe ser mínimo.

1. ¿Cuál es el número mínimo de puertas que deben estar abiertas para la exposición?
2. Indique todos los pares de entrada-salida que se pueden abrir para la exposición?

El plano de planta del museo es como se muestra. Las líneas superior e inferior del plano indican el lado norte y sur del edificio respectivamente.

Solución:

1. Dado que un recorrido por la exposición debe visitar cada sala exactamente una vez, tendrá que entrar y salir de cada sala por puertas diferentes. Esto implica que se deben abrir un mínimo de 17 puertas, incluida una puerta de entrada y una de salida.
2. Al colorear las habitaciones como cuadrados de un tablero de ajedrez de 4 x 4 , como se muestra, se hace evidente que cualquier camino a través de la exposición tendrá que pasar por los cuadrados de colores alternos.

Dado que se tiene que visitar el total de 16 habitaciones, el primer y el último cuadrado deben colorearse en colores opuestos. Entonces, los posibles pares de entrada-salida son (A1, B1), (A1, B3), (A2, B2), (A2, B4) y simétricamente, (A4, B4), (A4, B2), (A3, B3) y (A3, B1) . Algunas de las rutas para estos pares de entrada y salida son las que se muestran.