The Three Hat Problem 325
Posted
by
michael
from the howmathematiciansoccupytheirtime dept.
from the howmathematiciansoccupytheirtime dept.
jeffsenter writes: "The NYTimes has a nice article on the three hat problem, which has recently become quite popular among mathematicians. Three people are given either a red or a blue hat to wear. The goal is to have someone guess the correct color of his/her own hat with no person guessing incorrectly." Read the article for the rules of the puzzle. This problem is quite comparable to the Monty Hall problem, where people initially think that they can't do better than chance, but then realize that there is an extra source of information which can be tapped  either the host's knowledge of which door has the prize, or in this case, the fact that which player makes a guess can be determined after the game has started, that is, based on information available about the hats. Think about it  it's an interesting puzzle.
Re:Math + Usefullness (Score:1)
100% fucking stupid (Score:1)
Re:Better solution (Score:1)
Re:The requirements are unclear (Score:1)
Mea Culpa (Score:1)
Thanks for catching that.
Very good, eh! (Score:1)
Of course, you _could_ have just followed the link to the website in my identity block  but then that would have been cheating.
Some clarifications to the puzzle: (Score:5)
Here's some key points:
1) All guesses must be correct. If any of the 3 players guess and get it wrong, everybody loses.
2) Guesses are simultanious, not sequential  ie, you write down your guess, and all 3 guesses are passed to the host, who then reads them
3) There are 3 hats, but two colours. This means that out of 12 possible combinations, there are 2 that are "all hats same colour"  so 1/6th of the time. Thus, if you see 2 hats of the same colour, the probability that your hat is the same color is 1/6  which in turn implies that guessing that your hat is a different colour will be correct 5/6th of the time.
Thus, if you see any two differentlycoloured hats, you pass. If you see all hats the same colour, then invert the color you see and guess that. This starts at 5/6ths correct with 3 hats, and gets better for larger numbers of hats not a power of 2.
Hamming codes (Score:1)
It's always great to see theoretical work evolve from recreational activities.
Solutions to 5hat (and guess about N^2 hat) (Score:1)
Devide the 32 possible combinations into 3 groups:
1) All hats same (2 possible)
2) 4/1 split (10 possible)
3) 3/2 split (20 possible)
Now, to get group 3 right look at the other 4. If same number of red/blue then pass. If there is a majority guess the oposite.
This will make you get all the situations in group 2 wrong. It is possible to salvage the last two in group one though. If all you see is the same, guess what you see.
Are there any better solutions?
Harry
PS. I beleive that for any group where there are are a power of 2 members (1,2,4,8,etc) it is impossible to get above 50%. Can anyone confirm?
Re:Math + Usefullness (Score:1)
Arithmetic (Multiplication, Division, Simple Estimation)
Made an estimate of what sprinkler I needed for my lawn and type of grass, taking into account water coverage and projected rainfall.
Arithmetic (Subtraction, Division)
Determined what operations to make to get a bit structure in the format I desired, over a system with endian differences (using Fortran  yuck!)
Boolean Algebra
For fun, calculated how many managers it would take to run a company, based on each manager having a maximum of 4 people under them (still working on those formulas  I leave it as an excerise for the reader to determine why I decided on 4, or you could go join the Discordians and find out for yourself).
Sumnation Math (1st sem. calculus)
Calculated my wife's reading rate, to determine when she would be done with the Harry Potter book
Arithmetic (Multiplication, Division)
Cut down a recipe for 10 to a recipe for 2 1/2.
Arithmetic (simple division).
Determined whether it would be a better idea to make an extra car payment, house payment, get a CD, or invest in a mutual fund
Arithmetic (Simple Comparisons)
Tried to figure out your age, based on how little math you have had (19? 20?)
No math just a flame.
It's been a slow math week, too. In my job (systems programmer), I've used logic, binary arithmetic, calculus, trig, geometry, statistics, and other flavors of math.
I see no trig. No geometry. No statistics. All most all is just arithmetic. And all but your just for fun problem was high school math.
I'm gonna have to agree for the first guy dude. For 90% of the people out there (prolly more really) a solid understanding of High School level math is all it really takes.
Harry
Re:Solutions to 5hat (and guess about N^2 hat) (Score:1)
In the real world it would be trivial to ignore player 4, and have 13 operate just like in the 3hat game.
In the math world this can't really be done. There is no way to decide which player to ignore.
Basically the way I'm looking at the problem (and the way I think the problem is supposed to be looked at) the only information you have to base a decision on is the number of red/blue on everyone else's head. You can't differentiate between them. Am I making sense? I hope so.
Harry
Did the article misquote something? (Score:1)
The strategy is as follows:
Look at the other hats, and see whether there's one color that's a minority (if you see a tie, keep your mouth shut; i.e. always pass). Then, if you see m hats showing the minorty, pass until round m+1 at which point you guess that your hat has the minority color.
An example with nine players. Say players p1 through p6 have R hats, and p7, p8 and p9 have B hats:
Walking in, players p1 through p6 each see five R hats and three B hats, and so decide that if the game lasts to round four, they will guess "B".
Players p7, p8, and p9 each see six R hats and two B hats, and so decide to guess "B" in round three, if the game gets that far.
Then, everyone passes for rounds one and two. In round three, the three players with B hats all guess "B", and the game is over (with the team having won).
This strategy of course results in losing the game if all the hats are the same color, or if there are an even number of players and the number of R hats equals the number of B hats.
Re:What I don't get about the Monty Hall Problem (Score:1)
The basic idea you're missing is that when you made your initial pick you chose from a different set of doors than you're presented with when you get to do your switchorstay choice.
First of all, clear your mind of the notion that simply because there are two options, both of them must be equally likely to lead to reward. The real world rarely works like that, and in fact you should never assume that even theoretical problems work that way unless its so stated. As a trivial example, suppose that we play a game in which we walk up to a random person on the street and ask them for their signature. Would you like to win when they sign with their right hand or with their left?
So what is stated: the prize is behind a randomly chosen door, and before the game is equally likely to be behind any one of the three. The host chooses randomly when he can. You are in control of your own strategy.
Now, let's take a diversion and play a game similar to Monty Hall, but with one important difference: the host chooses one of the two doors regardless of what may be behind it and just places a big X on the door marking it offlimits. You can then switch or not. Now, then, the universes play out this way:
case A: (1/3 chance) You choose initially the correct door: no matter which door the host Xes out, you lose if you switch and win if you stay.
case B: (1/3 chance) You initially choose incorrectly and the host Xes out the door with the prize. No matter what you do, you lose. Sometimes life is like that.
case C: (1/3 chance) You initially choose incorrectly and the host Xes out the other empty door. You win if you switch, but lose if you stay.
It is important to note that the probabilities for the different cases are NOT computed by simply using 1/3 since we have three cases, but rather from the statement of the problem: we _know_ that the location of the prize is distributed uniformly, and therefore have a 1/3 chance of guessing correctly initially (case A). In the 2/3 of the time that we guess incorrectly initially, half of the time the host will X out the prize door (so 2/3 * 1/2 == 1/3 chance for case B) and half the time the host will X out another empty door (2/3 * 1/2 == 1/3 chance for case C)
So we see that the strategy analysis works out like this: if you switch, you win 1/3 of the time and lose 2/3 of the time. If you stay, same odds. Therefore, there's no advantage to either strategy.
Now, how does this differ from the regular Monty Hall game? The difference is that the host doesn't choose randomly, and only Xes out a door without the prize. This then redistributes the probabilities between cases B and C. Specifically, case B never happens, so we have case A when we guess correctly initially (1/3 chance), and case C when we guess incorrectly initially.
It is important to note that the reason changing the rules and eliminating case B doesn't cause the probability of case A to go up is that the probability of case A doesn't depend at all on the host's action.
For example, let's go back to the evil game above and assume that our host doesn't like us much at all and therefore if the host can X out the door with the prize on it, he will do so 2/3 of the time. Then, the distributions become:
case A: (1/3 chance) win on stay.
case B: (2/3 * 2/3 == 4/9 chance) always lose.
case C: (2/3 * 1/3 == 1/9 chance) win on switch.
Then, we have that if we stay we will win 1/3 of the time, whereas if we switch we will win only 1/9 of the time.
It is useful to work with other Monty Hall variants (for example, if the host prefers to open the leftmost door you didn't choose when given a choice, or a game where the host may choose to open the door which you initially chose, bumping your choice to the next door) and to then check one's reasoning with a math prof. or computer simulation. Going through exercises like this can really help one appreciate some of probability's finer points.
Re:Math + Usefullness (Score:1)
The mathematical reasoning I mention is not to be confused with school classes labelled ``math''. As you have found out, they are not very interesting.
I can easily complain about English classes like you do about Mathematics classes. Whereas you ask why we are taught angle bisection and not cheque book balancing, I can equally ask why we are made to know Shakespear and not practice on writing résumés.
Some people argue that literature is intellectually interesting and important to an advance civilization, whether it is directly useful or not. The same can be said about mathematics. Provided it is taught and learned right. The problem is that mathematics is not conveyed right by schools.
Please give mathematics a second consideration. Do not look at it as something that should be used  any area is useful only to a small niché. Look at it as a possible pastime, an interesting art, an interesting science, a way of thinking (the insistence on precision and proofs is certainly a viable philosophy), and a framework for solving puzzles.
Get it right 7/8 of the time... (Score:1)
Person A looks and if B is Red and C is Blue,
then Person A flips a coin and says red or blue.
Next, person B looks. If C is Blue, person B guesses Blue.
Now, person C guesses red.
If it gets by person A, then there are only 3 possibilities for B&C. By getting by B, there's only one left.
There's a 1/4 chance that A will have to guess, so a 1/8 chance that he will guess and guess wrong. If B or C guess, they'll be right.
So, you can do it with only a 1/8 chance of doing it wrong.
I know this doesn't follow the "everybody guess at the same time rule," but I didn't see that in the NYT article...
You're a ETlover (Score:2)
Great! What if the aliens read this post? Now they will make us wear masks.
__
Origin of "Red Hat" (Score:2)
__
Re:Perhaps... (total OT reply) (Score:1)
Re:Play monte hall! (Score:1)
There's your problem  donuts float better than concrete blocks. Throwing something that floats overboard will leave the boat at the same level.
Throwing something that sinks won't.

Play monte hall! (Score:2)
Oh, and by the way, you should always switch.
Here's another one I like, but in a differetn (physics) vein  a man is in a boat holding a cement block. He throws it overboard. Does the lake level go up, go down, or stay the same?

Re:Blue hat? (Score:2)
(It was extremely tempting to turn that into a goatlink, but I didn't :) )
It's a Dr Seuss April Fools joke (Score:4)
This is all taken from the Dr Seuss' book "One Fish. Two Fish. Red Fish. Blue Fish [amazon.com]", just changed to be One Hat Two Hat Red Hat Blue Hat.
Truely LMAO!
Answer, I think (spoiler) (Score:1)
Sorry, article was archived (Score:1)
The requirements are unclear (Score:2)

Re:Answer is here (Score:2)
Research? (Score:4)
Sounds fun! How can I get a job at said "research" institute??
Except... (Score:1)
You see a bad buyer might use someone elses formula, but a better buyer will understand that model and adjusted it to better suit her particular environment.
We don't normally train folks to be below average, therefore everyone (named above, and possible just a few more) needs to be trained in math, not just counting.
Joe
Answer obvious to me (Score:1)
This needs a bunch of professional mathematicians thinking for days?
Not so obvious with a lot of hats, though.
Re:How to cheat (Score:1)
In my opinion, your response is funnier than my original post.

How to cheat (Score:5)
Then when it's time to look at your fellow players, pick the one farthest to your right and look at his chest for down, or his hat for up. Point your whole face.
Then glance with your eyes at the others. If even one of them has read this post, you're in good shape. If they both have, you're free.
Unless the aliens are just shitting you, and intend to implant an 80foot satellite dish in your ass regardless of the outcome.

Re:Perhaps... (total OT reply) (Score:1)
Re:There is NO way to guarantee a win. (Score:1)
The simultaneous guess solution is perfect since it overlaps the wrong guesses while spreading out the correct guesses.
Schematics (W=Wrong guess, C = Correct guess,  = pass):
r r r W W W
b b b W W W
r b b C  
b r r C  
b r b  C 
b b r   C
r r b   C
r b r  C 
Re:Hmmmm (Score:1)
Re:So what is the strategy for larger teams? (Score:1)
Everyone but p1: If p1 has the opposite color of the rest guess that you have the same color as p1.

Extend rules for higher order solutions. Following is a schematic of how I reached the above rules.
r r r r W W W W
r r b b  C  
r b r r  C  
r b b b C W W W
r b r b   C 
r b b r    C
r r r b    C
r r b r   C 
b r r r C W W W
b r b b  C  
b b r r  C  
b b b b W W W W
b b r b   C 
b b b r    C
b r r b    C
b r b r   C 
Re:So what is the strategy for larger teams? (Score:1)
Everyone: If everyone has the same color guess that you have the opposite color.
Everyone but p(x): If p(x) has the opposite color of the rest guess that you have the same color as p(x).
Re:So what is the strategy for larger teams? (Score:2)
So the condition for winning does *not* have to occur. If everyone passed, they'd lose.
Re:Sorry, article was archived (Score:1)
That problem's intersting, but not quite the same, though  in the 3 hat problem, everyone guesses simultaneously. Plus, only one person has to be right for the group to win, as long as everyone else passes. Plus, you can't win all of the time, but you can win a lot more of the time than you'd think.

How many classes do you have to take
Re:What I don't get about the Monty Hall Problem (Score:2)
Our mind seems to prefer "shortcuts" based on similar numbers.
The Monty Hall experiement can made clear to everyone changing just quantities.
Let's say you have 1000 doors, with 999 false choices and one winner.
You choose one and then the host shows 998 false doors. Now it's easy to see that indeed changing choice is the better decision and everyone whom I explained it this way immediatly got it.
It's just that 2 is so damn near to 3 what confuses people.
Re:Some clarifications to the puzzle: (Score:1)
No, it's 1/2.

Re:Better solution (Score:2)

Re:Some clarifications to the puzzle: (Score:2)
000
001
010
011
100
101
110
111
Let's give the people names:
ABC
DEF
GHI
JKL
MNO
PQR
STU
VWX
Now, we're only talking people who see two hats of the same color. That leaves
ABC
F
H
J
M
Q
U
VWX
There are 12 people here. Six of them are wearing a hat that's the same color as the ones they see. Six are not.
1/2.
QED

Re:Some clarifications to the puzzle: (Score:2)
Thus, if you see 2 hats of the same colour, the probability that your hat is the same color is 1/6
I (correctly) pointed out that the probability was actually 1/2. That's what the previous few posts have been in reference to.

Completely wrong (Score:1)
Here's my explanation of the Monty Hall problem that so many of you think is wrong.
When you initially choose a door, probability of getting a prize is 1/3 (3 doors, one prize, hence 1 in 3 chance). The chance of picking a goat is 2/3.
After a host opens one of the two doors, he does so with FULL knowledge! He will not open a prize door by tossing a coin, he will always open a door with a goat. This is EXTREMELY important clue to the puzzle!
Now, after he open a door with a goat, he does so with full knowledge AND the door that he opens is one of the TWO doors that you didn't choose (i.e. he will not open a door that you chose). Once he does that, things change BIG time.
The probability of your current door having the prize is still 1/3! Nothing changed since you picked the door among three other doors. The door that's left (DoorL), however, now has a chance of 2/3 of being the door with a prize! Why? Well... initially it (DoorL) had a chance of being the prize with P=1/3, the door that was opened (DoorG) had a chance of P=1/3 but now the chance of the DoorG having the prize is P=0! So, the chance of DoorL having the prize now must be P=2/3.
Q.E.D.
Here's my solution.... (Score:1)
After a host opens one of the two doors, he does so with FULL knowledge! He will not open a prize door by tossing a coin, he will always open a door with a goat. This is EXTREMELY important clue to the puzzle!
Now, after he open a door with a goat, he does so with full knowledge AND the door that he opens is one of the TWO doors that you didn't choose (i.e. he will not open a door that you chose). Once he does that, things change BIG time.
The probability of your current door having the prize is still 1/3! Nothing changed since you picked the door among three other doors. The door that's left (DoorL), however, now has a chance of 2/3 of being the door with a prize! Why? Well... initially it (DoorL) had a chance of being the prize with P=1/3, the door that was opened (DoorG) had a chance of P=1/3 but now the chance of the DoorG having the prize is P=0! So, the chance of DoorL having the prize now must be P=2/3.
Q.E.D.
Re:Completely wrong (Score:1)
My Better solution, with some rule deformity (Score:2)
Here's my strategy.
When the 3 hats are distributed, one of the players yells "NOW". then, each player that can see 2 RED hats guesses BLUE. Otherwise all players pass. If all hats are RED, we lose at this point, otherwise we will eventually win.
Then, if all players pass, we have new information. That information is: "There is no more than 1 RED Hat". So, we coordinate another guess. Someone yells "NOW" again. Then, everyone that can see one RED hat correctly guesses "BLUE".
If all players pass again, new information is obtained: "There are NO red hats". Then, after someone coordinates the guesses again, all players can guess "BLUE" and be right.
The generalised solution has a failure rate of 1/2^N, where N is the number of players. For 15 players, the chance of failure with this strategy is 1/32768, far better than the 1/16 for the simpler strategy in the article.
This problem is similar to the "Three Philosophers" problem that was mentioned in Scientific American some years ago. In this one, three philosophers are aleep under a tree, and a bird soils the foreheads of all of them. When they wake, they all start laughing at each other. Then one suddenly stops laughing. Why?

Re:Math + Usefullness (Score:1)
Grow up, please
Re:Another question!!! (Score:1)
a and b being the same variable isn't in the problem domain.
Simple nuff.
Re:Another question!!! (Score:2)
a
b
a
Re:Better solution (Score:1)
Re:Some clarifications to the puzzle: (Score:2)
There are 3 hats, but two colours. This means that out of 12 possible combinations
There are three hats, and each has two possible colours. Thus there are 2 * 2 * 2 = 8 possible combinations, not 12, and there's a 2/8 chance of them being all the same colour.
Perhaps... (total OT reply) (Score:2)
I have always hated Dr. Seuss...
I'll never forget the way my teachers in grade school (around 1st2nd grade) treated me: They wanted me to read the stupid Dr. Seuss books, and other kid books  rather than let me read the ones I could see I wanted to read  Science Experiment books, Alfred Morgan electricity books, books on space and technology, computers, etc.  Telling me those were for the "older" children, only (like, WTF? I might learn something? What the hell am I going to learn about "Green eggs and ham, Sam I am"? How to read? I already knew how to do that, unlike my lamer peers!)...
Thank the gods my parents had some sense, and bought me both a science and a regular encyclopedia for me before I turned 6 years old...
That, and plenty of Lego...
Worldcom [worldcom.com]  Generation Duh!
Re:Perhaps... (total OT reply) (Score:2)
I could just see what utterly useless pap Dr. Seuss was. The first book I remember being "introduced" to was a science encyclopedia my parents got in the mail  they knew I liked building toys and such, so they showed it to me, and I read that thing nearly covertocover, so they got me more like it (always asking my input on whether it was something I would like to read). Later they got a set of encyclopedias (Brittanica  not a cheap set to get), mainly for school work. Any other kinds of book wanted to read, I could pick out from the bookstore or elsewhere.
Don't get me wrong  my reading interests weren't all reference, nor did I read only "adult" oriented books  I read my share of children's novels. I just enjoyed the kind of books that had more than 1015 pages, and more words than pictures. For those books that had pictures, I vastly preferred pictures that at least looked like a real setting, rather than a complete candycoated strangeass druginduced fantasy land (and if you look at Dr. Seuss in this light as an adult, perhaps that is why some adults are fascinated by his work...perhaps).
Worldcom [worldcom.com]  Generation Duh!
Re:Perhaps... (total OT reply) (Score:2)
I will change it immediately, thanks for the update...
Worldcom [worldcom.com]  Generation Duh!
No... (Score:2)
Worldcom [worldcom.com]  Generation Duh!
Kinda wacky... (Score:2)
Worldcom [worldcom.com]  Generation Duh!
Re:Research? (Score:2)
I'm buying my pseudoticket today!
Re:Math + Usefullness (Score:2)
For the people who developed computer microchips, then the advanced math is VERY relevent. However, unless you find yourself under that particular umbrella, things like advanced calculus are surprisingly abstract. I'll even go so far as to say that grade 12 is getting a little
And, for the record, I have always gotten approximately 95% in ALL of my math courses, so I DO understand the material.

CitizenC
Re:This defies random odds (Score:3)
Of the 8 possible hat combinations, 6 of them will have exactly one person answer correctly, and the other 2 will have all 3 people answer incorrectly.
Re:This defies random odds (Score:2)
Probability is a best guess, when you don't have all the facts. Nothing funny or strange about it all.
Perhaps the best solution. (Score:2)
Player 1 guesses Red only if he sees all Blue hats. This strategy is only triggered in two cases regardless of the number of players. It will always be wrong in half of those two cases, and it is the only guess that ever takes place.
Each subsequent player ignores the colors of the hats of the players who preceded him. He is only concerned with the colors of the hats of the player who will follow. If he sees only Blue hats among them, he states that his own hat is Red.
This strategy works because if the first player passed, the rest of the players know that he saw at least one Red hat. If a player sees no Red hats among the players that follow him, and he is not the first player, then he knows that the players who passed to him saw the Red hat on his head.
Since there must be a single guess to differentiate between two cases to start the inference, there is one losing case. We can't improve the odds to a sure thing. However, we have just reduced them to one losing case regardless of the number of players. Therefore, the best strategy loses still loses 1 time in 2^n cases.
If the players believe that the contest is rigged, Player 1 can randomly select the color of his guess. This brings the worst case in a rigged contest from 0% back up to 50%. I don't think there is a way to improve on that.
Re:Perhaps the best solution. (Score:2)
Re:Math + Usefullness (Score:2)

Solution for the general case using Hamming codes (Score:5)
The general case is perhaps best illustrated by example for the case of 7 players. Here's how it goes:
First, number the players 1 through 7. Now think of a player with a red hat as being assigned a binary zero, and a player with a blue hat as being assigned a binary 1. Then an assignment of hats to the players can be associated with a length 7 binary sequence: As an example, if all the players have red hats, this correspond to the sequence 0000000 (seven zeros), and if all but the last player have red hats, we get the sequence 0000001. We'll call length 7 binary sequences words; every hat assignment has an associated word, and vice versa. For future reference, denote the two words in the example above as c0 and c1 respectively.
A brief digression on Hamming codes: A length 7 Hamming code is a certain (carefully chosen) subset of the 2^7=128 possible words. This subset consists of 16 words, called codewords. We need just one fact about Hamming codes to describe the players' strategy: [Fact 1] If any one bit in a codeword is flipped, the resulting word is not a codeword. For example: c0, the all zero word, is always a codeword in a Hamming code; c1, which differs from c0 in just one bit, cannot be a codeword.
Suppose I am one of the players. Here's my strategy:
By observing the hats of the other 6 players, I construct two words. The first, w0, is the word that would be associated with our hat assignments if my hat is red. The second, w1, is the word that would be associated with our hat assignments if my hat is blue. We have 3 possible cases:
So, why does this work? To understand, we need one more property of Hamming codes: [Fact 2] For every word that is not a codeword, there is a unique bit, which if flipped, will produce a codeword. For instance, if the last bit in c1 is flipped, we get c0, the all zero codeword. Now suppose that the hat assignment is associated with a word that's not a codeword (which, as shown above, happens 7/8 of the time). To be specific, suppose the assignment corresponds to c1. Here, the 7th bit is the unique bit that can be flipped to get a codeword. Then, by Fact 2, players 1 through 6, after constructing their w0 and w1 words, will find themselves in Case 1 : neither word is a codeword. They'll keep quiet, while the 7th player will declare his hat to be blue (Case 2). Success!
Of course, if the hat assignment corresponds to a codeword, then every player will speak up, and they'll all guess wrong! Example again: if every player is assigned a red hat (corresponding to c0), they'll all say they have blue hats.
It's not hard to see how this generalizes for an arbitrary number of players n, where n=2^k1. The players will succeed if and only if the associated word is not a codeword. A Hamming code of length n=2^k1 has 2^(nk) codewords, so success is achieved 12^k of the time, which tends to 1 as k tends to infinity.
There, I knew those grad courses in coding theory would come in useful sometime!
Unattributed puzzle taken from 1993 ACM paper (Score:5)
This puzzle comes from a paper by James Aspnes, Richard Beigel, Merrick Furst, and Steven Rudich [google.com]. Attribution: I got this information from my friends on Mattababy [mattababy.org].
Re:Hmmmm (Score:2)
It isn't a matter of who is right. The challenge is making sure no one is wrong. Reread the challenge.
Re:Better solution (Score:2)
Spazimodo
Fsck the millennium, we want it now.
Re:The requirements are unclear (Score:2)
Re:Hmmmm (Score:2)
Re:Hmmmm (Score:2)
Again, it's a team game, if any money is going to be shared. Because information is not perfect, wrong guesses must be made for the game to be played at all, it is your responsibility to guess incorrectly if the circumstances are correct, or else you will not be helping to consolidate all the wrong guesses into a concentrated play.
Re:This defies random odds (Score:2)
The Red Hat problem (Score:5)

Re:So what is the strategy for larger teams? (Score:2)
The first round, if anybody saw six hats of a color, they would guess the other color; otherwise, they would pass. If all the hats are the same color, you lose right here, otherwise you're going to win. If there are six hats of one color and one of the other, you win right here.
The second round, everybody knows that nobody saw six hats of a color. (Ahh... but does this count as communications? Hmmm...) So, anybody who sees five hats of a given color guesses the other color, while everybody else passes. If you have five hats of one color and two of the other, the two with the other color will guess correctly, and you win.
The third round, everybody knows that nobody saw five hats of a color. Anybody who sees four hats of a given color guesses the other color. This is guaranteed to be the last round, as the three in the minority guess their hat color correctly.
Even numbers should be fun. Having four hats, two of each color, would result in winning in the second round with everybody guessing their hat color correctly.
Solution (Score:2)
Blue hat? (Score:3)
There is something other than Red Hat?
Lane [rit.edu]
I have read one similar to this (Score:2)
Three guys come want to stay in a hotel and pay equal amount each to share a hotel room. When they ask the woman behind the counter what the price is for a single room, she replies that it is 30 dollars. This is to their delight as they will be able to split that very evenly between the three of them. They each give her $10 and are happily on their way to thier room. About an hour later, the woman's boss comes in and asks if anything happened while he was out. She tells him the story of the three men to which he responds be telling her that they paid too much and that the price of the room should have been $25. He tells her to take $5 and give it back to them. In the process of returning the money, she remebers how they all wanted to pay an equal amount. So to make it easy on them, she gave them each $1 back, and kept the remaining $2 for herself.
This is where it get's tricky. They each paid $9 which multiplied by 3 is $27. She kept $2 and when added on to the $27 that they paid is $29. Where did the 30th dollar go?
I love that one.
Real world problems (Score:2)
No wonder custom business software is often over engineered. We're bored to death with mundane business logic!
Re:Some clarifications to the puzzle: (Score:2)
"It's 0.75."
The cases in which you see two hats of the same color are RRR, RRB, BBR, and BBB, where the last color in each case is your own hat. These cases have equal probability of occurring. The frequency with which your hat is the same color is 1/2 of these equally probable cases, and so the probability is 1/2.
So, the answer to the question "If you see two hats of the same color, what is the probability your hat is the same color?" is 1/2.
However, the answer to the question "If (at least) two hats are the same color, what is the probability all hats are the same color?", the probability is 1/4.
This is because the equally probable cases in which two hats are the same color (as is always the case of course) are RRR, RRB, RBR, RBB, BRR, BRB, BBR, and BBB. Of those, the proportion that have all three the same color is 1/4, and hence the probability is 1/4.
Re:Some clarifications to the puzzle: (Score:2)
Your comments are consistent with a misintepretation of the question. Specifically, your comments appear consistent with an attempt to demonstrate how the algorithm described in the New York Times article yields a 75% probability of success. However, the question addressed here has been a different problem. The question in this thread is, if you see two hats of the same color, what is the probability your hat is the same color?
That probability is indeed 1/2.
Perhaps you would like to reconsider your assertions that others were in error.
Re:There is NO way to guarantee a win. (Score:2)
You three know that if the two hats you can see are of the same color, chances are that your hat is of a different color.
This is a very old probabilistic fallacy. Since all the hats were chosen independently, the probability that your hat is a different colour from the other two is still 50%.
The apparent contradiction is resolved in this problem because you don't always actually make a guess, and a "win" is based on three answers, not one. Take a look at my other [slashdot.org] post.
Also, I was saying there is no way to guarantee a win  in other words, have zero probability of failure.

Re:This defies random odds (Score:3)
Am I incorrect or is this based upon the supposition that by looking at the other draws you can base conclusions on your own
You would be correct if a single person were being asked to guess either red or blue for his own hat.
But, this is not the case. Three people are being asked to give simultaneously one of three answers: red, blue, or pass. Each person can see the hats of the other two, and finally, they have an agreed strategy for guessing.
The best way to think of it (IMHO) is this: the guessing strategy is completely mechanical, so it's fair to think of it as part of the randomized process, rather than the response to one.

There is NO way to guarantee a win. (Score:3)
Someone suggested that if the players are allowed to give their answers in sequence, and subsequent players can know the others' responses, then you can guarantee a win.
However, this is clearly untrue, because of the following reasoning:
The first person to guess has access only to the colours of the other two hats. This gives no information about the colour of his own, since they were chosen independently. Any concrete guess will have a 50% chance of being correct. Thus, in order to guarantee a win, the first person must pass.
Since the first person must pass regardless of what colours the other two have, the second person has no new information about his own hat. He, too, must pass.
By the same reasoning, the third person also has no new information, and is therefore forced to guess, and incurs the wrath of the other two, 50% of the time.
There is no way to guarantee a win except by allowing the players to collaborate in some way.

Re:Better solution (Score:2)
That was, indeed, my problem. I didn't realize that they had to guess simultaneously. Had the players been able to guess in order, mine would've worked. (And still would've tied back to the hamming code concept.)
Owel, back to the drawing board.
Re:Math + Usefullness (Score:2)
Re:Math + Usefullness (Score:4)
I used math over the last seven days to:
Guestimate how long it will take me to do a task, based on past performance and how much was budgeted.
Made an estimate of what sprinkler I needed for my lawn and type of grass, taking into account water coverage and projected rainfall.
Determined what operations to make to get a bit structure in the format I desired, over a system with endian differences (using Fortran  yuck!)
For fun, calculated how many managers it would take to run a company, based on each manager having a maximum of 4 people under them (still working on those formulas  I leave it as an excerise for the reader to determine why I decided on 4, or you could go join the Discordians and find out for yourself).
Calculated my wife's reading rate, to determine when she would be done with the Harry Potter book
Cut down a recipe for 10 to a recipe for 2 1/2.
Determined whether it would be a better idea to make an extra car payment, house payment, get a CD, or invest in a mutual fund
Tried to figure out your age, based on how little math you have had (19? 20?)
It's been a slow math week, too. In my job (systems programmer), I've used logic, binary arithmetic, calculus, trig, geometry, statistics, and other flavors of math.
Understanding the materials is a long way from realizing practical applications. Even these folks who do math for a living don't comprehend possible applications yet, but it's been a safe bet that today's math theory is tommorrow's application.
Re:Solution (Score:2)
100% solution (Score:2)
Re:50% (Score:2)
Let me guess...I bet you got alot of those tricky word problems wrong, didn't you? But you were always the first one done!
What do you guys think my odds of getting that one right are? =)
I just check my checkbook balance (Score:3)
Simple solution (Score:2)
Out of 100000 tests:
75093 (75.093%) resulted in success.
24907 (24.907%) resulted in failures.
Seems pretty obvious to me.
7 hats case (Score:2)
We have 7 hats. The following combinations can occur.
rrrrrrr
rrrrrrb
rrrrrbb
rrrrbbb
rrrbbbb
rrbbbbb
rbbbbbb
bbbbbbb
Yep, I consider the order of the hats irrelevant. The article does not reveal if this assumption is correct; from what I found for this case I guess order is relevant. See my remarks at the end.
Let X be a hat wearer.
Case 1: X sees only 1 color of hats (6r or 6b)
Case 2: X sees a distribution of 5/1 (5r/1b or 5b/1r)
Case 3: X sees a distribution of 4/2 (4r/2b or 4b/2r)
Case 4: X sees a distribution of 3/3 (3r/3b)
Now, there are not many strategies to choose from, really. For either case, one can choose guess I'm red, guess I'm blue or pass. You could easily check them one by one and see which strategy works best. For instance, I tried (and I strongly believe this is optimal):
Case 1: if 6r, choose b, if 6b, choose r
Case 2: pass
Case 3: if 4r, choose b, if 4b, choose r
Case 4: pass
This strategy makes sure everyone guesses wrong for the two cases that have only one permutation (ie. 7b/0r and 7r/0b, Case 1 applies), which is the best achievable result. Because consider: we did 14 wrong guesses, but lost in only 2 out of 128 cases (there are 2**7 = 128 permutations for 7 hats). Knowing that on the average, 50% of our guesses will be wrong, ditching 14/128 of them while loosing only twice is a good start.
At the same time, this strategy makes sure that for 4r/3b and 3r/4b, we win. Since 4r/3b renders the most permutations (35 possible permutations for each), we guess right for 70 out of 128 permutations.
A closer look on this: (Cases repeated from above for convenience)
Case 1: X sees 6r/0b => b; or 6b/0r => r
Case 2: X sees 5r/1b or 5b/1r; pass
Case 3: X sees 4r/2b => b; or 4b/2r => r
Case 4: X sees 3r/3b; pass
rrrrrrr (7r/0b)
=> Case 1; everyone guessses b, all lose
====> (7 0) = 1 combination exists for this case
rrrrrrb (6r/1b)
=> for the r's, Case 2 applies (5r/1b) so they pass
=> for the b, Case 1 applies, so it guesses b (and is right)
====> (7 1) = 7 combinations exist for this case
rrrrrbb (5r/2b)
=> for the r's, Case 3 applies (4r seen), they choose r (wrong)
=> for the b's, Case 2 applies, they pass (irrelevant)
====> (7 2) = 21 combinations exist for this case (ouch)
rrrrbbb (4r/3b)
=> for the r's, Case 4 applies, they pass
=> for the b's, Case 3 applies, they choose r (right)
====> (7 3) = 35 combinations exist for this case (wheee!)
repeat above, but exchange the colors. Now for the totals:
rrrrrrr / bbbbbbb: 2 wrong (2*(7 0))
rrrrrrb / bbbbbbr: 14 right (2*(7 1))
rrrrrbb / bbbbbrr: 42 wrong (2*(7 2))
rrrrbbb / bbbbrrr: 70 right (2*(7 3))
Right: 84
Wrong: 44
Total percentage: 84/128 = 66% or about 2/3.
Conclusion: in about 2/3 of the cases the above strategy wins. Now the problem is, I don't really see how to improve on this. But the article claims that a strategy exists that wins 7 out of 8 times or 88%. That would would match with a strategy that is losing for the 7r, 7b 6r/1b and 1r/6b cases, and winning for the 5r/2b, 2b/5r, 4r/3b and 4b/3r cases. I don't think there is such a strategy.
The only thing that I can imagine is that hat wearer X gets a piece of paper which shows information like this:
rrXbrbbr
Not only can he see how many red/blue hats there are, but also their relative locations, and his own. This would probably open up a host of other strategies.
If not, please someone explain how to improve on the above strategy. I'm curious. In any case, a nice problem. It surprised me that the Slashdot crowd did not seem willing to take on this problem for other than the 3 hats case, which is why I did it myself.
Hmmmm (Score:5)
I was going to post a solution like this (before reading the rest of the article, duh) but then I thought it didn't work. That's because I was taking a single point of view (which is Timothy's point). I should have gone ahead and done it....
There are 8 possible universes. The algorithm works as follows:
RRR = every player sees two reds, every player says "blue"  LOSS
BBB = every player sees two blues, every player says "red"  LOSS
RRB = the reds see conflict and pass, the blue sees two reds and guesses "blue"  WIN
RBR = the reds see conflict and pass, the blue sees two reds and guesses "blue"  WIN
BRR = the reds see conflict and pass, the blue sees two reds and guesses "blue"  WIN
RBB = the blues see conflict and pass, the red sees two blues and guesses "red"  WIN
BBR = the blues see conflict and pass, the red sees two blues and guesses "red"  WIN
BRB = the blues see conflict and pass, the red sees two blues and guesses "red"  WIN
That's 6 wins in 8 plays or 3 wins in 4 plays. I'm not going to try to extend this to further cases.

Re:Math + Usefullness (Score:2)
The lesson of my story is that I once thought math wasn't worth my time to learn and found out the hard way how wrong I was.
Now you may argue that that's 8th grade trig and more practical then calculus. That's fine but if you want to do anything in a science field then you will need the calculus. If you don't think you'll ever do anything in a science field then you'll probably be stunned to find out that when you graduate they don't need quite so many IT professionals and do need chemists and physicists and EE's (EE's who actually know how to build devices not just program in JAVA.) and if you don't know the advanced math you'll be someones secretary or pool cleaner.
Re:Math + Usefullness (Score:2)
Math formulas (probabilities) (Score:2)
As someone who took "Physics for Engineers"... (Score:2)

Re:Math + Usefullness (Score:2)
I like to think of math as a language. For one, it's a way of communicating ideas both abstract and concrete. Also like other languages, it provides us a conceptual framework which allows us to understand things better. And finally it's a powerful tool when you learn how to manipulate it.
Much of our math education is just the manipulation part of math, which is useful but never by itself (except on tests, as you said). Learning to describe and understand things mathematically is at least as important. With these three aspects mastered, mathematics becomes indispensable to whatever you do. Well, except for sex  but other than that, it's pretty useful.
So what is the strategy for larger teams? (Score:2)

Screwed up the formatting (Score:2)
r r r r W W W W
r r r b    C
r r b r   C 
r r b b  C  
r b r r  C  
r b r b   C 
r b b r    C
r b b b C W W W
b r r r C W W W
b r r b    C
b r b r   C 
b r b b  C  
b b r r  C  
b b r b   C 
b b b r    C
b b b b W W W W
Ah! Now I understand. Players 2  4 are essentially playing their own game, with player 1 simply trying not to mess everything up. In this scenario, player 1 could pass every time and not affect the outcome.
