Simple City

Yesterday I heard a great talk by Robert Lubarsky, which provided a delightfully easy route into fairly deep logical waters. He was talking about joint work of his with Stefan Geschke.

This is the first of two two posts about it, each based around a puzzle. So let’s get going with the first, which is something of a classic. The second is altogether trickier, indeed a complete answer seems to be as yet unknown…

Here’s the first puzzle: ten (or a hundred or any number) people stand in a line, one in front of the other. Each is wearing either a black or a white hat. If you’re in the queue, you don’t know your own hat-colour, or those of the the people behind you. But you can see the ones in front. Starting from the back of the line, the challenge is for each person to call out in turn, trying to guess the colour of their own hat. They are allowed to discuss strategy beforehand. So what plan can they hatch to maximise the number of right answers?

Here is one possibility: the first person says the colour of the hat directly in front of him. So the second knows her hat colour, which she calls out. The third person then does the same favour for the fourth, and so on. This way, the team are guaranteed to get half the hats right. (We only care about guaranteed correct answers in this game, not lucky guesses.) In fact, there is a much better strategy. If you don’t know the answer, have a think about it now. The solution is on the other side of this picture.

Here’s an answer: the person at the back counts the number of black hats in front of him. If that’s an odd number, he says “black”. If it’s even, he calls “white”. Now, the next person can see all the same hats the first could see, except her own. Say she sees 5 black hats, and hears “black”. Can her own hat be black too? No, because otherwise that would make 6 black hats in front of the first person, an even number. So she knows her own hat must be white. Similarly, if she hears “white” then she knows that her own hat must be black. All the people in front can work out their own hat in the same way, by combining what they can see with what the people behind have said.

Now, this strategy allows everyone to discover their own hat colour, except for first the very first person. It is easy to see this is the best that can be done: no-one can see the first hat, so any tactic the team try will be immune to a change in its colour. To avoid this exception, in the next post we’ll assume the person at the head of the queue is hatless.

To set things up for the next post, I’ll write this another way, using “1” to represent black and “0” for white. So the sequence of hats might read 0010001111. The first person sees the whole sequence, adds up all the digits to get 5, and says “1”. (This is the total modulo 2, if you like.). The second person sees 010001111, and so on, with everyone seeing the same binary sequence, but with the beginning chopped off in different places.

I hope you agree that this hat game is a fun puzzle, with a neat answer. Its solution uses what computer scientists call a parity bit, a technique used to guard against data becoming corrupted.

In the next post things will become a little more serious, when we allow the queue of hat-wearers to grow infinitely long. In this new version, we have to assume that the hatters have various superpowers: they can see infinitely far in front of them, for example. It is obvious that the same tactic will not work in this setting, since everyone is likely to see infinitely many black hats in front of them (and of course it makes no sense to ask whether ‘infinity’ is odd or even). So what is the optimal result here, and what strategy will produce it? And, critically, what further superpowers do the people need to enact it?

Update: the second post is here.