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

39. An executioner lines up 100 prisoners single file and puts a red or a blue hat on each prisoner's head. Every prisoner can see the hats of the people in front of him in the line - but not his own hat, nor those of anyone behind him. The executioner starts at the end (back) and asks the last prisoner the colour of his hat. He must answer "red" or "blue." If he answers correctly, he is allowed to live. If he gives the wrong answer, he is killed instantly and silently. (While everyone hears the answer, no one knows whether an answer was right.) On the night before the line-up, the prisoners confer on strategy to help them. What should they do?

This puzzle appears in a book called 'Are You Smart Enough to Work at Google?' Quite incredibly in February 2016 it seems to have been solved by Google's own Artificial Intelligence program.

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:

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.

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.

## 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.© Nigel Coldwell 2004 - – The

**questions**on this site may be reproduced without further permission, I do not claim copyright over them. The

**answers**are mine and may not be reproduced without my expressed prior consent. Please enquire using the link at the top of the page.

__PayPal__

I always think it's arrogant to add a donate button, but it has been requested. If I help you get a job though, you could buy me a pint! - nigel