12.1. Parity and an Error Detecting Riddle#
Imagine there are 108 mathematicians standing in a line. Each is wearing a black hat or a white hat. The distribution of hats is completely random and magical, so no mathematician can see the color of their own hat but can see the colors of the hats of all the mathematicians in front of them. Each mathematician, starting from the back of the line, is given the opportunity to guess their color hat. For each person that guesses correctly, each mathematician wins a dollar. If each mathematician simply guesses randomly, on average, they will each earn $54. So about 1 in every two mathematicians guess correctly. Is there a better way? Can you think of a strategy they might employ?
Strategy 1:#
Suppose we assign a number to Each mathematician starting from the back. Every mathematician with an odd number shouts out the color of the hat of the mathematician in front of them. Now, every even numbered mathematician knows exactly what color hat she has on and will guess correctly. On average, how much will each mathematician win? Every other person is guaranteed to guess correctly. Additionally, of the remaining people, about half on average will guess correctly because it will just so happen that their hats are the same color as the hats of the people directly in front of them. Now, each mathematician will earn, on average, $81 in this very weird contest.
Strategy 2:#
Each mathematician examines the hats of the two mathematicians standing directly in front of him. There are four possibilities:
He sees two white hats.
He sees two black hats.
He sees one white hat directly in front of him and one black hat further on.
He sees one black hat directly in front of him and one white hat further on.
Imagine that the mathematicians have decided ahead of time that in each group of three, the mathematician in the back will call out “White!” if the hats are either both black, or both white. He will call out “Black!” if the hats are different colors. Can the other two mathematicians in the group of three correctly deduce their color?
Yes! If the mathematician in the middle of each group of three hears the mathematician behind her yell “White!” then she knows her hat matches the one of the mathematician in front of her. If she sees a white hat, she calls out “White!” if she sees a black hat, she shouts “Black!” Then the mathematician in front of her also heard the one in the back yell out “white” so they know their hat is a match for the one behind them. Whatever she calls out they also call out and both guess correctly.
But what if the hats don’t match? Our middle mathematician knows this if the mathematician behind her calls out “Black!” She can see the hat in front of her so she simply calls out the opposite color. Likewise, the mathematician in front of her hears the one in the back call out “Black!” They know their hat is not a match for the one behind them so whatever the mathematician behind them calls out, they call out the opposite color. Of each group of three, only one is truly guessing. Therefore, their winnings will be, on average, $90.
Strategy 3:#
Believe it or not, there is a strategy that allows all the mathematicians except the one in the very back of the line to guess correctly and guarantee that each mathematician will win at least $107. Can you guess what it is? This strategy is described at the end of the chapter.