wu :: forums - Print Page


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

        riddles >> hard >> Re:SIMULTANEOUS HAT COLOR GUESSING
        
(Message started by: Matt on Jun 2^nd, 2003, 3:19pm)

Title: Re:SIMULTANEOUS HAT COLOR GUESSING
Post by Matt on Jun 2^nd, 2003, 3:19pm

I've been trying to work on this problem, but i can't seem to find a way to make a perfect 100% probability. Can someone help? Here's the riddle in case you can't find it on the site.
--------------------------------------------------------------------------------
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.

Title: Re: Re:SIMULTANEOUS HAT COLOR GUESSING
Post by Leonid Broukhis on Jun 2^nd, 2003, 5:44pm

It is allowed for all players to pass, I assume.

The same strategy for 4 players wins with p=1/2, loses badly with p=1/8, and with p=3/8 everybody is silent ("loses gracefully"), and I do not see a way to improve that.

For 5 players we can do better than pWin=5/16 achievable by
THUDandBLUNDER's strategy.

Title: Re: Re:SIMULTANEOUS HAT COLOR GUESSING
Post by tohuvabohu on Jun 3^rd, 2003, 4:08pm

Any individual guess is 50/50. But you improve those odds by grouping the guesses.
Essentially, you plan it so that there are a few instances where there are a lot of wrong guesses and a lot of instances where there are a few right ones (and no wrong ones). When people guess wrong, everybody guesses wrong, and when people guess right, only the right ones are guessing.

Maybe one of the experts here can check my math.

For 5 players, add the strategem that if you see 2 red, 2 blue, guess a predetermined color (say Red). You'll win 20 out of 32 times.

For 6 players, by guessing the color that you see 0 or 3 of, you win 42 out of 64, I think.

For 7 players, guess the color that you see 0 or 2 of. 84/128.

For 8 players, guess the color that you see 0,3 or 5 of. 142/256

For 9 players, guess the color that you see 0,3 or 6 of. 342/512

For 10 players, guess the color that you see 0,3 or 7 of. 530/1024.

For 11 players, guess the color 1,4,7,9. 1366/2048

For 12 players, guess the color 1,4,8,11. 2158/4096

For 13 players, guess the color 2,5,8,11. 5460/8192

Title: Re: Re:SIMULTANEOUS HAT COLOR GUESSING
Post by Matt on Jun 3^rd, 2003, 11:24pm

I've found a way to make the probability 75%, but I'm told by a friend that there is a way of making it 100%, but he won't tell me.

If you take into account all probabilities, and work on a strategy, rather than individual guesses, you can increase the probability.

Here are the possible outcomes:

BBB
BBR
BRB
BRR
RBB
RBR
RRB
RRR

If you use the strategy:
If a person sees a blue and a red, they pass;
If a person sees a blue and a blue, they guess red;
If a person sees a red and a red, they guess blue;
The probability comes out like this:

(B=blue, R=red, P=pass)

actual guess correct?
BBB RRR no
BBR PPR yes
BRB PRP yes
BRR BPP yes
RBB RPP yes
RBR PBP yes
RRB PPB yes
RRR BBB no

As you can see, this is a 6/8, or 75% chance of being correct. Can anyone find the 100%.

Title: Re: Re:SIMULTANEOUS HAT COLOR GUESSING
Post by tohuvabohu on Jun 4^th, 2003, 6:39am

Without communicating in any way, there's no way any of them can know his own hat color. Your friend may have some cheating in mind, like passing information by the way you look at each other, but that's communicating.

And my answer for 5 players was incorrect. You can win 22 out of 32 times by guessing the color you see 1 or 4 of.

Title: Re: Re:SIMULTANEOUS HAT COLOR GUESSING
Post by Dante on Jun 6^th, 2003, 5:46am

OK, it's a Friday afternoon, and my brain doesn't work so well at the end of the week. But when you have 4 or more players, can't you get a 75% win just as easily as with 3?

In the initial strategy session, nominate 3 players to play the game. They look at each others hats only, and play as though the others weren't there (using the 75% strategy outlined by THUDandBLUNDER). Everyone else passes.

Am I missing something?

Title: Re: Re:SIMULTANEOUS HAT COLOR GUESSING
Post by Rujith de Silva on Jun 6^th, 2003, 7:24am

There's no way to reach 100% certainty, but you can get pretty close
to it as the number of players increases. Sorry, I don't know a
formula for it. Here's a write-up I did a while back that maps the
problem into a hyper-cube. It may help you visualize the problem
better. http://home.earthlink.net/~rujith/threecrowns/
- Rujith.

Title: Re: Re:SIMULTANEOUS HAT COLOR GUESSING
Post by tohuvabohu on Jun 6^th, 2003, 7:54am

My answer is still right. It's just the answer to a different riddle. Let's say that there was no strategy session, that no information could ever pass between the players, but every player knew the other players were smart enough to figure out the best overall strategy. Then my method is the best they could do. Picking just 3 people to guess would be an improvement, though.
Rujith's strategy is better still. It is basically the same approach I attempted, except that I unnecessarily limited myself by requiring all players to use the same strategy. Of course, I was able to work out the strategy for 13 prisoners with just a piece of paper in a few minutes. I'd like to see the prisoners try drawing a 13-dimension hypercube and figuring out where to put their lollipops while the guards so very patiently wait.

Title: Re: Re:SIMULTANEOUS HAT COLOR GUESSING
Post by Leonid Broukhis on Jun 6^th, 2003, 9:21am

The restriction requiring all players to use the same strategy is not unnecessary, it is required by the problem statement, which says that the players are allowed a strategy session. If the strategy they devise is not uniform, they would need to hold a tactics session to assign sub-strategies to particular players, and they are not allowed to do that.

Title: Re: Re:SIMULTANEOUS HAT COLOR GUESSING
Post by James Fingas on Jun 6^th, 2003, 12:20pm

You might want to check out the other thread for this puzzle here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1028010706).

This gives slightly better lower bounds for the success rates. Our consensus last time was that the strategy could include certain people always remaining silent. If you use the "Hamming Codes" solution, then you will use the N=3 solution for N=4,5, and 6. Once you get to N=7, you get a better solution:

1) Number all participants 1 to 7
2) Identify 16 different "codes" that the participants will identify. Here are 16 such codes that they could use:
RRRRRRR
BBBRRRR
BRRBBRR
BRRRRBB
RBRBRBR
RBRRBRB
RRBRBBR
RRBBRRB
RRRBBBB
RBBRRBB
RBBBBRR
BRBRBRB
BRBBRBR
BBRBRRB
BBRRBBR
BBBBBBB
3) If a participant sees all 6 other people matching the "code", then the participant guesses that his hat does not match the code.

Notice that each code given differs from all other codes in at least 3 places. This means that if a combination of hats differs by one from any code, then it differs by at least two hats from any other code. There are 7 ways to almost get a code for every code. For each of those 7 ways, one person will see what looks like a code, and the rest will know it's not a code. That one person will guess that his hat color doesn't match the code, and will be correct.

That gives us 16*7=112 ways to win out of 16*8=128 possibilities. The only way to lose is if a code is actually generated, in which case everybody guesses wrong simultaneously. The probability of winning is therefore 7/8.

As the number of people increases, you do get closer and closer to 100% performance. The jumps are as follows:

1: 0.500 = 1/2
3: 0.750 = 3/4
7: 0.875 = 7/8
15: 0.9375 = 15/16
31: 0.96875 = 31/32
63: 0.984375 = 63/64
etc.

However, generating the codes to do this is very difficult.

Title: Re: Re:SIMULTANEOUS HAT COLOR GUESSING
Post by tohuvabohu on Jun 6^th, 2003, 2:10pm

I guess I rushed my original numbers. I didn't use the best strategy when the total was even. Up the winning odds for N=8 to 170/256. For N=10 it's 680/1024. For 12 it's 2730/4096. So for large N, my method tends toward .666...
Not nearly as good as the hamming method, but like I said, I'm solving a different riddle where there's no prior information passing, just each prisoner figuring out by himself the strategy he expects everyone to use.
So there's no numbering or ordering of the prisoners (I'll seat them in a circle so there is no number one, or maybe have them mill around in a crowd), so the only info they have is how many red hats they see and how many blue hats.

Here's how I figured it for 21 prisoners.
In 2 cases the hats are 21/0 (red/blue or blue/red)
The prisoners all see 20/0
42 cases of 20/1. They see 0./20 or 19/1 (the first number represents the wearer's own color, tho he doesn't know that)
420 cases of 19/2. They see 1/19 or 18./2
2660 cases of 18/3. They see 2/18. or 17/3.
11970 cases of 17/4. They see 3./17 or 16/4
40698 cases of 16/5. They see 4/16 or 15./5
108528 cases of 15/6. They see 5/15. or 14/6.
232560 cases of 14/7. They see 6./14 or 13/7
406980 cases of 13/8. They see 7/13 or 12./8
587860 cases of 12/9. They see 8/12. or 11/9.
705432 cases of 11/10. They see 9./11 or 10/10

The bold numbers with decimal points are the guesses they should make (for example, if you see 9 of one color and 11 of the other, guess 9. Whenever that number is in the numerator, it's a win.) that maximize the number of victories and result in everybody guessing wrong at the same time. That's a win 1398102/2097152 times or 66.666698%

Title: Re: Re:SIMULTANEOUS HAT COLOR GUESSING
Post by Yoda on Aug 15^th, 2003, 9:16am

In the three player hat game I think they can figure out their hat colors 87.5% of the time. Better than the 75% that was posted. And I think this logic can be used to improve all of the other games as well:

Round 1:
If you see two red hats call blue. (If you see 1 blue hat or two blue hats don't call anything).

Round 2:
Since the game has gone this far you know at least two hats are blue or somebody would have seen two red hats and called blue in round 1. So if you see a red hat you KNOW yours is blue.

Round 3: If nobody calls 'blue' in round 2, that is because nobody saw a red hat, so they are all blue. So everybody calls blue.

Title: Re: Re:SIMULTANEOUS HAT COLOR GUESSING
Post by Yoda on Aug 15^th, 2003, 9:31pm

I think the algorithm that I suggested above can be generalized to beat everybody else's algorithms as such.

For the N player scenerio.

Round one:
If you see n-1 red hats call blue. Otherwise call pass.

Round two:
If nobody called anything in round 1, then there are at least 2 blue hats so if you see n-2 red hats call blue. Otherwise call pass.

Round m <n:
If by now, nobody has yet called blue then, there must be at least m blue hats. If you see n-m red hats call blue. Otherwise call pass.

Round n:
If nobody has called blue by now, your hat is blue (as is everybody else's)

This algorithm has a probability of winning 1-1/2^n

3 player: .875
4 player: .9375
5 player: .96875
6 player: .984375
7 player: .9921875

And so at 7 players we already have a greater than 99% chance. 8)

And the cool thing is that if you don't fail on the first round, you know you've won. In fact if you see two colors you know you've won because if somebody does make a guess on the first round they will guess right.

I think an intersting reformulation of this problem might be to change it so that there are ten players and each player has a red or blue hat but they don't know which. At least one person's hat is blue. They all answer simultaneously etc. etc. etc. . . . How can they be 100% certain of getting the right answer?

The algorithm above will work.

Title: Re: Re:SIMULTANEOUS HAT COLOR GUESSING
Post by Yoda on Aug 15^th, 2003, 9:52pm

Oops! I see we are solving slightly different puzzles. I assumed that if everybody passes, then they will be asked again and so on until at least one person takes a stab at guessing.