Teaser: Prisoners and Hats

**drmomentum**[$] · #1 04-12-2002, 05:20 PM

Okay. You have 10 men being held by a sadistic jailer.

The jailer is known for his weird games, but he follows through on his promises. He tells the 12 men that he is going to come into the jail tomorrow and line them all up. The first person in line is going to be facing the wall, about 1 foot from it. The next man will be behind him facing the first man's back, just out of arm's reach. The next man is behind him the same way, and so on down the line. The first man can only see the wall. The last man can see all the other men.

A hat will be placed on the head of each man - either black or white.

Then, starting at the back of the line and moving toward the wall, the jailer will ask each man the color of his hat. The man must shout out the color he thinks he is wearing. If he guesses correctly, he will be freed. If he guesses incorrectly he will be executed the next day.

Clearly, each man has a 50% chance. However, after the jailer leaves, the men realize there is a way to increase their chance dramatically. Once they arrive at their solution, they must draw lots to implement it.

Even though the jailer is fair, he will not allow the men to touch, nor will he allow any communication between the men. They are to call out the guess in a normal voice. The jailer would not stand for any funny business.

What is the best chance they can hope for? What solution did hey arrive at to increase their chances?

murasaki · #2 04-13-2002, 12:00 PM

Well, I don't know how good of an answer this is, but...

The last man in the line shouts out the color of the first man's hat. The second to last man in line shouts out the color of the second man's hat. And so on

The first five or six (depending on if there are 10 or 12 guys in line

) will know the color of their hats because the last five or six in line will tell them. The last five or six in line, still have a 50% chance of getting the color of their hat right.

--naomi

**drmomentum**[$] · #3 04-13-2002, 01:16 PM

Quote:

Originally posted by murasaki
Well, I don't know how good of an answer this is, but...

It's very good. It increases the overall chance of survival considerably.

But there are still solutions that increase it even further.

Keep going.

-JP

magenta321 · #4 04-13-2002, 01:54 PM

Can you clarify?

Quote:

You have 10 men being held by a sadistic jailer.

Quote:

He tells the 12 men that he is going to come into the jail tomorrow and line them all up.

Are there 10 or 12 prisoners. It probably won't matter, but I'd just like to know.

magenta321 · #5 04-13-2002, 01:58 PM

Also, do the men know the number of black hats and white hats ahead of time (say five black and five white)?

I'm thinking they must, because you said there was a 50% chance of them getting it right on their own. But if there were 7 whites and 3 blacks, that would be a 70%/30% chance of getting it right, no?

Also, will the men know ahead of time if the person behind them was correct?

magenta321 · #6 04-13-2002, 02:05 PM

Also, and this is probably over-simplified, can they be standing in front of a wall with a mirror on it?

**drmomentum**[$] · #7 04-13-2002, 05:34 PM

There are 10 men.

They do not know the number of hats which are white vs. black. If they knew there how many were of each color, that might alter the probabilities, but they do not.

There is no mirror.

I stated in the problem that each man has a 50% chance - but we have discovered that they really have *at least* a 50% chance. Murasaki's answer gives each individual a 75% chance.

-JP

**AuntieEmma**[$] · #8 04-13-2002, 07:11 PM

Building on Murasaki's answer (which I never would have thought of on my own in a million years) .... each man shouts out the color of the hat of the man directly in front of him.

**drmomentum**[$] · #9 04-13-2002, 07:56 PM

Quote:

Originally posted by AuntieEmma
Building on Murasaki's answer (which I never would have thought of on my own in a million years) .... each man shouts out the color of the hat of the man directly in front of him.

I can see you have your creative thinking cap on, but unfortunately this is not an improvement. Murasaki's suggestion yielded a .75 probability of survival. This new scenario puts us back to .55.

Everyone will know the color of his hat, but only the man in front will be able to use that information, because he's the only one not forced to just say the color of the hat in front of him. So he will survive, but everyone else is 50-50.

To calculate the probability, you will die if you lose both the straw-draw and the hat guess. The straw draw is 9/10, the guess is 1/2. That's a .45 probability of death, or (subtracting from 1) a .55 probability of survival.

-JP

theeye · #10 04-15-2002, 12:36 AM

Ok, I was really almost there with this solution, but I made the mistake of talking it over with my husband, who (of course) solved it. So he gets credit for this one.

The first man to respond, of course, can only have a 50% chance of success. Everyone else, however, can be saved with 100% certainty, so long as the first man cooperates (which doesn't impact his own survival chances) and everyone pays attention.

Here's how it works:

The first man sees every hat but his own. He counts up the black hats and determines whether he sees an odd or an even number of them (obviously, the choice of black rather than white is arbitrary). As arranged by mutual agreement, he will guess "black" if he sees an even number of black hats and "white" if he sees an odd number. (This choice is, of course, also arbitrary.)

The first man survives or not, as luck has it.

The second man counts up the black hats that he sees. If the parity (oddness or evenness) matches the parity implied by the first man's declaration, then he knows that he is wearing a white hat and he so declares. Otherwise, he must be wearing a black hat. Either way, he can guess correctly and survive.

The next man pays close attention to both of the previous responses. He knows whether the first man saw an odd or even number of black hats. If the second man was wearing a black hat, then the parity reverses. He now compares the adjusted parity to the number of black hats that he sees and, just as in the previous case, can now say with certainty which color hat he is wearing.

This continues on down the line, which may be of arbitrary length (so long as the assumption still holds that everyone can see all hats in front of them -- and hear all responses behind them).

In the case of a line of 10 men, the overall expected survival rate is 9/10 * 100% + 1/10 * 50% = 95%.

This is clearly optimal as the first man has no source of any information that might improve his chances from 50% and all other men have maximized chances of 100%.

QED.

**drmomentum**[$] · #11 04-15-2002, 04:10 PM

Excellent! Quite right.

If you're familiar with the idea of a parity check (most people in the computer and electrical fields) it makes perfect sense.

Since every man knows whether the count of black hats in front of him is odd or even, then all he needs to know is what the man at the end of the line sees, and keep track of the oddness or evenness as you hear the hats called out.

A tricky problem, isn't it?

-JP

**AuntieEmma**[$] · #12 04-22-2002, 02:19 AM

Quote:

Originally posted by drmomentum
Everyone will know the color of his hat, but only the man in front will be able to use that information, because he's the only one not forced to just say the color of the hat in front of him....

Oh, yeah. Oops!

Quote:

Originally posted by theeye
Here's how it works:

The first man sees every hat but his own. He counts up the black hats and determines whether he sees an odd or an even number of them ...

The second man counts up the black hats that he sees. If the parity (oddness or evenness) matches the parity implied by the first man's declaration, then he knows that he is wearing a white hat and he so declares. Otherwise, he must be wearing a black hat...

Wow. I'm impressed!

Quote:

Originally posted by drmomentum
A tricky problem, isn't it?

I'll say!