Posted by: yanzhang | September 10, 2008

M-2 (maybe M-3) – People and Hats

Today we have a M-2… but it feels more like a M-3 or M-4. I’ll explain after the two problems.

The first problem is fairly classical. It appears in many texts, and was first brought to my attention by Chris Evans:

N people stand in line, all facing right, where each person can only see the people in front. They each get a hat (red or blue), and in order (from left to right), they are asked to guess the color of their own hat. Find a strategy to maximize the number of people who guess their hat colors correctly. Note that the strategy can depend on what people further right hear from the guesses of people further left.

Solution:

The funny thing about this problem is that you can ask it as a stronger statement (“find a strategy so that N-1 people guess their hat color correctly”), which makes the problem a lot easier =) This is why I ask the problem in the above form.

Now that I’ve said that, you may want to take a moment to try to do it again.

Give up? Do this: Think of a red hat as a 0 and a blue hat as a 1. The first person guesses the color corresponding to the sum of everyone else (mod 2). Note that this gives each person after him enough information; the second person can just subtract off what he sees from what the first person says. The third person, after hearing the second person’s guess, knows the sum of all hats after and including the third, so he can just subtract off what he sees to get his own hat. This gets at least N-1 right, and half of the times gets all N right. Note we can’t possibly do anything better since the first person can only ever get his own hat right with probability 1/2.

I heard the second problem recently from Nick Rosenbloom and Dustin Clausen:

Countably infinite people stand in line, all facing right… the rest of the setup is the same. Find a strategy to maximize the cardinality of people who guess their hat colors correctly.

Sketch:

The awesome thing about this problem is there is also a way to ask this problem that hints at the answer. What is slightly different about this formulation of asking the problem is that it sounds like a strictly harder problem has been asked: one can restrict the problem so that the strategy cannot rely on hearing what people left of each person answers.

This looks kind of impossible, which is perfect for things like the Axiom of choice (or equivalently, Zorn’s Lemma). Consider all countably infinite binary strings and divide them up into equivalence classes, where two strings A and B are equivalent if they share a truncation (i.e. the bits after the k_th bit of A are equal to the bits after the l_th bit of B). Note it takes a bit of work to show that this is an equivalence class, which I’ll leave as an exercise. You might want to do the case of the string being periodic after a certain point differently from the case where it is not.

Now, just pick a representative from each equivalence class. I leave it as another exercise to see that you are done =) It basically involves each person to try to fit himself into a string which has the same equivalence class at what he sees. The earliest people may get this wrong, but the later people (once you get to the common truncation) will get them all right. So you get all but finitely many guesses correct.

I think the coolest thing about this set of problems is the way you can rephrase each one and still ask the problem at the same strength. Note this becomes a M-3 if there was a solution to the second problem that breaks the restriction given at the beginning of the proof. So if any of you have ideas, let me know!

-Y

Source: Chris Evans, Nick Rosenbloom, Dustin Clausen

Advertisements

Responses

  1. My favorite related problem supposes that there are some number of people (finite, countably infinite, uncountably infinite, whatever) in a room, with red/blue hats as usual, but now all of them can see everyone else’s hats. They have previously agreed on a strategy, but now must all simultaneously guess their own hat color.

    Prove that they it is possible to choose a strategy so that they will either all be right or all be wrong.

    (They must all guess “red” or “blue”. So all of them saying “green” is not what I mean … PS pardon my grammar.)

  2. Thanks for the post, Yan. This is the most intense thing I’ve read in a month.

  3. In the infinite hats problem, you can guarantee that all but the first person survives if everyone is allowed to hear earlier guesses. Divide into equivalence classes and pick representatives by the Axiom of Choice as before. The first person says “red” if the hats he sees differ from the standard representative by an odd number of hats, and says blue otherwise. Then everyone proceeds as in the finite version.

    (I first learned this from Melanie Wood, but I think it’s been discovered many times.)


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: