wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Guess the hat color in infinite sequence.
        
(Message started by: inexorable on Jan 13^th, 2010, 4:13pm)

Title: Guess the hat color in infinite sequence.
Post by inexorable on Jan 13^th, 2010, 4:13pm

This is a variation of an old puzzle posted in riddles page.

The king has a countable number of wise men. The line starts from the left and is infinite in the right direction. The wise men are all facing to the right and they see the infinite tail of the line. Again, the king places either a black or white hat on each head and they can only say one of two words: black or white. Will they be able to devise a strategy beforehand that ensures that not more than one person makes a mistake?

Title: Re: Guess the hat color in infinite sequence.
Post by Obob on Jan 13^th, 2010, 11:56pm

I think it depends a bit on what you mean by "strategy."

Let X be the set of all countable sequences of B's and W's, and call two such sequences equivalent if they differ in only finitely many places. The wise men agree on a set Y of equivalence class representatives for this equivalence relation (this requires the axiom of choice).

Now for any sequence of hats, there is a unique equivalent sequence in Y; furthermore, every wise man can tell what the equivalent sequence is. For an OK strategy, they can just guess their hats as though the sequence were actually the equivalent sequence. This will only kill finitely many of them.

They can do better, though. Have the first wise man report the parity of the number of differences between the sequence of hats he can see and the expected sequence (thinking of Black and White as 0 and 1). The second wise man can then tell if his hat is different from the expected hat by comparing the parity of the number of differences between the sequence of hats he can see and the parity reported by the first wise man. The third man can then guess his hat, etc.

Analyzing this solution, what we've done is adapted the solution for finitely many wise men (where the first wise man reports the parity of the number of white hats, say) to infinitely many wise men by replacing the initial infinite sequence of hats by a sequence where only finitely many of them are white, say (this is what choosing equivalence class representatives does).

Of course this solution is completely impractical (impossible, even). I very much doubt a strategy exists without the axiom of choice.

Title: Re: Guess the hat color in infinite sequence.
Post by Aryabhatta on Jan 15^th, 2010, 2:12pm

Nice strategy, Obob.

Title: Re: Guess the hat color in infinite sequence.
Post by pscoe2 on Jan 17^th, 2010, 5:34am

What if the person standing behind says the color of the hat of the one standing in front....
this will ensure everyone knowing the exact color of the hat leaving one person even though what they say may not be the color of the hat they are wearing

is knowing the main concern or speaking?

Title: Re: Guess the hat color in infinite sequence.
Post by Obob on Jan 17^th, 2010, 1:16pm

Everyone will know their color, but they will also be answering the question wrong: when they say a color, that is also their answer.

Once the first person has answered, everybody else has to get their hat color correct, so they have no freedom in what they say.

Title: Re: Guess the hat color in infinite sequence.
Post by pscoe2 on Jan 18^th, 2010, 10:52am

If tht is the case...i have another soln(inspired by obobs parity soln)

The first person can count the number of white hats only..if it is odd...he says white..else black...

The second person will count all white hats again...if they are odd...he has a black hat or else a white...every person can keep track in such a way

Title: Re: Guess the hat color in infinite sequence.
Post by Aryabhatta on Jan 18^th, 2010, 11:03am

on 01/18/10 at 10:52:03, pscoe2 wrote:

The count of the white hats could be infinite. Is that odd or even?

Title: Re: Guess the hat color in infinite sequence.
Post by pscoe2 on Jan 18^th, 2010, 12:27pm

I was being a bit practical assuming tht thr a limited number of ppl...but the numbers may be high

Title: Re: Guess the hat color in infinite sequence.
Post by Obob on Jan 18^th, 2010, 12:59pm

The riddle specifically says that there are an infinite number of people.

The riddle is also interesting when there are only finitely many people (albeit quite a bit easier), and in that case the solution you outlined works.

Title: Re: Guess the hat color in infinite sequence.
Post by pscoe2 on Jan 18^th, 2010, 8:29pm

on 01/13/10 at 16:13:37, inexorable wrote:

Seeing these 2 lines...it seems that the question is inconsistent on whether the line is infinite or not. If the number of ppl are countable...so are the number of white hats and thus my solution works...

Can u clear the question please as to whether the number of white hats are countable or not

Title: Re: Guess the hat color in infinite sequence.
Post by Obob on Jan 18^th, 2010, 9:49pm

By "countable" he means "countably infinite." That is, infinite, but infinite in the way that the natural numbers are (you can "count" them), as opposed to infinite in the way that the real numbers are (for example).

http://en.wikipedia.org/wiki/Countable

Title: Re: Guess the hat color in infinite sequence.
Post by Aryabhatta on Feb 14^th, 2010, 11:18pm

A different proof of this (from a friend):

Consider the hat colours are 0 or 1, so we get an infinite bit string.

Consider the infinite dimensional hypercube (two infinite bit strings are connected if they differ in exactly one bit).

By the http://en.wikipedia.org/wiki/De_Bruijn%E2%80%93Erd%C5%91s_theorem, we can easily show that this hypercube is 2-colourable, using the fact that any n-hypercube is 2-colourable.

Thus the wise men decide upon afunction f: {0,1}^N -> {0,1} which gives a colouring of the oo-hypercube.

The first person considers the infinite bitstring starting from the 2nd (say x) and calls out f(x).

This allows each subsequent person to guess their hat colours correctly.

Title: Re: Guess the hat color in infinite sequence.
Post by Obob on Feb 15^th, 2010, 10:25am

An interesting way of thinking about it, but it all boils down to the same thing: the axiom of choice.

On the other hand, it is easy to see that the solution I posted constructs a 2-coloring of the infinite hypercube: an infinite sequence is white, say, if and only if the chosen sequence it differs from in only finitely many places has an even number of differences.

Title: Re: Guess the hat color in infinite sequence.
Post by Obob on Feb 18^th, 2010, 8:28pm

It is interesting to note, however, that if you have ANY strategy, it will provide a coloring of the infinite hypercube. If two sequences differ in only one place, the first person HAS to say two different things for those two sequences, no matter what the strategy is. Otherwise the person whose color is different can't perceive any difference, and will make a mistake for one of the two sequences.

So having a winning strategy is entirely equivalent to selecting a 2-coloring of the hypercube. There are no other winning strategies.

We know 2-colorings of the infinite hypercube exist if we assume the axiom of choice; on the other hand, it would not surprise me in the least if the hypothesis that there is no 2-coloring of the hypercube were consistent with set theory without the axiom of choice.