Can you solve the prisoner hat riddle? - Alex Gendler — Transcript

Full transcript

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