Tu equipo de investigación ha encontrado un virus prehistórico
conservado en el permafrost y lo ha aislado para su estudio.
Tras una noche de trabajo, estás cerrando el laboratorio
cuando de repente
se produce un terremoto y hay un corte de electricidad.
Cuando se encienden los generadores de emergencia
una alarma confirma tu peor pesadilla:
todos los viales con las muestras se han roto.
El virus está contenido por ahora,
pero a menos que puedas destruirlo,
los respiraderos pronto se abrirán
y desencadenarán una mortífera plaga aérea.
Sin dudarlo, agarras tu traje de protección
y te preparas para salvar el mundo.
El laboratorio es un complejo de cuatro por cuatro de 16 habitaciones
con una entrada en la esquina noroeste y una salida en el sureste.
Las habitaciones están conectadas entre sí por una esclusa,
y el virus ha sido liberado en cada habitación excepto la entrada.
Para destruirlo, debes entrar en cada habitación contaminada
y tirar del interruptor de emergencia para su auto-destrucción.
Pero hay una trampa.
Debido a que el sistema de seguridad está bloqueado,
una vez que entras en la habitación contaminada,
no se puede salir sin activar el interruptor,
y una vez que lo hayas hecho,
ya no podrás volver a esa habitación.
Empiezas a dibujar posibles rutas en una libreta de papel,
pero ninguna parece llevarte a la salida
sin que falte al menos una habitación.
Entonces, ¿cómo puedes destruir el virus en cada habitación contaminada
y sobrevivir para contar la historia?
Pausa aquí si quieres averiguarlo por tí mismo.
Respuesta en: 3
Respuesta en: 2
Respuesta en: 1
Si tu primer instinto es dibujar tus posibles rutas en una cuadrícula,
vas bien encaminado.
Este rompecabezas está relacionado con el problema del camino hamiltoniano
nombrado en honor del matemático irlandés del siglo XIX William Rowan Hamilton.
El desafío del problema del camino
es descubrir si una gráfica dada tiene una ruta hamiltoniana.
Es una ruta que visita cada punto dentro de ella exactamente una vez.
Este tipo de problema, clasificado como NP-completo,
es muy difícil cuando el gráfico es lo bastante grande.
Aunque cualquier solución propuesta puede ser verificada fácilmente,
no tenemos ninguna fórmula fiable o atajo para encontrar uno,
o determinar que existe.
Y ni siquiera estamos seguros de si es posible para los ordenadores
encontrar de manera fiable tales soluciones.
Este rompecabezas agrega un giro al problema de la trayectoria hamiltoniana
ya que tienes que empezar y terminar en puntos específicos.
Pero antes de gastar una tonelada de papel cuadriculado,
debes saber que una verdadera ruta hamiltoniana
no es posible con estos puntos finales.
Eso es porque las habitaciones forman una cuadrícula
con un número par de habitaciones en cada lado.
En cualquier cuadrícula con esa configuración,
un camino hamiltoniano que comienza y termina en esquinas opuestas es imposible.
He aquí una manera de entender por qué.
Imagina un tablero cuadriculado con un número par de cuadros en cada lado.
Cada ruta a través de él alternará blanco y negro.
La cuadrícula también tendrá un número total de cuadrados par,
porque un número par por otro número par da par.
Así que un camino hamiltoniano en una cuadrícula par que empieza en negro
tendrá que terminar en blanco.
Y si empieza en blanco tendrá que terminar en negro.
Sin embargo, en cualquier cuadrícula con lados pares,
las esquinas opuestas son del mismo color,
por lo que es imposible iniciar y terminar un camino hamiltoniano
en las esquinas opuestas.
Parece que se te ha acabado la suerte.
A no ser que mires las reglas con atención y notes una importante excepción.
Es cierto
que una vez que activas el interruptor en una habitación contaminada,
es destruida y no puedes volver atrás.
Pero hay una habitación que no estaba contaminada - la entrada.
Esto significa que puedes dejarla una vez sin tirar del interruptor
y regresar a ella cuando hayas destruido cualquiera de estas dos habitaciones.
La habitación de la esquina puede haber sido contaminada
por la apertura de la esclusa, pero no pasa nada
porque puedes destruir la entrada después de tu segunda visita.
Ese viaje de vuelta te da cuatro opciones para una ruta exitosa,
y un grupo similar de opciones si destruiste esta habitación primero.
Enhorabuena.
Has evitado una epidemia de dimensiones apocalípticas,
pero tras un suceso tan estresante, necesitas un descanso.
Tal vez deberías aceptar esa nueva oferta de trabajo
para ser vendedor ambulante.