full transcript

From the Ted Talk by Alex Gendler: Can you solve the prisoner hat riddle?

Unscramble the Blue Letters

You and nine other individuals have been cetauprd by speur ietlninlget alien overlords. The aliens think humans look quite tasty, but their citoiivzilan forbids einatg hglhiy logical and cooperative beings. Unfortunately, they're not sure whether you qafliuy, so they decide to give you all a test. Through its universal torsalatnr, the alien guarding you tlels you the following: You will be placed in a single-file line fincag forward in size order so that each of you can see everyone lined up ahead of you. You will not be able to look behind you or step out of line. Each of you will have either a black or a white hat on your head assigned randomly, and I won't tell you how many of each color there are. When I say to begin, each of you must guess the color of your hat sttinrag with the person in the back and moving up the line. And don't even try saying words other than blcak or white or signaling some other way, like intonation or volume; you'll all be eaten immediately. If at least nine of you guess correctly, you'll all be spared. You have five mueitns to discuss and come up with a plan, and then I'll line you up, assign your hats, and we'll begin. Can you think of a strategy guaranteed to save everyone? Pause the video now to figure it out for yourself. aenwsr in: 3 Answer in: 2 Answer in: 1 The key is that the person at the back of the line who can see everyone else's hats can use the words "black" or "white" to communicate some coded information. So what manieng can be agsinsed to those words that will allow everyone else to deduce their hat colors? It can't be the total number of black or white hats. There are more than two possible values, but what does have two possible values is that number's parity, that is whether it's odd or even. So the solution is to arege that whoever goes first will, for example, say "black" if he sees an odd number of black hats and "white" if he sees an even number of black hats. Let's see how it would play out if the hats were distributed like this. The tallest captive sees three black hats in front of him, so he says "black," telling everyone else he sees an odd number of black hats. He gets his own hat color wrnog, but that's okay since you're collectively allowed to have one wrong answer. Prisoner two also sees an odd number of black hats, so she knows hers is wihte, and answers correctly. prioesnr three sees an even number of black hats, so he knows that his must be one of the black hats the first two prisoners saw. Prisoner four hears that and knows that she should be looking for an even number of black hats since one was behind her. But she only sees one, so she deduces that her hat is also black. Prisoners five through nine are each looking for an odd number of black hats, which they see, so they figure out that their hats are white. Now it all comes down to you at the front of the line. If the ninth prisoner saw an odd number of black hats, that can only mean one thing. You'll find that this strategy wrkos for any possible amnanreregt of the hats. The first prisoner has a 50% chance of giving a wrong answer about his own hat, but the pratiy information he conveys allows everyone else to gseus theirs with absolute certainty. Each begins by expecting to see an odd or even nmbuer of hats of the specified color. If what they count doesn't match, that means their own hat is that cloor. And everytime this happens, the next person in line will switch the parity they expect to see. So that's it, you're free to go. It looks like these ainels will have to go hgnury, or find some less logical organisms to abduct.

Open Cloze

You and nine other individuals have been ________ by _____ ___________ alien overlords. The aliens think humans look quite tasty, but their ____________ forbids ______ ______ logical and cooperative beings. Unfortunately, they're not sure whether you _______, so they decide to give you all a test. Through its universal __________, the alien guarding you _____ you the following: You will be placed in a single-file line ______ forward in size order so that each of you can see everyone lined up ahead of you. You will not be able to look behind you or step out of line. Each of you will have either a black or a white hat on your head assigned randomly, and I won't tell you how many of each color there are. When I say to begin, each of you must guess the color of your hat ________ with the person in the back and moving up the line. And don't even try saying words other than _____ or white or signaling some other way, like intonation or volume; you'll all be eaten immediately. If at least nine of you guess correctly, you'll all be spared. You have five _______ to discuss and come up with a plan, and then I'll line you up, assign your hats, and we'll begin. Can you think of a strategy guaranteed to save everyone? Pause the video now to figure it out for yourself. ______ in: 3 Answer in: 2 Answer in: 1 The key is that the person at the back of the line who can see everyone else's hats can use the words "black" or "white" to communicate some coded information. So what _______ can be ________ to those words that will allow everyone else to deduce their hat colors? It can't be the total number of black or white hats. There are more than two possible values, but what does have two possible values is that number's parity, that is whether it's odd or even. So the solution is to _____ that whoever goes first will, for example, say "black" if he sees an odd number of black hats and "white" if he sees an even number of black hats. Let's see how it would play out if the hats were distributed like this. The tallest captive sees three black hats in front of him, so he says "black," telling everyone else he sees an odd number of black hats. He gets his own hat color _____, but that's okay since you're collectively allowed to have one wrong answer. Prisoner two also sees an odd number of black hats, so she knows hers is _____, and answers correctly. ________ three sees an even number of black hats, so he knows that his must be one of the black hats the first two prisoners saw. Prisoner four hears that and knows that she should be looking for an even number of black hats since one was behind her. But she only sees one, so she deduces that her hat is also black. Prisoners five through nine are each looking for an odd number of black hats, which they see, so they figure out that their hats are white. Now it all comes down to you at the front of the line. If the ninth prisoner saw an odd number of black hats, that can only mean one thing. You'll find that this strategy _____ for any possible ___________ of the hats. The first prisoner has a 50% chance of giving a wrong answer about his own hat, but the ______ information he conveys allows everyone else to _____ theirs with absolute certainty. Each begins by expecting to see an odd or even ______ of hats of the specified color. If what they count doesn't match, that means their own hat is that _____. And everytime this happens, the next person in line will switch the parity they expect to see. So that's it, you're free to go. It looks like these ______ will have to go ______, or find some less logical organisms to abduct.

Solution

  1. hungry
  2. wrong
  3. intelligent
  4. civilization
  5. translator
  6. aliens
  7. facing
  8. guess
  9. answer
  10. captured
  11. super
  12. number
  13. highly
  14. parity
  15. tells
  16. prisoner
  17. eating
  18. white
  19. works
  20. arrangement
  21. color
  22. agree
  23. minutes
  24. starting
  25. qualify
  26. assigned
  27. meaning
  28. black

Original Text

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. Through its universal translator, the alien guarding you tells you the following: You will be placed in a single-file line facing forward in size order so that each of you can see everyone lined up ahead of you. You will not be able to look behind you or step out of line. Each of you will have either a black or a white hat on your head assigned randomly, and I won't tell you how many of each color there are. When I say to begin, each of you must guess the color of your hat starting with the person in the back and moving up the line. And don't even try saying words other than black or white or signaling some other way, like intonation or volume; you'll all be eaten immediately. If at least nine of you guess correctly, you'll all be spared. You have five minutes to discuss and come up with a plan, and then I'll line you up, assign your hats, and we'll begin. Can you think of a strategy guaranteed to save everyone? Pause the video now to figure it out for yourself. Answer in: 3 Answer in: 2 Answer in: 1 The key is that the person at the back of the line who can see everyone else's hats can use the words "black" or "white" to communicate some coded information. So what meaning can be assigned to those words that will allow everyone else to deduce their hat colors? It can't be the total number of black or white hats. There are more than two possible values, but what does have two possible values is that number's parity, that is whether it's odd or even. So the solution is to agree that whoever goes first will, for example, say "black" if he sees an odd number of black hats and "white" if he sees an even number of black hats. Let's see how it would play out if the hats were distributed like this. The tallest captive sees three black hats in front of him, so he says "black," telling everyone else he sees an odd number of black hats. He gets his own hat color wrong, but that's okay since you're collectively allowed to have one wrong answer. Prisoner two also sees an odd number of black hats, so she knows hers is white, and answers correctly. Prisoner three sees an even number of black hats, so he knows that his must be one of the black hats the first two prisoners saw. Prisoner four hears that and knows that she should be looking for an even number of black hats since one was behind her. But she only sees one, so she deduces that her hat is also black. Prisoners five through nine are each looking for an odd number of black hats, which they see, so they figure out that their hats are white. Now it all comes down to you at the front of the line. If the ninth prisoner saw an odd number of black hats, that can only mean one thing. You'll find that this strategy works for any possible arrangement of the hats. The first prisoner has a 50% chance of giving a wrong answer about his own hat, but the parity information he conveys allows everyone else to guess theirs with absolute certainty. Each begins by expecting to see an odd or even number of hats of the specified color. If what they count doesn't match, that means their own hat is that color. And everytime this happens, the next person in line will switch the parity they expect to see. So that's it, you're free to go. It looks like these aliens will have to go hungry, or find some less logical organisms to abduct.

Frequently Occurring Word Combinations

ngrams of length 2

collocation frequency
black hats 6
odd number 5
wrong answer 2

Important Words

  1. abduct
  2. absolute
  3. agree
  4. alien
  5. aliens
  6. allowed
  7. answer
  8. answers
  9. arrangement
  10. assign
  11. assigned
  12. begins
  13. beings
  14. black
  15. captive
  16. captured
  17. certainty
  18. chance
  19. civilization
  20. coded
  21. collectively
  22. color
  23. colors
  24. communicate
  25. conveys
  26. cooperative
  27. correctly
  28. count
  29. decide
  30. deduce
  31. deduces
  32. discuss
  33. distributed
  34. eaten
  35. eating
  36. everytime
  37. expect
  38. expecting
  39. facing
  40. figure
  41. find
  42. forbids
  43. free
  44. front
  45. give
  46. giving
  47. guaranteed
  48. guarding
  49. guess
  50. hat
  51. hats
  52. head
  53. hears
  54. highly
  55. humans
  56. hungry
  57. immediately
  58. individuals
  59. information
  60. intelligent
  61. intonation
  62. key
  63. line
  64. lined
  65. logical
  66. match
  67. meaning
  68. means
  69. minutes
  70. moving
  71. ninth
  72. number
  73. odd
  74. order
  75. organisms
  76. overlords
  77. parity
  78. pause
  79. person
  80. plan
  81. play
  82. prisoner
  83. prisoners
  84. qualify
  85. randomly
  86. save
  87. sees
  88. signaling
  89. size
  90. solution
  91. spared
  92. starting
  93. step
  94. strategy
  95. super
  96. switch
  97. tallest
  98. tasty
  99. telling
  100. tells
  101. test
  102. total
  103. translator
  104. universal
  105. values
  106. video
  107. white
  108. words
  109. works
  110. wrong