Author |
Topic: Guess the hat color in infinite sequence. (Read 4353 times) |
|
inexorable
Full Member
Posts: 211
|
 |
Guess the hat color in infinite sequence.
« on: Jan 13th, 2010, 4:13pm » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
Obob
Senior Riddler
Gender: 
Posts: 489
|
|
Re: Guess the hat color in infinite sequence.
« Reply #1 on: Jan 13th, 2010, 11:56pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Guess the hat color in infinite sequence.
« Reply #2 on: Jan 15th, 2010, 2:12pm » |
Quote Modify
|
Nice strategy, Obob.
|
|
IP Logged |
|
|
|
pscoe2
Junior Member
Gender:
Posts: 77
|
|
Re: Guess the hat color in infinite sequence.
« Reply #3 on: Jan 17th, 2010, 5:34am » |
Quote Modify
|
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?
|
| « Last Edit: Jan 18th, 2010, 10:42am by pscoe2 » |
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Guess the hat color in infinite sequence.
« Reply #4 on: Jan 17th, 2010, 1:16pm » |
Quote Modify
|
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.
|
| « Last Edit: Jan 17th, 2010, 1:22pm by Obob » |
IP Logged |
|
|
|
pscoe2
Junior Member
Gender:
Posts: 77
|
|
Re: Guess the hat color in infinite sequence.
« Reply #5 on: Jan 18th, 2010, 10:52am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Guess the hat color in infinite sequence.
« Reply #6 on: Jan 18th, 2010, 11:03am » |
Quote Modify
|
on Jan 18th, 2010, 10:52am, pscoe2 wrote: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 |
|
The count of the white hats could be infinite. Is that odd or even?
|
|
IP Logged |
|
|
|
pscoe2
Junior Member
Gender:
Posts: 77
|
|
Re: Guess the hat color in infinite sequence.
« Reply #7 on: Jan 18th, 2010, 12:27pm » |
Quote Modify
|
I was being a bit practical assuming tht thr a limited number of ppl...but the numbers may be high
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Guess the hat color in infinite sequence.
« Reply #8 on: Jan 18th, 2010, 12:59pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
pscoe2
Junior Member
Gender:
Posts: 77
|
|
Re: Guess the hat color in infinite sequence.
« Reply #9 on: Jan 18th, 2010, 8:29pm » |
Quote Modify
|
on Jan 13th, 2010, 4:13pm, inexorable wrote: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. |
|
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
|
| « Last Edit: Jan 18th, 2010, 8:43pm by pscoe2 » |
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Guess the hat color in infinite sequence.
« Reply #10 on: Jan 18th, 2010, 9:49pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Guess the hat color in infinite sequence.
« Reply #11 on: Feb 14th, 2010, 11:18pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Guess the hat color in infinite sequence.
« Reply #12 on: Feb 15th, 2010, 10:25am » |
Quote Modify
|
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.
|
| « Last Edit: Feb 15th, 2010, 10:31am by Obob » |
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Guess the hat color in infinite sequence.
« Reply #13 on: Feb 18th, 2010, 8:28pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print