Can you solve the control room riddle? - Dennis Shasha

View full lesson: http://ed.ted.com/lessons/can-you-solve-the-control-room-riddle-dennis-shasha

As your country's top spy, you must infiltrate the headquarters of the evil syndicate, find the secret control panel, and deactivate their death ray. But your reconnaissance team is spotty, and you have only limited information about the control panel's whereabouts. Can you solve the control room riddle and deactivate their weapon in time? Dennis Shasha shows you how.

Lesson by Dennis Shasha, animation by Zedem Media.

As your country's top spy,

you must infiltrate the headquarters
of the evil syndicate,

find the secret control panel,

and deactivate their death ray.

But all you have to go on
is the following information

picked up by your surveillance team.

The headquarters is a massive pyramid
with a single room at the top level,

two rooms on the next,

and so on.

The control panel is hidden
behind a painting

on the highest floor that can satisfy
the following conditions:

Each room has exactly three doors
to other rooms on that floor,

except the control panel room,

which connects to only one,

there are no hallways,

and you can ignore stairs.

Unfortunately,
you don't have a floor plan,

and you'll only have enough time
to search a single floor

before the alarm system reactivates.

Can you figure out which floor
the control room is on?

Pause now to solve the riddle yourself.

Answer in: 3

Answer in: 2

Answer in: 1

To solve this problem,
we need to visualize it.

For starters, we know
that on the correct floor

there's one room,

let's call it room A,

with one door to the control panel room,

plus one door to room B,

and one to C.

So there must be at least four rooms,

which we can represent as circles,

drawing lines between them
for the doorways.

But once we connect rooms B and C,

there are no other connections possible,

so the fourth floor down
from the top is out.

We know the control panel has to be
as high up as possible,

so let's make our way down the pyramid.

The fifth highest floor
doesn't work either.

We can figure that out by drawing it,

but to be sure we haven't missed
any possibilities,

here's another way.

Every door corresponds to a line
in our graph

that makes two rooms into neighbors.

So in the end, there have to be
an even number of neighbors

no matter how many connections we make.

On the fifth highest floor,
to fulfill our starting conditions,

we'd need four rooms
with three neighbors each,

plus the control panel room
with one neighbor,

which makes 13 total neighbors.

Since that's an odd number,
it's not possible,

and, in fact, this also rules out every
floor that has an odd number of rooms.

So let's go one more floor down.

When we draw out the rooms,

low and behold, we can find an arrangement
that works like this.

Incidentally, the study
of such visual models

that show the connections and
relationships between different objects

is known as graph theory.

In a basic graph, the circles representing
the objects are known as nodes,

while the connecting lines
are called edges.

Researchers studying such graphs
ask questions like,

"How far is this node from that one?"

"How many edges does
the most popular node have?"

"Is there a route between these two nodes,
and if so, how long is it?"

Graphs like this are often used
to map communication networks,

but they can represent almost
any kind of network,

from transport connections within a city

and social relationships among people,

to chemical interactions between proteins

or the spread of an epidemic
through different locations.

So, armed with these techniques,
back to the pyramid.

You avoid the guards and security cameras,

infiltrate the sixth floor from the top,

find the hidden panel,

pull some conspicuous levers,

and send the death ray crashing
into the ocean.

Now, time to solve the mystery

of why your surveillance team
always gives you cryptic information.

Hi everybody.

If you liked this riddle,
try solving these two.