The Hat Problem
Ramon Kiley
http://dailynews.yahoo.com/h/nyt/20010409/tc/why_mathematicians_now_care_about_their_hat_color_1.html
You might want to work on the problem first and then go to the web site to
read the rest. Considering how popular the article says the puzzle is now,
I don't understand why I haven't seen it mentioned here yet. Maybe it was
already posted and I missed it.
--------------------------------------------------------------
The hat problem goes like this:
Three players enter a room and a red or blue hat is placed on each person's
head. The color of each hat is determined by a coin toss, with the outcome
of one coin toss having no effect on the others. Each person can see the
other players' hats but not his own.
No communication of any sort is allowed, except for an initial strategy
session before the game begins. Once they have had a chance to look at the
other hats, the players must simultaneously guess the color of their own
hats or pass. The group shares a hypothetical $3 million prize if at least
one player guesses correctly and no players guess incorrectly.
The same game can be played with any number of players. The general problem
is to find a strategy for the group that maximizes its chances of winning
the prize.
One obvious strategy for the players, for instance, would be for one player
to always guess "red" while the other players pass. This would give the
group a 50 percent chance of winning the prize. Can the group do better?
--------------------------------------------------------------
--
"Ramon Kiley" is actually 78039 46251 <78039...@GoFor21.com>.
01234 56789 <-Use this key to decode my email address and name.
Patrick Hamlyn
>
>One obvious strategy for the players, for instance, would be for one player
>to always guess "red" while the other players pass. This would give the
>group a 50 percent chance of winning the prize. Can the group do better?
Since the colours are independant, then without cheating this would seem to be
the best you can do. If more than one person quesses you would be reducing your
chances of winning, and no information can be gleaned from the other hat
colours.
Adam Stephanides
ramon...@GoFor21.com wrote on 4/11/01 7:43 PM:
Partial spoiler after original puzzle
> The hat problem goes like this:
>
> Three players enter a room and a red or blue hat is placed on each person's
> head. The color of each hat is determined by a coin toss, with the outcome
> of one coin toss having no effect on the others. Each person can see the
> other players' hats but not his own.
>
> No communication of any sort is allowed, except for an initial strategy
> session before the game begins. Once they have had a chance to look at the
> other hats, the players must simultaneously guess the color of their own
> hats or pass. The group shares a hypothetical $3 million prize if at least
> one player guesses correctly and no players guess incorrectly.
>
> The same game can be played with any number of players. The general problem
> is to find a strategy for the group that maximizes its chances of winning
> the prize.
>
> One obvious strategy for the players, for instance, would be for one player
> to always guess "red" while the other players pass. This would give the
> group a 50 percent chance of winning the prize. Can the group do better?
>
> --------------------------------------------------------------
Yes. A group of three (and hence any larger group) can win the prize 3/4 of
the time.
Label the players A, B, and C. If A sees that the hats of the other two are
the same color, she guesses that color; otherwise she passes. If B sees
that A and C have hats of different colors, she guesses the color of A's
hat; otherwise she passes. If C sees that A and B have hats of different
colors, she guesses the color of A's hat; otherwise she passes. This wins
the prize unless A's hat is red and B's and C's are blue, or vice versa.
This is clearly the maximum for three players: for the group to win at least
3/4 of the time, there must be at least one player who guesses right at
least 1/4 of the time, and that player must also guess wrong at least 1/4 of
the time.
--Adam
P. S. I've changed the subject heading because it's a neat puzzle, but a
lot of people won't look at it because they'll think it's the old chestnut
that's been brought up here again and again.
Charles Bryant
As the article indicates, this is a difficult problem. Here's the
answer:
They can win the prize six times out of eight. There are two
strategies. Let the players be named Fred, Jim, and Sheila.
In the first strategy, they all apply the same rule: if someone sees
two hats the same colour, they guess the opposite colour. Otherwise
they pass. The possibilities are:
hats guess
F J S F J S result
----- ----- ------
r r r b b b lose - all wrong
r r b - - b win
r b r - b - win
r b b r - - win
b r r b - - win
b r b - r - win
b b r - - r win
b b b r r r lose - all wrong
There is another, asymmetric, solution. In this case, if Sheila sees
two hats the same, she guess that colour, and otherwise passes, while
Fred and Jim guess if they see two different colours, giving Sheila's
hat colour. The possibilities are:
hats guess
F J S F J S result
----- ----- ------
r r r - - r win
r r b b b r lose - all wrong
r b r r - - win
r b b - b - win
b r r - r - win
b r b b - - win
b b r r r b lose - all wrong
b b b - - b win
Here's an easier puzzle: Suppose they can try again if they all pass
(with the same hats, but without any other communication). Can they
improve further?
--
Eppur si muove
Monwhea Jeng
> in article 3ad5f9a4....@news.mia.bellsouth.net, Ramon Kiley at
> ramon...@GoFor21.com wrote on 4/11/01 7:43 PM:
>
> Partial spoiler after original puzzle
>
> > The hat problem goes like this:
> >
> > Three players enter a room and a red or blue hat is placed on each person's
> > head. The color of each hat is determined by a coin toss, with the outcome
> > of one coin toss having no effect on the others. Each person can see the
> > other players' hats but not his own.
> >
> > No communication of any sort is allowed, except for an initial strategy
> > session before the game begins. Once they have had a chance to look at the
> > other hats, the players must simultaneously guess the color of their own
> > hats or pass. The group shares a hypothetical $3 million prize if at least
> > one player guesses correctly and no players guess incorrectly.
> >
> > The same game can be played with any number of players. The general problem
> > is to find a strategy for the group that maximizes its chances of winning
> > the prize.
> >
> > One obvious strategy for the players, for instance, would be for one player
> > to always guess "red" while the other players pass. This would give the
> > group a 50 percent chance of winning the prize. Can the group do better?
> >
> > --------------------------------------------------------------
(Semi)-Spoiler space
>
>
>
>
>
>
>
> Yes. A group of three (and hence any larger group) can win the prize 3/4 of
> the time.
>
> Label the players A, B, and C. If A sees that the hats of the other two are
> the same color, she guesses that color; otherwise she passes. If B sees
> that A and C have hats of different colors, she guesses the color of A's
> hat; otherwise she passes. If C sees that A and B have hats of different
> colors, she guesses the color of A's hat; otherwise she passes. This wins
> the prize unless A's hat is red and B's and C's are blue, or vice versa.
A shorter solution is for each player to agree to look at the other two
hats. If those hats are the same color, the player will guess the
opposite color, but will otherwise remain silent. Then they win unless
all hats are red or all hats are blue. Of course, this is no better than
your solution.
RESULTS
-------
It looks to me to be teribly difficult to solve this problem for the
general case of N hats. I can, however, prove the following. Any
strategy must fail at least 1/(N+1) of the time. Furthermore, when
N+1 is a power of 2, this optimum can be reached, and there is a
strategy that fails exactly 1/(N+1) of the time. So for general N,
the failure rate is somewhere greater than 1/(N+1) and less than
or equal to 1/M, where M is the largest power of 2 smaller than N.
PROOF
-----
Here is a rough and partial sketch of the proof. Consider the phase
space of possible hats (R,R,R,R),(R,R,R,B), etc. . (for N=4, e.g.).
It's a N-dimensional cube, with 2^N points. Any given strategy will
return "C" (correct) for some of the points, and "W" (wrong) for others.
We want to maximize the number of points marked "C." If a strategy
returns "C" for a given point, that means that at least one player must
make a guess for that configuration of hats, which means that that
player would be wrong if his hat's color was reversed, which means that
an adjacent point must be marked "W." So every "C" is adjacent to a "W."
Furthermore, any configuration of "W"'s and "C"'s which has every "C"
adjacent to at least one "W" is infact acheivable by a specific strategy
(we can get each "C" just by giving appropriate specific instructions to
the player whose axis leads to a "W"). So the problem is reformulated
as follows: Take a N-dimensional cube of 2^N points, and mark
some corners with "W"'s, so that every point either has a "W" or is
adjacent to one. Our failure rate will then be W/2^N, so we want as few
"W"'s as possible.
Since each "W" is adjacent to N sites, each "W" then "covers" N+1 sites,
so to cover the entire hypercube, we need at least W >= [(2^N)/(N+1)],
where the brackets indicate rounding up to the nearest integer.
This means that we will fail at least a fraction 1/(N+1) of the time,
and that is (N+1) is not an exact power of 2, we must fail at least a
little more (because of the rounding).
When N+1 is an exact power of 2, this limit can in fact be reached. I'm
getting tired, and won't give the construction right not, but basically
you get the construction for N+1=8 by sticking together several N+1=4
solutions, the construction for N+1=16 by sticking together several
N+1=8 solutions, and so on. So when N+1 is an exact power of 2, the
problem is solved.
When N is not a power of 2, this seems fairly difficult, and perhaps
intractable (I wasn't able to access the site mentioned earlier, so I
don't know if this problem is solved). I would expect that you could
usually get close to the 1/(N+1) bound. However, for the N=5 case,
that bound tells us that we must have a failure rate of at least 6/32.
However, I find, by hand-searching the N=5 case, that this bound cannot
be reached, and we need at least 7 "W"'s, for a failure rate of 7/32.
Momo
Adam Stephanides
n122604...@chch.demon.co.uk wrote on 4/11/01 11:56 PM:
> Here's an easier puzzle: Suppose they can try again if they all pass
> (with the same hats, but without any other communication). Can they
> improve further?
Spoiler:
Are they allowed to keep trying as long as they all pass, or do they get a
at most one additional try? If the former, it's easy for them to get 7/8
probability of winning: on the first round, guess blue if you see two red
hats, otherwise pass; on the second round, guess blue if you see one read
hat, otherwise pass; on the third round, always guess blue.
If the latter, I don't see how they can do better than 3/4.
--Adam
Adam Stephanides
Monwhea Jeng at mo...@sal.physics.ucsb.edu wrote on 4/12/01 2:51 AM:
[partial spoiler space]
Your proof sketch seems good, but you need to rule out the possibility of a
probabilistic strategy (e.g. someone guessing red with probability 0<p<1 if
everyone else has red, and passing otherwise). From the little exploring
I've done, this doesn't seem to give any improvement, but I'm not sure how
you would prove it.
> When N is not a power of 2, this seems fairly difficult, and perhaps
> intractable (I wasn't able to access the site mentioned earlier, so I
> don't know if this problem is solved).
The optimum solution for general N is not known, although it is known when N
< 9 (and when N + 1 is a power of 2, as your post pointed out).
--Adam
Monwhea Jeng
> in article Pine.LNX.4.30.01041...@sal.physics.ucsb.edu,
> Monwhea Jeng at mo...@sal.physics.ucsb.edu wrote on 4/12/01 2:51 AM:
>
> [partial spoiler space]
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> Your proof sketch seems good, but you need to rule out the possibility of a
> probabilistic strategy (e.g. someone guessing red with probability 0<p<1 if
> everyone else has red, and passing otherwise). From the little exploring
> I've done, this doesn't seem to give any improvement, but I'm not sure how
> you would prove it.
Any probablistic strategy is a combination of deterministic strategies,
each of which has a certain chance of being followed. Thus the chance of
success with a probablistic strategy is a (weighted) average of chances of
success with deterministic strategies, which means that at least one of the
deterministic strategies must have a higher (or equal) chance of success
than the probablistic strategy. Thus there exists a deterministic strategy
which is optimal.
The only point of a probablistic strategy is if you have an opponent who
is in some way trying to out-guess you. If your opponents actions do not
depend on yours, you might as well go with a deterministic strategy.
> > When N is not a power of 2, this seems fairly difficult, and perhaps
> > intractable (I wasn't able to access the site mentioned earlier, so I
> > don't know if this problem is solved).
>
> The optimum solution for general N is not known, although it is known when N
> < 9 (and when N + 1 is a power of 2, as your post pointed out).
Do you have a site with the solutions for N<9 ?
This is a cool puzzle.
Momo
Courtenay Footman
>This is taken from
>http://dailynews.yahoo.com/h/nyt/20010409/tc/why_mathematicians_now_care_about_their_hat_color_1.html
>
>You might want to work on the problem first and then go to the web site to
>read the rest. Considering how popular the article says the puzzle is now,
>I don't understand why I haven't seen it mentioned here yet. Maybe it was
>already posted and I missed it.
You didn't. I saw it for the first time in Tuesday's NYT's, and if other
people hadn't started posting, I would have posted it myself.
--
Courtenay Footman I have again gotten back on the net, and
c...@lightlink.com again I will never get anything done.
(All mail from non-valid addresses is automatically deleted by my system.)
Adam Stephanides
Monwhea Jeng at mo...@twiki.physics.ucsb.edu wrote on 4/12/01 3:40 PM:
> Do you have a site with the solutions for N<9 ?
I'm afraid not. I got my info from the URL given by Mr. Kiley, which says
that solutions are known for N < 9, but not what they are. It does say that
the solutions are derived from binary codes. In fact, the entire problem is
closely connected to coding theory, which is why mathematicians are so
interested in it.
> This is a cool puzzle.
Yes, it is.
--Adam
Jonathan G. Dushoff
: Here's an easier puzzle: Suppose they can try again if they all pass
: (with the same hats, but without any other communication). Can they
: improve further?
Adam Stephanides has already solved this problem for three people. This
solution can be extended for any number of people to win with
probability 1-1/2^n in at most n rounds as follows.
This is clearly an optimal probability but I don't know if it is an
optimal number of rounds.
Spoiler:
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Designate one person as the "guru" (in honor of a related problem, which
many will recognize). If the guru sees no blue hats she should guess at
random on the first round. Otherwise any player who sees exactly n blue
hats (ignoring the guru's hat) should guess that their own hat is blue
in round n+2.
Jonathan Dushoff
Ike R. Malony
>Yes. A group of three (and hence any larger group) can win the prize 3/4 of
>the time.
"And hence any larger group"? Why is that?
--
"Ike R. Malony" is actually 62379 80415 <62379...@GoFor21.com>.
012 3 456789 <-Use this key to decode my email address and name.
Jonathan G. Dushoff
>Yes. A group of three (and hence any larger group) can win the prize 3/4 of
>the time.
Ike R. Malony (ike.r....@GoFor21.com) wrote:
: "And hence any larger group"? Why is that?
Because if there is no better solution, the larger group can agree that
three of them will pretend that they are the only three players, and
everybody else will keep their mouths shut.
Jonathan Dushoff
K. Y. Lemonair
>Because if there is no better solution, the larger group can agree that
>three of them will pretend that they are the only three players, and
>everybody else will keep their mouths shut.
Yes, of course. Thanks.
So if I understand the article correctly, there's an improved solution for
each successive n, where the corresponding group consist of (2^n)-1 people.
That means that there should be a strategy with better than 3/4 probability
for a group of 7 people.
And since the article says:
>For example, in the game with 15 players, there is a strategy for which the
>group is victorious 15 out of every 16 times they play.
That seems to imply that there's a solution for 7 people where there's a
7/8 probability of winning. If so, I wonder what it could be.
--
"K. Y. Lemonair" is actually 23951 68407 <23951...@GoFor21.com>.
0 1 23456789 <-Use this key to decode my email address and name.
Monwhea Jeng
> That seems to imply that there's a solution for 7 people where there's a
> 7/8 probability of winning. If so, I wonder what it could be.
I sketched the proof for (2^n)-1 people in an earlier post, but didn't
give all the details. It's a little difficult to describe in detail,
since my proof has a lot of pictures. The strategy does not give
identical instructions to every players, so it's not a simple short
strategy. In fact, for a large number of player N, no strategy which
gives identical instructions to every player can do much better
than a 2/3 success rate.
Momo
Howard Cheng
> So if I understand the article correctly, there's an improved solution for
> each successive n, where the corresponding group consist of (2^n)-1 people.
> That means that there should be a strategy with better than 3/4 probability
> for a group of 7 people.
>
> And since the article says:
>
> >For example, in the game with 15 players, there is a strategy for which the
> >group is victorious 15 out of every 16 times they play.
>
> That seems to imply that there's a solution for 7 people where there's a
> 7/8 probability of winning. If so, I wonder what it could be.
After reading the article and see various remarks about coding theory,
I now understand what they really meant and so I have a strategy with
probability of winning = n/n+1 when n is of the form 2^m - 1. The big
hint that I got was the quote "it's O.K. to be wrong as long as you
contrive not to be wrong alone."
[ spoiler ahead... ]
We represent all the possible situations as binary strings of length
n. For two strings of equal length, we define the Hamming distance to
be the number of positions in which they differ.
Now suppose you have some strategy. Look at two situations S1 and S2
such that their Hamming distance is 1. Let's say S1 and S2 differ in
position i. That means any strategy that forces player i to guess
must be right in one situation and wrong in the other. Now, the hint
given in the article was that "it's O.K. to be wrong as long as you
contrive not to be wrong alone." So let's look at the case in which
everyone is wrong in some situation S. Suppose that for any i = 1,
..., n, the i-th person seeing the colors of the remaining hat would
guess the opposite of the color he has in situation S. In that case,
S would be wrong but all situations with distance 1 will be right. In
a sense, you have a sphere of radius 1 in which the center is wrong,
but everything is right. Note that this sphere has n+1 points, so
within this sphere the probability of success is n/(n+1).
Now, let's say we have a set W of situations in which we designate as
"wrong". If the unit spheres centered at these situations do not
overlap, then it is clear that the min distance between any pair of
strings in W must have distance >= 3. We now have the following
strategy. Everyone would have to know the members of W in advance.
Now when person i looks around he will see the string
x = x_1 x_2 ... x_{i-1} ? x_{i+1} ... x_n
Find a member w in W matching all bits except for the i-th bit, and
then guess the opposite of the i-bit in w. If such a member w does
not exist, pass.
Claims:
1. There is at most one member in W matching x.
2. In any situation v not in W, if v is 1 away from a member w in W,
then exactly one person will guess and he guesses correctly.
3. In any situation v not in W, if v is > 1 away from any member w
in W, then everyone passes.
4. In any situation in W, everyone guesses wrong.
These can be proven by the fact that every pair of elements in W must
have distance >= 3.
Now, if you can cover the whole space with non-overlapping unit
spheres, then the probability of winning is n/(n+1). It is well-known
that this can be done if and only if n is of the form 2^m-1. In that
case the members of W is the valid codewords of the Hamming code.
The problem is now reduced to finding the most efficient single-bit
error-correcting code with n bits. When n is not of this form, then
the probability is a bit lower since some strings cannot be covered.
Howard
---
Howard Cheng e-mail: hchc...@scg.math.uwaterloo.ca
University of Waterloo URL : http://www.scg.uwaterloo.ca/~hchcheng/
Computer Science Graduate Student (PhD)
There is no future in time travel.
Menial Roky
>We represent all the possible situations as binary strings of length
>n.
Howard, the seven team members are in a huddle waiting for their
instructions, and you're the coach. They don't want to hear about any
binary strings, they just want to know what to do! The clock is running
down and it's almost time for the players to be temporarily blindfolded so
they can receive their colored hats. They're counting on you! Quick, what
should they do?
--
"Menial Roky" is actually 51679 23084 <51679...@GoFor21.com>.
012345 6789 <-Use this key to decode my email address and name.
Jonathan G. Dushoff
: Howard Cheng <hchc...@scg.math.uwaterloo.ca> wrote:
: Howard, the seven team members are in a huddle waiting for their
: instructions, and you're the coach. They don't want to hear about any
: binary strings, they just want to know what to do! The clock is running
: down and it's almost time for the players to be temporarily blindfolded so
: they can receive their colored hats. They're counting on you! Quick, what
: should they do?
We follow a strategy of "guessing away". This means we pretend that
certain configurations can't occur. If the information you have is
consistent with a forbidden configuration, you guess a hat color for
yourself that is not consistent with that configuration.
The simplest solution for three, for example, involves using all blue and
all red as "forbidden". Thus, anyone who sees two hats of the same
color pretends to know that they can't have the same color, and guesses
the opposite.
I was able to find a relatively simple solution for 7, using all red,
all blue, and all configurations of the form XXXOXOO, where X and O are
different colors, and we start from any individual and move clockwise,
as forbidden configurations. This gives a total of 16 configurations.
So, look around you, see if one of these configurations is possible
based on what you see. If not, keep your mouth shut. If so "guess
away" from the possible forbidden configuration.
This would take practice to do in a reasonable amount of time, and could
make a fun drinking game.
ObIrrelevantQuestion: Why has Menial Roky's apparent real name changed
since his 5x5 poker days?
Jonathan Dushoff
Rainy Mokle
>In fact, for a large number of player N, no strategy which
>gives identical instructions to every player can do much better
>than a 2/3 success rate.
That could be. I believe this is the best strategy for the seven player
game that gives identical instructions to each player. It produces an
average of 85 wins out of 128 for 66.41%. Please check me on this:
If you see 0 blue hats, pick blue.
If you see 1 blue hat, pick pass.
If you see 2 blue hats, pick red.
If you see 3 blue hats, pick blue.
If you see 4 blue hats, pick pass.
If you see 5 blue hats, pick red.
If you see 6 blue hats, pick blue.
Of course red and blue can be swapped.
--
"Rainy Mokle" is actually 89064 32571 <89064...@GoFor21.com>.
01234 56789 <-Use this key to decode my email address and name.
Jonathan G. Dushoff
: In fact, for a large number of player N, no strategy which
: gives identical instructions to every player can do much better
: than a 2/3 success rate.
This depends what you mean by identical instructions. I suspect that
you were excluding the possibility of allowing players to distinguish
between their teammates in a symmetric way. For example, the identical
instructions could start like this:
"Number the other players from 1 to n-1 moving clockwise from your
left."
For seven players this sort of identical instruction allows a perfect
solution (7/8 success; at least I think so, you can see my proposed
solution on this thread). I wonder whether there is such a symmetric
solution for all 2^n-1.
Jonathan Dushoff
Monwhea Jeng
> Monwhea Jeng (mo...@twiki.physics.ucsb.edu) wrote:
>
> : In fact, for a large number of player N, no strategy which
> : gives identical instructions to every player can do much better
> : than a 2/3 success rate.
>
> This depends what you mean by identical instructions. I suspect that
> you were excluding the possibility of allowing players to distinguish
> between their teammates in a symmetric way. For example, the identical
> instructions could start like this:
>
> "Number the other players from 1 to n-1 moving clockwise from your
> left."
Yes, you are right, I did mean to exclude such instructions. I was not
being careful enough in my phrasing. What I really meant was what you
said.
Momo
Adam Stephanides
Monwhea Jeng at mo...@twiki.physics.ucsb.edu wrote on 4/12/01 3:40 PM:
> Do you have a site with the solutions for N<9 ?
I'm afraid not. I got my info from the URL given by the original poster,
which says that solutions are known for N<9, but not what they are. It does
say these solutions are derived from binary codes. In fact, the entire
problem is closely related to coding theory, which is why mathematicians are
so interested in it.
> This is a cool puzzle.
Yes, it is.
--Adam
Charles Bryant
Jonathan G. Dushoff <jdus...@yuma.Princeton.EDU> wrote:
>Charles Bryant (n122604...@chch.demon.co.uk) wrote:
>
>: Here's an easier puzzle: Suppose they can try again if they all pass
>: (with the same hats, but without any other communication). Can they
>: improve further?
>
>Adam Stephanides has already solved this problem for three people. This
>solution can be extended for any number of people to win with
>probability 1-1/2^n in at most n rounds as follows.
>
>This is clearly an optimal probability but I don't know if it is an
>optimal number of rounds.
>
>many will recognize). If the guru sees no blue hats she should guess at
>random on the first round. Otherwise any player who sees exactly n blue
>hats (ignoring the guru's hat) should guess that their own hat is blue
>in round n+2.
That certainly works. The solution I was thinking of would number the
people 1..N and goes like this: In round N, person N guesses 'red'.
In round N-1, person N-1 knows what person N would guess on the next
round, and can see if that would be correct, so they guess 'red' if
person N would lose (i.e. N has a blue hat). Similarly in round r person
r guesses 'red' if they know that person r+1 would guess incorrectly
(i.e. all people (r+1..N) have blue hats).
Therefore, if any of people 2..N guess, they will guess correctly
(and know it). If person 1 guesses, they only do so when all of 2..N
have blue hats, and they're only wrong if everyone has a blue hat.
--
Eppur si muove
John Rickard
: >: Here's an easier puzzle: Suppose they can try again if they all pass
: >: (with the same hats, but without any other communication). Can they
: >: improve further?
: That certainly works. The solution I was thinking of would number the
: people 1..N and goes like this: In round N, person N guesses 'red'.
: In round N-1, person N-1 knows what person N would guess on the next
: round, and can see if that would be correct, so they guess 'red' if
: person N would lose (i.e. N has a blue hat). Similarly in round r person
: r guesses 'red' if they know that person r+1 would guess incorrectly
: (i.e. all people (r+1..N) have blue hats).
Another solution: In round r, anyone who can see exactly (r-1) blue
hats guesses "blue" (unless someone has already guessed in a previous
round, of course). This works unless all the hats are red.
--
John Rickard <John.R...@virata.com>
Adam Stephanides
jdus...@yuma.Princeton.EDU wrote on 4/13/01 11:13 AM:
> Charles Bryant (n122604...@chch.demon.co.uk) wrote:
>
> : Here's an easier puzzle: Suppose they can try again if they all pass
> : (with the same hats, but without any other communication). Can they
> : improve further?
>
> Adam Stephanides has already solved this problem for three people. This
> solution can be extended for any number of people to win with
> probability 1-1/2^n in at most n rounds as follows.
>
> This is clearly an optimal probability but I don't know if it is an
> optimal number of rounds.
It is, and it's not hard to prove. There is only one distribution of hats
which will be guessed wrongly, and this must come in the first round (since
any guess in the first round has a chance of being wrong), so all guesses in
subsequent rounds must be certain to be correct. A distribution can be
guessed correctly in the first round only if it differs by one hat from the
"wrong" distribution. By induction, a distribution can be guessed correctly
in the kth round only if it differs by no more than k hats from the wrong
distribution.
In floor(n/2) rounds, n players can win with probability 1-1/2^(n-1): on the
kth round, if you see fewer than k hats of one color, guess that color. A
variation of the proof above shows that this is optimal.
--Ada