Puzzler -prisoners with hats


#1

I just heard the answer to the Prisoner with Hats and the logic involved. What prison was this?–the prison for MIT students? I saw James Cagney prison movies–I even watched White Heat 30 times----so i am an expert on prisons!

There is no way that the prisoners would figure this out–unless it was a white collar prison filled with crooked accountants, lawyers and hosts of NPR shows!


#2

All it would take would be to have one investment banker (math major) to figure this out and persuade the rest. Unfortunately, there would only be a few investment bankers incarcerated while they really ought to be a higher percentage of the population.


#3

"There is no way that the prisoners would figure this out–unless it was a white collar prison filled with crooked accountants, lawyers and hosts of NPR shows! "

That was NOT a very hard one to solve…This type of thinking (logic) is usually taught the first year of college. My daughter was taught it in high-school. If you want difficult logic puzzler I can give you a couple.


#4

Hey MikeInNH, this is a great idea. You ought to start a new thread with interesting logic puzzles that are more interesting than the recycled summer puzzlers. There would need to be a clear indication in the puzzle statement whether this was a new puzzle or whether it was a spoiler for a previously posted one. I’m in.

Good idea!!


#5

MikeInNH wrote:“This type of thinking (logic) is usually taught the first year of college. My daughter was taught it in high-school.”

My point was not about the difficulty of the puzzle but about the likelihood that average prisoners would solve it. Most prisoners did not take logic classes in college, many did not finish high school, many cannot read.


#6

“Most prisoners did not take logic classes in college, many did not finish high school, many cannot read.”

If your point is they have much in common with prison guards, you’re right.

It’s not a difficult problem; after all, I solved it. The prisoner in the back (#30) has the most information, but he only has three pieces of information that no one else does: the color of the hat on prisoner #29, the total count of each color he (#30) can see, and the meta-information about whether the count is odd or even. The total count is useless, #29’s color only helps #29, so all that’s left is odd or even. It’s a rolling parity bit that’s passed down the line from prisoner to prisoner.


#7

Transcribed, mostly. – “At a certain jungle prison, there are 30 prisoners who have been sentenced to be executed. The warden decides to play a little game and he tells the prisoners that he will stand all of them in a straight line, with prisoner number one facing the wall, and all of the remaining prisoners all lined up behind him, so that each prisoner is able to see the heads of those in front of him, but not his own head, of course, or the heads of those behind him. He will place either a white or a black hat on each prisoner’s head, starting at the back of the line, and then a guard will go down the line in the same direction starting with the last prisoner, number thirty, and ask each prisoner to identify the color of his own hat. Prisoner number 30 can see all 29 hats in front of him, 29 can see 28 hats, etc, but prisoner one can see nothing. When asked, a prisoner may say one of two words: Black, or White. The warden gives the prisoners one hour talk among yourselves and come up with a strategy. After that, no talking.”

My plan is much easier, but gives the #30 guy at least a 50/50 to guess his own hat instead of just dying like the “answer” suggests, and doesn’t require math. When the warden hands out hats, the guy behind him sees what the guy in front of him is wearing, and blows on the back of his neck if he’s got a white hat. If there’s no breath felt, then you’ve got a black hat. They’re all dead anyway, so if anyone survives and the warden doesn’t pick up on it, at least 29 guys win the game.


#8

Your last sentence makes no sense, but otherwise your solution seems good at first*. Except it doesn’t change the odds for #30 like you suggest.

  • Oh, one more thing. By “trancribing”, “mostly” you missed the part where the warden says “If I suspect anything is amiss, you all die.” So you’ve got a line of guys blowing on each other and that doesn’t raise a red flag? Since they can all see all the hats in front of them they are not in a straight line, so they’d have to turn their heads to blow on the neck of the guy in front of them. Thank you, come again.

http://www.cartalk.com/content/puzzler/transcripts/201127/index.html


#9

First of all… nowhere in the statement of the puzzle is there anything about prisoners having their life spared if they state the color of their hat correctly. So they all get one hour more of life by discussing… and THAT’S IT! Plus they get the satisfaction of knowing they have improved their odds of getting the puzzle solved.

So assuming they decide to try for the pure intellectual satisfaction of it (the puzzle does state, “is there a strategy that they can use that will improve their chances, and if so, what is it?”) - the answer is not as simple as Ray presents. The one white hat out of 30 example makes it seem simpler than it is. Prisoners must track the odd/even state as it goes along. Only #30 has the easy answer. Unfortunately, his easy answer makes it a 50/50 chance for himself. He MUST report the color of the odd number ahead of him. Piter is correct. This is a ROLLING parity bit. If only #10 has a white hat as in Tom’s example… pretty easy to track since it only swaps once. But if there are lots of white hats, every prisoner must make the computation of parity (ODD or EVEN) and keep track of it as it swaps back and forth. Not trivial as the single white hat example would lead one to believe.

Let’s take the worst case example - the hats alternate, 15 black and 15 white interleaved. Prisoner #30 is doomed. Whichever color he has, he will see an odd number of the other color, and must report that. That will always be wrong. We’ll give him a white hat. He says BLACK because he sees 15 black hats in front of him… an odd number of blacks.

So #29 thinks: #30 saw an odd number of blacks, I see 14 (EVEN), therefore I must have one of the black hats he saw. So #28 must track - #30 saw odd blacks, #29 KNOWS he has a black hat, therefore he must see an EVEN number of blacks. I (#28) still see an EVEN number of blacks, therefore I must not have one of them, and I must have a WHITE hat. So far so good, but #27 must have been tracking all this, because there’s no way for him to determine his own color, based solely on the color reported by the guy behind him. He must know that #30 said BLACK, meaning and odd number of blacks, #29 said BLACK meaning now there is an EVEN number of blacks, #28 said WHITE meaning an even number of blacks… and so it goes. Poor guys with low numbers… they must track the entire sequence, and compute right along with each of the couple dozen guys behind them what odd count is when it gets to each one, and what their answer means.

Look what they must track:
First guy to speak (#30) says BLACK, because he sees an odd number of blacks
Second guy (#29) says BLACK, because he sees an EVEN number of blacks so must have one of them.
Third guy (#28) has to remember that second guy said BLACK because the first guy saw odd, and the second guy saw EVEN. #28 still sees EVEN and says WHITE, because the guy before him (#29) said BLACK because he saw an EVEN number of blacks.
Fourth guy (#27) is already struggling. He knows that the guy before him said WHITE, but he has to remember what WHITE means in this string of answers. He must remember everything third guy remembered, plus add in his own knowledge. #27 must remember:

First guy said BLACK meaning ODD number of BLACKS in front of him; second guy said BLACK meaning now EVEN number of BLACKS in front of him; third guy said WHITE meaning there was an EVEN number, and now there is still an EVEN number of BLACKS so he can’t have one of them. I see an ODD number, therefore I must have one and say, “BLACK.”

Just in typing this I made 4 mistakes I had to correct, and I’m only on the fourth guy. Poor numbers 1 through 6. They got lost shortly after this started - and are now back to guessing - 50/50 chance.

By choosing 1 white hat out of 30, Tom gives Ray a test sample that makes the solution seem simple…


#10

First of all… nowhere in the statement of the puzzle is there anything about prisoners having their life spared if they state the color of their hat correctly.

Yes, as I pointed out in the original thread on this subject.

Otherwise, what’s your point? It’s NOT the real world. Who lets someone get out of a death penalty on the basis of a guessing game?

The solution does require each prisoner not to mess up, but it’s like card-counting: each prisoner only has to keep one piece of binary information, black or white, in mind at a time.

THIS is wrong, and it was a long way to go, wasn’t it? :

Fourth guy (#27) is already struggling. He knows that the guy before him said WHITE, but he has to remember what WHITE means in this string of answers. He must remember everything third guy remembered, plus add in his own knowledge. #27 must remember:…

The fourth guy doesn’t have to remember ANYTHING. He just needs to play along at home. That’s why it’s a rolling parity bit. Even if he remembers everything, if someone before him screws up, he’s out of luck. All every prisoner has to remember is whether the last prisoner to speak saw an odd or even number of black hats. They don’t have to remember how it got that way.


#11

Ray’s answer is just plain BO-O-OGUS! Each prisoner has two competing priorities that can’t both be satisfied. He can’t answer correctly about his own hat, and also give accurate information about the parity of the other hats that he sees.


#12

OK, piter. Blowing is a dead giveaway; the warden would fry them all. But what about using time as a tipoff.
For an hour, the inmates practice by giving their responses with no variation in intonation or pitch (Like blowing, voice cues would arouse suspicion.). The last in line “guesses” his hat color by revealing the color of the hat worn immediately in front of him. His survival chances are 50/50. Inmate #29 then pauses no more than one second after being prompted, provided that inmate #28’s hat is the same color as his. If it isn’t, he pauses an additional two seconds, thus tipping off inmate #28; and so on. (Hey, these are nervous dudes, and this is a big moment in their lives; the warden wouldn’t suspect such a subtle cue.)
After an hour of practice, each inmate should have mastered the skill of differentiating between a one and three second delay. And unless the warden videotapes the proceeding and has an analyst study the responses, the first 29 inmates in line surely avoid execution.
Of course, all bets are off if Mel Tillis is one of the jailbirds.


#13

They don’t have an hour to practice, they have an hour to get 30 people to agree on a strategy and practice it. I’d like to see a longer delay than two seconds, but your solution sounds practical. It is of course not the desired solution, but I like it.


#14

" Stefan_G_T July 11 Report
Ray’s answer is just plain BO-O-OGUS! Each prisoner has two competing priorities that can’t both be satisfied. He can’t answer correctly about his own hat, and also give accurate information about the parity of the other hats that he sees.
"

Well, that’s just mind-bogglingly wrong. Giving correct information about his own hat tells the person in front of him the color of his hat. (Except for #30, who doesn’t have any information about the color of his hat. Sorry, #30).


#15

Also note that the cuing approach has a distinct advantage over the cumbersome odd-even strategy: practicing for the better part of an hour entails neither counting nor props, only binary logic and getting the timing right.


#16

More advanced Logic puzzle…It CAN be solved…

There is a row of five different color houses. Each house is occupied by a man of different nationality. Each man has a different pet, prefers a different drink, and smokes different brand of cigarettes.

The Brit lives in the Red house.
The Swede keeps dogs as pets.
The Dane drinks tea.
The Green house is next to the White house, on the left.
The owner of the Green house drinks coffee.
The person who smokes Pall Mall rears birds.
The owner of the Yellow house smokes Dunhill.
The man living in the centre house drinks milk.
The Norwegian lives in the first house.
The man who smokes Blends lives next to the one who keeps cats.
The man who keeps horses lives next to the man who smokes Dunhill.
The man who smokes Blue Master drinks beer.
The German smokes Prince.
The Norwegian lives next to the Blue house.
The man who smokes Blends has a neighbour who drinks water.

Who has fish at home?


#17

More of a typing exercise really. Once I solved it I googled and confirmed the solution.

Abejrtvna Qnar Oevg Trezna Fjrqr
Lryybj Oyhr Erq Terra Juvgr
Qhauvyy Oyraqf CnyyZnyy Cevapr Oyhr Znfgre
Pngf Ubefrf Oveqf Svfu Qbtf
Jngre Grn Zvyx Pbssrr Orre


#18

I think Stefan_G_T may be correct, that each prisoner has
competing priorities and that the answer is BOOOOOGUS.

According to the strategy, if a prisoner sees an odd number of
white hats, he says ‘white.’ If he sees an odd number of black
hats, he says ‘black.’

#30 sees an odd number of white hats and says ‘white.’
#29 still sees an odd number of white hats and is, thus,
supposed to report ‘white,’ even though he knows he’s wearing
a black hat! So, what does he do - save himself or save the
guy in front of him??? I don’t think the odd/even strategy
works.


#19

The problem is that you don’t understand it. You’ve managed to say something WRONG in each of 3 paragraphs.

Para 1. Simply wrong.
Para 2. According to your understanding presented in this paragraph, what does Prisoner #11 say if he sees an odd number of black hats and an odd number of white hats?
Para 3. Head-shakingly WRONG. I’m not even going to spell it out.


#20

the odd-Even strategy works perfectly.

I think people are reading too much into this.

Forget about that it’s a prison…This is a mind puzzle…nothing more. It could be a bunch of school teachers or students…IT DOESN’T MATTER. Why even think about that part.

#30 sees an odd number of white hats and says ‘white.’
#29 still sees an odd number of white hats and is, thus,
supposed to report ‘white,’ even though he knows he’s wearing
a black hat! So, what does he do - save himself or save the
guy in front of him??? I don’t think the odd/even strategy
works.

If there are a even number of white hats and #30 sees an odd number of white hats then he MUST be wearing a white hat…The next prisoner also sees an odd number of white hats…but he also knows what the prisoner behind him said and if the answer was correct or not…THUS he knows that the color of his hat is black…You forgot about the part of knowing what each of the prisoners behind you say. You have to keep track of that part too.