Can you solve the famously difficult green-eyed logic puzzle? - Alex Gendler
-
0:07 - 0:09Imagine an island where 100 people,
-
0:09 - 0:14all perfect logicians,
are imprisoned by a mad dictator. -
0:14 - 0:18There's no escape,
except for one strange rule. -
0:18 - 0:23Any prisoner can approach the guards
at night and ask to leave. -
0:23 - 0:26If they have green eyes,
they'll be released. -
0:26 - 0:30If not, they'll be tossed
into the volcano. -
0:30 - 0:34As it happens,
all 100 prisoners have green eyes, -
0:34 - 0:37but they've lived there since birth,
-
0:37 - 0:41and the dictator has ensured
they can't learn their own eye color. -
0:41 - 0:43There are no reflective surfaces,
-
0:43 - 0:46all water is in opaque containers,
-
0:46 - 0:48and most importantly,
-
0:48 - 0:51they're not allowed
to communicate among themselves. -
0:51 - 0:55Though they do see each other
during each morning's head count. -
0:55 - 0:59Nevertheless, they all know no one would
ever risk trying to leave -
0:59 - 1:03without absolute certainty of success.
-
1:03 - 1:05After much pressure
from human rights groups, -
1:05 - 1:09the dictator reluctantly agrees
to let you visit the island -
1:09 - 1:12and speak to the prisoners
under the following conditions: -
1:12 - 1:15you may only make one statement,
-
1:15 - 1:18and you cannot tell them
any new information. -
1:18 - 1:21What can you say
to help free the prisoners -
1:21 - 1:24without incurring the dictator's wrath?
-
1:24 - 1:26After thinking long and hard,
-
1:26 - 1:31you tell the crowd,
"At least one of you has green eyes." -
1:31 - 1:33The dictator is suspicious
-
1:33 - 1:38but reassures himself that your statement
couldn't have changed anything. -
1:38 - 1:42You leave, and life on the island
seems to go on as before. -
1:42 - 1:45But on the hundredth morning
after your visit, -
1:45 - 1:47all the prisoners are gone,
-
1:47 - 1:51each having asked to leave
the previous night. -
1:51 - 1:54So how did you outsmart the dictator?
-
1:54 - 1:59It might help to realize that the amount
of prisoners is arbitrary. -
1:59 - 2:04Let's simplify things
by imagining just two, Adria and Bill. -
2:04 - 2:06Each sees one person with green eyes,
-
2:06 - 2:10and for all they know,
that could be the only one. -
2:10 - 2:12For the first night, each stays put.
-
2:12 - 2:15But when they see each other
still there in the morning, -
2:15 - 2:18they gain new information.
-
2:18 - 2:22Adria realizes that if Bill had seen
a non-green-eyed person next to him, -
2:22 - 2:24he would have left the first night
-
2:24 - 2:28after concluding the statement
could only refer to himself. -
2:28 - 2:32Bill simultaneously realizes
the same thing about Adria. -
2:32 - 2:34The fact that the other person waited
-
2:34 - 2:39tells each prisoner his
or her own eyes must be green. -
2:39 - 2:42And on the second morning,
they're both gone. -
2:42 - 2:45Now imagine a third prisoner.
-
2:45 - 2:49Adria, Bill and Carl each see
two green-eyed people, -
2:49 - 2:54but aren't sure if each of the others
is also seeing two green-eyed people, -
2:54 - 2:56or just one.
-
2:56 - 2:58They wait out the first night as before,
-
2:58 - 3:01but the next morning,
they still can't be sure. -
3:01 - 3:04Carl thinks, "If I have non-green eyes,
-
3:04 - 3:07Adria and Bill were just
watching each other, -
3:07 - 3:10and will now both leave
on the second night." -
3:10 - 3:12But when he sees both
of them the third morning, -
3:12 - 3:16he realizes they must
have been watching him, too. -
3:16 - 3:19Adria and Bill have each
been going through the same process, -
3:19 - 3:22and they all leave on the third night.
-
3:22 - 3:24Using this sort of inductive reasoning,
-
3:24 - 3:29we can see that the pattern will repeat
no matter how many prisoners you add. -
3:29 - 3:32The key is the concept
of common knowledge, -
3:32 - 3:35coined by philosopher David Lewis.
-
3:35 - 3:39The new information was not contained
in your statement itself, -
3:39 - 3:43but in telling it to everyone
simultaneously. -
3:43 - 3:47Now, besides knowing at least one
of them has green eyes, -
3:47 - 3:51each prisoner also knows
that everyone else is keeping track -
3:51 - 3:54of all the green-eyed people they can see,
-
3:54 - 3:59and that each of them
also knows this, and so on. -
3:59 - 4:01What any given prisoner doesn't know
-
4:01 - 4:04is whether they themselves are one
of the green-eyed people -
4:04 - 4:06the others are keeping track of
-
4:06 - 4:13until as many nights have passed
as the number of prisoners on the island. -
4:13 - 4:17Of course, you could have spared
the prisoners 98 days on the island -
4:17 - 4:21by telling them at least 99 of you
have green eyes, -
4:21 - 4:26but when mad dictators are involved,
you're best off with a good headstart.
- Title:
- Can you solve the famously difficult green-eyed logic puzzle? - Alex Gendler
- Speaker:
- Alex Gendler
- Description:
-
View full lesson: http://ed.ted.com/lessons/the-famously-difficult-green-eyed-logic-puzzle-alex-gendler
One hundred green-eyed logicians have been imprisoned on an island by a mad dictator. Their only hope for freedom lies in the answer to one famously difficult logic puzzle. Can you solve it? Alex Gendler walks us through this green-eyed riddle.
Lesson by Alex Gendler, animation by Artrake Studio.
- Video Language:
- English
- Team:
- closed TED
- Project:
- TED-Ed
- Duration:
- 04:42
Jessica Ruby edited English subtitles for Can you solve the famously difficult green-eyed logic puzzle? | ||
Jessica Ruby edited English subtitles for Can you solve the famously difficult green-eyed logic puzzle? | ||
Jessica Ruby edited English subtitles for Can you solve the famously difficult green-eyed logic puzzle? | ||
Jessica Ruby edited English subtitles for Can you solve the famously difficult green-eyed logic puzzle? | ||
Jessica Ruby approved English subtitles for Can you solve the famously difficult green-eyed logic puzzle? | ||
Jessica Ruby accepted English subtitles for Can you solve the famously difficult green-eyed logic puzzle? | ||
Jessica Ruby edited English subtitles for Can you solve the famously difficult green-eyed logic puzzle? | ||
Jessica Ruby edited English subtitles for Can you solve the famously difficult green-eyed logic puzzle? |