Your research team has found a prehistoric virus preserved in the permafrost and isolated it for study. After a late night working, you're just closing up the lab when a sudden earthquake hits and knocks out the power. As the emergency generators kick in, an alarm confirms your worst fears: all the sample vials have broken. The virus is contained for now, but unless you can destroy it, the vents will soon open and unleash a deadly airborne plague. Without hesitation, you grab your HazMat suit and get ready to save the world. The lab is a four by four compound of 16 rooms with an entrance on the northwest corner and an exit at the southeast. Each room is connected to the adjacent ones by an airlock, and the virus has been released in every room except the entrance. To destroy it, you must enter each contaminated room and pull its emergency self-destruct switch. But there's a catch. Because the security system is on lockdown, once you enter the contaminated room, you can't exit without activating the switch, and once you've done so, you won't be able to go back in to that room. You start to draw out possible routes on a pad of paper, but nothing seems to get you to the exit without missing at least one room. So how can you destroy the virus in every contaminated room and survive to tell the story? Pause here if you want to figure it out for yourself. Answer in: 3 Answer in: 2 Answer in: 1 If your first instinct is to try to graph your possible moves on a grid, you've got the right idea. This puzzle is related to the Hamiltonian path problem named after the 19th century Irish mathematician William Rowan Hamilton. The challenge of the path problem is to find whether a given graph has a Hamiltonian path. That's a route that visits every point within it exactly once. This type of problem, classified as NP-complete, is notoriously difficult when the graph is sufficiently large. Although any proposed solution can be easily verified, we have no reliable formula or shortcut for finding one, or determining that one exists. And we're not even sure if it's possible for computers to reliably find such solutions, either. This puzzle adds a twist to the Hamiltonian path problem in that you have to start and end at specific points. But before you waste a ton of graph paper, you should know that a true Hamiltonian path isn't possible with these end points. That's because the rooms form a grid with an even number of rooms on each side. In any grid with that configuration, a Hamiltonian path that starts and ends in opposite corners is impossible. Here's one way of understanding why. Consider a checkerboard grid with an even number of squares on each side. Every path through it will alternate black and white. These grids will all also have an even total number of squares because an even number times and even number is even. So a Hamiltonian path on an even-sided grid that starts on black will have to end on white. And one that starts on white will have to end on black. However, in any grid with even numbered sides, opposite corners are the same color, so it's impossible to start and end a Hamiltonian path on opposite corners. It seems like you're out of luck, unless you look at the rules carefully and notice an important exception. It's true that once you activate the switch in a contaminated room, it's destroyed and you can never go back. But there's one room that wasn't contaminated - the entrance. This means that you can leave it once without pulling the switch and return there when you've destroyed either of these two rooms. The corner room may have been contaminated from the airlock opening, but that's okay because you can destroy the entrance after your second visit. That return trip gives you four options for a successful route, and a similar set of options if you destroyed this room first. Congratulations. You've prevented an epidemic of apocalyptic proportions, but after such a stressful episode, you need a break. Maybe you should take up that recent job offer to become a traveling salesman.
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