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.
Votre équipe de chercheurs a trouvé un virus préhistorique préservé dans le permafrost et l'a isolé pour l'étudier. Après une longue nuit de travail, vous vous apprêtez à fermer le labo quand un tremblement de terre soudain paralyse le réseau électrique. Quand le générateur de secours démarre, une alarme confirme votre pire crainte : tous les flacons d'échantillons sont cassés. Le virus est contenu pour l'instant, mais si vous ne le détruisez pas, les conduits d'aération s'ouvriront et libèreront une peste mortelle. Sans hésiter, vous enfilez votre combinaison de protection et vous vous préparez à sauver le monde. Le labo est une enceinte de 4 par 4, soit 16 pièces, avec une entrée à l'angle nord-ouest et une sortie au sud-est. Chaque pièce est reliée aux pièces voisines par un sas, et le virus a été libéré dans chaque pièce sauf l'entrée. Pour le détruire, vous devez entrer dans chaque pièce contaminée et enclencher l'interrupteur d'auto-destruction. Mais il y a un piège. Comme le système de sécurité est verrouillé, quand vous entrez dans une pièce contaminée, vous ne pouvez plus en sortir sans activer l'interrupteur, et une fois que c'est fait, vous ne pourrez plus retourner dans cette pièce. Vous commencez à dessiner tous les itinéraires possibles sur un bloc-notes, mais rien ne vous permet d’atteindre la sortie sans rater au moins une pièce. Alors comment faire pour détruire le virus dans chaque pièce contaminée, et survivre pour raconter l'histoire ? Faites « Pause » si vous souhaitez trouver la réponse par vous-même. Réponse dans : 3 Réponse dans : 2 Réponse dans : 1 Si votre premier instinct est de dessiner tous les chemins possibles sur une grille, vous avez la bonne idée. Ce puzzle est lié au problème du chemin hamiltonien, du nom du mathématicien irlandais du 19ème siècle, William Rowan Hamilton. Le défi de ce problème est de trouver si un graphe donné possède un chemin hamiltonien. C'est un trajet qui passe exactement une seule fois par chaque point. Ce type de problème, classé comme NP-complet, est réputé difficile quand le graphe est suffisamment grand. Bien que toute solution proposée puisse être facilement vérifiée, il n'existe aucune formule ou raccourci fiable pour en trouver une, ou pour déterminer s'il en existe une. Et nous ne sommes même pas sûrs que les ordinateurs puissent trouver de manière fiable de telles solutions. Cette énigme ajoute une contrainte au problème du chemin hamiltonien, puisque vous devez commencer et finir par des points spécifiques. Mais avant de gaspiller une tonne de papier quadrillé, vous devriez savoir qu'un vrai chemin hamiltonien est impossible avec ces extrémités. C'est parce que les pièces forment une grille aux côtés pairs. Dans toute grille avec cette configuration, un chemin hamiltonien qui débute et finit par des coins opposés est impossible. Voici un moyen de comprendre pourquoi. Imaginez un échiquier avec un nombre pair de carrés de chaque côté. Chaque chemin traversant l'échiquier alternera le blanc et le noir. Ces grilles ont aussi toutes un nombre total de carrés pair parce qu'en multipliant deux nombre pairs, on obtient un nombre pair. Un chemin hamiltonien sur une grille aux côtés pairs démarrant sur du noir devra se terminer sur du blanc. Et un chemin commençant sur du blanc devra se terminer sur du noir. Toutefois, dans toute grille aux côtés pairs, les coins opposés sont de la même couleur, il est donc impossible de débuter et finir un chemin hamiltonien sur des coins opposés. On dirait que vous n'avez pas de chance, à moins de bien regarder les règles et remarquer une exception importante. C'est vrai qu'une fois l'interrupteur activé dans une pièce contaminée, celle-ci est détruite et vous ne pouvez plus y retourner. Mais il y a une pièce qui n'a pas été contaminée - l'entrée. Cela signifie que vous pouvez en sortir une fois sans activer l'interrupteur et y retourner une fois que vous avez détruit l'une de ces pièces. La pièce du coin peut être contaminée par l'ouverture du sas, mais ce n'est pas grave parce que vous pouvez détruire l'entrée après votre deuxième passage. Ce voyage retour vous donne 4 options pour un trajet couronné de succès, et un lot similaire d'options si vous détruisez cette pièce en premier. Félicitations. Vous avez évité une épidémie de proportion apocalyptique, mais après un épisode aussi stressant, vous avez besoin d'une pause. Peut-être devriez-vous accepter cette offre d'emploi pour devenir VRP.