Spiked Math Games  // Math Fail Blog  // Gauss Facts  // Spiked Math Comics

# puzzle-002

MPF - Hats - February 17, 2012
• Currently 4.7/5
• 1
• 2
• 3
• 4
• 5

Today is Math Puzzle Friday (MPF), Yay! Every Friday I'll describe a riddle, game, logic puzzle, etc., that I find interesting and want to share with you. Some of you will surely have heard of the puzzles discussed and may already know the solutions, but to those who haven't, I hope you find them enjoyable!

Today's puzzle: Try to make sense of the above comic. Why did they all say damn at the same time? What ARE the odds? Why? How? What? Who? When? Where?

Context: Okay fine! I'll provide some context. This is the hats puzzle for three people:

"Three people enter the room, each with a hat on their head. There are two colors of hats: red and blue; they are assigned randomly. Each person can see the hats of the two other people, but they can't see their own hats. Each person can either try to guess the color of their own hat or pass. All three do it simultaneously, so there is no way to base their guesses on the guesses of others. If nobody guesses incorrectly and at least one person guesses correctly, they all share a big prize. Otherwise they all lose.

One more thing: before the contest, the three people have a meeting during which they decide their strategy. What is the best strategy?" (Text source: http://www.relisoft.com/science/hats.html)

Problem 1 (medium):
Solve the hats puzzle for three people (i.e., maximize their chance of winning).

Problem 2 (hard): Solve the hats puzzle for 2^N - 1 people.

Recently, hat problems have become a hot topic in mathematics, ever since it was discovered that Hamming codes can be applied to the puzzle (this is a hint for a possible solution to Problem 2).

Problem 3 (easier): The following puzzle (submitted by Florian) might be more manageable:

"Four dwarfs are buried to the head in sand by some sadistic and cruel man, but he gives them a chance to escape the otherwise inescapable death, if one of them can find out the color of his hat. They are positioned as follows:

A || B C D

Above, A looks towards the wall ||, as do B, C and D. The wall is neither mirrored nor transparent, A sees exactly the wall and nothing else. Each dwarf has a hat on his head, there are 2 white hats and 2 black ones. The dwarfs cannot see their own hats, nor are they allowed to get it down from their head. Speaking, signaling with hands etc is not allowed, and punishable by instant death for everyone.

Assuming that every dwarf thinks logically and every dwarf knows that the others think logically, who would know the color of his hat?"

Problem 3: If B and C have the same colour hat, then D knows that his hat is the other colour.
C waits for a bit - if D says nothing, then C knows that his hat is the opposite colour to B.

It goes a bit further iif you assume that the other dwarfs can here the answer one of them gives. If A hears D's answer he knows his hat is the same color, also B and C know that their hats are the other color. Everyone is happy. If B hears C's answer he knows his hat is the other color. Unfortunately that still doesn't help A and D. Poor guys.

"If nobody guesses incorrectly and at least one person guesses correctly, they all share a big prize. Otherwise they all lose."
Is this supposed to mean that only if one person guesses incorrectly? Because at least one person guessing correctly would mean that there may be multiple people that guess incorrectly, maybe I'm missing something.

They can pass. Then they neither guess correctly, nor incorrectly.

A similar problem that has bugging me for more than a year now is:

You have infinitely many professors standing in a line, each wearing either a blue or red hat. They can see everyone else's hat, but not their own. There is communication amongst them. They all simultaneously try to guess the colour of the hat on their head.

Is there a way in which, regardless of the hat configuration, only finitely many professors are wrong?

SORRY! NO communication amongst them (they don't tell each other what hat they have on!!)

See the first entry

Still thinking about problem 1. Can they wait some time (similar to Tom's problem 3 solution), or should they say their guess immediately?

For problem 3, what Tom said.

This reminded me of a very similar (easier?) problem (in the original, n=2). There are n people in the same situation as above, but with n different possible colors. They must all try to guess the color of their hats. There can be incorrect guesses (only one correct guess is needed) and they must make their guess immediately

I can't say about solving the puzzle, but I can reason why the logicians in the comic failed: Each assumed (falsely) that there would be both colors of hats present and that, since they could only see the other's hats, they themself must be the one wearing the other color.

Why there are four classes on the table? And one of them are really big. I can guess one answer: 'rightmost logician have one big and one small class', but this can't be the case.

It's easy, the big glass with lots of beer is the prize :)

In America, people drink beer out of tiny glasses. It's surprisingly difficult to buy a glass of beer here bigger than 1 litre. Fortunately, good European style breweries have glasses that range towards 2-3 litres, but that larger glass is called a "pitcher", and they're all sharing it using their smaller glasses.

I think the optimal strategy is: if one sees that the other two have their hats in the same colour, he says the other colour; if one sees that the other two have different colours, he passes. Then the only way they can loose is in the situation from the comic - when they all have the same colour. Only I don't see where this 1/16 comes from. Shouldn't it be 1/4?

Yup, but he's talking about the odds of failing two times in a row

Yes, but there are 2 failing outcomes in 4 possible, so it's 1/2 of failing in one game, 1/4 of failing two times in a row. Unless I got something wrong? Are the hat's distinguishable? Then it would be 1/16 indeed.

There are 8 possible configurations (2^3) of which 6 succeed and 2 fail (all red or all blue), so 1/4 for failing once and 1/16 for failing twice in a row.

Hmm, as I see it, it all depends on how the hat color is assigned. If we know there are exactly 6 hats (3 red and 3 blue), then clearly the best strategy is to call out blue only if the two hats seen are red (and vice versa). The probability of you also having a red hat, given that the other two hats are red, is .25, so it's a relatively safe bet that your hat is blue (it also produces the 1/16 odds mentioned in the comic for two tries). If you see mis-matched hats on your colleagues, then you should pass as the probability of you being right is only .5, and the pigeonhole principle shows that at least two people will have matching colors, so one person has the .75 chance of being right.

However, all of the above only applies if we're drawing from a pool of 6 hats, and the "assigned randomly" means any hat from that pool could go on any person (ie, your hat color probability is dependent on the other hat's colors). If the hat colors are assigned via a different, independent method (like, say, have everyone be given a random 0 or 1, and then have a hat color corresponding to that number) then the earlier strategy would be based on the gambler's fallacy, which is useless. Then again, it only decreases the probability of winning to .5 (if two people's hats match, then there is a .5 chance that you have the other color), so maybe the same strategy would still be optimal.

Of course, I could be entirely off on this. If I am, would someone be so kind as to correct me?

Interesting. I was once asked a variation of problem 3: Three boys are captured by an evil logician terrorist. He puts them in a locked room with no mirrors or other reflective surfaces. He shows them he has 5 stickers: two red and three blue. He proceeds to put a blue sticker on each of their foreheads and tells them he'll release the first who could correctly work out the colour of his own sticker and explain how he figured it out. Each of them can see the stickers on the other two's foreheads, but if they attempt to communicate with each other or try to look at their own stickers, he'll kill them all. He also assures them that the game is perfectly fair, that they should all be able to figure out the colour of their own stickers using logic alone. After a few moments, one of them says "I have a blue sticker!" He explains how he figured it out, the terrorist congratulates him and releases him.

How did he figure it out?

Btw. this is actually even easier to solve than the problem of the dwarves, but surprisingly no one I've asked has ever been able to solve it. Also, I've sworn never to reveal the solution to anyone who wasn't clever enough to figure it out on their own.

There are 3 possible scenarios:

1) Two red and one blue
2) One red and two blue
3) Three blue

Case 1), i.e. Alice seeing two reds would immediately know he has blue.
Case 2), i.e. Alice and Bob with blue stickers would both see one red and one blue, since person Alice didn't shout "I'm blue", Bob knows Alice doesn't see two reds -> Bob knows he has blue (and vice-versa).
Case 3), since nobody solved yet, neither 1) nor 2) took place, so everybody must be seeing two blues -> everybody has a blue sticker

An even easier solution is that the game is perfectly fair, so they should all have the same color sticker. Since there are three boys and only two red stickers, using red would not be fair; all three must have blue stickers.

Exactly!

What about there were 4 people and 7 stickers (3 red and 4 blue)?

1) 3 reds and 1 blue
2) 2 reds and 2 blues
3) 1 red and 3 blues
4) All four are blue.
I need help in the logic used for cases 2, 3, and 4, yet number 1 is obvious

the distribution used to place the hats wasn't stated, but assuming that each person has a chance of 1/2 for red or blue, you have 8 possible configurations. using your strategy (which is indeed optimal) only 2 of the configurations result in failure. that means a 1/4 chance of failure for each game. 1/16 for 2 games...

Don't you forget the conditional probability? Given the hats you see, there are only 2 possible configurations. I go with Fre's reasoning.

No, foo's argument is correct. Unfortunately you are falling prey to gambler's fallacy. In the problem it says all the hats are randomly chosen and therefore they are all independent events. So just because the other 2 hats are a particular color, the probability that the remaining person has to same color is still 1/2. Therefore, the best way for a group of 3 to approach this problem is as described by zeissman above.

Is it a coincidence that I stumbled upon an article on this yesterday?
http://www.msri.org/people/members/sara/articles/hat.html

For 1 & 2: If the there is no limit to the amount of hats of any color then the best strategy is for only one person to speak and everyone else to pass, that way they have a 50% chance to get it right, otherwise each person who attempts to guess decreases the odds of winning.

For 3: Simple, the dwarf who can see two hats of the same color knows the guys hat color, the other two dwarves should pass.

Could you make an "what my friends think i do"-meme-based Comic please?

On topic:
It is clear, that it is preferable that only one logician tries to guess his color. Everyone has a chance of 1/2 to be right. So when is it reasonable to guess? Only when one logician sees two hats of the same color. There are is a chance of 3/4 to guess right. Thus the chance to guess incorrectly is 1/4, this yields the 1/16.

For the case with 7 people, they can use the (7,4)-Hamming-Code where red hats are 0 and blue hats are 1. Beforehand they assign a number to each one which represents their bit position in the 7-bit code word. Then everyone calculates the error vector of the code word first assuming he has a 0 hat and then assuming he has a 1 hat. If in either case the error vector is zero, they guess the other bit (so if the error vector is zero assuming they have a 0 hat, they guess 1 and vice versa). In all other cases they pass.
The properties of the hamming code should guarantee that exactly one guesses correctly if the hats form a code word with a non-zero error vector and they all guess incorrectly if it has a zero error vector, which means that they have a chance of 1/8 to fail (16 code words out of 128 possibilities) and 7/8 to succeed. I guess this method also works for 2^n-1 people using the (2^n-1, 2^n-n-1)-Hamming-Code.

Silly question: After a logician heard his friends say "My hat is", why don't he rethink?

That is an extremely astute point. They're all likely guessing on the fact that there are two other reds and the human gut decision makes it feel unlikely for all three to be red. Also, I suppose there are 3/8 situations with 2 reds, but only 1/8 with all red. So gut decision makes sense in a way.

But if everyone's confident, then everyone should question it. Really good point.

The way I read the problem is that the simultaneousness (what's the right word?) of the responses means that you can't base your guess on what others say. I interpret it as "once you start talking, you must guess."

Well, in this case you still could guess. For example, if they were to follow the strategy as previously presented and only guess when they see the others wearing two of the same color hat. Then the case that more than one person would be guessing will be when they are all wearing the same color. Therefore if you begin the phrase but while doing so hear the others as well then you could just guess that your hat is the same color as the other two players.

What about if they each toss a coin and guess their hat if they get a head and pass if they get a tail.
Then each person has a 1/4 chance of guessing correctly, a 1/4 chance of guessing incorrectly and a 1/2 chance of passing.
They win if they all guess correctly (1/64) or if two guess correctly and the other passes (6/64) or if one guesses correctly and the others both pass (12/64). This is a 19/64 chance of success which beats the 1/4 chance the logicians up there are going for.
Actually I think they can beat this by biasing the coin - I think they want the chance of guessing to be (6-sqrt(8))/7 which is a little less than a half.

Oops.
Brain fail :(

Strategy:
1) If you see one blue hat and one red had, you say nothing.
2) If you see two hats of the same colour you speak: "My hat is"
3) If the others are speaking at the same time, you declare the colour to be the same as that of the other two. If the others are not speaking, you declare the colour to be the other one.

Success rate: 100%

While the puzzle solutions usually use "3 red hats" and "3 blue hats" as losing configurations, it is possible to use other configurations, too, as long as the two losing configurations differ in all 3 hats.
Oh, this is a hint for the second puzzle, too ;).

If three people wearing hats enter a room, don't they already know what color hat they have? Where did there hats come from? Did they just magically appear when they passed through the door?

If you see a mix, guess the opposite, else pass. 75% chance of winning

Zwejhajfa: I agree with your solution. Moreover, the probability 1-1/2N of winning for 2N-1 logicians cannot be beaten: indeed, assume that the strategy of the logicians is devised so that the first one shall answer something (rather than passing) in a proportion p(1) of the cases, the second one will answer in a proportion p(2) of the cases, etc. Obviously, whatever the strategy chosen, each time a logician answers he will be right half the time, and wrong half the time. So, the probability that at least one logician gets right is at most ∑ p(i)/2 (that value maximum being attained provided that it nevers occurs that two logicians get right at the same time), and the probability that at least one gets wrong is at least max p(i)/2 (that value being attained provided that, each time some logician gets wrong, then necessarily the logician with maximal p(i) gets wrong too). So, the probability of losing divided by the probability of winning is at least (max p(i)/2)/(∑ p(i)/2), which is obviously always larger than or equal to the number of logicians. This corresponds to a probability of winning of 1-1/(Z+1), Z being the number of logicians, which indeed is attained by Zwejhajfa's strategy in the case Z = 2N-1.

(Note: You must have javascript enabled to leave comments, otherwise you will get a comment submission error.)
If you make a mistake or the comment doesn't show up properly, email me and I'll gladly fix it :-).

Welcome to Spiked Math!

Hello my fellow math geeks. My name is Mike and I am the creator of Spiked Math Comics, a math comic dedicated to humor, educate and entertain the geek in you. Beware though, there might be some math involved :D

New to Spiked Math?
View the top comics.

New Feature: Browse the archives in quick view! Choose from a black, white or grey background.

Other Math Comics