The riddle of prisoners and gods hair It is a famous logical puzzle, also known for being used by Google in the staff selection interviews. The goal of this test was to evaluate the logical thought of the candidates and understand who among them was able to think out from schemes. There are different variations, but in all there are prisoners condemned to death, hats whose color and potential strategy is unknown to be able to save themselves.
In this article we see the version with Ten prisonersand only five minutes to process a plan.
The riddle of the ten prisoners and hats
Ten prisoners they were locked up in a prison, waiting to be sentenced to death. Suddenly, the jailer offers them a chance of salvation by proposing a challenge: he tells them that between five minutes will be put
In Indian row, ordered for height and addressed forward. Anyone who tries to turn around or to get out of the row will be executed on the spot. Everyone will be put in the lead a hat, white or black, chosen randomly. It will not be possible to know how many hats are of each color, nor of what color your hat is.
When the jailer will start, each one will have to guess the color of your hatstarting from the person at the bottom of the row, the highest one, and proceeding in order up to the lowest. Those who guess their color will be freed. Those who make mistakes will be condemned.
He also says that they will only be able to pronounce the word “white” or “black”without adding anything and without using strange intonations or other signals. Any attempt to communicate in another way will lead to the immediate execution of all. The jailer grants 5 minutes to prisoners to discuss freely and try to elaborate a strategy. How will they save the greatest number of prisoners?
The solution to the abundance of hats and prisoners
The fate of the prisoners is in the hands of the highest personthe one at the bottom of the row. It is the only one who can see the hats of the other nine and, therefore, has the Most information. If he could simply say how many black hats and how many whites he sees, the problem would be easily solved. But it can only pronounce a word: “white” or “black”.
Prisoners then come a brilliant idea:
If the person at the bottom of the row sees in front of him a even number Of black hatswill have to say “black“; If you see a odd number Of black hatswill have to say “white“.
Thanks to this strategy, at least 9 out of 10 prisoners will be able to save themselves. Let’s see why.
If the prisoners are distributed as in the image, the first to speak, which we call Andrea, see in front of him Five black hats. Since five is a number shotssays “white“Aloud, according to the agreed strategy. The color of their hat is wrong, but now everyone knows that the black hats in front of him are in odd numbers.
Now it’s up to Beatricethe second of the row. To understand what color his hat is, Beatrice thinks like this:
Andrea saw an odd number of black hats. If I see them too shotsmeans that I am seeing the same black hats that he saw him and therefore mine must be white. If, however, I see them evenmeans that one of the black hats that Andrea has seen must be on my head. In that case, my hat is black.
In front of him Beatrice sees four black hats, that is, an equal number. He therefore knows that his hat is black, says it aloud and saves.
Now, all prisoners know that The remaining black hats must be equal.
An almost perfect strategy
He then touches in Cecilia, the third of the rowwhich in front of it sees an equal number of black hats, that is four. This means that Cecilia and Beatrice see exactly the same number of black hats, and therefore Cecilia has a white hat in its head. He then declares “white” and she is saved too.
Each prisoner continues following the same type of reasoning: part expecting to see an equal (or odd) number of black hats, if the number that matters is actually equal (or odd), it means that your hat is white. If, on the other hand, it does not correspond, then it is black.
The prisoners continue in this way until they reach the last two of the row, Laura and Marco, who took the account of all the traces between peers and odd and know that Ilaria, the third last, saw an odd number of black hats. Since Marco has a white hat, Laura tells everyone that her hat is black. Thus Marco understands that there are no more black hats. He tells the jailer that his hat is white and he too manages to save himself.
This strategy is the best possible And it works even if we increase the number of prisoners. There first person who speaks has the 50% Of possibility Of err The color of one’s hat, but thanks to the information he gives with his answer, everyone The others prisoners succeed in save.
