wu :: forums - Print Page


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

        riddles >> hard >> Simultaneous Hat Color Guessing II
        
(Message started by: Barukh on Oct 10^th, 2006, 2:01am)

Title: Simultaneous Hat Color Guessing II
Post by Barukh on Oct 10^th, 2006, 2:01am

This is simular to Simultaneous Hat Color Guessing (http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#popQuiz), with the following differences:

1. Players can't pass (every player must guess his hat’s color).
2. They can guess incorrectly.
3. They win if the number of correct guesses is greater than the number of incorrect guesses.

Is there a strategy that ensures the victory? If no, what’s the strategy with best changes to win?

Title: Re: Simultaneous Hat Color Guessing II
Post by towr on Oct 10^th, 2006, 3:08am

on 10/10/06 at 02:01:02, Barukh wrote:

Is there a strategy that ensures the victory?

Obviously not in general; if there's just one person, he can't win with certainty.
For two the prospect isn't much better.

Quote:

If no, what’s the strategy with best changes to win?

[hide]I'd go with picking the opposite of the majority.[/hide]

Title: Re: Simultaneous Hat Color Guessing II
Post by towr on Oct 10^th, 2006, 3:21am

Actually, maybe that's not a good strategy in general (e.g. case n=4)..

This seem familiar somehow.

Title: Re: Simultaneous Hat Color Guessing II
Post by rmsgrey on Oct 10^th, 2006, 3:35am

on 10/10/06 at 03:08:04, towr wrote:

Obviously not in general; if there's just one person, he can't win with certainty.
For two the prospect isn't much better.

[hide]I'd go with picking the opposite of the majority.[/hide]

So what happens when the observed hats split evenly?

For the 3-person case, I'd suggest [hide]pick the opposite of the hat on your left[/hide] with a 75% win chance.

With 4 people, I'd go with [hide]pick the majority colour[/hide] which gets what I suspect is the optimum result of a 62.5% win chance.

For large N, [hide]pick the majority colour[/hide] does better than average though I haven't worked out exact figures, nor if there's a better option.

Title: Re: Simultaneous Hat Color Guessing II
Post by towr on Oct 10^th, 2006, 3:54am

on 10/10/06 at 03:35:26, rmsgrey wrote:

So what happens when the observed hats split evenly?

I'd say random choice.
But your approach seems to give a better result.

Quote:

For large N, [hide]pick the majority colour[/hide] does better than average though I haven't worked out exact figures, nor if there's a better option.

I'd say pick the color that maximizes P(color | observed hats)
It maximizes the chance you get your color right, and since it can't influence other people choice, it should be optimal. It generalizes for multiple types of hats too.
Although, in light of the n=3 case, it might be warranted not to choose randomly in case of a draw, but synchronize choices among the group.

Title: Re: Simultaneous Hat Color Guessing II
Post by Icarus on Oct 10^th, 2006, 3:48pm

I'm missing something here:

on 10/10/06 at 02:01:02, Barukh wrote:

3. They win if the number of correct guesses is greater than the number of incorrect guesses.

If you can find a way to determine your own hat color after a few guesses, then all you need to do is keep guessing correctly until you have passed the incorrect guesses.

As for what to do: have everyone guess "Red" if the 2 hats they see are the same color, and "Blue" if they are different colors. The first round will let everyone know their own hat color. In subsequent rounds they will all be right.

Title: Re: Simultaneous Hat Color Guessing II
Post by Deedlit on Oct 10^th, 2006, 6:01pm

Each person makes just one guess.

towr's strategy is not so good; if n is even, it is guaranteed to fail 100% of the time. If n = 2k + 1, then it wins 1 / [C(2k+1,k) 2^k] of the time (it always loses unless exactly k are of one color, in which case all k people will guess wrong, so the other k+1 people must randomly guess right.)

For rmsgrey's strategy, the best bet when you see the same number of colors is to guess a prespecified color; this will win half the time, ass opposed to guessing randomly, which will win only 1/2^k+1 of the time as previously mentioned.

If the specified color is red, then you will win unless [n/2] if the people have color red. For n large, this will happen about sqrt {2/ (pi n)} of the time.

on 10/10/06 at 03:54:58, towr wrote:

The probability of picking your color correctly is 1/2, regardless of what strategy you use.

Using this fact, we can get an upper bound on the probability of success. Letting C and I be the number of correct and incorrect answers, the average value of C equals the average value of I. So

P(winning) E(C - I | winning) + P(losing) E(C - I | losing) = 0
P(winning) 1 + P (losing) (-n) <= 0
P(winning) <= n P(losing)

So we can win on at most [n 2ⁿ / (n + 1)] colorings. Note that we get the same upper bound for the original problem.

If n is even, then C - I must be even, so we get an upper bound of [n 2ⁿ / (n + 2)]. So rmsgrey's answers for n=3 and n=4 are optimal. For n=5 and 6 we get 13/16 and 3/4 for the upper bound, whereas taking the majority gives 11/16 for both.

Title: Re: Simultaneous Hat Color Guessing II
Post by towr on Oct 11^th, 2006, 1:23am

on 10/10/06 at 18:01:19, Deedlit wrote:

The probability of picking your color correctly is 1/2, regardless of what strategy you use.

Hmm.. yes, I was thinking that for example it was more likely that one hat has a different color than that all are the same; so if you see all the same color, you should guess opposite.
But in as far it might be usefull, it doesn't give the probability of ones own color.. But there are k cases where it'll give one person his right color, whereas there's 1 case where k persons have it wrong, and that's plus (if it combines well with the other guesses)

Title: Re: Simultaneous Hat Color Guessing II
Post by towr on Oct 11^th, 2006, 4:31am

on 10/10/06 at 18:01:19, Deedlit wrote:

For n=5 and 6 we get 13/16 and 3/4 for the upper bound, whereas taking the majority gives 11/16 for both.

Running a program to try out all (deterministic) strategies (that disregards order and thus just look at how many hats of each color re visible)
11/16 is the best you can do in both cases.

You might still do better if you change either or both of those two constraints on the strategies.

[edit]
results for for 7 to 15
93/128
186/256
386/512
772/1024
1586/2048
3172/4096
6476/8192
12952/16384
26333/32768

And it's always the simple majority strategy that's best too.
[/edit]