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.
Il tuo team di ricerca ha scoperto un virus preistorico preservato nel permafrost e l'ha isolato per studiarlo. Dopo una lunga notte di lavoro, stai chiudendo il laboratorio quando arriva una scossa di terremoto che fa saltare la corrente. Appena i gruppi elettrogeni si attivano, un allarme conferma le tue peggiori paure: tutte le fiale dei campioni si sono rotte. Il virus per ora è contenuto, ma a meno che non lo si distrugga, i fori di aerazione si apriranno presto e libereranno nell'aria una peste letale. Senza esitare, prendi la tua tuta HazMat e ti prepari a salvare il mondo. Il laboratorio è un complesso 4 per 4 di 16 stanze con un ingresso nell'angolo a nord-ovest e un'uscita in quello a sud-est. Ogni stanza è collegata a quella adiacente da un'intercapedine, e il virus è stato rilasciato in ogni stanza ad eccezione dell'ingresso. Per distruggerlo, devi entrare in ogni camera contaminata e attivare l'interruttore di emergenza per l'autodistruzione. Ma c'è un intoppo. Dato che il sistema è in blocco di sicurezza, una volta entrati in una stanza contaminata, non si può uscire senza aver attivato l'interruttore, e una volta fatto ciò, non si può più tornare indietro in quella stanza. Inizi a disegnare possibili percorsi su un taccuino, ma nessuno sembra portarti all'uscita senza saltare almeno una stanza. Quindi come puoi distruggere il virus in ogni stanza contaminata e sopravvivere per raccontarlo? Mettete in pausa qui se volete ragionarci da soli. Soluzione in: 3 Soluzione in: 2 Soluzione in: 1 Se la prima cosa che fai è tracciare ogni possibile percorso in una griglia hai avuto l'idea giusta. Questo indovinello rimanda al problema del ciclo Hamiltoniano dal nome del matematico irlandese del 19° secolo William Rowan Hamilton. La sfida posta dal problema è di scoprire se un dato grafo possiede un ciclo Hamiltoniano. Questo è un percorso che attraversa ogni punto esattamente una volta. Questo genere di problema, definito come NP-completo, è notoriamente difficile quando il grafo è molto ampio. Anche se ogni soluzione proposta può essere facilmente verificata, non conosciamo nessuna formula o scorciatoia per trovarne uno, o determinarne l'esistenza. Non siamo nemmeno sicuri che i computer possano trovare delle soluzioni adeguate. Questo indovinello aggiunge una variante al problema Hamiltoniano perché presenta specifici punti di partenza e di arrivo. Ma prima di usare una tonnellata di carta millimetrata, dovresti sapere che un ciclo Hamiltoniano non è possibile con questi due estremi. Questo perché la griglia è formata da un numero pari di stanze per ogni lato. In ogni griglia con quella configurazione, un ciclo Hamiltoniano che ha inizio e fine in due angoli opposti è impossibile. Ecco una spiegazione del perché. Consideriamo una griglia a scacchiera con un numero pari di caselle per ogni lato. Ogni percorso alternerà una casella bianca e una nera. Inoltre queste griglie avranno in tutto un numero pari di caselle perché un numero pari moltiplicato per un numero pari è pari. Quindi un ciclo Hamiltoniano che su una griglia pari inizia in una casella nera dovrà finire in una bianca. E uno che inizierà in una casella bianca dovrà finire in una nera. Comunque, in ogni griglia con lati formati da caselle pari, gli angoli opposti sono dello stesso colore, quindi un ciclo Hamiltoniano non può avere inizio e fine in angoli opposti. Sembrerebbe che non ci sia nulla da fare, a meno che non si guardino bene le regole e non si noti un'importante eccezione. È vero che una volta attivato l'interruttore in una stanza contaminata, quella è distrutta e non si può tornare indietro. Ma c'è una stanza non contaminata: l'ingresso. Questo significa che si può uscire una volta senza attivare l'interruttore e tornarci una volta che si è distrutta una di queste due stanze. L'ingresso potrà essere stato contaminato dall'apertura della camera di equilibrio, ma va bene perché si potrà distruggere dopo la seconda visita. Quel viaggio di ritorno apre quattro possibili percorsi ottimali, lo stesso se si distrugge prima questa stanza. Congratulazioni. Hai sventato un'epidemia di proporzioni apocalittiche, ma dopo una vicenda così stressante, hai bisogno di una pausa. Forse dovresti accettare quell'offerta di lavoro per fare il commesso viaggiatore.