Can you solve the virus riddle? - Lisa Winer
-
0:08 - 0:11Your research team has found
a prehistoric virus -
0:11 - 0:13preserved in the permafrost
-
0:13 - 0:15and isolated it for study.
-
0:15 - 0:17After a late night working,
-
0:17 - 0:20you're just closing up the lab
when a sudden earthquake hits -
0:20 - 0:22and knocks out the power.
-
0:22 - 0:27As the emergency generators kick in,
an alarm confirms your worst fears: -
0:27 - 0:31all the sample vials have broken.
-
0:31 - 0:33The virus is contained for now,
-
0:33 - 0:35but unless you can destroy it,
-
0:35 - 0:40the vents will soon open
and unleash a deadly airborne plague. -
0:40 - 0:43Without hesitation, you grab
your HazMat suit -
0:43 - 0:46and get ready to save the world.
-
0:46 - 0:50The lab is a four by four compound
of 16 rooms -
0:50 - 0:55with an entrance on the northwest corner
and an exit at the southeast. -
0:55 - 0:58Each room is connected to the adjacent
ones by an airlock, -
0:58 - 1:03and the virus has been released
in every room except the entrance. -
1:03 - 1:06To destroy it, you must enter each
contaminated room -
1:06 - 1:09and pull its emergency
self-destruct switch. -
1:09 - 1:12But there's a catch.
-
1:12 - 1:14Because the security system
is on lockdown, -
1:14 - 1:16once you enter the contaminated room,
-
1:16 - 1:20you can't exit without
activating the switch, -
1:20 - 1:21and once you've done so,
-
1:21 - 1:25you won't be able to go
back in to that room. -
1:25 - 1:29You start to draw out possible
routes on a pad of paper, -
1:29 - 1:31but nothing seems to get you
to the exit -
1:31 - 1:34without missing at least one room.
-
1:34 - 1:38So how can you destroy the virus
in every contaminated room -
1:38 - 1:41and survive to tell the story?
-
1:41 - 1:46Pause here if you want
to figure it out for yourself. -
1:46 - 1:47Answer in: 3
-
1:47 - 1:49Answer in: 2
-
1:49 - 1:51Answer in: 1
-
1:51 - 1:55If your first instinct is to try to graph
your possible moves on a grid, -
1:55 - 1:57you've got the right idea.
-
1:57 - 2:00This puzzle is related to
the Hamiltonian path problem -
2:00 - 2:05named after the 19th century Irish
mathematician William Rowan Hamilton. -
2:05 - 2:07The challenge
of the path problem -
2:07 - 2:12is to find whether a given graph
has a Hamiltonian path. -
2:12 - 2:16That's a route that visits
every point within it exactly once. -
2:16 - 2:20This type of problem, classified
as NP-complete, -
2:20 - 2:24is notoriously difficult when the graph
is sufficiently large. -
2:24 - 2:28Although any proposed solution
can be easily verified, -
2:28 - 2:31we have no reliable formula or shortcut
for finding one, -
2:31 - 2:34or determining that one exists.
-
2:34 - 2:36And we're not even sure
if it's possible for computers -
2:36 - 2:40to reliably find
such solutions, either. -
2:40 - 2:44This puzzle adds a twist
to the Hamiltonian path problem -
2:44 - 2:48in that you have to start
and end at specific points. -
2:48 - 2:50But before you waste a ton of graph paper,
-
2:50 - 2:53you should know that a true
Hamiltonian path -
2:53 - 2:55isn't possible with these end points.
-
2:55 - 3:01That's because the rooms form a grid
with an even number of rooms on each side. -
3:01 - 3:03In any grid with that configuration,
-
3:03 - 3:10a Hamiltonian path that starts and
ends in opposite corners is impossible. -
3:10 - 3:13Here's one way of understanding why.
-
3:13 - 3:18Consider a checkerboard grid with
an even number of squares on each side. -
3:18 - 3:21Every path through it will alternate
black and white. -
3:21 - 3:26These grids will all also have an even
total number of squares -
3:26 - 3:30because an even number times
and even number is even. -
3:30 - 3:34So a Hamiltonian path on an
even-sided grid that starts on black -
3:34 - 3:36will have to end on white.
-
3:36 - 3:40And one that starts on white
will have to end on black. -
3:40 - 3:43However, in any grid with even
numbered sides, -
3:43 - 3:46opposite corners are the same color,
-
3:46 - 3:53so it's impossible to start and end
a Hamiltonian path on opposite corners. -
3:53 - 3:55It seems like you're out of luck,
-
3:55 - 4:01unless you look at the rules carefully
and notice an important exception. -
4:01 - 4:05It's true that once you activate
the switch in a contaminated room, -
4:05 - 4:07it's destroyed and you can never go back.
-
4:07 - 4:11But there's one room
that wasn't contaminated - the entrance. -
4:11 - 4:15This means that you can leave it once
without pulling the switch -
4:15 - 4:20and return there when you've
destroyed either of these two rooms. -
4:20 - 4:22The corner room may have
been contaminated -
4:22 - 4:25from the airlock opening,
but that's okay -
4:25 - 4:29because you can destroy the entrance
after your second visit. -
4:29 - 4:33That return trip gives you four options
for a successful route, -
4:33 - 4:37and a similar set of options if you
destroyed this room first. -
4:37 - 4:43Congratulations. You've prevented
an epidemic of apocalyptic proportions, -
4:43 - 4:46but after such a stressful episode,
you need a break. -
4:46 - 4:51Maybe you should take up that recent
job offer to become a traveling salesman.
- Title:
- Can you solve the virus riddle? - Lisa Winer
- Speaker:
- Lisa Winer
- Description:
-
View full lesson: http://ed.ted.com/lessons/can-you-solve-the-virus-riddle-lisa-winer
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 breaks all the sample vials. Will you be able to destroy the virus before the vents open and unleash a deadly airborne plague? Lisa Winer shows how.
Lesson by Lisa Winer, animation by Artrake Studio.
- Video Language:
- English
- Team:
- closed TED
- Project:
- TED-Ed
- Duration:
- 05:13
Jessica Ruby approved English subtitles for Can you solve the virus riddle? | ||
Jessica Ruby accepted English subtitles for Can you solve the virus riddle? | ||
Jessica Ruby edited English subtitles for Can you solve the virus riddle? | ||
Jennifer Cody edited English subtitles for Can you solve the virus riddle? |