Answer to Puzzle #39: 100 Prisoners in a Line, Red & Blue Hats and the Executioner

Before reading the answer can I interest you in a clue?

It would appear I am not smart enough to work at Google. Because I couldn't see it. I had considered the prisoners splitting off in to pairs and agreeing that the back one would call out the colour the front one was wearing. Giving us an expected survival rate of 75%. But we can do much better...

The person at the back, lets call him person number 1, will agree that if he sees an odd number of red hats he calls out red, if he sees an even number of red hats he calls out blue. (Obviously any similar scheme would work, but we will use this one.) Unfortunately this means he has a 50% chance of survival but it guarantees everyone else's.

Consider an example of just 5 people below:

• Person 1 - Follows the only rule 'if the first person sees an odd number of red hats he calls out red, if he sees an even number of red hats he calls out blue.' he calls out blue because he sees an even number of red hats and dies.
• Person 2 - Knows that including himself there are an even number of red hats. He looks forward and can also see an even number of red hats. This means he is wearing a blue hat. Had he been wearing a red hat then the person behind him would have seen 3, an odd number, which he knows not to be the case.
• Person 3 - Knows that to start there were an even number of red hats. He knows that non of them have gone, that is to say nobody other than possibly the first person has declared themselves to be wearing a red hat, so including himself there are an even number of red hats. He looks forward and can see one red hat, an odd number. That this has changed between him and the people in front of him means he is wearing a red hat.
• Person 4 - Knows that to start there were an even number of red hats. He knows one has gone. So including himself there is an odd number of red hats. He looks forward and can zero (an even number,) of red hats. That this has changed between including and excluding him means he is wearing a red hat.
• Person 5 - Knows that to start there were an even number of red hats. He knows that two have gone. So including himself there is an even number of red hats. He looks forward and can zero (an even number,) of red hats. That this has not changed between including and excluding him means he is wearing a blue hat.
  
  
• Generally - someone knows whether the group of n-1 people started with an odd or an even number of red hats. And they know the number of red hats that have gone before them. If the number of red hats that have gone before them is even then the number of red hats including them and those forward of them will be as indicated by the first person, if it is odd it will be opposite. Knowing the odd or even nature of the of the number of red hats including them and the group in front of them they can observe the group in front of them, and if they are not the same it must be changed by the hat they are wearing.

So all but the first person survives. And he would have survived had he been wearing a blue hat. This gives us an expected survival rate of 99.5% for 100 people; or (n - ½)/n in the general case.

A Larger Group

We can now try a more formulated response to a larger group.

Person	Odd/Even to Start	Reds Gone Before	Even Including	Reds In Front	Even Excluding	Changed	Says	Lives
1				5	✗		red	✓
2	odd	0	✗	5	✗	✗	blue	✓
3	odd	0	✗	4	✓	✓	red	✓
4	odd	1	✓	3	✗	✓	red	✓
5	odd	2	✗	2	✓	✓	red	✓
6	odd	3	✓	2	✓	✗	blue	✓
7	odd	3	✓	1	✗	✓	red	✓
8	odd	4	✗	0	✓	✓	red	✓
9	odd	5	✓	0	✓	✗	blue	✓
10	odd	5	✓	0	✓	✗	blue	✓

The first person, #1, does his duty declaring red, having see an odd number of reds in front of him. In this case he survives.

For each of the other people the procedure is the same. They know that the red count for the group 2 to 10 is odd. They use the number of reds that have gone before them to determine if the red count for them to 10 is odd or even. They count the reds in front of them. Comparing the odd or even nature of the two they are able to determine if they are wearing a red hat.

More Colours

How would you approach this problem if there were three colours of hats, or more? Without setting out an explicit procedure the rough idea is not that complicated. Using one person at the back, with their sacrifice, allows us to convey one bit forward. If we engage more people at the back we could convey more information.



Bard was citing this very site so naturally it's answer was mostly right.

If you're curious what Bard made of this puzzle...

Show/Hide Google's Bard AI's Answer

If you're curious what ChatGPT made of this puzzle...

Show/Hide ChatGPT's Answer