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

00:10you 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

00:37will 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

01:03guess 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

01:28assign your hats iot again can you think of a strategy guaranteed to save everyone 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

01:55assigned 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

02:21sees 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

02:47answer prisoner 2 also sees an odd number of black hats so she knows hers is white and answers correctly prisoner 3 sees an even number of black hats so he knows that his must must be one of the black hats the first two prisoners saw prisoner 4 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

03:13that her hat is also black prisoners 5 through n 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

03:39first prisoner has a 50% chance of giving a wrong answer about his own hat but the parody 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 every time this happens the next person in

04:05line will switch the parody 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