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.