The prisoners' hats

30 prisoners are informed that they are going to be placed in a row and they are going to put a hat on the head of each one, white or black, without specifying how many caps they will wear in each color. Each prisoner will only see the hats of the prisoners in front of him but not his or the ones behind.

A guard will ask each of the prisoners successively starting at the last of the row (who sees all but his) until the first (who does not see any) of what color is his hat. Inmates can only answer black or white: if they succeed they are released and if not, they are executed. All prisoners can hear the answers before theirs. The prisoners can not beckon, or touch the others, or give clues with the tone or volume of voice ... they must answer black or white in the most aseptic way possible because if the jailers detected any trick of those mentioned, they would kill everyone.

Before carrying out this, prisoners, who know the test they are going to be subjected to but not naturally what color their hats will be, have time to talk to each other and think about a group strategy.

Can you think of any strategy to save as many prisoners as possible?

Solution

It is possible to safely save everyone but the last in line who will have a 50% chance of saving.

The strategy followed by the prisoners consists in "codifying" the parity of one of the two colors of hats in the row. So, for example, they can agree that the last one in the row (who will be the first to say the color of their hat and cannot know what it will be) will say “white” if the total number of white hats you see is even or say “black ”If the total number of white hats you see is odd.

Imagine the first one sees 25 white caps, which is an odd number. He doesn't know what color his is, so he can't be sure what he has to say to save himself but since the amount of white hats he sees is odd and he has reached an agreement with his teammates, he says "black."

The second, as he has heard "black", knows that the total white caps that the first has seen is odd, so he counts them and if he sees an even amount, his cap is white and if it is odd, his cap is black . So he says it.

The third party knows that, originally, the quantity is odd (because the first information is that the color is black, otherwise it would be even). If the one before him has said white, counting his, there must be an even amount, and if he has said black, odd. By studying the parity of those he sees, he can know what color his is. Black, if the information you calculate matches what you see, white otherwise.

In short, the information that the first transmits is the parity of the number of targets he sees (black is odd, white is even). Each one must change the parity from odd to even each time one of the prisoners he speaks says "white," and count the ones he sees. If the parity he calculates matches the information he is given, his hat is black, and if it does not match, it is white.

There is no better system, since there is no way for the former to know the color of his hat, so he will have a 50% chance of failing, follow the strategy that is followed.