Author |
Topic: Simultaneous Hat Color Guessing II (Read 1217 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Simultaneous Hat Color Guessing II
« on: Oct 10th, 2006, 2:01am » |
 Quote  Modify
|
This is simular to Simultaneous Hat Color Guessing, 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?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Simultaneous Hat Color Guessing II
« Reply #1 on: Oct 10th, 2006, 3:08am » |
Quote Modify
|
on Oct 10th, 2006, 2:01am, 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? |
|
I'd go with picking the opposite of the majority.
|
| « Last Edit: Oct 10th, 2006, 3:12am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Simultaneous Hat Color Guessing II
« Reply #2 on: Oct 10th, 2006, 3:21am » |
Quote Modify
|
Actually, maybe that's not a good strategy in general (e.g. case n=4)..
This seem familiar somehow.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: Simultaneous Hat Color Guessing II
« Reply #3 on: Oct 10th, 2006, 3:35am » |
Quote Modify
|
on Oct 10th, 2006, 3:08am, 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.
I'd go with picking the opposite of the majority.
|
|
So what happens when the observed hats split evenly?
For the 3-person case, I'd suggest pick the opposite of the hat on your left with a 75% win chance.
With 4 people, I'd go with pick the majority colour which gets what I suspect is the optimum result of a 62.5% win chance.
For large N, pick the majority colour does better than average though I haven't worked out exact figures, nor if there's a better option.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Simultaneous Hat Color Guessing II
« Reply #4 on: Oct 10th, 2006, 3:54am » |
Quote Modify
|
on Oct 10th, 2006, 3:35am, 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, pick the majority colour 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Simultaneous Hat Color Guessing II
« Reply #5 on: Oct 10th, 2006, 3:48pm » |
Quote Modify
|
I'm missing something here:
on Oct 10th, 2006, 2:01am, 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.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Simultaneous Hat Color Guessing II
« Reply #6 on: Oct 10th, 2006, 6:01pm » |
Quote Modify
|
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) 2k] 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/2k+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 Oct 10th, 2006, 3:54am, towr wrote:
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.
|
|
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 2n / (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 2n / (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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Simultaneous Hat Color Guessing II
« Reply #7 on: Oct 11th, 2006, 1:23am » |
Quote Modify
|
on Oct 10th, 2006, 6:01pm, 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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Simultaneous Hat Color Guessing II
« Reply #8 on: Oct 11th, 2006, 4:31am » |
Quote Modify
|
on Oct 10th, 2006, 6:01pm, 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]
|
| « Last Edit: Oct 11th, 2006, 5:10am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print