Can you solve the prisoner hat riddle? - Alex Gendler
-
0:11 - 0:14You and nine other individuals
have been captured -
0:14 - 0:17by super intelligent alien overlords.
-
0:17 - 0:21The aliens think humans look quite tasty,
-
0:21 - 0:26but their civilization forbids eating
highly logical and cooperative beings. -
0:26 - 0:30Unfortunately, they're not sure
whether you qualify, -
0:30 - 0:33so they decide to give you all a test.
-
0:33 - 0:34Through its universal translator,
-
0:34 - 0:38the alien guarding you
tells you the following: -
0:38 - 0:43You will be placed in a single-file line
facing forward in size order -
0:43 - 0:47so that each of you can see
everyone lined up ahead of you. -
0:47 - 0:51You will not be able to look behind you
or step out of line. -
0:51 - 0:55Each of you will have either a black
or a white hat on your head -
0:55 - 0:57assigned randomly,
-
0:57 - 1:01and I won't tell you
how many of each color there are. -
1:01 - 1:05When I say to begin, each of you must
guess the color of your hat -
1:05 - 1:09starting with the person in the back
and moving up the line. -
1:09 - 1:13And don't even try saying words
other than black or white -
1:13 - 1:17or signaling some other way,
like intonation or volume; -
1:17 - 1:20you'll all be eaten immediately.
-
1:20 - 1:24If at least nine of you guess correctly,
you'll all be spared. -
1:24 - 1:27You have five minutes to discuss
and come up with a plan, -
1:27 - 1:32and then I'll line you up,
assign your hats, and we'll begin. -
1:32 - 1:36Can you think of a strategy guaranteed
to save everyone? -
1:36 - 1:39Pause the video now
to figure it out for yourself. -
1:39 - 1:40Answer in: 3
-
1:40 - 1:41Answer in: 2
-
1:41 - 1:43Answer in: 1
-
1:43 - 1:46The key is that the person
at the back of the line -
1:46 - 1:50who can see everyone else's hats
can use the words "black" or "white" -
1:50 - 1:54to communicate some coded information.
-
1:54 - 1:57So what meaning can be
assigned to those words -
1:57 - 2:01that will allow everyone else
to deduce their hat colors? -
2:01 - 2:04It can't be the total number
of black or white hats. -
2:04 - 2:07There are more than two possible values,
-
2:07 - 2:12but what does have two possible values
is that number's parity, -
2:12 - 2:15that is whether it's odd or even.
-
2:15 - 2:19So the solution is to agree
that whoever goes first will, -
2:19 - 2:23for example, say "black" if he sees
an odd number of black hats -
2:23 - 2:28and "white" if he sees
an even number of black hats. -
2:28 - 2:32Let's see how it would play out
if the hats were distributed like this. -
2:32 - 2:35The tallest captive sees three black
hats in front of him, -
2:35 - 2:41so he says "black," telling everyone else
he sees an odd number of black hats. -
2:41 - 2:44He gets his own hat color wrong,
but that's okay -
2:44 - 2:48since you're collectively allowed
to have one wrong answer. -
2:48 - 2:51Prisoner two also sees an odd
number of black hats, -
2:51 - 2:55so she knows hers is white,
and answers correctly. -
2:55 - 2:58Prisoner three sees
an even number of black hats, -
2:58 - 3:01so he knows that his must be
one of the black hats -
3:01 - 3:04the first two prisoners saw.
-
3:04 - 3:05Prisoner four hears that and knows
-
3:05 - 3:09that she should be looking for
an even number of black hats -
3:09 - 3:11since one was behind her.
-
3:11 - 3:16But she only sees one, so she deduces
that her hat is also black. -
3:16 - 3:20Prisoners five through nine are each
looking for an odd number of black hats, -
3:20 - 3:25which they see, so they figure out
that their hats are white. -
3:25 - 3:29Now it all comes down to you
at the front of the line. -
3:29 - 3:32If the ninth prisoner saw
an odd number of black hats, -
3:32 - 3:35that can only mean one thing.
-
3:35 - 3:39You'll find that this strategy works
for any possible arrangement of the hats. -
3:39 - 3:45The first prisoner has a 50% chance of
giving a wrong answer about his own hat, -
3:45 - 3:47but the parity information he conveys
-
3:47 - 3:52allows everyone else
to guess theirs with absolute certainty. -
3:52 - 3:56Each begins by expecting to see an odd
or even number of hats -
3:56 - 3:58of the specified color.
-
3:58 - 4:03If what they count doesn't match,
that means their own hat is that color. -
4:03 - 4:04And everytime this happens,
-
4:04 - 4:09the next person in line will switch
the parity they expect to see. -
4:09 - 4:11So that's it, you're free to go.
-
4:11 - 4:13It looks like these aliens
will have to go hungry, -
4:13 - 4:16or find some less logical
organisms to abduct.
- Title:
- Can you solve the prisoner hat riddle? - Alex Gendler
- Speaker:
- Alex Gendler
- Description:
-
View full lesson: http://ed.ted.com/lessons/can-you-solve-the-prisoner-hat-riddle-alex-gendler
You and nine other individuals have been captured by super-intelligent alien overlords. The aliens think humans look quite tasty, but their civilization forbids eating highly logical and cooperative beings. Unfortunately, they’re not sure whether you qualify, so they decide to give you all a test. Can you solve this hat riddle? Alex Gendler shows how.
Lesson by Alex Gendler, animation by Artrake Studio.
- Video Language:
- English
- Team:
- closed TED
- Project:
- TED-Ed
- Duration:
- 04:35
Jessica Ruby approved English subtitles for Can you solve the prisoner hat riddle? | ||
Jessica Ruby accepted English subtitles for Can you solve the prisoner hat riddle? | ||
Jessica Ruby edited English subtitles for Can you solve the prisoner hat riddle? | ||
Jessica Ruby edited English subtitles for Can you solve the prisoner hat riddle? | ||
Jessica Ruby edited English subtitles for Can you solve the prisoner hat riddle? | ||
Jennifer Cody edited English subtitles for Can you solve the prisoner hat riddle? | ||
Jennifer Cody edited English subtitles for Can you solve the prisoner hat riddle? |