Slashdot Mirror
The Three Hat Problem
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.
The real power of math is abstraction. That's why we all have to deal with it.
You are a fucking idiot. Read the puzzle again. Simultaneous answers. NO communication. Now go fucking crawl back into your hole and die.
There's 50% chance that Player3's guess is wrong, so you only win 50% of the time (or less).
It's clearly stated that they must answer at the same time.
Oops, how embarrasing. :(
Thanks for catching that.
Want to learn about race cars? Read my Book
A decent bit of logical deduction, my dear Watson.
;)
Of course, you _could_ have just followed the link to the website in my identity block - but then that would have been cheating.
Want to learn about race cars? Read my Book
It seems some people aren't reading the article very well (on Slashdot? Horrors!)
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 differently-coloured 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.
Want to learn about race cars? Read my Book
The darn things turn up everywhere, don't they? :-)
It's always great to see theoretical work evolve from recreational activities.
--
I beleive the optimal solution to the 5hat problem yields a win 22/32 times (or rather 11/16).
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?
Guestimate how long it will take me to do a task, based on past performance and how much was budgeted.
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
Or am I missing something? I seem to have a strategy that will work for all odd-numbers-of-players games, with a failure only when all the hats are the same color. I assume that when the article talked about the optimal strategy being unknown it was referring to the case of an even number of players.
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.
> What am I missing here people?
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 switch-or-stay 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 off-limits. 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 left-most 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.
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.
Persons A,B,C...
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...
If even one of them has read this post, you're in good shape. If they both have, you're free.
Great! What if the aliens read this post? Now they will make us wear masks.
__
__
Men with no respect for life must never be allowed to control the ultimate instruments of death.
GW Bu
Does somebody know where "Red hat" got their name from?
__
__
Men with no respect for life must never be allowed to control the ultimate instruments of death.
GW Bu
It sounds like you were crunched for time as a kid. There was plenty of time when I was a little kid to read Seuss and other more educational books. My parents never had to introduce me to books, I just picked up what I wanted too. I think most other people had the choice as kids to read many things.
> Based on my experiments with a chunk of donut
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.
--
rant
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?
---
(It was extremely tempting to turn that into a goatlink, but I didn't :) )
This is all taken from the Dr Seuss' book "One Fish. Two Fish. Red Fish. Blue Fish", just changed to be One Hat Two Hat Red Hat Blue Hat.
Truely LMAO!
I think a very similar puzzle was asked and solved in an earlier Ask Slashdot, here.
You'll have to search the whole thread for Another puzzle.
--
Sounds pretty difficult to pull off without any communication.
Sounds fun! How can I get a job at said "research" institute??
So other than "the people who developed computer microchips", and developers (who have to analyse algorithms), and network admin (who have to optimize networks), and people who build houses (who make estimates based on simple plans), and buyers for large companies who make purchases based on economic indicators and polls, and may be chemists, yah, you're right.
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
Joe Batt Solid Design
When I read how the 3-hat-problem goes, the solution immediately popped up in my head (a person who sees two different hats passes, one who sees two similiar hats guesses the other color).
This needs a bunch of professional mathematicians thinking for days?
Not so obvious with a lot of hats, though.
-- bmp System Support - Vienna, Austria
As author of the original post, I'd like to give you the recognition you deserve here, because the moderation system will surely miss it:
In my opinion, your response is funnier than my original post.
-
If you're ever kidnapped by aliens and forced to play this game in return for your life, figure out what the names of the two colors are, and assign "down" to the one that comes first alphabetically, such as "blue" in the standard example, and "up" to the other, "red" in the standard example.
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 80-foot satellite dish in your ass regardless of the outcome.
-
I'm sorry, was I supposed to be impressed?
Correctly observed. The first person to guess will always have atleast a 25% chances to fail. If he is going to relay enough information to the other guessers.
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 -
Actually, no. This doesn't work since with this algorithm you will have to do a guess when you see hats with different color (you can't pass since that would mean they were the same color according to your reasoning). This guess would make 2/8 = 25% wrong directly.
Everyone: If everyone has the same color guess that you have the opposite color.
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 -
Oops, you asked for the 7 player solution. Ok, I am not 100% sure but it should be like this:
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).
It says they pass or guess simultaneously, and that they win if someone guesses correctly without anyone else guessing incorrectly.
So the condition for winning does *not* have to occur. If everyone passed, they'd lose.
There's some nice psychologie going on here. It's similar to this 30$, three guys bla thing.
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.
--
--
Mod up a post Rob doesn't like and you'll never mod again
You're completely wrong buddy.
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.
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.
If the rules are the players must guess simultaneously, but not necessarily at a specific time, then we can bend the rules slightly and win 87.5% of the time with 3 players.
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 co-ordinate 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 co-ordinates 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?
--
The only thing necessary for the triumph of evil is for good men to do nothing. - Edmund Burke
You don't use any advanced mathematics? Within 1 year of graduating, I had to apply Newton's Method to a problem I was dealing with. Half of all SQL I do comes from principles I learned in Set Theory. And I won't even go into the analytical thinking gained through the mathematics courses I did.
Grow up, please
e to the i pi equals negative one
The problem was "How do you swap two numbers without an additional variable?"
a and b being the same variable isn't in the problem domain.
Simple nuff.
e to the i pi equals negative one
Solution in Pseudo C
:= a + b;
:= a - b;
:= a - b;
a
b
a
e to the i pi equals negative one
The solution works quite nicely, it just doesn't take into account that the guessing is simultaneous.
Not quite. To quote:
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.
They have to guess without knowledge of the other guesses. Without communication the problem becomes a lot harder. Everything I've thought of gets caught by the rules.
No, you can get a 75% chance of winning. Read the article again - the rules say each player has to guess at the same time (or pass). It's the passing that improves the odds. Because only the player that see two hats of the same colour is guessing, they've got a greater chance of getting it right.
Enjoy your job, make lots of money, work within the law. Choose any two.
What's so interesting about it? In a vacuum they would fall at the same speed, but there's a lot more air resistance on the feather than the ball so the ball hits first.
Enjoy your job, make lots of money, work within the law. Choose any two.
Before opening any doors, you have a 1/3 chance of picking the prize, and there's a 2/3 chance the prize is in one of the other doors. One of those doors is opened, and it doesn't have the prize. Now there's a 2/3 chance it's in the door you didn't pick. It relies on the host's knowledge of where the prize is.
Enjoy your job, make lots of money, work within the law. Choose any two.
Except that this is a different puzzle.
Enjoy your job, make lots of money, work within the law. Choose any two.
If the ordering of the guessers is predetermined, but each player gets to hear each other players guess, you can get it right 7/8 of the time.
(I.e. the only information that is passed around is person 1s guess to 2 and 3, and 2s guess to 3.)
person 1) if 2 & 3 are red, guess blue, otherwise pass.
person 2) if person 1 guessed, then pass.
otherwise if person 3 is red, guess blue (100% chance)
else pass
person 3) if anyone has guessed then pass,
else guess blue (100% chance)
the only time this fails is RRR...
thus 7/8. This is the best possible (as for any information to happen, there must be a case where person 1 guesses, and hence at least a 1/8 chance of failure.
The strategy is simple: everyone guesses blue in the first round. Then the number of wrong guesses is the number of red hats. If the number of red hats you see is different, you're wearing a red hat.
To get the answer with more no more that one response more than there are number of hats...
1. Assume 3 hats (works with any number)
2. First person looks at other peoples hats, and says "I see two red hats, therefor mine must be blue"
3. Second person looks at all other hats, and says "I see two red hats, and person 1 saw two red hats, therefor my hat is red"
4. Third person looks and sees two red hats, and repeats person two's phrase.
5. First person hears all the phrases, and concludes that his guess is wrong, and changes it to red.
Works for any combination of red and blue hats, and any number of people.
So x is 9. Question is.. why?
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.
Actually it is 6/8 times one of the players will get it right and 2 players will pass. There will be a total of 24 individual plays (8 plays and 3 players). Out of these only 6 will be successful, 6 wrong and 12 passes.
So changes for a correct guess is just 1/4th. Chances for failure is 1/4th too, and half the time there will not be any success or failure.
Unfortunately, the rules require that everyone respond simultaneously.
I don't practice what I preach because I'm not the kind of person that I'm preaching to.
If it's anything I've learned in school, it's that grades != knowledge... I've seen the most knowledgable people score in the bottom 10%, and I've seen less knowledgable people (who happen to be good at test taking) score in the upper 10%. So I don't really think that grade is really indicative of intelligence or knowledge of the material.
You may be right, but in all honesty...
I have always hated Dr. Seuss...
I'll never forget the way my teachers in grade school (around 1st-2nd 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 - Generation Duh!
Reason is the Path to God - Anon
I just didn't like Dr. Seuss books...
Worldcom - Generation Duh!
Reason is the Path to God - Anon
The first thing I drew in kindergarten was a picture of a UFO. What is strange to me about this is that I don't have any recollection of seeing any images of "UFOs" before this, either on TV or in a book or somesuch...
Worldcom - Generation Duh!
Reason is the Path to God - Anon
With Ordering of resposes that is easy, 100% chance to win, Everyone by 3 players aways pass.
You have 3 left A, B, C if A pass before B if C == red B passes before A if C == Blue C then calls the colour.
Nowever the question did state Everyone calls out at the same time. No ordering, it does however
not say what happens if everyone passes? is there another round? or is everyone passing a lose
James
Probability is a funny, funny thing...
You'd think that the best you can do is 50% correct, since there's that chance for your hat being blue or red.
However, if you look at the possibilities for three people, the hats can be :
rrr
rrb
rbr
brr
bbr
brb
rbb
bbb
If you count, 6 out of the 8 possibilities have two hats of one color, and one hat of the other. Therefore, as the article said, you improve your odds of guessing correctly if you see two hats of the same color. It's all a matter of perspective, as to whether you look at the individual random item, or the full set of random items.
I agree, at first appearance it does seem to defy what we're taught about odds/probability and the like. I won't pretend to be quite comfortable with it...
---
"You know your god is man-made when he hates all the same people you do."
There are two real differences: it is only a question of one boy's mud (not the group's mud), and the boys always see everyone else with mud.
Here is a problem similar to the mud:
Three boys are standing in a straight line, facing the same way. Each has a star on his back. All of the stars are red but one, which is white. The boys know this information, but can only see the stars of boys in front.
A boy wins if he can deduce that his star is white (similarly to in the mud problem).
Is this affected if there are only two boys? how about if there are five?
Solutions aren't NP-complete. NP-completeness applies to problems (in fact, a problem such that if it were discovered to be in P, then all NP problems would be in P).
Once you have found an algorithm for finding the optimal behaviour for N people, you can then decide if it's in P or NP, and then decide whether it is NP-complete or not.
Stop working as a Visual Basic programmer
Nokia cellphones have this game now. Hence its popularity surge....
:)
it's great for when you're on the bus, or waiting for food
This is like saying programming is only useful for one thing: getting paid.
:)
I'm sure you can find many Slashdotters who disagree
You aren't a Comp Sci student by any chance? ;)
The explanation given in the article is completely rigorous. However, your experiment has a small flaw: perhaps the next 100,000 cases will give 25% success and 75% failure. (or any other answer, in fact).
Answering the exam questions.
Other then basic arithmatic, I have yet to use, outside of a classroom setting, my knowledge about finding the tangent of a line, the cosine of anything, or how to bisect an angle. Unless you persue a career in architecture, or a similar field, the math that you learn begins to become more and more abstract.
------------
CitizenC
It is not too hard to prove that the Hamming code strategy is optimal. I will assume that the
players adopt a deterministic strategy.
Let N be the number of players. There are 2^N possible games, corresponding to the 2^N ways of assigning hats to the players. Let W be the number of games that they win, and let L be the number of games that they lose. (W + L = 2^N)
Let G be the total number of correct guesses made by the players. Since the players have no information about their own hats, G is also the total number of incorrect guesses.
Since winning requires at least one correct guess, G >= W. On the other hand, G <= N*L, since there cannot be more than N incorrect guesses in a losing game. Combining these inequalities gives W <= N*L, thus W/(W+L) <= N/(N+1).
This means that if there are N players, then they cannot win more than N/(N+1) of the time. This bound is achieved by the Hamming code strategy when N is one less than a power of two.
If you had RTFA, you would know that there is a strategy where the group has a 75% chance of success.
--
Obfuscated e-mail addresses won't stop sadistic 12-year-old ACs.
Win dain a lotica, en vai tu ri silota
Yes. The players must all answer simultaneously and are not allowed to communicate.
--
Obfuscated e-mail addresses won't stop sadistic 12-year-old ACs.
Win dain a lotica, en vai tu ri silota
If you had RTFA instead of just going by Timothy's summary, you would see that if everyone passes, you lose.
--
Obfuscated e-mail addresses won't stop sadistic 12-year-old ACs.
Win dain a lotica, en vai tu ri silota
You can't guarantee it. All the posters who have given 100% guaranteed solutions have either had something wrong with their understanding of the problem or their method. The idea is, in fact, to maximize the probability of being right.
--
Obfuscated e-mail addresses won't stop sadistic 12-year-old ACs.
Win dain a lotica, en vai tu ri silota
Not really. As a nerd (look at the Slashdot header and note who the news is for), I found this much more interesting than, say, a Web-enabled air conditioner.
--
Obfuscated e-mail addresses won't stop sadistic 12-year-old ACs.
Win dain a lotica, en vai tu ri silota
The person at the back of the line says what the parity of the 9 hats in front of him is. Person 9 computes the parity of the people in front of him, and deduces his hat color. Each subsequent person knows the parity of the front 9 people, hears the color of all of those behind, and sees those in front of him (except for person 10, who is fucked no matter what). Thus they can all deduce their hat color.
That was jargonspeak for "he says blue if there are an odd number of blue hats in front of him, and red if there are an odd number of red hats in front of him". Or vise versa, as long as everyone knows the plan.
Or, if you meant just say the color of the hat in front of person #10, that is the "trivail" solution in which up to 5/10 die.
They talk about this at the bottom of the article. It would appear to break the laws of random odds, since the other players hats give you no information about your own. And in fact, if you look carefully, you only guess right 50% of the time. The trick is, when one person guesses wrong, all three do, yet it only counts as one failed trial.
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.
http://digital-salvage.net/3hats.php
A little PHP script that generates 3 random hat color per reload. Totally useless for any scientific purposes, but fun or those of us who nead a little visualization to help understand the concept.
Personally I like to pretend that I am Hat2, and that the other two hats always pass. If Hat1 and Hat3 have the same color, and my hat is the opposite color, I win (since that's how myself and the other hats worked it out ahead of time). Woo Hoo.
--
> Probability is a funny, funny thing...
Probability is a best guess, when you don't have all the facts. Nothing funny or strange about it all.
I think your solution generalizes to any number of players.
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.
The net will not be what we demand, but what we make it. Build it well.
am I missing something here?
Yeah, all players have to guess simultaneously.
Mozilla
On the surface the math looks correct, but there's one fundamental assumption that is not explicitly stated in the problem: Monty knows ahead of time which door hides the prize, and Monty will only open a door for you that does NOT contain the prize. So the door he opens depends on your initial pick. If the prize is behind #1 and you initially choose #1, Monty can open up #2 or #3. In fact this is the only arrangement that will cause you to lose by switching. Pick door #2, and he must open up door #3 only. Pick door #3, and he must open up door #2. In the last two cases, the other door that was still closed hides the prize. Think of it this way: when you first pick, there's a 1/3 chance that your door hides the prize. Play the game 3000 times, but stay with your first choice each time. You'll win in about 1000 cases. That means you'll lose the other 2000. Now if you switched every time, you'd win 2000 times and lose 1000 times, plus-or-minus a few in each case. You certainly couldn't expect to win 1500 times by staying.
-CausticPuppy "Of all the people I know, you're certainly one of them." -Somebody I don't know
You are correct in stating that the order doesn't matter. However, the outcomes that you are listing are not equally probable.
The rest of this post is left as an exercise to the reader.
You could think of the players as being tagged, and the info available to each player being: Al's hat is red, Betsy's hat is blue, and so on...
Shameless plug: see my solution for the general case using Hamming codes.
Your construction does not generate a valid Hamming code, for reasons I'll get to in a minute. I haven't given this much thought, but I suspect that the two facts I listed in my post do not completely specify Hamming codes, i.e. there might be non-Hamming codes that meet those criteria. However since the proposed strategy fails for precisely those hat assignments that are associated with codewords, improvement over the Hamming code can only be achieved if a code with fewer than 16 codewords meets those criteria. (By "improvement", I mean a higher percentage of hat assignments that result in a reward for the team).
On why your construction does not represent a valid Hamming code: Hamming codes are linear codes, in that the bitwise, modulo-2 sum of 2 codewords is also a codeword. In particular, the sum of a codeword with itself must be a codeword; but that sum is always the all-zero word, because addition is modulo-2 (an XOR). So the all zero word is a codeword. Taken with Fact 1 of the previous post, this means that words with a single 1 in them are not codewords in a Hamming code.
The general definition of Hamming codes is in terms of matrices. However, the n=7 case is easily described in terms of parity check bits. Call the first 4 bits i1 through i4--these are the information bits. Call the next three bits p1 through p3--the parity bits. To construct the Hamming code take the 16 four bit sequences formed by i1 through i4, and append the 3 parity bits generated according to the formulas: p1=i1+i2+i3, p2=i1+i2+i4, and p3=i1+i3+i4, where all additions are again modulo 2.
The general construction of binary Hamming codes of length n=2^k-1 specifies the contents of a matrix G with n rows and n-k columns, from which the codewords may be generated by the matrix multiplication Gv, where v is any length n-k column vector. The structure of G is fairly simple, but a little too much trouble to specify in HTML, so I'll just refer anyone interested to any coding theory text.
For those wondering, Blahut(*) defines a perfect code as "one for which there are equal-radius spheres about the codewords that are disjoint and that completely fill the space." In our case, that radius is of course, 1.
As an aside, I haven't given any thought to showing that the Hamming code strategy is optimal...ideas, anyone?
(*) R.E. Blahut,"Theory and Practice of Error Control Codes," Addison-Wesley, 1983.
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:
- Neither w0 nor w1 is a codeword
- w0 is a codeword
- w1 is a codeword
Cases 2 and 3 are mutually exclusive because of Fact 1. My strategy? That's it. This strategy will result in the team winning every time the word associated with the hat assignment is not a codeword, which happens (128-16)/128=7/8 of the time.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^k-1. The players will succeed if and only if the associated word is not a codeword. A Hamming code of length n=2^k-1 has 2^(n-k) codewords, so success is achieved 1-2^-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!
This puzzle comes from a paper by James Aspnes, Richard Beigel, Merrick Furst, and Steven Rudich. Attribution: I got this information from my friends on Mattababy.
How about this solution which works 100 percent of the time? I don't see why this isn't a solution.
It isn't a matter of who is right. The challenge is making sure no one is wrong. Reread the challenge.
Since the three player game offers a 75% win rate, that would obviously be the minimum, since the team, if unaware of a better strategy, could always pretend it's the three player game (players 4-n always pass and are ignored by the first three).
It's even more interesting if you follow the rules of the problem. There is no "first speaker."
If they can talk to each other, then why not just say "Hey buddy, your hat is blue."
Because the guy behind him didn't.
Minimum must be 75%, since that's what the three hat game yields, and all games can be played like the three player version (all other players are ignored.)
uh, the player 3 guessing red thing reduces your chance of success to %50. remember, they all have to guess at the same time.
-Spazimodo
Fsck the millennium, we want it now.
Fsck the millennium, we want it now.
Millennium Crisis Line: 0890 900 2000 [calls cost 50p/min]
He's discussing a solution to a different problem. The article's problem has 2 colors only and every one answers at the same time. His problem has 'm' colors and every one answers in sequence
Semper Ubi Sub Ubi
You're color blind?
There is no correlation from one person to another, and therefore the probablility of guessing correctly is merely 50%. Each hat is determined by an unrelated coin flip, and therefore the guesses are unrelated. The probability of one flip getting a red hat does not affect the probability of the color of the next. Don't think in terms of three's, think in terms of infinite flips. It all evens out in the end, and the pattern is completely random.
Not really. Always got A's in math. Sigh. Coin flip arguements...
you can still always win if you pass when you see 2 hats of the same color. even if they are ALL the same color. ex. I see 2 red, so i pass, next person sees 2 red, BUT they also know that i passed. Now they know that i saw 2 hats of the same color. If 2 people pass then they know that all the hats are the same color.\ =\=\=\=\
=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=
you can still win 100% of the time. (click my userinfo and read my other post to see how)\ =\=\=\
=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=
They can still pass though, acording to your quote. If they decide to pass then they they will know that they all have the same color.\ =\=\=\=\
=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=
you don't get me, player 2 would know his color once player one passes. Knowing that player 1 saw 2 different colors means that what player 2 must have the opposite color of player 3= \=\
=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\
Player 2 sees RR - doesn't know if Player 1 passed because he saw RB or RR. /blockquote)
you get one piece of information from each person who passes. If there are 3 people you can alway know after 2 people pass. But this is all a moot point anyway because someone else just pointed out to me that the rules say that they must all guess at the same time.
\ =\
=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=\=
Evan - needs to hit preview before submitting
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.
Evan - needs to hit preview before submitting
Not true. Picture this.
Of course, this is an specific example where the first to guess must have a hat of different color from the other two. And, everyone must be aware of (2). But in this specific example, it's better to give the answers in sequence.
--
This space left intentionally blank.
Don't those two conditions imply that the code is perfect? There are only a few families of perfect codes. I suppose there might be nonlinear codes meeting those conditions (eg. the set of words w for which w + c is a Hamming codeword, for some fixed nonzero c). I can't find my coding theory textbook, so I'm not sure; it's been a while since I thought about this stuff.
- The group has agreed to a strategy ahead of time.
- Only one needs to be right - the rest of the group can pass.
- If they are all wrong, they are not penalized any more than if only one of them were wrong.
50% of the time each individual's answer is wrong (as expected) but the group is wrong only 25% of the time.The Playboy has a nice article about lead ball and birds feather
problem which become quite popular among physicists.
You have lead ball and birds feather and drop them down from high
tower. Which one will reach ground first?
Think about it - it's an interesting puzzle.
A few weeks ago there was a problem of the week here at macalester that asked the same question. A friend of mine had done quite a bit of actual thought into actually encoding the other wizards. It just so happended that I was able to offer a small bit of insight into the problem that allowed us to solve it together. (I actually turned the solution into some mathematica code when I was bored).
Regardless of the arrangement of the people with hats, as long as you have a finite number of colors, there can be modular arithmetic done that would guarantee all but one (the first speaker) success, and even that first person would have 1/number of colors chance in getting their hat correct.
I don't know, it's an interesting problem, but not really that difficult.
Yes I agree more articles on mathmatical theory and more duct tape for Jon Katz mouth.
Rats! Someone already posted the answer. I guess my hours of looking through old Playboys to find the answer was just a waste of time ;-)
--
dman123 forever!
--
dman123 forever!
Filtering out the -1s and 0s since 1999.
The rules allow for a strategy to be planned in advance of the hats being worn. According to the solution in the article, either 1 person will guess or all 3 will guess. There is no possibility of no one guessing or exactly 2 guessing (according to this specific solution). We must assume that the players are actually following their predetermined strategy.
--
dman123 forever!
--
dman123 forever!
Filtering out the -1s and 0s since 1999.
yep, you are missing something, thats communication and no communication is allowed. afaics they discuss strategy beforehand, they go into their separate chaning rooms where a randomly coloured hat gets placed on their head. they walk out, look at each other and then answer at the same time, the answer being red, blue or pass.
:)
this waiting and then answering depending on what you see stuff is still communication as far as I am concerned
dave
this doesn;t work cos the maths is backwards.
:)
they initially paid $10 each for the room, or $30 in total. the woman came and gave them back a dollar each so that the new figures are that they paid $9 each or $27 on total. however of that $27 dollars, the room cost $25 and she kept $2. you're adding instead of subtracting.
all I can say is that I hope they good decent room service
dave
This strategy allows 3 players to always win. Before hand they agree that if ANY player sees that the other two have different coloured hats, that player would pass. The other 2 players would immediately know that their hats had the opposite colours, and since they can see the other player they know what their colour is.
If NO ONE passes, that means that all players have the same colour hat. A simple 30 second solution. This strategy can also be expanded to any number of players as long as they divide themselves two groups - one group with three people and the other group with everyone else.
Can I have my award now?
Revolution = Evolution
Not sure you read the rules of the puzzle correctly. If any of the players guess incorrectly, they all lose. So, player 3 will be wrong about 50% of the time, never mind players 1 and 2.
Gentoo Linux http://gentoo.org/
I dont know - makes a change from paranoia and linux.
Why does their x.0 releases always suck?
--
Je t'aime Stéphanie
The rules of the game are about the collective guesses of the team (at least one right guess and no wrong guesses), not individual guesses. And players can pass. The correct strategy can cause all three players to guess wrong together 25% of the time, while the remaining 75% of the time one player will guess correctly and two will pass, something like this: X=Wrong, +=Right, -=Pass Trial: 1 2 3 4 P1 X + - - P2 X - + - P3 X - - + The number of right guesses is the same as the number of wrong guesses, but they still win 75% of the time. This is because the strategy helps tell the players when they ought to pass instead of trying to guess at all.
The rules of the game are about the collective guesses of the team (at least one right guess and no wrong guesses), not individual guesses. And players can pass.
The correct strategy can cause all three players to guess wrong together 25% of the time, while the remaining 75% of the time one player will guess correctly and two will pass, something like this:
X=Wrong, +=Right, -=Pass
TrialNo: 1 2 3 4
Player1: X + - -
Player2: X - + -
Player3: X - - +
The number of right guesses is the same as the number of wrong guesses, but they still win 75% of the time. This is because the strategy helps tell the players when they ought to pass instead of trying to guess at all.
perhaps i'm being dense but can someone detail how this affects / solves real life problems?
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.
It goes down. The block in the boat displaces the same mass of water as its own mass. The block on the lake floor displaces the same volume of water as it own volume. Concrete is denser than water, so the sunk block displaces less water than the floating one.
Athletic Scholarships to universities make as much sense as academic scholarships to sports teams.
How funny, my wife just go back into the game "Mastermind" where you pick four colored pegs and the other player gets ten tries to guess the colors, with a minimal amount of feedback in the form of red and white pegs that indicate if you have chosen just a correct color (white) or correct color and position (red).
second society
Well, there's the exception where everyone has a blue hat, in which case the no one answers until the last guy and since he automatically says "red" he automatically gets it wrong. So your method fails exactly when all the hats are blue. Not a bad result, but here's a small patch: If the first guy sees only blue hats he has to take a blind guess. Sure, his chances are only 50% but if he followed your rules that turn would be lost inevitably--so this patch cuts the error rate of your method in half.
Well, it's possible we both misunderstood the problem, because this is just too easy... But whatever. So this might be a good solution to a different problem.
Spork
First person adds up all the colors on hats that aren't his own. If the sum is an even number then he guesses "Red" and if it's odd he guesses "Blue". This is, of course, not an informed guess and he might be toast...BUT:
Now everyone else knows what hat they are wearing: They just add up all the hats they see except the first guy's. If they get an even number and the first guy said "Red" they know their hat is red. If he said "Blue" then their own hat is blue. Likewise, if their sum is odd, each person has to say the opposite of what the first guy said... But they are guaranteed to be saved.
Wait... I'm confused...
There is something other than Red Hat?
---Lane
What's the point of moderating?!
Here is an alternate hat problem I heard from Everest Huang who heard it from Matt Secor:
Ten people are in a line so that each person can only see the people in front of him. God puts either a red or blue hat on each person. No one is allowed to look at their own hat but can see the hats of all people before them. Each person is allowed 1 guess at their own hat color. If they get it right, they live, otherwise they die immediatly. The person in the back of the line who can see the other 9 people guesses first and the guesses go on down the line.
Question: If god is malicious and places the hat colors to kill the maximum number of people, how many can you save? You can easily save 5 as follows: person 10 says person 9's hat color possibly killing person 10. Person 9 now knows his hat color and says it so he lives. Person 8 says person 7's hat color and possibly dies. Person 7 knows his hat color, says it and lives, etc. In this scheme, all the even numbered people die and the odd numbers live so you save 5. Can you save more?
If x is the answer then
echo x | md5sum
will return
7c5aba41f53293b712fd86d08ed5b36e -
That's right. What's funny about this whole thing, is that my dad, who has been in the concrete business for 20+ years figured it out while me, the network engineer and my brother the CS major and Math minor couldn't figure it out. Goes to show you where I'm at I guess.
Thanks for the reply.
Of course, that's just my opinion, I could be wrong.
The problem is in the wording. It leads you to try and find the wrong solution. Oh well, such is life.
Of course, that's just my opinion, I could be wrong.
Although it's not near as complex, as a mind such as mind can't handle such things, it is kind of cool.
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.
Of course, that's just my opinion, I could be wrong.
In reality, when faced with this situation and a possible prize, people will tend to second guess themselves, somehow deciding that the other choice might be more likely to be correct since they didn't remove it... no logical sense, but logic doesn't always play a big part in a swift, nervous decision.
Well, I was doing this hat problem for more users than three, and I came across something interesting....
:)
The whole gist of this puzzle is to find out if there is a number of hats, red or blue, that is more prominent in random simultaneous flipping than others. To get this, you have to add up the number of red and blue hats in each entry of the possible combinations. For example, with 3 people:
rrr -- 3 r's
rrb -- 2 r's
rbr -- 2
rbb -- 1
brr -- 2
brb -- 1
bbr -- 1
bbb -- 0
total number of combinations that have 0 r's:
1
total number of combinations that have 1 r:
3
total number of combinations that have 2 r's:
3
total number of combinations that have 3 r's:
1
See anything familiar? Try the same with 4 people, you should get 1-4-6-4-1. And for 5, you should get 1-5-10-10-5-1. Fibonacci's sequence! It shows up so often in so many places...
I know we also have to deal with the blue hats in this hat problem, but the Fibonacci sequence directly relates to it, and can help for finding the best way to choose when there are, say, 20 people.
The choice of which to remove was not arbitrary -- there is information in it. Switching means that you will be right 2/3 of the time because you will be right *unless* your initial guess was right. Staying with your original guess X doesn't change the fact that there was only a 1/3 chance of X being right in the first place.
;)
Trust me, I'm a mathematician
It should say OK.
How about this (I'm not positive about the additional rules of the game, so this may not be a viable answer) but here is what should happen -
:)
The three people walk into the room. The first person to notice that the other two are wearing different color hats passes. Then the person to their left looks to the other person and guesses the opposite color hat. If no one passes, someone just blurt out the color of the others hats.
That should get it about every time
Revelations 0:0 - The begining of the end.
How come the problems I encounter at work aren't nearly this interesting! My problems are typically as complex as, "Gee, should the GUI button say OK or Okay?".
No wonder custom business software is often over engineered. We're bored to death with mundane business logic!
For some reason one of our Chinese chemists was taken by the 3-of-5 hat puzzle a couple of weeks ago. A full truth table is unnecessary. If you think of "rounds" as the 3 realize lack-of-response by others is information, you can solve it from a participant's-eye-view. And by symmetry, reasoning applied to 1 unspecified person holds for any hence all. There's an extention in which 1 of the 3 people is blind and he can still solve it!
Fred Durst of Limp Bizkit know about this blantant Tradmark infringement>>>
I'd also like to see solutions for the 7 hat version.
My guess is that seat positions would come into play, but i'm not sure how yet, or even if that can work.
I mean lets say there's 4 red and 3 blue.
4 see it 3-3, and 3 see it 4-2
but if it was 5-2, 5 people would see it 4-2.
Seeing it split 4-2 wouldn't seem to help much if everyone guessed something each time they saw it. Other than knowing that its probably 4-3 35/64 times rather than 5:2 21/64, so guess blue if u see 4r and 2b, and pass if you see 3/3 ???
This would mean, you'd always lose when the outcome was 5/2. Similarly, if you see 6 of one colour, guess the opposite. So you lose whenever its 7/0, but win 6/1.
This strategy wins 42/64 times. The article suggests there's better, but its not easy to see.
What if, you don't make a guess as long as you see people with your minority colour to the left (numbering players 1-7, and putting them in a line). So if you see 4-2 from seat 3 or 4 (with 2 minority colours in seat 1 and 2), you pass, but this gives no info to the later seats since they don't know if you passed because you saw 3-3 or not... but if seat 7 sees 4-2, can he assume 3 and 4 also saw 4-2, and call it 5-2? it doesn't work... sorry for thinking aloud.
how can you get better than 42/64?
thanks for posting.
so you can choose your codewords any way you please?
I seem to be able to make more than 16 if I:
use the 7 numbers with a single 1 in them
the 7 with a single 0
There's more than 2 numbers with 3 1s and 3 0s in them ?
Yes, they have to answer simultaneously. Answering in succession would constitute communication between players, which is disallowed.
How about this solution which works 100 percent of the time? I don't see why this isn't a solution.
Say the three people are A B and C. The three of them agree ahead of time to this method.
A will say the color on B's head.
B will say the color on C's head.
C will say the color on A's head.
If you break this out to all possible permutations you get the followin results:
ABC = Result
BBB = They all are right
BBR = A is right
BRB = C is right
BRR = B is right
RBB = B is right
RBR = C is right
RRB = A is right
RRR = They all are right
I did just before I read you message. You are right. I do think it is an interesting solution to the wrong problem.
...and they won't have to worry about the color of their hats.
rrr
rrb
rbb
bbb
That is to say the rrb=rbr=brr as in all cases there is only one blue hat. I could very well be wrong here, but could someone explain why? Cause I just knocked our chances of winning back down to 50%!
I finally got it! I'd been trying to explain the apparent fallacy that based on the colours of the other two hats, you can guess your own.
Here is how things break down from a single person's point of view:
Hence, 75% of the time, you (as a group) will win.
--
Accountability on the heads of the powerful.
Power in the hands of the accountable.
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 post.
Also, I was saying there is no way to guarantee a win - in other words, have zero probability of failure.
--
Accountability on the heads of the powerful.
Power in the hands of the accountable.
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.
--
Accountability on the heads of the powerful.
Power in the hands of the accountable.
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.
--
Accountability on the heads of the powerful.
Power in the hands of the accountable.
In the article, in the 3 hat case, they've got a 75% chance of winning (their solution generated a loss if all 3 hats were the same color). I've managed to come up with an 87.5% chance of winning, instead:
Player 3's strategy will be to always guess 'red'.
Player 2's strategy will be to guess 'red' only if Player 3's hat is 'blue'. Otherwise, Player 2 passes, knowing Player 3 will win.
Player 1's strategy will be to guess 'red' only if Player 2 and Player 3 both have 'blue'. Otherwise, Player 1 passes, knowing Player 2 or Player 3 will win it.
The only time this solution will fail is the case where all three hats are blue. This occurs 1 out of 8 times (12.5%).
In the 15 player case mentioned later on, the article claims they've got a situation that works 15 out of 16 times (93.75%). Using my method above, it should work 99.99% of the time.
In the immortal words of Joel Hodgson, "What do you think, sirs?"
If you take another peek at what I wrote, player 1 arbitrarily chooses 'red' if he sees both player 2 and player 3 with 'blue' hats. Him choosing 'red' should be the same as a blind guess -- he wins 50% of the time. However, I chose to hardcode his guess into the algorithm so that it made things easier to conceptually analyze (BBB would be the only losing case).
Under your patch, they'd win half the time when it was RBB and half the time when it was BBB, which should come out the same as winning mine where they win all the time as RBB and none of the time as BBB.
Also, by making each arbitrary guess 'red', it makes it really easy to code an algorithm for the guesses, since each person uses an identical thought process:
If someone after me has a red hat, I will pass to them so that they may win. If no one after me has a red hat, I will guess red.
Well, it's possible we both misunderstood the problem, because this is just too easy... But whatever. So this might be a good solution to a different problem.
That is, indeed, the case. The thing we've missed is that the players must answer simultaneously, so player 3 can't predicate his answer on the fact that player 1 and player 2 failed to answer. Personally, though, I had enough fun fiddling with the non-simultaneous case, even if it isn't as mathematically significant.
everyone take off their hats and look at them :)
.... that defeats the question.
Oh wait
I am
...is that the 'mud' puzzle relies on all the boys reasoning correctly and quickly.
Based on the evidence of their eyes none of the boys can reliably argue they have or have not mud. Once the winning boy sees that neither of the other boys has worked anything out he ASSUMES that it is because he (winner) has mud on his head. However that is a good bet rather than a proof. The other boys could be poor logicians or just slower than him.
So the mud puzzle has a 'best bet' answer based on some difficult to quantify factors (the other boys' abilities), whereas the hats problem has a answer which has a probability of success you can calculate absolutely.
You are right. This is the classic thing most people struggle with when they study probability - the difference between the probability of the next in a series of mutually exclusive events versus the probability of the group of events seen as a whole
True story - when I was studying Maths at University we had a lecture on this - the example was rolling dice. A single roll always has the same probability regardless of what you just rolled. On the other hand the probability of rolling say 3 6's in a row is a different thing.
That evening I was playing Monopoly with some friends. One guy, Richard - Business & Marketing - had a strange habit. He asked to be allowed to 'nominate' his dice roll, he would roll the dice several times and then say 'OK the next one counts'. He was convinced that if he had rolled a series of low scores the probability of a high score was greater!
I started off thinking I could just explain his 'simple error' to him. Later, frustrated I was just begging him to trust my word as a Mathematician. Never under-estimate the power of competitive spirit!
We never finished the game...
So if this puzzle appeals to you and you like a bit of math, you can go read the paper over lunch :-)
"The Crystal Wind is the Storm, and the Storm is Data, and the Data is Life"
It's been a while since I've played with finite math, and a lot of it's been forgotten, however this seems to defy the nature of random odds. i.e. Am I incorrect or is this based upon the supposition that by looking at the other draws you can base conclusions on your own (which of course defies the nature of random odds and is a common fallacy).
Excellent question and I'm very curious myself. It would seem to me that the success rate would drop dramatically as the sample set got larger, yet the article seems to indicate differently : i.e. that it actually gets MORE accurate as there are more "players". Odd.
Perhaps somebody could enlighten me about the Monty Hall problem, aside from it being offtopic.
.5. Switching your guess does not benefit you. What am I missing here people?
According to my understanding of the problem, you have 3 choices with only one correct choice. After you choose, one of the 3 choices(not yours) is shown to be incorrect and removed. You now have the option of changing your guess. The option of changing your guess completely redefines the problem! The probability of you picking the correct answer is no longer based out of 3 choices, but out of 2! Since an incorrect choice was removed from the 3, that leaves a correct choice and an incorrect choice. The 3rd choice is now completely and utterly irrelevant and devoid of the problem. It never existed! It is not a possible choice! The problem, once an incorrect choice is removed, is now based on 2 possible choices. One is right, one is wrong. The probability of you having originally picked the correct door is
i'm not going to check your work here, but i thought i'd point out there are several solutions to this problem (that i know of) and i wouldn't be surprised to find more.
Yeah, ever since i shared this one with the CTO we've used it in the developer interview process.
Can I see the perl code?
--
Why shouldn't I solve this three hat problem? That a tough one, but I'll take a shot. Say I'm minding my own business and somebody puts this three hat problem on my desk, something nobody else can break. Maybe I take a shot at it, maybe I solve it. I'm really happy with myself, because I did my job well. But maybe the solution to the three hat problem was the location of some rebel army in North Africa or in the Middle East and once they have that location they bomb the village where the rebel army is hiding. Fifteen hundred people that I never met, never had no problem with, just got killed. Now the politicians are saying "Oh, send in the Marines to secure the area," because they don't give a shit. It won't be their kid over there getting shot just like it wasn't them when their number got called because they were pulling a tour in the National Guard. It'll be some kid from Southie over there taking shrapnel in the ass. He comes back to find that the plant he used to work at got exported to the country he just got back from, and the guy that put the shrapnel in his ass got his old job, because he'll work for fifteen cents a day and no bathroom breaks. Meanwhile he realizes that the only reason he was over there in the first place was so we could install a government that would sell us oil at a good price. And of course the oil companies use the little skirmish to scare up oil prices. It's a cute little ancillary benefit for them, but it ain't helping my buddy at two-fifty a gallon. They're taking their sweet time bringing the oil back, of course, and maybe they took the liberty of hiring an alcoholic skipper who likes to drink martinis and fucking play slalom with the icebergs. It ain't too long until he hits one, spills the oil, and kills all the sea life in the North Atlantic. So now my buddy's out of work, he can't afford to drive, so he's walking to the fucking job interviews which sucks because the shrapnel in his ass is giving him chronic hemorrhoids. Meanwhile, he's starving because any time he tries to get a bite to eat the only Blue Plate Special they're serving is North Atlantic Scrod with Quaker State. So what did I think? I'm holding out for something better. I figure, fuck it. While I'm at it, I might as well just shoot my buddy in the ass, take his job, give it to his sworn enemy, hike up gas prices, bomb a village, club a baby seal, hit the hash pipe and join the National Guard. I could be elected President. --From "Good Will Hunting" (Matt Damon's character speaking to an three hat problem poser, in a heavy Boston accent)
You can also play an open-source non-JavaScript Monty Hall simulation and see the aggregate results for everyone who's played.
Since there's no benefit to switching, why don't you play my Monty Hall simulation a few times choosing to stay with your original choice. Most people choose to switch, and I need more numbers on the "stay" side to make it statistically significant.
In addition to its similarity to the Monte Hall problem, the 3 hat problem bears a remarkable similarity to the "restricted choice" problem in bridge http://www.rpbridge.net/4b73.htm. All are applications of conditional probability arguments.
So if the concrete block weighs as much as a duck...
A witch!!! Burn it!!!
I take drugs seriously.
And you don't have to register with them to see the problem! (I hate NYT.) http://www.greylabyrinth.com/Puzzles/puzzle007.htm
- Jodiamonds
One person is set as the check bit. He is the first to answer. He answers pass in under 10 seconds if there is an even numnber of red hats over 10 if there is an odd number of red hats. Then each person from then on out counts the red hats and and if it is suposed to be even, and he counts odd then he is a red hat, if it is suposed to be even and he counts even then he is a blue hat.
As x approaches total apathy I couldn't care less.
In response to your sig line, both ships worked great until they were run into solid objects by their captains. Seems unfair to fault the shipwrights, no?
Virg
"// this is the most hacked, evil, bastardized thing I've ever seen. kjb"
I think you changed too much from the original problem to claim 100% accurate guessing. The guessing needs to happen at once, without the advantage of "turns".
In your game, if the first person sees the same color hats on the other 2 guys, what does he use to guess 100% accurately his hat color (because passing would indicate different color hats to the other guys!)???
Silly Rabbit: tricks are for kids.
Next the article is an interesting read and so is the solution to the problem, but I still have this doubt whether it was not one of the April fool jokes played around the world, or else the application of the theory of probability should have been simple enough. But then I am no mathematician and what may seem obvious to me may not be so obvious afterall.
There's always sufficient, but not always at the right place nor for the right folks.
The problem is quite obvious with 3 persons but it really gets tricky with more people because if the colors you see on your screen are not all the same, then this strategy does not work any more. You will not only have to calculate the probabilities that your hat is red or blue, but also you will have to make up your mind as to whether to hit pass. Perhaps setting a minimum level of probabilitiy will help like if out of 10 persons, you see that 8 of them have red hats, you are really entitled to hit the blue button whereas if 4 of them wear read hats, then you really should hit pass. That's the whole problem.
However, I don't understand how this would have more applications...
É que os desafinados também têm um coração
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? =)
First, I'll point out again that all three players must answer simultaneously. But just for a minute, let's change the rules where players can answer in succession. What then does your strategy get you? So the first person passes if she sees two red (or two blue). What if the other two hats are different? Pass? This won't give the other two any information then, since the action is to pass in either case. Or will she take a guess? Chances of success are 50/50 in that case.
I'm making a
The link given didn't require any registration when I went to read the article. I only wished they had explained how the hamming codes were used. IIRC hamming codes depend on ordering to do their thing.
Slow news day, huh guys? :-P
---
evil adrian
I don't see why the article claims they can win only 75% of the time....am I missing something here?
Yes, you are. They have to guess simultaneously.
if I'm losing money, but not losing as much as I thought I was, and do plan to make more eventually, I must tbe wearing a RedHat
More fun
Dancin Santa
If played strictly without passes, actually anyone still has 50% no matter what, no matter what colors he sees.
It's the old misthought people have when playing roullete. Even if after 1000 rounds the number 20 has not showed up, in the next turn it is not any more probable than usual.
Why should the color of my hat depend on the colors of two other people? They are all thrown equally.
The hat's are likely to confuse thoughts, make it simpler take dice's in example. If I throw 3 at the time, do they depend on each other? Nah, all combinations have equal chances.
Take the hat's again, say if another two pwople with another's two ramdon hats are behind a wall, and i cannot see them, thus the chances of my hat color differ on the colors of theirs?
--
Karma 50, and all I got was this lousy T-Shirt.
When i read the puzzle another problem which give the same answer under a certain condition visualized in my mind.
:). I have no clue how real error correction work i just keep getting all these wierd ideés. Sorry.
:).
This is the case:
You have got three diskdrives. You store the same data on each drive. You know that correct sequence always should be 000 or 111.
Given that the possibility of error on every single drive is 50% there is no way to know if 000 or 111 is the correct sequence. Since a drive cannot trust its own data it can only look on the other two drives to decide if its data should be o 0 or a 1. If the other drives have conflicting data e.g 01 or 10 no choice can be made. And conflicting data should turn up in 50% of the cases.
This tells me those 2 cases(000,111) you are not able to get a better ration than 50%.
An intressting thing to do is to extend this problem is letting every disk know its own error ratio( eg. A person knows that he has a 60% chance of getting a blue hat and 40% chance of getting a red hat). How does this effect the equation. Then we can add the parameter time.
Lets repete the problem over and over again and each time lets each disc recalculate it's own error ratio. After some time the system should reach some kind of optimal error correction state for this hardware. Well in the real world we should have a controller that have all this input:
Total checks = 1000
Disk1: data=0, error_ratio =0.05 (errors 50)
Disk2: data=1, error_ratio =0.1 (errors 100)
Disk3: data=0, error_ratio =0.01 (errors 10)
The controller fixes the error on disk 2 and recalculate the error ratio. Well it gets more interesting with more disks.
Sorry this is becoming really of topic, it might even be stupid for what i know
But posting this might give someone else some wierd ideés
Well if you can indicate to one another. why not possition the other players to your right if if their hat is red and behind you for blue or look right red back (roll Your Eyes Back) for blue
red!... no wait... blue! er, no, red...
You have stated a somewhat similar strategy to the one that they came up with in the article. However, you must realize that there is a condition to the game which you are omitting: "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."
Your solution can lead to 100% success, *IF* the players can guess in succession (this eliminates ever losing when the hats are all the same color). However, since the rules of the puzzle state that all three must guess at the same time, the cases where all the hats are the same color inject the possibility of them all being wrong. Hence lowering the probability down to 75%, or whatever they came up with. To show how they would be wrong with your strategy: if all hats are same color, and all players must guess simultaneously, all three would say 'pass' (since each one sees the other two wearing the same colored hats). Since no one guessed correctly, no one wins.
The article is a little funny with its wording when it says the following: "The group can win every time this happens by using the following strategy: Once the game starts, each player looks at the other two players' hats. If the two hats are different colors, he passes. If they are the same color, the player guesses his own hat is the opposite color." This makes it sound like they are guessing in succession, when in reality this is the strategy chosen and executed concurrently among all the players to maximize their chance of winning.
Yes, actually I did major in Comp Sci for my first few semesters.
Just for fun, I ran the program overnight with 200,000,000 cases. The percentages were even closer to 75/25.
I realize that this method wasn't completely rigorous. With all of the arguments for and against this method, I just wanted to check to see if the methodology held up in a "(simulated) Real World" scenario.
--
Home is where you hang your @.
I tried to post the source to /., but formatting problems got in the way. So, if you'll contact me directly (at the above address), I'll be happy to send you a copy of the source. And, no, I don't have a home page right now, so I can't post it for you to download.
--
Home is where you hang your @.
Out of 100000 tests:
75093 (75.093%) resulted in success.
24907 (24.907%) resulted in failures.
Seems pretty obvious to me.
--
Home is where you hang your @.
This made me curious for the 7 hats case. According to the article, since the number of hats is a power of two minus one (2**3 - 1), they claim there is a strategy that is succesful for 7 out of 8 times played. Ok, let's have a look.
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.
My karma ran over your dogma
The error is in the math process: Start with the $30 paid to the hotel. The boss takes $25 of them, leaving $5 to distribute between the woman and the 3 guests. The woman takes $2, leaving $3,and gives $1 to each one of the three guests, which adds up to the $3. QED
- Make it idiot-proof, and someone will build a better idiot.
Check this old article at the Amazing Randi site. The hats are different colours but I think it is the same puzzle. He usually has a great riddle or puzzle every week.
i don't do the nyt reg, but this sounds like the problem when a row of prisoners is lined up and can see all of the people in front of them (and their hats). they can discuss a plan the night before, but they can not say anything but a color once the hats are put on. the gaurds also tell them what the possible colors are. also, everyone can hear the answers from the people behind them. even when it is expanded to n people and m colors (with mn) only one person will die with the best algorithm! it took me about ten minutes to figure out after i was told what the best possible outcome was...
THE ANSWER: (SPOILER!!)
1) each color is given a number (alphabetically to remove the ambiguity) from 1 to m
2) the first person adds up all of the colors in front of him modulo m. he will likely die (especially with a lot of colors)
3) the second person adds up all of the people in front of him modulo m. he then subtracts this from the color the first person said. (if it is negative he adds m) this gives him the color on his head.
4) the nth person subtracts the sum of all of the previous n-2 people's answers modulo m from the first persons response, and adds m if necessary, to get the color on his head!
this is one of the coolest math problems i have ever heard. does anyone have some more alone the same vein?
that doesn't necessarily work for ANY number (greater than 4 or otherwise). ALL OF THE HATS CAN BE THE SAME COLOR!!! think about it. you want to garauntee that people get it correct, not have a certain probability of it...
"Three-fourths of the time, two of the players will have hats of the same color and the third player's hat will be the opposite color. The group can win every time this happens by using the following strategy: Once the game starts, each player looks at the other two players' hats. If the two hats are different colors, he passes. If they are the same color, the player guesses his own hat is the opposite color."
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.
--
324006
You're right. Each person will guess correctly 50% of the time. BUT, look at this table. The first letter represents the player's hat - (R)ed or (B)lue, the second the player's guess- (R)ed, (B)lue, or (P)ass, and the third the result -(T)rue, (F)alse, or nothing (X).
PL1 PL2 PL3
RRF RRF RRF
BBT RPX RPX
RPX BRT RPX
BPX BPX RBT
RPX RPX BRT
BPX RBT BPX
RBT BPX BPX
BRF BRF BRF
As you can see, each player guesses wrong twice and guesses right twice. 50%, as expected. But the group wins every time except for the first and last, 75%.
That's now a part of my experience, and maybe the next time I'm faced with a novel problem that seems perfectly obvious, I look a little more closely, thus increasing my chances of finding an optimal solution.
An aikido instructor once said, "When I first started aikido, I was frustrated with all the theoretical stuff (awareness, focus, etc.). I wanted to get to the practical stuff (punching and kicking). But I finally realized that the theoretical stuff helped me enormously in everyday life, while the practical stuff was virtually useless."
Example:
Four men are buried in the sand all facing East. Between the front man and the man behind him is a 10 ft high brick wall.
Each man is given a hat. There are four hats in total, 2 are black, 2 are white. If a man guesses his hat colour correctly, all are free, otherwise all are beheaded. After a few seconds, the middle man of the three behind the wall shouts out the colour of his hat correctly. How did he know?
For more examples of hat problems, see this URL.
Free unix account: freeshell.org
players must simultaneously guess the color of their own hats or pass
Sorry, the article says nothing about multiple rounds, no one can be wrong and at least one person must be right.
Help find a cure for cancer!
- Guess blue, saw 2 reds (which works
.5 of the time)
- Guess red, saw 2 blues (also works
.5 of the time)
- pass, saw one of each.
You only fail when you are red, and see 2 reds or are blue and see 2 blues. The probability of you failing is equal to the probability of everyone being the same colour (.25). The probability of succeding equals 1 - probability of failure (1 -Help find a cure for cancer!
That is true if you had no other information. However, you do have other information in the form of knowing the odds of a particular set of hats being chosen, and that is what is being used here.
Dance like no ones looking and love like it's never going to hurt.
Very cool.
--
The probabilities are the same whether the coins are tossed sequentially or simultaneously. I don't know where you got the bizarre idea that they aren't. A basic concept of probability is that independent probabilistic events such as coin tosses are not affected by past results.
You can't change the probability of any individual guessing the correct hat, which is always 50%, but by choosing the proper condition of when to guess a certain answer you can concentrate the probability
In the winning method with 0.75 probability win, all players still guess wrong 50% of the time they guess, it's just that all wrong guesses are packed into one game where they don't do any extra harm, while the right guesses are spread out to a maximum one per game.
--
This is how the concrete block in the boat was displacing water in proportion to its mass, obviously (which it equally obviously would no longer do once in the water). It was covered in the original post.
--
Assuming typical lakes, boats, and blocks, any difference in lake level caused by an action on the boat or block will be unmeasurably small, so we can assume it will remain effectively unchanged.
--
What if the strategy were as follows: Each person goes into the room and decides to wait 30 seconds before saying anything. Then whoever sees that the other two people are wearing the same colored hats, they will say "pass". If two of them say pass, the third one will know the color of his own hat. This covers the case of three hats being the same color. If the hats are dispersed in a 1-2 relationship, then that one person will say pass...nobody else will and the next two people can guess by looking at each other. This seems like a pretty obvious solution to get a 100% chance of winning and is basically the first thing that popped into my head...I don't see why the article claims they can win only 75% of the time....am I missing something here?
"The Cube": it just wouldn't be the same without fellatio "Corey Kosak": It just wouldn't be the same... oh, looks like
Forgive me for reordering your matrix: 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.
--
Yes, the nick is flamebait
If there are seven players, what is my strategy? Do I guess Red if I see 4 blue hats? If I have to see 6 blue hats then we will pass almost 90% of the time. And why isn't this under the Red Hat topic?
--
Yes, the nick is flamebait
Forgive me for reordering your matrix:
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.
--
Yes, the nick is flamebait
Let's look at the rules for this. 1. All guesses must be simulatneous. All players must guess or decline to guess at the same time. 2. At least ONE guess must be right. If no guesses are right, the game is over (you lose) 3. If any player guesses wrong, the game is over (you lose) So, Looking at part 2, if all three players decline to guess, then Rule 2 comes into play, and the group loses. What this does is throw a monkey wrench into the whole works, because NOBODY knows who's going to guess, and who's going to decline to guess! Players may be forced to guess, because since there's no communication, there's no way to figure out if the other two players are going to guess! I'd say in this case the odds are no better then 10-15%
People Talking in Movie shows.. people smoking in bed.. people voting republican.. GIVE THEM A BOOT TO THE HEAD!
1) In the strategy session, everyone agrees to NOT look at any of the hats.
:-)
2) When your turn comes up, say "my hat is red AND blue!"
3) When the tester looks at your hat, you sue them for changing your hat color and messing up the test.
I guess they'd have to be really tiny hats though...
The strategy in the general Red/Blue Hat Problem is as follows:
Any strategy that minimizes the number of people making a choice is valid.
RULE: Only the person(s) that, from their standpoint is(are) belonging to the group with the smallest number of chosers should make a choice the others should pass.
From the available solutions the choser should take the solution with the highest multiplicity.
In the three persons case:
RRR 3 persons see two same colored hats
RRB 2 persons see two diff col hat 1 two same color
RBR 2 persons see two diff col hat 1 two same color
RBB 2 persons see two diff col hat 1 two same color
BRR 2 persons see two diff col hat 1 two same color
BRB 2 persons see two diff col hat 1 two same color
BBR 2 persons see two diff col hat 1 two same color
BBB 3 persons see two same colored hats
Following RULE only the person with sees the same color should choice.
Reactions to: mailto:hansvanv@hotmail.com