WEBVTT

00:00:08.173 --> 00:00:10.778
Il tuo team di ricerca ha scoperto
un virus preistorico

00:00:10.778 --> 00:00:12.689
preservato nel permafrost

00:00:12.689 --> 00:00:15.170
e l'ha isolato per studiarlo.

00:00:15.170 --> 00:00:16.859
Dopo una lunga notte di lavoro,

00:00:16.859 --> 00:00:20.489
stai chiudendo il laboratorio
quando arriva una scossa di terremoto

00:00:20.489 --> 00:00:22.449
che fa saltare la corrente.

00:00:22.449 --> 00:00:27.449
Appena i gruppi elettrogeni si attivano,
un allarme conferma le tue peggiori paure:

00:00:27.449 --> 00:00:30.734
tutte le fiale dei campioni
si sono rotte.

00:00:30.734 --> 00:00:32.953
Il virus per ora è contenuto,

00:00:32.953 --> 00:00:34.546
ma a meno che
non lo si distrugga,

00:00:34.546 --> 00:00:40.072
i fori di aerazione si apriranno presto
e libereranno nell'aria una peste letale.

00:00:40.072 --> 00:00:42.640
Senza esitare, prendi
la tua tuta HazMat

00:00:42.640 --> 00:00:46.250
e ti prepari a salvare il mondo.

00:00:46.250 --> 00:00:50.041
Il laboratorio è un complesso
4 per 4 di 16 stanze

00:00:50.041 --> 00:00:54.991
con un ingresso nell'angolo a nord-ovest
e un'uscita in quello a sud-est.

00:00:54.991 --> 00:00:58.412
Ogni stanza è collegata
a quella adiacente da un'intercapedine,

00:00:58.412 --> 00:01:03.030
e il virus è stato rilasciato
in ogni stanza ad eccezione dell'ingresso.

00:01:03.030 --> 00:01:06.040
Per distruggerlo, devi entrare
in ogni camera contaminata

00:01:06.040 --> 00:01:09.480
e attivare l'interruttore di emergenza
per l'autodistruzione.

00:01:09.480 --> 00:01:11.540
Ma c'è un intoppo.

00:01:11.540 --> 00:01:13.822
Dato che il sistema è
in blocco di sicurezza,

00:01:13.822 --> 00:01:16.111
una volta entrati
in una stanza contaminata,

00:01:16.111 --> 00:01:19.580
non si può uscire senza
aver attivato l'interruttore,

00:01:19.580 --> 00:01:21.070
e una volta fatto ciò,

00:01:21.070 --> 00:01:25.401
non si può più tornare indietro
in quella stanza.

00:01:25.401 --> 00:01:29.150
Inizi a disegnare possibili percorsi
su un taccuino,

00:01:29.150 --> 00:01:31.324
ma nessuno sembra portarti all'uscita

00:01:31.324 --> 00:01:34.410
senza saltare almeno una stanza.

00:01:34.410 --> 00:01:38.341
Quindi come puoi distruggere il virus
in ogni stanza contaminata

00:01:38.341 --> 00:01:40.732
e sopravvivere per raccontarlo?

00:01:40.732 --> 00:01:45.592
Mettete in pausa qui se volete
ragionarci da soli.

00:01:45.592 --> 00:01:47.036
Soluzione in: 3

00:01:47.036 --> 00:01:48.890
Soluzione in: 2

00:01:48.890 --> 00:01:50.843
Soluzione in: 1

00:01:50.843 --> 00:01:54.800
Se la prima cosa che fai è tracciare
ogni possibile percorso in una griglia

00:01:54.800 --> 00:01:56.960
hai avuto l'idea giusta.

00:01:56.960 --> 00:02:00.310
Questo indovinello rimanda
al problema del ciclo Hamiltoniano

00:02:00.310 --> 00:02:05.491
dal nome del matematico irlandese
del 19° secolo William Rowan Hamilton.

00:02:05.491 --> 00:02:07.050
La sfida posta dal problema

00:02:07.050 --> 00:02:11.811
è di scoprire se un dato grafo
possiede un ciclo Hamiltoniano.

00:02:11.811 --> 00:02:16.081
Questo è un percorso che attraversa
ogni punto esattamente una volta.

00:02:16.081 --> 00:02:19.541
Questo genere di problema,
definito come NP-completo,

00:02:19.541 --> 00:02:24.171
è notoriamente difficile 
quando il grafo è molto ampio.

00:02:24.171 --> 00:02:27.752
Anche se ogni soluzione proposta
può essere facilmente verificata,

00:02:27.752 --> 00:02:31.461
non conosciamo nessuna formula
o scorciatoia per trovarne uno,

00:02:31.461 --> 00:02:33.542
o determinarne l'esistenza.

00:02:33.542 --> 00:02:36.091
Non siamo nemmeno sicuri 
che i computer possano

00:02:36.091 --> 00:02:40.351
trovare delle soluzioni adeguate.

00:02:40.351 --> 00:02:43.541
Questo indovinello aggiunge una variante
al problema Hamiltoniano

00:02:43.541 --> 00:02:47.602
perché presenta specifici
punti di partenza e di arrivo.

00:02:47.602 --> 00:02:50.202
Ma prima di usare una tonnellata
di carta millimetrata,

00:02:50.202 --> 00:02:52.672
dovresti sapere
che un ciclo Hamiltoniano

00:02:52.672 --> 00:02:55.371
non è possibile con questi due estremi.

00:02:55.371 --> 00:03:01.183
Questo perché la griglia è formata
da un numero pari di stanze per ogni lato.

00:03:01.183 --> 00:03:03.442
In ogni griglia con quella configurazione,

00:03:03.442 --> 00:03:10.222
un ciclo Hamiltoniano che ha inizio e fine
in due angoli opposti è impossibile.


00:03:10.222 --> 00:03:12.831
Ecco una spiegazione del perché.

00:03:12.831 --> 00:03:17.562
Consideriamo una griglia a scacchiera con
un numero pari di caselle per ogni lato.

00:03:17.562 --> 00:03:21.012
Ogni percorso alternerà
una casella bianca e una nera.

00:03:21.012 --> 00:03:25.702
Inoltre queste griglie avranno in tutto 
un numero pari di caselle

00:03:25.702 --> 00:03:29.653
perché un numero pari moltiplicato
per un numero pari è pari.

00:03:29.653 --> 00:03:34.243
Quindi un ciclo Hamiltoniano che su una 
griglia pari inizia in una casella nera

00:03:34.243 --> 00:03:36.483
dovrà finire in una bianca.

00:03:36.483 --> 00:03:40.294
E uno che inizierà in una casella bianca
dovrà finire in una nera.

00:03:40.294 --> 00:03:43.152
Comunque, in ogni griglia con lati formati
da caselle pari,

00:03:43.152 --> 00:03:46.112
gli angoli opposti
sono dello stesso colore,

00:03:46.112 --> 00:03:52.753
quindi un ciclo Hamiltoniano non può avere
inizio e fine in angoli opposti.

00:03:52.753 --> 00:03:54.734
Sembrerebbe che non ci sia nulla da fare,

00:03:54.734 --> 00:04:00.644
a meno che non si guardino bene le regole
e non si noti un'importante eccezione.

00:04:00.644 --> 00:04:04.504
È vero che una volta attivato
l'interruttore in una stanza contaminata,

00:04:04.504 --> 00:04:07.283
quella è distrutta
e non si può tornare indietro.

00:04:07.283 --> 00:04:11.473
Ma c'è una stanza
non contaminata: l'ingresso.

00:04:11.473 --> 00:04:14.994
Questo significa che si può uscire
una volta senza attivare l'interruttore

00:04:14.994 --> 00:04:19.978
e tornarci una volta che si è distrutta
una di queste due stanze.

00:04:19.978 --> 00:04:22.034
L'ingresso potrà essere stato contaminato

00:04:22.034 --> 00:04:24.983
dall'apertura della camera di equilibrio,
ma va bene

00:04:24.983 --> 00:04:28.618
perché si potrà distruggere
dopo la seconda visita.

00:04:28.618 --> 00:04:32.588
Quel viaggio di ritorno apre quattro
possibili percorsi ottimali,

00:04:32.588 --> 00:04:37.154
lo stesso se si distrugge 
prima questa stanza.

00:04:37.154 --> 00:04:42.755
Congratulazioni. Hai sventato un'epidemia
di proporzioni apocalittiche,

00:04:42.755 --> 00:04:46.169
ma dopo una vicenda così stressante,
hai bisogno di una pausa.

00:04:46.169 --> 00:04:50.587
Forse dovresti accettare quell'offerta di
lavoro per fare il commesso viaggiatore.