4 hours ago
1
Earlier today I set you the following logic problem, as a retrospective commemoration of World Logic Day. Here it is again with the solution – and a comment about how it relates to the real world.
Queue eye
1. Ten logicians are put in a line, all facing in the same direction. A red or green hat is put on each of their heads. The logicians do not know which colour is on their heads, nor the colour of the hats of the people behind them in the line. Each logician can look only forwards, and so only knows the hat colour of the person or people in front them.
One by one, each logician says aloud either the word ‘red’ or the word ‘green’. Every logician says one of these words, and no logician speaks twice.
Can you think of a strategy – which the logicians will have agreed on before the line up – that results in at least nine of them saying the colour word that correctly describes the hat on their head?
There are no mirrors or reflective materials. The knowledge about their own hat colour is deduced entirely from what they can see and what is said.
2. The same set up as before, but now there are three hat colours: red, green and yellow.
Can you think of a strategy in which each logician says a single word, now either ‘red’, ‘green’ or ‘yellow’, and results in at least nine of them saying the correct colours of their own hats.
Solution
1. Here is a strategy that works. The first person to speak is the person at the back of the line. Second is the person directly in front of them, and so on until the person in the front of the line is the last person to speak. The person at the back of the line may or may not say the correct colour of their hat, but everyone else will.
The person at the back, who sees everyone’s hat bar their own says ‘red’ if they see an even number of red hats and ‘green’ if they see an odd number of red hats.
The next person can deduce their hat colour by looking at the number of red hats in front of them. Suppose the person at the back said ‘red’, and they see an even number of red hats, they know their hat cannot be red, because if it was they would see an odd number of red hats (the number seen by the person last in line minus one). So they say ‘green’. On the other hand, if they see an odd number of red hats, they will say ‘red’.
The person third in line does the same thing. They look to see how many red hats they can see. If the first person said ‘red’ and the ‘second’ said ‘green’ and they see an even number of red, they know they have ‘green’, and if they see an odd number they know they have a red hat. And on it goes. Each person deduces he colour of their hat by looking at whether there are an odd or even number of red hats in front of them, and comparing that to the knowledge imparted by the person behind them in the line.
2. The same strategy, but rather than looking at odds/even, we are looking at remainders when divided by 3. (The technical term is numbers modulo 3)
Let ‘red’ = 0, ‘green’ = 1 and ‘yellow’ = 2.
The person at the back of the line will look at the hats in front of him and using the code above, tot up the numbers for the hat colours. So, if they see three red, three green and three yellow, they would count 0 + 3+ 6 = 9. Then they divide that number by 3. If there is a remainder of 0, they say ‘red’, a remainder of 1 they say ‘green’ and a remainder of 2 they say ‘yellow’.
The next person in line adds up the numbers of the hats they see according to the code, and calculates the remainder when divided by 3. If the remainder is the same as the remainder announced by the person preceding them, then they have a red hat. (Because their hat added 0 to the hat count). If the remainder is one less than the colour said aloud by the person preceding them, they have a green hat, and if it is two less, they have a yellow hat.
Repeat the same procedure as you move through the line.
This type of thinking is used in certain ‘error-correcting codes’, technology that is robust to errors. Suppose each person in the line is a computer, and the hat a piece of data in that computer. If any computer loses their data (i.e. can no longer see its own hat), it is possible to reconstruct the data based on the data in the other computers.
I hope you enjoyed the puzzle – I’ll be back in two weeks.
Thanks to Deniz Sarikaya, of the Vrije Universiteit Brussel and Universität zu Lübeck, who is coordinator of World Logic Day.
I’ve been setting a puzzle here on alternate Mondays since 2015. I’m always on the look-out for great puzzles. If you would like to suggest one, email me.
