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.

66 of 325 comments (clear)

  1. Some clarifications to the puzzle: by DG · · Score: 5

    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
    1. Re:Some clarifications to the puzzle: by Mike+Schiraldi · · Score: 2
      Okay, look. Here are the eight possible outcomes:

      000
      001
      010
      011
      100
      101
      110
      111

      Let's give the people names:
      ABC
      DEF
      GHI
      JKL
      MNO
      PQR
      STU
      VWX

      Now, we're only talking people who see two hats of the same color. That leaves
      ABC
      F
      H
      J
      M
      Q
      U
      VWX

      There are 12 people here. Six of them are wearing a hat that's the same color as the ones they see. Six are not.

      1/2.

      QED

      --

    2. Re:Some clarifications to the puzzle: by Mike+Schiraldi · · Score: 2
      I don't disagree with that. Note that the post that started this all was:

      Thus, if you see 2 hats of the same colour, the probability that your hat is the same color is 1/6

      I (correctly) pointed out that the probability was actually 1/2. That's what the previous few posts have been in reference to.

      --

    3. Re:Some clarifications to the puzzle: by mistered · · Score: 2
      Ohh, so close but you missed one point:

      There are 3 hats, but two colours. This means that out of 12 possible combinations

      There are three hats, and each has two possible colours. Thus there are 2 * 2 * 2 = 8 possible combinations, not 12, and there's a 2/8 chance of them being all the same colour.

      --
      Enjoy your job, make lots of money, work within the law. Choose any two.
    4. Re:Some clarifications to the puzzle: by edp · · Score: 2

      "It's 0.75."

      The cases in which you see two hats of the same color are RR-R, RR-B, BB-R, and BB-B, where the last color in each case is your own hat. These cases have equal probability of occurring. The frequency with which your hat is the same color is 1/2 of these equally probable cases, and so the probability is 1/2.

      So, the answer to the question "If you see two hats of the same color, what is the probability your hat is the same color?" is 1/2.

      However, the answer to the question "If (at least) two hats are the same color, what is the probability all hats are the same color?", the probability is 1/4.

      This is because the equally probable cases in which two hats are the same color (as is always the case of course) are RRR, RRB, RBR, RBB, BRR, BRB, BBR, and BBB. Of those, the proportion that have all three the same color is 1/4, and hence the probability is 1/4.

    5. Re:Some clarifications to the puzzle: by edp · · Score: 2

      Your comments are consistent with a misintepretation of the question. Specifically, your comments appear consistent with an attempt to demonstrate how the algorithm described in the New York Times article yields a 75% probability of success. However, the question addressed here has been a different problem. The question in this thread is, if you see two hats of the same color, what is the probability your hat is the same color?

      That probability is indeed 1/2.

      Perhaps you would like to reconsider your assertions that others were in error.

  2. You're a ET-lover by Pseudonymus+Bosch · · Score: 2

    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
  3. Origin of "Red Hat" by Pseudonymus+Bosch · · Score: 2

    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
  4. Play monte hall! by Booker · · Score: 2
    The monty hall problem is a great one... you can play it here.

    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?

    ---

  5. Re:Blue hat? by KlomDark · · Score: 2
    Yes, right here: http://www.bluehat.org

    (It was extremely tempting to turn that into a goatlink, but I didn't :) )

  6. It's a Dr Seuss April Fools joke by KlomDark · · Score: 4
    Haha, funny to see how people are taking this problem entirely too seriously, and forgetting their childhoods at the same time.

    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!

  7. The requirements are unclear by pen · · Score: 2
    When I read the problem at first, I assumed that all of the players had to either guess at the same time or write down their answers. I didn't think that they were allowed to answer in succession. Then again, that's one of the keys to the puzzle.

    --

    1. Re:The requirements are unclear by Fjord · · Score: 2

      The odd thing is that the solution I got for answering in succession is as likely as when they all answer at the same time (being 75%). I'm still now sure why my same time answer works. I'm working on that now.

      --
      -no broken link
  8. Re:Answer is here by sandler · · Score: 2

    Sounds pretty difficult to pull off without any communication.

  9. Research? by sandler · · Score: 4
    The problem has even spread to the Caribbean. At a workshop at a research institute in Barbados, one hardy group of theoretical computer scientists stayed up late one rum- soaked night, playing a drinking game based on the puzzle.

    Sounds fun! How can I get a job at said "research" institute??

    1. Re:Research? by underwhelm · · Score: 2

      It's easy. Just become a "theoretical" computer scientist.

      I'm buying my pseudo-ticket today!

      --

      I don't need large brains to have a good time.

  10. How to cheat by Syberghost · · Score: 5

    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.


    -

  11. Re:So what is the strategy for larger teams? by Sancho · · Score: 2

    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.

  12. Re:What I don't get about the Monty Hall Problem by platypus · · Score: 2

    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.

  13. Re:Better solution by Mike+Schiraldi · · Score: 2
    If any player guesses wrong (as opposed to passing), they all lose.

    --

  14. My Better solution, with some rule deformity by B.D.Mills · · Score: 2

    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
  15. Re:Another question!!! by crosseyedatnite · · Score: 2

    Solution in Pseudo C

    a := a + b;

    b := a - b;

    a := a - b;

    --
    e to the i pi equals negative one
  16. Perhaps... (total OT reply) by cr0sh · · Score: 2

    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
    1. Re:Perhaps... (total OT reply) by cr0sh · · Score: 2

      Not crunched for time at all...

      I could just see what utterly useless pap Dr. Seuss was. The first book I remember being "introduced" to was a science encyclopedia my parents got in the mail - they knew I liked building toys and such, so they showed it to me, and I read that thing nearly cover-to-cover, so they got me more like it (always asking my input on whether it was something I would like to read). Later they got a set of encyclopedias (Brittanica - not a cheap set to get), mainly for school work. Any other kinds of book wanted to read, I could pick out from the bookstore or elsewhere.

      Don't get me wrong - my reading interests weren't all reference, nor did I read only "adult" oriented books - I read my share of children's novels. I just enjoyed the kind of books that had more than 10-15 pages, and more words than pictures. For those books that had pictures, I vastly preferred pictures that at least looked like a real setting, rather than a complete candy-coated strange-ass drug-induced fantasy land (and if you look at Dr. Seuss in this light as an adult, perhaps that is why some adults are fascinated by his work...perhaps).

      Worldcom - Generation Duh!

      --
      Reason is the Path to God - Anon
    2. Re:Perhaps... (total OT reply) by cr0sh · · Score: 2

      Sue me - I suck at spelling - I think it is rather funny that you point this out - I have had the sig running for quite a long time, yet you are the first to point it out.

      I will change it immediately, thanks for the update...

      Worldcom - Generation Duh!

      --
      Reason is the Path to God - Anon
  17. No... by cr0sh · · Score: 2

    I just didn't like Dr. Seuss books...

    Worldcom - Generation Duh!

    --
    Reason is the Path to God - Anon
  18. Kinda wacky... by cr0sh · · Score: 2

    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
  19. Re:Math + Usefullness by citizenc · · Score: 2
    I'm neither a total moron NOR a troll.

    For the people who developed computer microchips, then the advanced math is VERY relevent. However, unless you find yourself under that particular umbrella, things like advanced calculus are surprisingly abstract. I'll even go so far as to say that grade 12 is getting a little .. iffy. I'm not ungrateful. I just speak my mind.

    yeah, hate what you don't understand ...
    And, for the record, I have always gotten approximately 95% in ALL of my math courses, so I DO understand the material.

    ------------
    CitizenC
  20. Re:This defies random odds by norton_I · · Score: 3

    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.

  21. Re:This defies random odds by UnknownSoldier · · Score: 2

    > 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.

  22. Perhaps the best solution. by dsplat · · Score: 2

    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.
    1. Re:Perhaps the best solution. by dsplat · · Score: 2

      Of course my face, although not my hat, is red. The word simultaneously does appear in the rules to describe how the guesses must happen. This solution only works if the guesses are sequential. It is interesting only in that it demonstrates that as long as the only communication is a choice of guessing or passing there will always be at least one losing case.

      --
      The net will not be what we demand, but what we make it. Build it well.
  23. Re:Math + Usefullness by Nexx · · Score: 2

    Grashopper, calculus is only the beginning to true enlightenment, and will only reach the first layer of abstraction with it. You need much more mathematics, at the university level, to understand its importance. Mathematics will be critical in engineering, physics, finance (no, finance isn't just addition :-P), etc. You just showed your ignorance, sir.
    --

  24. Solution for the general case using Hamming codes by e271828 · · Score: 5
    Nobody seems to have posted this yet, and since I've wasted a few hours on this already, I figured I should share. Here's the solution for the general case where the number of players is n=2^k-1; it involves Hamming codes.

    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:

    1. Neither w0 nor w1 is a codeword
    2. w0 is a codeword
    3. w1 is a codeword
    Cases 2 and 3 are mutually exclusive because of Fact 1. My strategy?
    In case 1, I say nothing, in case 2, I declare my hat to be blue, and in case 3, I declare my hat to be red.
    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!

  25. Unattributed puzzle taken from 1993 ACM paper by frankie · · Score: 5

    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.

    Date: Tue, 10 Apr 2001 10:58:43 -0400
    From: Steven Rudich
    Subject: New Yorkl Times fails to credit me.

    Today, the New York Times had a lively article on a brilliant puzzle going around mathematical circles.

    Just before doing my post-doc, Richard Beigel and I formulated formulated our voting puzzles. Subsequently, our puzzles were developed into a now classic paper in theoretical computer science (with M. Furst and J. Aspnes). There paper can be found at www.rudich.net/papers/voting.ps . My initial solution to the first voting puzzle was a coding theory solution that is strictly identical to the much touted solution in the NYT article. When giving talks on the subject, I mentioned that if my voters had the ability to abstain, that my coding solution was still optimal and that the voters would make no errors in a most situations. This is strictly identical to the hat puzzle in the NYT article. My talks were very popular and many of the people in the article attended these talks. Subsequently, Burt Enderton gave a simple solution to my puzzle that did not have the abstention interpretation and hence is not a solution to the hat puzzle. I liked Burt's solution and put it in our paper.

    In the last few months I have reminded people that *all* the proofs and connections to coding theory were developed by me. Nonetheless, these same people ignored me in the Times article.

    I have had many ideas stolen, but never featured in vivid detail in the Times.

    Steven
  26. Re:Hmmmm by GreyyGuy · · Score: 2

    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.

  27. Re:Better solution by spazimodo · · Score: 2

    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]
  28. Re:Hmmmm by chancycat · · Score: 2
    The spirit of the puzzle means that you don't know a partner passing versus them guessing. I know the words don't say that exactly, but that's the boiled-down spirit of it. You could say they write the word pass on a piece of paper instead of writing the color guess.

    --
    Evan - needs to hit preview before submitting
  29. Re:Hmmmm by chancycat · · Score: 2
    A "win" is considered to be when the money is split among the players, not just a correct guess.

    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
  30. Re:This defies random odds by snorb · · Score: 2
    Much like the Monty Hall problem, at first this seems to defy the rules of probability, but it doesn't. The key points:
    • 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.
  31. The Red Hat problem by SpanishInquisition · · Score: 5

    Why does their x.0 releases always suck?
    --

    --
    Je t'aime Stéphanie
  32. Re:So what is the strategy for larger teams? by Sir+Tristam · · Score: 2
    If you only have one opportunity to pass or choose a color, I would say that there would be a problem. However, if they keep saying, "Come on, anybody have a guess?" if everybody passes (i.e. there are rounds of passing or guessing until somebody makes a guess) then it would go something like this for a group of seven:

    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.

  33. Solution by gowen · · Score: 2

    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.
    1. Re:Solution by ferd_farkle · · Score: 2

      Also, because the boat becomes lighter, it displaces less, so the level goes down.

  34. Blue hat? by ritlane · · Score: 3

    Wait... I'm confused...

    There is something other than Red Hat?



    ---Lane

  35. I have read one similar to this by woody_jay · · Score: 2

    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.
  36. Real world problems by zettabyte · · Score: 2

    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!

  37. Re:There is NO way to guarantee a win. by DeadVulcan · · Score: 2

    You three know that if the two hats you can see are of the same color, chances are that your hat is of a different color.

    This is a very old probabilistic fallacy. Since all the hats were chosen independently, the probability that your hat is a different colour from the other two is still 50%.

    The apparent contradiction is resolved in this problem because you don't always actually make a guess, and a "win" is based on three answers, not one. Take a look at my other 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.
  38. Re:This defies random odds by DeadVulcan · · Score: 3

    Am I incorrect or is this based upon the supposition that by looking at the other draws you can base conclusions on your own

    You would be correct if a single person were being asked to guess either red or blue for his own hat.

    But, this is not the case. Three people are being asked to give simultaneously one of three answers: red, blue, or pass. Each person can see the hats of the other two, and finally, they have an agreed strategy for guessing.

    The best way to think of it (IMHO) is this: the guessing strategy is completely mechanical, so it's fair to think of it as part of the randomized process, rather than the response to one.

    --

    --
    Accountability on the heads of the powerful.
    Power in the hands of the accountable.
  39. There is NO way to guarantee a win. by DeadVulcan · · Score: 3

    Someone suggested that if the players are allowed to give their answers in sequence, and subsequent players can know the others' responses, then you can guarantee a win.

    However, this is clearly untrue, because of the following reasoning:

    The first person to guess has access only to the colours of the other two hats. This gives no information about the colour of his own, since they were chosen independently. Any concrete guess will have a 50% chance of being correct. Thus, in order to guarantee a win, the first person must pass.

    Since the first person must pass regardless of what colours the other two have, the second person has no new information about his own hat. He, too, must pass.

    By the same reasoning, the third person also has no new information, and is therefore forced to guess, and incurs the wrath of the other two, 50% of the time.

    There is no way to guarantee a win except by allowing the players to collaborate in some way.

    --

    --
    Accountability on the heads of the powerful.
    Power in the hands of the accountable.
  40. Re:Better solution by Erasmus+Darwin · · Score: 2
    Not sure you read the rules of the puzzle correctly.

    That was, indeed, my problem. I didn't realize that they had to guess simultaneously. Had the players been able to guess in order, mine would've worked. (And still would've tied back to the hamming code concept.)

    Owel, back to the drawing board.

  41. Re:Math + Usefullness by RedWizzard · · Score: 2
    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.
    I agree, although I think that opportunities to use the likes of trig, geometry, statistics and calculus are there but people don't have the confidence in their knowledge and/or are too lazy to do it.
  42. Re:Math + Usefullness by JWhitlock · · Score: 4
    It's true, not everyone needs math. In fact, if most people don't learn math, then folks like me get paid more for our math knowledge.

    I used math over the last seven days to:

    Guestimate how long it will take me to do a task, based on past performance and how much was budgeted.

    Made an estimate of what sprinkler I needed for my lawn and type of grass, taking into account water coverage and projected rainfall.

    Determined what operations to make to get a bit structure in the format I desired, over a system with endian differences (using Fortran - yuck!)

    For fun, calculated how many managers it would take to run a company, based on each manager having a maximum of 4 people under them (still working on those formulas - I leave it as an excerise for the reader to determine why I decided on 4, or you could go join the Discordians and find out for yourself).

    Calculated my wife's reading rate, to determine when she would be done with the Harry Potter book

    Cut down a recipe for 10 to a recipe for 2 1/2.

    Determined whether it would be a better idea to make an extra car payment, house payment, get a CD, or invest in a mutual fund

    Tried to figure out your age, based on how little math you have had (19? 20?)

    It's been a slow math week, too. In my job (systems programmer), I've used logic, binary arithmetic, calculus, trig, geometry, statistics, and other flavors of math.

    Understanding the materials is a long way from realizing practical applications. Even these folks who do math for a living don't comprehend possible applications yet, but it's been a safe bet that today's math theory is tommorrow's application.

  43. 100% solution by bmongar · · Score: 2

    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.
  44. Re:50% by shyster · · Score: 2
    What a silly problem. The color of the hats are determined my independant coin tosses. No communication is allowed. Other that cheating and viewing your own hat in some way, the maximum chance is 50%. Coin toss. Old statistics problem.

    This is like a word problem you would get in third grade where the wording of the problem would be such that you could be tricked. I am amazed that any mathematician would waste their time analyzing it.

    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? =)

  45. I just check my checkbook balance by typical+geek · · Score: 3

    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

  46. Simple solution by ThirdOfFive · · Score: 2
    So, is it possible to increase your odds or not? I wondered this, so I created a Perl script that chooses three hat colors at random. It then applies the technique mentioned in the article. The result? And I quote:

    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 @.

  47. 7 hats case by kipsate · · Score: 2

    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
  48. Hmmmm by BillyGoatThree · · Score: 5

    "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
  49. Re:Math + Usefullness by loydcc · · Score: 2
    I once had a life or death situation where I could have used Pythagorus's Theorum if only I could remember it. I was anchored in a bad storm close to some rocks. I knew my depth and my anchor rode length. So I knew height and hypotenuse. I needed to figure out the A side to figure the radius of the circle my boat would spin around (provided it didn't drag the anchor.) Since I couldn't remember it I was forced to stay up all night to make sure I didn't end up on the rocks. I was exhausted the next day trying to beat back to port in the tale end of the storm. When I got back to my slip I went straight home and learned a^2 + b^2 = c^2 once and for good! Then I slept for 17 hours.

    The lesson of my story is that I once thought math wasn't worth my time to learn and found out the hard way how wrong I was.

    Now you may argue that that's 8th grade trig and more practical then calculus. That's fine but if you want to do anything in a science field then you will need the calculus. If you don't think you'll ever do anything in a science field then you'll probably be stunned to find out that when you graduate they don't need quite so many IT professionals and do need chemists and physicists and EE's (EE's who actually know how to build devices not just program in JAVA.) and if you don't know the advanced math you'll be someones secretary or pool cleaner.

  50. Re:Math + Usefullness by loydcc · · Score: 2

    Actually the limit of my orgasm approaches 1 long before the limit of her orgasm approaches infinity.

  51. Math formulas (probabilities) by bark76 · · Score: 2
    With the idea of guessing independantly, you have a .5 chance. The other solutions brings in conditional probability, where the probability of guessing colour x correctly is conditional on situation y, or: P(x|y) which can be broken down into the following situations:
    • 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 - .25 = .75), this method is better than random guessing.
  52. As someone who took "Physics for Engineers"... by Flying+Headless+Goku · · Score: 2

    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.
    --

    --
  53. Re:Math + Usefullness by TopherC · · Score: 2
    I won't flame you because the vast majority of people, even with your level of math education, would agree with you. You're wrong about math, of course, but I think most of the blame lies in the way mathematics is taught. (I don't mean to suggest that I have a solution to this problem, either.)

    I like to think of math as a language. For one, it's a way of communicating ideas both abstract and concrete. Also like other languages, it provides us a conceptual framework which allows us to understand things better. And finally it's a powerful tool when you learn how to manipulate it.

    Much of our math education is just the manipulation part of math, which is useful but never by itself (except on tests, as you said). Learning to describe and understand things mathematically is at least as important. With these three aspects mastered, mathematics becomes indispensable to whatever you do. Well, except for sex -- but other than that, it's pretty useful.

  54. So what is the strategy for larger teams? by Hilary+Rosen · · Score: 2

    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
  55. Screwed up the formatting by Hilary+Rosen · · Score: 2

    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