Pouvez-vous résoudre l'énigme du virus ? - Lisa Winer

Voir la leçon complète : http://ed.ted.com/lessons/can-you-solve-the-virus-riddle-lisa-winer

Votre équipe de chercheurs a trouvé un virus préhistorique préservé dans le permafrost et l'a isolé pour l'étudier. Après une longue nuit de travail, vous vous apprêtez à fermer le laboratoire quand un tremblement de terre survient et casse tous les flacons d'échantillons. Serez-vous capable de détruire le virus avant que les conduits d'aération ne s'ouvrent et libèrent une peste mortelle ? Lisa Winer vous montre comment.

Leçon par Lisa Winer, animation par Artrake Studio.

Votre équipe de chercheurs a trouvé
un virus préhistorique

préservé dans le permafrost

et l'a isolé pour l'étudier.

Après une longue nuit de travail,

vous vous apprêtez à fermer le labo
quand un tremblement de terre soudain

paralyse le réseau électrique.

Quand le générateur de secours démarre,
une alarme confirme votre pire crainte :

tous les flacons d'échantillons
sont cassés.

Le virus est contenu pour l'instant,

mais si vous ne le détruisez pas,

les conduits d'aération s'ouvriront
et libèreront une peste mortelle.

Sans hésiter, vous enfilez votre
combinaison de protection

et vous vous préparez à sauver le monde.

Le labo est une enceinte
de 4 par 4, soit 16 pièces,

avec une entrée à l'angle nord-ouest
et une sortie au sud-est.

Chaque pièce est reliée
aux pièces voisines par un sas,

et le virus a été libéré
dans chaque pièce sauf l'entrée.

Pour le détruire, vous devez entrer
dans chaque pièce contaminée

et enclencher l'interrupteur
d'auto-destruction.

Mais il y a un piège.

Comme le système de sécurité
est verrouillé,

quand vous entrez
dans une pièce contaminée,

vous ne pouvez plus en sortir
sans activer l'interrupteur,

et une fois que c'est fait,

vous ne pourrez plus
retourner dans cette pièce.

Vous commencez à dessiner tous les
itinéraires possibles sur un bloc-notes,

mais rien ne vous permet
d’atteindre la sortie

sans rater au moins une pièce.

Alors comment faire pour détruire le virus
dans chaque pièce contaminée,

et survivre pour raconter l'histoire ?

Faites « Pause » si vous souhaitez
trouver la réponse par vous-même.

Réponse dans : 3

Réponse dans : 2

Réponse dans : 1

Si votre premier instinct est de dessiner
tous les chemins possibles sur une grille,

vous avez la bonne idée.

Ce puzzle est lié au problème
du chemin hamiltonien,

du nom du mathématicien irlandais du
19ème siècle, William Rowan Hamilton.

Le défi de ce problème

est de trouver si un graphe donné
possède un chemin hamiltonien.

C'est un trajet qui passe exactement
une seule fois par chaque point.

Ce type de problème, classé comme
NP-complet,

est réputé difficile quand le graphe
est suffisamment grand.

Bien que toute solution proposée
puisse être facilement vérifiée,

il n'existe aucune formule ou raccourci
fiable pour en trouver une,

ou pour déterminer s'il en existe une.

Et nous ne sommes même pas sûrs
que les ordinateurs

puissent trouver de manière fiable
de telles solutions.

Cette énigme ajoute une contrainte
au problème du chemin hamiltonien,

puisque vous devez commencer et finir
par des points spécifiques.

Mais avant de gaspiller
une tonne de papier quadrillé,

vous devriez savoir qu'un vrai
chemin hamiltonien

est impossible avec ces extrémités.

C'est parce que les pièces forment
une grille aux côtés pairs.

Dans toute grille avec
cette configuration,

un chemin hamiltonien qui débute et finit
par des coins opposés est impossible.

Voici un moyen de comprendre pourquoi.

Imaginez un échiquier avec
un nombre pair de carrés de chaque côté.

Chaque chemin traversant l'échiquier
alternera le blanc et le noir.

Ces grilles ont aussi toutes
un nombre total de carrés pair

parce qu'en multipliant deux nombre pairs,
on obtient un nombre pair.

Un chemin hamiltonien sur une grille
aux côtés pairs démarrant sur du noir

devra se terminer sur du blanc.

Et un chemin commençant sur du blanc
devra se terminer sur du noir.

Toutefois, dans toute grille
aux côtés pairs,

les coins opposés sont de la même couleur,

il est donc impossible de débuter et finir
un chemin hamiltonien

sur des coins opposés.

On dirait que vous n'avez pas de chance,

à moins de bien regarder les règles
et remarquer une exception importante.

C'est vrai qu'une fois l'interrupteur
activé dans une pièce contaminée,

celle-ci est détruite
et vous ne pouvez plus y retourner.

Mais il y a une pièce
qui n'a pas été contaminée - l'entrée.

Cela signifie que vous pouvez en sortir
une fois sans activer l'interrupteur

et y retourner une fois que
vous avez détruit l'une de ces pièces.

La pièce du coin peut être contaminée

par l'ouverture du sas,
mais ce n'est pas grave

parce que vous pouvez détruire l'entrée
après votre deuxième passage.

Ce voyage retour vous donne 4 options
pour un trajet couronné de succès,

et un lot similaire d'options
si vous détruisez cette pièce en premier.

Félicitations. Vous avez évité
une épidémie de proportion apocalyptique,

mais après un épisode aussi stressant,
vous avez besoin d'une pause.

Peut-être devriez-vous accepter
cette offre d'emploi pour devenir VRP.