One of the riddles that are driving me crazy

[GigaCluster]

See if you can solve it....

(I am not stupid... I am not stupid... I am not stupid... *sigh*)


10 straight-jacketed prisoners are on death row. Tomorrow they will be arranged in single file, all facing one direction. The guy in the front of the line (he can't see anything in front of him) will be called the 1st guy, and the guy in the back of the line (he can see the heads of the other nine people) will be called the 10th guy. An executioner will then put a hat on everyone's head; the hat will either be black or white, totally random. Prisoners cannot see the color of their own hat. The executioner then goes to the 10th guy and asks him what color hat he is wearing; the prisoner can respond with either "black" or "white". If what he says matches the color of the hat he's wearing, he will live. Else, he dies. The executioner then proceeds to the 9th guy, and asks the same question, then asks the 8th guy ... this continues until all of the prisoners have been queried.

This is the night before the execution. The prisoners are allowed to get together to discuss a plan for maximizing the number of lives saved tomorrow. What is the optimal plan?

Hint: if there are N prisoners, you can save N-1 lives, guaranteed!

 

[Orsorum]

Just have the guy in the back say the color of the hat on the guy in front of him. Saves every life but his.

 

[GigaCluster]

Originally posted by: Zakath15
Just have the guy in the back say the color of the hat on the guy in front of him. Saves every life but his.

That seems simple and correct, but it doesn't work.

Imagine that you're in the back of the line and wearing black (not knowing that), the person right ahead of you is wearing white, and the person ahead of HIM (8th) is wearing black. You see that person 9 is wearing white, so you say white. You die. The 9th person, knowing now his true color, is in a dilemma: if he says white, he lives but the person ahead of him doesn't know........................ DAMN.... he knows!

I didn't think this through!

 

[fatbaby]

5 black hats and 5 white hats correct?

 

[Cyberian]

Originally posted by: Zakath15
Just have the guy in the back say the color of the hat on the guy in front of him. Saves every life but his.

Good! - You get to be the last guy in line!

 

[Orsorum]

Originally posted by: GigaCluster

Originally posted by: Zakath15
Just have the guy in the back say the color of the hat on the guy in front of him. Saves every life but his.

That seems simple and correct, but it doesn't work.

Imagine that you're in the back of the line and wearing black (not knowing that), the person right ahead of you is wearing white, and the person ahead of HIM (8th) is wearing black. You see that person 9 is wearing white, so you say white. You die. The 9th person, knowing now his true color, is in a dilemma: if he says white, he lives but the person ahead of him doesn't know........................ DAMN.... he knows!

I didn't think this through!

Ohhhh.... riiight.

 

[Orsorum]

Originally posted by: Cyberian

Originally posted by: Zakath15
Just have the guy in the back say the color of the hat on the guy in front of him. Saves every life but his.

Good! - You get to be the last guy in line!

 

[MacBaine]

Originally posted by: Zakath15
Just have the guy in the back say the color of the hat on the guy in front of him. Saves every life but his.

But let's say the 10th guy says 'black', the color of the guy in front of him. If the 9th guy then says, black, he'll live, but the 8th guy won't have a clue. If you do it this way, you'll save 5 of the 10.

Edit: beat me to it

 

[Orsorum]

Originally posted by: MacBaine

Originally posted by: Zakath15
Just have the guy in the back say the color of the hat on the guy in front of him. Saves every life but his.

But let's say the 10th guy says 'black', the color of the guy in front of him. If the 9th guy then says, black, he'll live, but the 8th guy won't have a clue. If you do it this way, you'll save 5 of the 10.

Ja ja...

 

[MacBaine]

If there are 5 of each color, then the prisoner just needs to count the color of each in front of him, and determine which is missing. Each one in front of the last needs to remember how many of each have been called out.

 

[Orsorum]

Originally posted by: MacBaine
If there are 5 of each color, then the prisoner just needs to count the color of each in front of him, and determine which is missing. Each one in front of the last needs to remember how many of each have been called out.

Is it, in fact, an even number of each?

 

[HomeBrewerDude]

Originally posted by: GigaCluster
See if you can solve it....

(I am not stupid... I am not stupid... I am not stupid... *sigh*)


This is the night before the execution. The prisoners are allowed to get together to discuss a plan for maximizing the number of lives saved tomorrow. What is the optimal plan?

pretty nice of the guards to let them do that...


Nth guy (last in line - first to have to respond) responds with the color of the hat directly in front of him.

Nth - 1 guy then will then know the color of his hat, and can do something like respond immediately or after a long pause, depending on whether of not HIS hat color matches the hat color in front of him.

repeat this process. All but one guy will live for sure, and possible all of them will live.

 

[Orsorum]

Originally posted by: yamahaXS

Originally posted by: GigaCluster
See if you can solve it....

(I am not stupid... I am not stupid... I am not stupid... *sigh*)


This is the night before the execution. The prisoners are allowed to get together to discuss a plan for maximizing the number of lives saved tomorrow. What is the optimal plan?

pretty nice of the guards to let them do that...


Nth guy (last in line - first to have to respond) responds with the color of the hat directly in front of him.

Nth - 1 guy then will then know the color of his hat, and can do something like respond immediately or after a long pause, depending on whether of not HIS hat color matches the hat color in front of him.

repeat this process. All but one guy will live for sure, and possible all of them will live.

Oooh, not a bad idea.

 

[Jhill]

The person in back will just say his own color in a very high or very low tone of voice. High Means white low means black, or vise versa for the next guy. All live exept the last guy who has a 50/50 chance.

Easy.

 

[GigaCluster]

Thinking about it some more, I realize that my "eureka" a few minutes ago was false.

Let's say we are examining the last three men, as in my last example.

8 - black
9 - white
10 - black

Man 10 does not know his color, so he says "white". He dies.
Man 9 knows now his color. If he says white, he lives BUT the man ahead of him (#8) now does not know his color!

How do you explain that?!?

 

[Orsorum]

Originally posted by: GigaCluster
Thinking about it some more, I realize that my "eureka" a few minutes ago was false.

Let's say we are examining the last three men, as in my last example.

8 - black
9 - white
10 - black

Man 10 does not know his color, so he says "white". He dies.
Man 9 knows now his color. If he says white, he lives BUT the man ahead of him (#8) now does not know his color!

How do you explain that?!?

No, that's right. Just incorrect reasoning on my part.

 

[GigaCluster]

Originally posted by: Zakath15
No, that's right. Just incorrect reasoning on my part.

So does the AT community have a good answer to this? (BTW, things like changing your voice based on the color are cheating. There is a proper solution that I don't know.)

 

[HomeBrewerDude]

(BTW, things like changing your voice based on the color are cheating. There is a proper solution that I don't know.)

NOW you tell us the details!


are there any other constraints? is the distribution of hats exactly 50%white, 50% black?

 

[GigaCluster]

Originally posted by: yamahaXS

(BTW, things like changing your voice based on the color are cheating. There is a proper solution that I don't know.)

NOW you tell us the details!


are there any other constraints? is the distribution of hats exactly 50%white, 50% black?

No, the original problem in my first post states that the color is completely random -- it may be 9 white, 1 black, vice-versa, or anything in-between.

 

[HomeBrewerDude]

actually, I just figured it out.

the first dude, is screwed. he has a 50/50 chance of living. So he says the majority color of hats.

the next guy, will then know his color and can respond truthfully.

the next guy will then be able to add the last guys to the hats in front of him and figure out his color.

so on and so forth.

everyone deduces the color of their own hats with out altering their response and viola, N - 1 guys live, and possibly all of them.

 

[MacBaine]

Originally posted by: yamahaXS
actually, I just figured it out.

the first dude, is screwed. he has a 50/50 chance of living. So he says the majority color of hats.

the next guy, will then know his color and can respond truthfully.

the next guy will then be able to add the last guys to the hats in front of him and figure out his color.

so on and so forth.

everyone deduces the color of their own hats with out altering their response and viola, N - 1 guys live, and possibly all of them.

But that is assuming again that they know how many of each color there are

 

[Jhill]

I stand corrected. I think Yamaha got it.

I
I
\/

 

[HomeBrewerDude]

okay... here it is.

10th guy agrees ahead of time to say white if the number of white hats is odd.
9th guy can deduce whether he has a white hat by counting the number of white hats. If odd, then he has black. If even then he has white.
each successive guy adds the number of white hats in previous positions to those in front of him, and can deduce his hat's color.

 

[merlocka]

10th guy agrees ahead of time to say white if the number of white hats is odd.

Yeah, we had this riddle in a digital comm class back in the day. It basically taught us how a parity bit works.