Sai risolvere l'indovinello del virus? - Lisa Winer

Guarda l'intera lezione: http://ed.ted.com/lessons/can-you-solve-the-virus-riddle-lisa-winer

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 c'è una scossa di terremoto e si rompono tutte le fiale dei campioni. Riuscirai a debellare il virus prima che i fori di aerazione si aprano e rilascino un epidemico gas letale? Lisa Winer mostra come fare.

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.