Name: 【TED-Ed】Can you solve the virus riddle? - Lisa Winer
Uploaded: 2017-04-05T07:36:59.000Z
Duration: 5 min 13 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

Your research team has found a prehistoric virus preserved in the permafrost

you're just closing up the lab when a sudden earthquake hits

As the emergency generators kick in, an alarm confirms your worst fears:

the vents will soon open and unleash a deadly airborne plague.

Without hesitation, you grab your HazMat suit

The lab is a four by four compound of 16 rooms

with an entrance on the northwest corner and an exit at the southeast.

Each room is connected to the adjacent ones by an airlock,

and the virus has been released in every room except the entrance.

To destroy it, you must enter each contaminated room

and pull its emergency self-destruct switch.

Because the security system is on lockdown,

you can't exit without activating the switch,

you won't be able to go  back in to that room.

You start to draw out possible routes on a pad of paper,

but nothing seems to get you to the exit without missing at least one room.

So how can you destroy the virus in every contaminated room

Pause here if you want to figure it out for yourself.

If your first instinct is to try to graph your possible moves on a grid,

This puzzle is related to the Hamiltonian path problem

named after the 19th century Irish mathematician William Rowan Hamilton.

is to find whether a given graph has a Hamiltonian path.

That's a route that visits every point within it exactly once.

This type of problem, classified as NP-complete,

is notoriously difficult when the graph is sufficiently large.

Although any proposed solution can be easily verified,

we have no reliable formula or shortcut for finding one,

And we're not even sure if it's possible for computers

This puzzle adds a twist to the Hamiltonian path problem

in that you have to start  and end at specific points.

But before you waste a ton of graph paper,

you should know that a true Hamiltonian path

That's because the rooms form a grid with an even number of rooms on each side.

a Hamiltonian path that starts and ends in opposite corners is impossible.

Consider a checkerboard grid with an even number of squares on each side.

Every path through it will alternate black and white.

These grids will all also have an even total number of squares

because an even number times and even number is even.

So a Hamiltonian path on an even-sided grid that starts on black

And one that starts on white will have to end on black.

However, in any grid with even numbered sides,

so it's impossible to start and end a Hamiltonian path on opposite corners.

unless you look at the rules carefully and notice an important exception.

It's true that once you activate the switch in a contaminated room,

it's destroyed and you can never go back.

But there's one room that wasn't contaminated - the entrance.

This means that you can leave it once without pulling the switch

and return there when you've destroyed either of these two rooms.

The corner room may have been contaminated from the airlock opening,

but that's okay because you can destroy the entrance after your second visit.

That return trip gives you four options for a successful route,

and a similar set of options if you destroyed this room first.

Congratulations. You've prevented an epidemic of apocalyptic proportions,

but after such a stressful episode, you need a break.

Maybe you should take up that recent job offer to become a traveling salesman.