Futility Closet's "Hat Check"

The Game Room
1

From here

I don’t understand the answer given, at all. I’m going to paraphrase in it the spoiler box below, since I’m a little unwilling to just copy his entire blog here.

The answer is 99 - only the first person guesses wrong. Apparently, the discussed strategy is to count how many red hats are in front of you at the start. If it’s even, think ‘blue’, if odd, think ‘red’, and then change your answer every time you hear ‘Red’ guessed behind you.

How does this work? Does it work? I can’t get it to.

2

Here’s the intuition behind it.
Let’s say that before the people started guessing, a 101th person came by and made an announcement. He says “The total number of red hats is even”.

Now, with that extra knowledge, how many people would guess correctly? I think you would agree that the answer is everybody. It makes sense, right? The 100th person has to guess first. He knows that all 100 people together have an even number of red hats, and he can count how many of the front 99 people in line have red hats, so he can deduce whether he has a red hat. For the 99th person, he has a similar task. He can count how many of the first 98 people have red hats, and by listening to the 100th person’s guess, he’ll know whether the 100th person has a red hat.

More generally, for any arbitrary person in line, through a combination of looking at the people in front of him and hearing the (correct) guesses of the people behind him, he knows the hat color of every person in line except himself. Combined with the knowledge that the total number of red hats is even, he also knows his own hat color.

The solution you quoted was just a compact way of implementing what I just described. For an arbitrary person in line, he reasons as follows:
I know there are an even number of red hats. I’m going to assume (for now) that everybody behind me in line has a blue hat.
Now, how many red hats do I see in front of me?

  • If it’s odd, then I too must have a red hat to make the total even, so I’m going to think “red”.
  • If it’s even, then I must have a blue hat to keep the total even, so I’m going to think “blue”.
    The people behind me in line are now starting to announce their hat colors. What color did I just hear announced?
  • If it’s blue, then that’s consistant with my initial assumption that everyone behind me was wearing blue. That’s good.
  • If it’s red, that’s inconsistant with my initial assumption. So I’m going to change the color I’m thinking so that the overall parity is maintained.

In English, every person on line is going through that computation described earlier - you count the number of red hats you can see, you count the number of times you hear “red”, and you deduce your own color as whatever is needed so the overall total comes out even. Easy, right?

Wait. We’ve forgotten something. There is no 101st person. Nobody ever came in and announced that the total number of hats is even. So there goes all our reasoning. That sucks, right? Well, actually it only sucks for the 100th person in line. And then only half the time. If it turns out that there really are an even number of red hats, then it works out for everybody, and everybody guesses right. But what if there are an odd number of red hats? Then the 100th guy will end up guessing wrong. But everybody else will still guess right. Why? Because they’re all operating under the mistaken impression that there’s an even number of red hats, when really there’s an odd number. But they’re ALSO operating under the mistaken impression of what color the 100th guy’s hat is, because the 100th guy ended up guessing wrong. And those two mistakes perfectly cancel each other out. Everybody’s count of the total number of red hats will be off by 1, but that’s perfect, because they all thought there were an even number of red hats and really there were an odd number.

Ok? Some followup questions for homework:
True or false: If the 56th person in line messes up his count and says the wrong thing, that will make all 55 people in front of him end up guessing wrong.
True or false: If there are three hat colors, red, blue and white, it’s still possible to guarantee that 99 will guess right.

3

It doesn’t say that the number of red and blue hats would be the same.
There could be 57 red hats and 43 blue ones.

4

Let’s say, for example, that all of the hats are blue, except that of the second person from the back - the second person to guess. Her hat is red.

She counts in front of her - she sees no red hats, 0, which is even. She is thinking, therefore, that the hat on her head is blue.

The person behind her guesses - the one genuine guess. And… that’s where I’ve gone wrong, because he doesn’t guess, he counts the hats in front of him, sees an odd number, and says “Red”, regardless of what colour hat he has, which switches the second person’s thinking from Blue to Red. She then says Red - correctly - and her saying Red switches everyone else back to Blue, all the way down the line.

Zebra: It isn’t stated that they are 50/50 and if it was, the puzzle would be trivial - the person at the back could count all the hats and state which there was 49 of.