Hats on a death row!! One of my favorites puzzles!

[roolstar]

If you don't already know this one, I'm sure you will find it very interesting and fun to solve! And if you do find the answer (or already know it) please put it under a spoiler tab so that you don't take the fun from the rest of the intelligent people in this forum....

Here we go....

You are one of 20 prisoners on death row with the execution date set for tomorrow.

Your king is a ruthless man who likes to toy with his people's miseries. He comes to your cell today and tells you:

“I’m gonna give you prisoners a chance to go free tomorrow. You will all stand in a row (queue) before the executioner and we will put a hat on your head, either a red or a black one. Of course you will not be able to see the color of your own hat; you will only be able to see the prisoners in front of you with their hats on; you will not be allowed to look back or communicate together in any way (talking, touching.....)

(The prisoner in the back will be able to see the 19 prisoners in front of him

The one in front of him will be able to see 18…)

Starting with the last person in the row, the one who can see everybody in front of him, he will be asked a simple question: WHAT IS THE COLOR OF YOUR HAT?

He will be only allowed to answer “BLACK” or “RED”. If he says anything else you will ALL be executed immediately.

If he guesses the right color of the hat on his head he is set free, otherwise he is put to death. And we move on to the one in front of him and ask him the same question and so on…

Well, good luck tomorrow, HA HA HA HA HA HA!”

Now since you all can communicate freely during the night, can you find a way to guarantee the freedom of some prisoners tomorrow? How many?

Remark of Site Admin:

Note that solution for this puzzle is already given in the following post by bonanova.

[bonanova]

First guy is a coin toss - let's wish him good luck.

His job is to establish the parity of black hats visible to him.

He says "Black" if he sees an odd number of black hats; "Red" otherwise.

By paying attention to what has been said, each prisoner will know his hat's color.

Example:

Second to speak hears "Black" and sees an even number of black hats.

He knows his hat is black [odd changed to even - must be his is black] and says "black".

Third guy has heard "black" and "black" and sees an even number of black hats.

He knows his hat is red [even stayed even - his hat can't be black] and says "red".

And so on, to the front of the line.

General algorithm:

The first time you hear "black", say to yourself "odd".

Each time your hear "black" after that, change the parity: "even", "odd", ... etc.

When it's your turn, if the black hats you see match the running parity, you're Red; Black otherwise.

Call out your color.</div></div></div>

[bonanova]

I didn't understand your solution before. Now I get it. You're my hero.

It's a clever solution - not original with me - and very satisfying to see how it works.

Sometimes I can explain things better than I can analyze them.

[Guest]

19 Prisoners can be guaranteed a stay of exicution and the 20th prisoner has a 50% chance of survival.

[roolstar]

Sounds good....

Is your method bullet proof for all possibilities?

Does it work for 19 prisoners?

[Guest]

yes.

hint:

the prisoner at the end of the row (#20) has to be willing to sacrifice himself, or at leats risk sacrifice for the good of the group. (being in the military I can assure you all 20 would be willing to do that for comrads in prison together)

[Guest]

yes.

hint:

the prisoner at the end of the row (#20) has to be willing to sacrifice himself, or at leats risk sacrifice for the good of the group. (being in the military I can assure you all 20 would be willing to do that for comrads in prison together)

I assume you think prisonner #20 will tell the next prisonner the color of his hat but if all prisonners do the same, only prisonner #1 will be able to tell his own hat color. all others will have 50% chance.

To guarantee the freedom of 10 prisonners, #20 will tell #19's color, #18 will tell #17's color, etc.

[Guest]

bidonet: you are wrong in your assumption of the rest of my answer... good luck

[Guest]

bidonet: you are wrong in your assumption of the rest of my answer... good luck

A funny solution to guarantee 19 prisonners free is to tell the color of your hat loud or normally, loud meaning the color is red and normally, the color is black. That way, you meet all criteria, 19 prisonners are safe and the 20th has 50% chance.

[roolstar]

A funny solution to guarantee 19 prisonners free is to tell the color of your hat loud or normally, loud meaning the color of the hat in front of you is red and normally, the color of the hat in front of you is black. That way, you meet all criteria, 19 prisonners are safe and the 20th has 50% chance.

This technique would work (I suppose you meant the amended solution Bidonet)

stwalk technique may also work, provided it was very well rehearsed...

Now can you find a bullet proof technique, in case the king does not allow us to change the intonation of our voice, or makes us click on the right answer on a giant screen in front of everybody, or makes us push either one of two buttons where the computer says the choice we made.....

I'm just adding these handicaps because this is what I meant by saying: no communication is tolerated (touch, words...). Communication means no message to be sent by voive or touch or noise or light...

HINT: The words RED or BLACK from the first person asked will give all the info for the rest of the prisoners!

Can you find other solutions while respecting these new complications? (and there are more than one)

PS: This is not a latheral thinking puzzle. Common sense and logic can get you safe from being executed in this case.

[unreality]

It seems like that's impossible- the person at the very front, who goes first, who can see the 19 people in front of him, has no idea what color his own hat is. It seems like he would always have a 50/50 chance, so there can never be a 100% sucessful outcome. Or is my reasoning wrong?

[Guest]

It seems like that's impossible- the person at the very front, who goes first, who can see the 19 people in front of him, has no idea what color his own hat is. It seems like he would always have a 50/50 chance, so there can never be a 100% sucessful outcome. Or is my reasoning wrong?

Your reasoning is correct. It was stated that a correct strategy would guarantee the safety of 19 of the 20, with the 20th (first to guess) having a 50% chance.

With no other information present, I don't see how this is solvable. What strategy would allow you to say the word "red" or the word "black" and tell nineteen people which of two colors each was wearing? I believe it is impossible; you cannot convey that much information in a simple binary choice.

I can see a method to save at least 13 of the 20 people:

The first person looks at the two hats in front of him. If the hats are the same color, he says "red". If they are different colors, he says "black". This guarantees the safety of the two people in front of him, since the next guy in line will be able to figure out his own color. Starting with the first, every third person uses this code. There will be two people left at the end; the second-to-last guesses the color of the last person's hat, so the last person will also be assured of survival. If done correctly, only seven of the twenty will be in danger of death. A mathematically average run would see 3 or 4 executions among the 20, a 15-20% mortality rate -- not bad odds for 20 condemned prisoners. At worst, 13 survive, for a 65% minimum survival rate. And there is one chance in 128 that all will survive.

[Guest]

wow this sounds like a really fun one

I'm busy right now but I'm gonna sleep on it and tell you if I've found anything tomorrow... mK

[unreality]

I just figured out how to save 19 people FOR SURE I think. Maybe 18

[unreality]

Okay I was wrong- it saves 15 people FOR SURE and the other 5 each have a 50% chance of survival, meaning on average there will be 17.5 survivors (2 short of the 19.5 of the "perfect solution" of this problem), or a 1/32 that all 5 will make it.

Call them p1 through p20. p1 can see p2...p20 (all 19 in front of him). p2 can see all 18 in front of him. etc. p20 can see nothing.

p1 looks at p2, p3, and p4. If p2 and p3 are the same, he calls p4's hat color. If he sees that they are different, he calls the opposite of p4's hat color. Since both p2 and p3 can see p4, they know if they are the same or different based on what p1 called. If they are different, p2 says what p3 isnt, if they are the same, p2 says what p3 is. Then p3 knows what he is, because of this.

If they both called out the same color then p4 knows that his hat color is what p1 called. If they call out different colors, then p4 knows his hat is OPPOSITE of what p1 called. p2,3 and 4 are saved. p1 has a 50% chance.

Start over. p5 has a 50% chance, then p6,7,8 are saved.

The following have 50% chances:

p1, p5, p9, p13, p17

The rest have 100% chance of survival.

That's 15 people saved no matter what, and the other 5 people have a 50% chance, which means there is a 1/32 chance that all 20 survive, though it is likely that 17.5 people will survive on average... as said, 2 short of the 19.5 average of the "perfect solution"

It may be possible to expand on my technique. I tried but this seemed to make the most of it, and it seems that 15 people guaranteed is the best you can do- though stwalk thought 13 people was, so I'll keep working for that 19

[roolstar]

With no other information present, I don't see how this is solvable. What strategy would allow you to say the word "red" or the word "black" and tell nineteen people which of two colors each was wearing? I believe it is impossible; you cannot convey that much information in a simple binary choice.

You are on the right track in your reasoning spoxjox.

The most reliable and correct method should devide the big universe of possibilities of the 20 prisoners into 2 possibilities

And I assure you there is a way: don't give up yet guys...

I'm will not post a spoiler just yet. Finding the solution of this puzzle is a lot more fun than discussing the solution.

PS: The answer may surprise you with its simplicity. (OK enough hints for now)

[bonanova]

1

[Guest]

yeah, I'm havin trouble with this one..

[unreality]

1

In mine (a few posts up) I saved all but 5. Hmmm I must rethink this...

[unreality]

I hope its not something stupid like "Oh to make it a fair challenge the evil king makes everyone's hat color the same", I highly doubt it.

Is my answer on the right track at least?

[bonanova]

I hope its not something stupid like "Oh to make it a fair challenge the evil king makes everyone's hat color the same", I highly doubt it.

It's not. The strategy works for any distribution of colors.

Is my answer on the right track at least?

Yes. The survival of the first prisoner to speak cannot be guaranteed.

The others, if they follow the strategy and listen to all of the previous speakers, will know their hat color.

Roolstar gave a good clue:

The most reliable and correct method should devide the big universe of possibilities of the 20 prisoners into 2 possibilities

The first speaker tells which of these possibilities is true. What are the possibilities?

[Guest]

Your hint about 2 possibilities made it suddenly clear. Try this:

The first speaker counts the number of red vs black hats on the remaining 19. Whichever there are more of, is the color he says his is. Since there are 19 remaining, there must be more of one color or the other.

2nd speaker also counts the number of red vs black on the remaining 18. Based on the first person's pronouncement, he knows which color there should be more of on the 18 plus his own. He compares what he sees and knows which color his own hat must be.

3rd-20th speaker should be keeping track of the the changing number left based on each previous speakers correct pronouncement and can compare that to the number they see in front of themself. They will be able to correctly deduce their own color.

to illustrate as an example:

#1 sees 10 red and 9 black (10R/9B), he says red -maybe gets lucky and survives, if not he is the 1 sacrifice we knew we might have, brave soul that he was.

# 2 sees either 10R/8B or 9R/9B on the remaining 18 in front of himself. He knows there should be 10R/9B including his own so he knows which his must be.

# 3 knows from the original 10R/9B, accounts for the correct answer that #2 gave, then deduces his own color from what he sees in front of him.

# 4 - 20 repeat, keeping track of the running count of R & B vs what he sees in front of himself.

example 2

#1 sees 18R/1B - says R - maybe gets lucky on his own.

#2 two possibilies: he sees 18R/0B and knows he's B or he sees 17R/1B and knows he's R

etc.

This should work no matter what the initial distribution of hats is.

[Guest]

oops = thought it through and realized my logic didn't work. I think I'm on the right track - but didn't quite get it.

[unreality]

all you know is if there are more or less, so it only works if it's a tie in front of you, that's the only way you could deduce your own color. And then that would tell nothing to the people in front of you, so 10 would live for sure and 10 would have a 50/50. Yours doesnt work

the best one I've found so far is the one I posted a while back where 15 people are saved no matter what, but I'm thinking for the 19-saved solution

[roolstar]

Try this:

The first speaker counts the number of red vs black hats on the remaining 19. Whichever there are more of, is the color he says his is. Since there are 19 remaining, there must be more of one color or the other.

2nd speaker also counts the number of red vs black on the remaining 18. Based on the first person's pronouncement, he knows which color there should be more of on the 18 plus his own. He compares what he sees and knows which color his own hat must be.

3rd-20th speaker should be keeping track of the the changing number left based on each previous speakers correct pronouncement and can compare that to the number they see in front of themself. They will be able to correctly deduce their own color.

Very nice try PDR! This was my first intuition when I was first presented with this puzzle. And you are on the right track in your thinking process.

I'm feeling that someone else will get this one soon...

[Guest]

Okay, with all the clues and attempts, I think I've found a solution. If it's wrong, it's my fault, but if it's right, credit goes mostly to others who have already tried (and to those who gave hints).

The first person to guess sees 19 hats in front of him. The hats can divide up in several ways:

0 red, 19 black

1 red, 18 black

2 red, 17 black

...etc...

8 red, 11 black

9 red, 10 black

10 red, 9 black

11 red, 8 black

...etc...

17 red, 2 black

18 red, 1 black

19 red, 0 black

In each case, the number of hats can be represented as one even number and one odd number. The first guesser simply guesses the color of the EVEN number of hats. The second guesser, counting the hats he can see, can quickly deduce the color of his own hat based on the first guesser's statement of the even number of hats -- if he counts two odd numbers of hat colors, he knows he must have the remaining hat color named by the first guesser in order to complete the even number, and if he counts two even numbers of hat colors, he knows he must have the other hat color to make it odd. The second guesser can then use the first guesser's statement to state his own hat color, and so on down the line. Only the first guesser is liable to execution; if done correctly, I believe this will assure that all other guessers, as long as they keep track of the previous guesses and use logic correctly, will always be able to guess their own respective hat color.