In cricket, if a bowler manages to score 3 wickets, in 3 consecutive balls, it is called a hat trick. For baseball fans, imagine if a pitcher could get 3 batters out in a row with consecutive pitches. So anyway, with this third consecutive post about puzzles, I thought I’d include one about hats.
There are 10 prisoners in a jail. The warden comes to them one night and with a wicked grin announces that the next day he is going to play a game with them. All the prisoners will be lined up in a row one after the other. Then the warden will place a black or a white hat on their heads. Each prisoner will be able to see the colour of the hats of all the prisoners in front of him, but not the colour of the hat on his own head or of those behind him.
The warden will then ask the prisoners to tell the colour of the hat on their own head (the prisoners are free to choose the order in which they respond). If at least 9 out of 10 prisoners give the correct answer, he’ll let them all go. Otherwise, he will hang whoever gives the wrong answer. There is no constraint on the number of white or black hats (all may be white or black or 5 of each or 7 black and 3 white or so on).
The prisoners have the night to confer with each other. What strategy should the prisoners adopt?
First, the order of replies. Obviously, nobody knows the colour of the hat worn by the last prisoner in the line. So his answer has to be arbitrary and there is a 50% chance he will be wrong, so he may as well go first. But after that, the remaining 9 have to get their colour correct. So in his answer, the last man must give enough information so that everyone in front of him can answer correctly.
The answer is that the last prisoner should count the number of white hats among the 9 prisoners in front of him. If the number of white hats is odd, he should say white and if it is even, he should say black. The 9th man will answer next by checking the number of white hats in front of him. If the number is odd and the answer the 10th man had given is black then he knows his own hat must be white since the 10th man saw an even number of white hats whereas he sees an odd number. Similarly, if the number of hats he sees in front of him is even and the 10th man had said black, then the 9th prisoner knows that both he and the 10th prisoner see an even number of white hats so his own hat must be black.
The 8th man then counts the number of white hats in front of him and compares against the answers of the 9th and 10th men and so on.
Lets illustrate with an example. Suppose the order is like this:
White, black, black, white, white, white, black, white, white, black
The 10th prisoner (last one in the above row) sees 6 white hats in front of him worn by prisoners 1, 4, 5, 6, 8 and 9, since 6 is even, he says black.
The 9th prisoner sees 5 white hats (an odd number) in front of him worn by prisoners 1, 4, 5, 6 and 8. He also knows that the total number of white hats among the 1st 9 prisoners is even. Since the total is even but he can only see an odd number in front of him, he deduces that he must be wearing white hat and says white.
The 8th prisoner sees 4 white hats (an even number) worn by prisoners 1, 4, 5 and 6. Since the total number of white hats on the 1st 9 prisoners is even (according to prisoner 10) and prisoner 9 is wearing a white hat, then there must be an odd number of hats remaining on the 1st 8 prisoners, but prisoner 8 can only see an even number in front of him. So hea realises he must be wearing a white hat and he calls out white.
Prisoner 7 sees 4 white hats (an even number) worn by prisoners 1, 4, 5 and 6. Now since the total number of white hats on prisoners 1 to 9 was even and prisoners 9 and 8 both have white hats, then the number of white hats remaining must be even. Since the number of white hats he can see are also even, the hat on his own head must be black so he calls out black.
Prisoner 6 sees 3 white hats (an odd number) worn by prisoners 1, 4 and 5. Since there were an even number of hats on prisoners 1 to 9 (as deduced from the 10th prisoner saying black) and prisoners 8 and 9 have already called out white, then there must be an even number of white hats on the prisoners 1 to 6. But prisoner 6 can only see an odd number of white hats in front of him and so he realises his own hat must be white and calls out white.
I hope the reasoning is clear for the remaining prisoners.
This puzzle illustrates a concept called “parity bit” used in computers. As you probably know, on a computer, all data is stored in the form of ones and zeros (binary bits). A parity bit is an extra bit added to the end of a piece of data which is 1 if the number of ones in the data is odd and 0 if it is even. Now, if 1 bit in the data gets corrupted (a 1 becomes a 0 due to physical errors or vice versa), then checking the parity bit can tell us the data is corrupted.
e.g. Suppose our data is 11001100, there are 4 ones in this data so the parity bit will be 0. The data will be stored as 110011000.
If our data is 10101011, then there are 5 ones and the parity bit is 1. The data will be stored as 101010111. Now suppose the 1st bit gets corrupted so we get 001010111, now when it comes the turn of this data to be used, the computer can check that there are 4 data bits that are 1 but the parity bit is also 1 so one of the bits must have got corrupted and the data is unreliable.