Want to Play a Game?

[AuSmith]

I'm trying to vary these problems up a little bit, so I'll give you a game and you need to figure out the best strategy. Here are the rules:

1) Your math club enters a room and each teammate randomly receives a hat. They see eachothers' hats but not their own.

2) They all simultaneously guess the color of their hat: blue, red, or pass.

3) If one person guesses wrong, or if no one guesses correctly (everybody passes), the team loses.

Your teem meats and figures out a strategy beforehand. What is the best strategy and what is the probability of winning?

[AuSmith]

You can say there are 3 people on your team.

[MichaelGummelt]

1. Designate one person to be the guesser while everyone else passes

2. Somebody tells him the color of his hat

3. He says that color and the team wins.

[AuSmith]

Ha. I... hope you knew I meant no talking.

[bradp]

They can communicate using morse code.

[Quelloquialism]

1) Draw straws, in which half the straws are shorter than the other half.
2) Bludgeon the men with the shorter straws over the head with warhammers.
3) Have each survivor take a hat from a fallen comrade and remember the color.
4) Have each survivor say his new hat's color.

(I'm a programmer--this is a brute force solution)

ALTERNATIVE...

For each member:
1) Cut your head open with a blade of some sort.
2) Mutter "red" with your dying breath, as your hat must surely be red with all that blood.

[fht]

Can eye contact be used?
If the restriction is purely nonverbal, then you can designate one person before you go into the room. Except that person, everyone else will say pass. But they stare at that person when they say "pass" if he/she's wearing blue, and determinedly not look if red. Then chosen person will know his own color--"blue" if he/she's under intense stare, or red if unheeded.
If that's not exactly what you want (probably it's not) Then you need to rule out the eye contact possibility, because if faithfully and accurately executed, the plan should work every time and the tean won't lose.
Best Wishes

[AuSmith]

The only information you use once you have your hat is the color of other people's hats!

[AuSmith]

Remember, I only want the best strategy. You could designate somebody to guess blue while everybody else passes, and you have 50% chance of winning. Is there anything better than 50%?

[peterliang]

3 people

When its your turn

you look at the other 2 people's hats, if they are both the same color (red and red), then guess the other color. (blue)

or

if the other 2 people's hats are different colors (red and blue), you pass unless you are the last person to guess

[AuSmith]

Right, except they all simultaneously guess. If they all had red or all blue, the last person to guess would be the first person to guess, and so would not know any previous guesses.

How about 4 or 7 people?

[peterliang]

whats the answer

[Quelloquialism]

[AuSmith]

I learned about the game from Mira Bernstein, who put together an understandable powerpoint presentation on the game.

http://www.math.princeton.edu/mathlab/b ... s/mber.ppt

Our aim, though, is to look more past 3. I had a hard time choosing what to write as a solution. Anyways. At the bottom is a sort of explanation why we're treating 4 people so much differently than 3. I should warn you that care, I gave up and started using bad grammar.

For 4 people, there are 16 distinct possibilities. When the team is planning, they must prepare for each of the 16 possibilities. I say when they enter the room they should line up in a choo choo train so everybody agrees on the 16 bit strings they made by calling reds and blues 0's and 1's:

0000,0001,0010,0011,
0100,0101,0110,0111,
1000,1001,1010,1011,
1100,1101,1110,1111.

Notice that any time a player guesses right, there is another case (out of the 16) in which that player guesses wrong. Therefore, over all 16 cases, the total number of right guesses equals the total number of wrong guesses (important). Given any strategy, since we have everybody numbered, we know exactly when we lose. If we do guess wrong, it can only benefit us if everybody guesses wrong (increasing the total number of right guesses). We then impove our strategy by finding when we lose and telling everybody to guess wrong in that situation. Looking for an optimal strategy, we only consider the ones in which everybody guesses wrong at once.

Secondly, we wish to spread out the losing cases to where all the other cases have somebody that will guess right. This is most easily demonstrated on a hypercube and I drew a graph in paint. Players default to the pass option.

http://s151.photobucket.com/albums/s126 ... ercube.jpg

The blak dots are the ones we want to lose. We win all the dots adjacent to the blak ones since only one bit changes (that bit guessed wrong on the blak dot - it must guess right on the colored dot and everybody else pass).

The optimal strategy with 4 players is to pass unless you think it could possibly be a blak dot situation (0000,0111,1100,1011); the ones you want to screw up.

With n people, your chance of winning is no greater than [unparseable or potentially dangerous latex formula] since for every loss, you have at most n wins. If [unparseable or potentially dangerous latex formula], you may realize this maximum.

The blak dots have significance in error correction of... bitstrings I guess. Like, when you're sending something electronically.


=============================================
For 3 people, we gave everyone the same strategy and didn't think of red any differently than blue. In this spirit, we'll try the same for 4 people and see that it's not that convenient. Or, if you're not in the spirit, you should skip a little.

(1) We give the same strategy to all players
(2) Red and blue carry the same meaning. That is, if we toggled everybody's hat, we toggle everybody's guess, too.

Using our assumptions, 0011, 0101, 0110, 1001, 1010, 1100 are equivalent (either all win or all lose). We have to win these 6 cases, or else the most prudent strategy gets 50% (what we get if we tell one player to guess randomly and everybody else pass). If we win these 6 we lose most everything else, again getting at most 50%. Therefore, we have to let go of one or both of our assumptions to get a better rate. Turns out, neither assumption is good. We have to at some point break the symmetry between red and blue. And, we have to order our players. (Not order them around. Order them by lining them up.)

[AuSmith]

Oh yea, when coloring the hypercube, you can put a blak dot on (0,0,0,0) without loss of generality. Then, you get the blue dots right. Then, I chose (0,1,1,1) for the next blak dot because its adjacent points I colored red were as close to the blues as I could get without overlapping them. The browns and greens fell in to place after that.