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.
Je onderzoeksteam heeft een in de permafrost gepreserveerd prehistorisch virus gevonden en het voor onderzoek geïsoleerd. Net wanneer je na een lange avond werken het lab wilt afsluiten, treft een aardbeving het gebied en valt bijgevolg de stroom uit. Wanneer de noodgenerator aanslaat, bevestigt een alarm je grootste angst: alle flesjes met monsters zijn gebroken. Het virus is voor nu ingesloten, maar tenzij je het kunt vernietigen, zal de ventilatie spoedig opstarten ... en een dodelijke plaag verspreiden. Zonder aarzeling trek je je gaspak aan en maak je je klaar om de wereld te redden. Het complex bestaat uit vier keer vier ruimtes en heeft noordwestelijk een ingang en zuidoostelijk een uitgang. Iedere ruimte is via een luchtsluis met de naastgelegen ruimte verbonden en het virus is in iedere ruimte, behalve de ingang, vrijgekomen. Om het virus te vernietigen, moet je iedere besmette ruimte betreden en haar zelfvernietigingsknop gebruiken. Maar er zit een addertje onder het gras. Omdat het pand in quarantaine is, kun je een besmette ruimte, eens betreden, alleen verlaten als je de zelfvernietigingsknop gebruikt hebt. Is de zelfvernietiging in gang gezet, kun je die ruimte niet opnieuw betreden. Je begint de mogelijke routes op papier uit te tekenen, maar met geen van de routes bereik je de uitgang zonder minstens één ruimte te missen. Hoe kun je het virus in elke besmette ruimte vernietigen en het naderhand ook navertellen? Als je het zelf wilt uitvogelen, pauzeer het filmpje dan nu. Antwoord in: 3 Antwoord in: 2 Antwoord in: 1 Als het uittekenen van al je mogelijkheden je eerste ingeving was, ben je op de juiste weg. Deze puzzel is gerelateerd aan het vraagstuk van het Hamiltonpad, vernoemd naar de 19e eeuwse Ierse wiskundige William Rowan Hamilton. De uitdaging van het vraagstuk is ontdekken of een gegeven weergave een Hamiltonpad bevat. Dat wil zeggen: een route die ieder punt slechts eenmaal passeert. Dit als NP-volledig geclassificeerde vraagstuk is berucht om zijn moeilijkheidsgraad wanneer de weergave maar groot genoeg is. Hoewel iedere voorgedragen oplossing eenvoudig geverifieerd kan worden, is er geen betrouwbare formule of sluipweg om deze oplossing te vinden of om te bepalen of er één bestaat. We weten niet eens zeker of een computer op betrouwbare wijze een oplossing zou kunnen vinden. Deze puzzel voegt een extra dimensie aan het vraagstuk toe door een vast begin- en eindpunt te geven. Maar voordat je massa's papier verspilt, moet je weten dat een waar Hamiltonpad met dit begin- en eindpunt onmogelijk is. De ruimtes vormen een rooster met een even aantal ruimtes aan beide zijdes. In ieder rooster met die opstelling is een Hamiltonpad met het begin- en eindpunt in tegenovergestelde hoeken ... onmogelijk. Hier is één uitleg, waarom dat zo is. Denk aan een geruit bord met een even aantal vakjes aan elke kant. Iedere route over het bord zal om en om de zwarte en witte vakjes afwisselen. Zo'n rooster zal ook in totaal een even aantal vakjes hebben, omdat een even getal maal een even getal in een even getal resulteert. Een Hamiltonpad dat op een rooster met een even aantal vakjes op zwart start, zal dientengevolge op wit moeten eindigen. En één dat op wit start, zal op zwart moeten eindigen. Op eender welk rooster met aan alle zijdes een even aantal vakjes zullen tegenovergestelde hoeken echter dezelfde kleur hebben, waardoor een Hamiltonpad onmogelijk kan starten en eindigen in tegenovergestelde hoeken. Het lijkt erop dat je pech hebt, tenzij je consciëntieus op de regels let en een belangrijke uitzondering opmerkt. Het klopt dat eens de zelfvernietigingknop in een kamer is geactiveerd, de kamer verloren is en je niet terug kunt keren. Maar er is één ruimte niet besmet geraakt: de ingang. Hierdoor kun je de ruimte eenmalig verlaten zonder de knop te gebruiken en terugkeren wanneer je een van deze twee ruimtes hebt vernietigd. Door het openen van de luchtsluis is de hoekruimte nu besmet geraakt, maar dat is prima, omdat je de ingang kunt vernietigen bij je tweede bezoek. Het tweede bezoek biedt vier mogelijkheden voor een succesvolle route en een gelijk aantal mogelijkheden als je deze ruimte als eerste had vernietigd. Gefeliciteerd. Je hebt een epidemie van apocalyptische proporties voorkomen, maar na zo'n stressvolle gebeurtenis heb je even rust nodig. Misschien moet je toch maar die vacature voor een baan als colporteur overwegen.