Prisoners Problem (Easy Mode)

[KrazyerKate]

I listen to Cartalk on NPR, and always try to get their weekly puzzler. I download it a week after it airs, so I never actually have a chance to enter, but it's still fun to play along. The puzzler from a week or two ago sounded pretty familiar, and I realized I'd seen it on the forums [url=http://forums.xkcd.com/viewtopic.php?f=3&t=22450&p=667873&hilit=hats#p667873]here[/quote]. I remember skimming it, not really understanding it, shrugging, and moving on. Now I'm curious though. Any chance you guys could explain the solution to this simplified version to me?

The warden admits three prisoners into his chambers. He tells them, "One of you fellas is going to have a chance to get out. Here's the deal.

"I'm going to blindfold all of you, then I'm going to put hats on your heads. I have three white hats and two black hats. Each of you is going to get a hat. You have to figure out which color hat you have to get released."

He blindfolds them and puts a hat on each prisoner. They're led out of the room in single file. When the blindfolds are removed, the guy in the back can see the two people in front of him, the guy in the middle can see the one guy in front of him, and the guy in front can see nobody.

They walk around the prison, stopping outside the warden's office. The warden says to the fellow in back, who can see the two people in front of him, and their hats, "Can you tell me what color your hat is?"

Don't forget, there are three white hats and two black hats available. The fellow in back says nothing. He doesn't know.

The fellow in the middle is asked the same question. He is unable to answer.

The guy in the very front, who can see no hats, knows. He says, "I can identify the color of my hat."

How does he know?

[RonWessels]

Ok, there are three white hats and two black hats.

Spoiler:

First, let's consider the guy in the back. He can see the two people ahead of him. Now, if those two people are both wearing black hats, that uses up all of the available black hats, so he would know that he's wearing a white hat. However, since he doesn't know what color his hat is, he must see at least one and possibly two white hats.

Now, let's consider the middle guy. He knows the logic above, and can see the guy ahead of him. If that person is wearing a black hat, he must be wearing a white hat to have at least one of the two of them wearing a white hat. Since he doesn't know, it must be the case that the first guy is wearing a white hat.

So when it's the first guy's turn, he can tell that he is wearing a white hat based on the fact that the other two could not answer.

[jestingrabbit]

Originally done way back in 2006, when the height of spoilerising technology was whitetext.

viewtopic.php?f=3&t=353&hilit=king

Repeats get locked.

Edit: no, wait, I'm an idiot.

[osiris32]

How does he know?

Well, to give you the stupid, non-mathematical reason, it's because there is a window or mirror in front of him and he can see his reflection.

Sometimes you have to take a different approach to logic.

[jestingrabbit]

How does he know?

Well, to give you the stupid, non-mathematical reason, it's because there is a window or mirror in front of him and he can see his reflection.

Sometimes you have to take a different approach to logic.

Given that a perfectly adequate logical answer was provided by RonWessels two posts above yours, this is certainly not such an occasion.

[Adacore]

How does he know?

Well, to give you the stupid, non-mathematical reason, it's because there is a window or mirror in front of him and he can see his reflection.

Sometimes you have to take a different approach to logic.

The problem explicitly states that the guy at the front can see noone.

A better non-logical answer would be that the guy at the front can see the unused hats the warden is still holding and they're both black. The 'proper' answer is far more elegant, though, obviously.

[RonWessels]

A better non-logical answer would be that the guy at the front can see the unused hats the warden is still holding and they're both black. The 'proper' answer is far more elegant, though, obviously.

That doesn't work, because the problem explicitly states that the guy in front "can see no hats", which must include the remaining unused hats.

The only other possible explanation is that the front prisoner, being the ne'er-do-well brother-in-law of the warden, was slipped a note by the warden when everyone was still blindfolded. The warden knew his brother-in-law couldn't logic his way out of a wet paper bag, so he slipped him the note so he would have an excuse to release his wife's brother and therefore get some thank-you nooky from his wife that night. The only worry the warden had is whether his brother-in-law could get that second brain cell to fire and be able to read the note and figure out that it was the answer to be given.

Really, that's the only other possibility I can come up with!

[ Edit: Dang, I just came up with another possibility. ]

Since there is no down-side given to providing a wrong answer, the third prisoner thinks about the fact that there are a total of three white hats and two black hats, reasons that this means that there is a 3/5 (60%) chance of his hat being white (given a random distribution) and decides to go for it. After all, a 60% chance of freedom by guessing based on probabilities is better than a 100% chance of failure by not answering.

[Adacore]

You're right - I missed the extra information in the line where the front prisoner spoke - oops!

[Superisis]

[ Edit: Dang, I just came up with another possibility. ]

Since there is no down-side given to providing a wrong answer, the third prisoner thinks about the fact that there are a total of three white hats and two black hats, reasons that this means that there is a 3/5 (60%) chance of his hat being white (given a random distribution) and decides to go for it. After all, a 60% chance of freedom by guessing based on probabilities is better than a 100% chance of failure by not answering.

My version of the events: Three prisoners so dumb that the warden figures he can have a little fun with them. He marches them around and then asks his questions. Too dumb to figure out the logic behinds combinations, etc, the first two just say "I dunno". Knowing this (or not knowing) prisoner nr 3 decides it's 50-50 and opts to say his hat his hat is white*. He happens to get lucky and is released.

*

Spoiler:

Ironically, for him it is 50-50 since he's dense. If he was smarter (and made some assumptions) he'd know that it was 60%. If they all were smart and trying to be nice to each other then it's 100%.

[JoeZ]

Of course, this problem assumes

Spoiler:

that the backmost prisoner is a competent logician, and he was paying attention and has not forgotten anything or gotten colors and numbers mixed up. One interesting note, the middle guy doesn't seem to do anything in this problem except complicate it and add detail. Since there are more than two of each type of hat, being unsure after seeing only one hat doesn't provide any clues at all. The problem could be solved exactly the same way with two white hats, one black hat, and two prisoners.

Alternative non-logical answer; the front prisoner is a shaman monk who has mastered out-of-body travel and can simply look at his own head.

But one other thing... barring an unstated punishment for incorrect answers, shouldn't the back two prisoners be inclined to guess, ruining the game of the guy up front?

Edit: non-logical answer number two; He knows he's wearing a white hat because he's not a classhole.

[jestingrabbit]

One interesting note, the middle guy doesn't seem to do anything in this problem except complicate it and add detail. Since there are more than two of each type of hat, being unsure after seeing only one hat doesn't provide any clues at all.

The middle prisoner also has the information from the answer of the first prisoner, so their response does add information.

[math]

Okay, I'll take a crack at it.

Spoiler:

The prisoner in the back either sees two white hats or a black and a white, or he would have said something.
The prisoner in the middle thought this through, so if the man in front were wearing black, then he would be wearing white. But he didn't call his hat to be white, which means that the man in front had to be wearing white.

[RonWessels]

I think you are missing the point of the comment that the middle guy adds nothing to the problem. Clearly with 3+2 hats, you need three people to solve it. However, as pointed out, the equivalent problem could be stated with two prisoners and two white hats with one black hat. It could also be stated with four prisoners and four white hats with three black hats. In general, it can be stated with N prisoners and N white hats with N-1 black hats, for N>0. [ Obviously the N=1 case degenerates to a trivial problem ]. It's a statement about the problem itself rather than about the solution to the problem.

Spoiler:

The fundamental trick to this problem is realizing that, going down the line of prisoners, the first prisoner to see no white hats in front of him can deduce that he has a white hat. This includes the last prisoner who sees nobody and therefore no white hats.

It's similar to saying in the blue-eyes/brown-eyes island problem that the brown eyed people add nothing to the problem.

[jestingrabbit]

I see what you're saying but the sentence

Since there are more than two of each type of hat, being unsure after seeing only one hat doesn't provide any clues at all.

didn't support that reading of the response. But, if that was what was meant, I apologise for my harsh reading.

In general, with n prisoners, n-1 black hats, and n white hats,

Spoiler:

the last white hatted prisoner knows their hat is white, and no prisoner before that can determine their hat colour.

[RonWessels]

Good point. Now I'm starting to doubt my interpretation of what the poster meant.

By the way, I like your general solution description better than mine.

[JoeZ]

I see what you're saying but the sentence

Since there are more than two of each type of hat, being unsure after seeing only one hat doesn't provide any clues at all.

didn't support that reading of the response. But, if that was what was meant, I apologise for my harsh reading.

In general, with n prisoners, n-1 black hats, and n white hats,

Spoiler:

the last white hatted prisoner knows their hat is white, and no prisoner before that can determine their hat colour.

No need to apologize, you were right in the first place, I had it wrong. The funny thing is that the answer to this puzzle was immediately obvious to me, but I've been obsessively challenging it in my head ever since.

So I drew myself a picture. Now every time I doubt the solution I just go back to it and see where I went wrong.

Spoiler:

Black Hat Guy and White Hat Guy are © Randal Munroe; my most profuse apologies for the use of Comic Sans.

These are the only two possible solutions I see (except for the first hat being variable).

[dbanakin]

The original post wasn't clear, but can more than one prisoner be released if they all know their hat colors?
If more than one can be released, then the prisoner in the front of the line will ALWAYS be released.

Spoiler:

If the prisoner in the back says that he knows his color, then he has a white hat, and the other two prisoners know they have black hats.
If the prisoner in the back doesn't know and the prisoner in the middle says he does know, then the second prisoner has a white hat and the first prisoner has a black hat.
If the rear and middle prisoners both don't know, then the prisoner in the front has a white hat.
In this case, I guess it pays to go last!

Even for the general case N-prisoner, N-1 black hat case, the prisoner in front will always be released, and with this variant your chance of being released increases as you move towards the front of the line, I'm sure someone could work out the odds on this.

Just one other observation, for the N prisoner case, the last prisoner should always be released regardless of the number of white hats in the problem. However, the number of white hats in the problem will decrease the chances of the first N-1 prisoners being released in the variant since the possibility of everyone in front of them having black hats will decrease (assuming a uniform probability distribution).