math/logics puzzle

[VJ]

A slight variation of this riddle:

http://www.ocf.berkeley.edu/~wwu/riddles/intro.shtml

10 prisoners 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 (unknown how many white/black hats there are). 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.
Each prisoner hears the other guys' answer, and hears whether or not the answer he gave was correct. They are not allowed to communicate beforehand (-> this is the difference with the above link), but every guy will adopt the optimal strategy.

What can they do in order to save as many as possible ?
(I have a thought that might save 8 people in worst case scenario, but I need to verify it )


Jörg

[SitFlyer]

As I see it, since the it's unknown how many white/black hats there are, each man only has a 50/50 chance to guess correctly.
No strategy involved here. It's all luck.

[VJ]

Actually, no... If #10 says the colour #9 is wearing, then #9 can answer his own colour. #8 however has no information about his hat, but can supply the colour of the hat in front of him. So using this strategy, only 5 people (worst case) could be saved (numbers 9,7,5,3 and 1). (They can only say 1 colour)

As everyone adopts the optimal strategy, there is something that can be done...


Jörg

[Gurm]

Dude, you're making a HUGE assumption. You're assuming that these people will, rather than guessing, call out the color of the hat in front of them in an effort to save the guy in front of them.

That was NOT a parameter in the puzzle as stated, and therefore CANNOT be assumed.

As stated, every man has a 50/50 chance.

I have spoken.

- Gurm

[VJ]

It could be that I did not formulate it well (English is not my native language, puzzle was in Dutch originally), but the question is (I'll try to reformulate) : How can as many of all the people be saved, when everyone adopts the (unknown) optimal strategy ?
If the above were to be optimal, then everyone would realise it, and be able to act accordingly.

Jörg

[Nowhere]

if that asuumtption would work, 7 or 8 SHOULD be saved. The ones that are saying which color has the prisoner in front of them have 50% chance to say correct their own color...

but honestly I don't believe that would work at all - sooner or later the executor will notice that they are fighting for 1, 3, 5, 7, 9 positions
the ones on 2, 4, 6, 8, 10 could even say wrong on purpose...I mean, that wouldn't change their chance...in that case the ones on 1, 3, 5, 7, 9 know that the one behind him can say right or wrong - and again we have a 50/50 situation...

[VJ]

Well, I was thinking along these lines:

Optimal when they can communicate beforehand:
They agree that the last persons say "black" when he sees an even number of black hats (parity ! ). The other persons can then deduce, what colour their hat is, based on the knowledge they have of the colour of the hat behind them, and what they see.
However, when they are not able to communicate, there turn out to be 4 "optimal" solutions:
say "black" when you see an even number of black hats
say "black" when you see an odd number of black hats
say "white" when you see an even number of white hats
say "white" when you see an odd number of white hats
As there are 10 hats initially, there are always either even white+even black hats, or odd white + odd black hats. Person 9 however does not know wheter 10 used black->even or black->odd, so he cannot be sure. If he makes a wrong guess (despite what 10 did), we might have 2 victims, but then the others can deduce what hat they are wearing.
If he happens to be right by guess, then 8 gets in the situation.
Does this make sense ?


Jörg

[Kurt]

If they could have communicated beforehand, they probably wouldn't be prisoners in the first lace

I think you need to reformulate your problem.

[Nowhere]

besides you assume they'll choose the stretegy that's the best for the group - optimal from logical point of view.
And that's not the case in that kind of situations - we must also remember about social conditions...

[Ozbreeze]

i'm usually pretty good at these type of things...but i have no clue where to begin on this one....doh!

[Gurm]

Originally posted by Gurm
Yes. (He is right on this one, guys - work it out. You might lost the last guy, but the others walk!) So the only thing you're relying on in this solution is that the last guy has a 50/50 chance of survival. 9/10 make it, the 10th guy has a 50/50 shot... let's hope that last guy has some serious balls!



No, and I'll explain why...



This is really only two optimal solutions. Think about it. Odd black hats makes you say either black or white. All these solutions boil down to that. Period.



This is correct.



No. The others ALSO have no way of knowing what system the two others used.

Let's say guy 10 says "black". He is wrong. That means he had a white hat.

Guy 9 says "black". He is wrong. That means he had a white hat.

The others can ONLY deduce from this that those two guys had white hats.

-------------------- New possibility:

Now... let's say that, again, EVERYONE knows that everyone else will be using one of the above "optimal" solutions. In this case, number 8 has to think...

10 either saw an odd number of black hats (or white hats, it's irrelevant) or an even number. Let's say he used the system where odd black hats makes him say "black". He was wrong. His hat was white. Oops.

Now number 9 is faced with the following information.

- For some reason, #10 said "black". Either he saw odd or even black hats, but he said black.
- His hat was white.

So number 9 looks ahead, sees... either an even or odd number of black hats. Since he doesn't know what system #10 was using, he must also guess. Let's say he picks a system where an even number of black hats makes him say "black". Two possibilities here... either his hat is black or white.

Black: He goes free - he was the odd man.

Now number 8... he knows that 10 wore white, and 9 wore black. He doesn't know which of the 2 systems they used. He looks in front of him and sees either an even or odd number of black hats.

10 said black... he was wrong. 9 said black... he was right. There are 4 possibilities:

A. 10 OB=B, 9 OB=B
B. 10 OB=B, 9 EB=B
C. 10 EB=B, 9 OB=B
D. 10 EB=B, 9 EB=B

Let's assume, for a minute, that 8 sees an odd number of black hats in front of him. That makes his hat black, but he doesn't know that.

Now, if it's A, that means that 10 saw odd... and so did 9. But that makes no sense, since 9's hat WAS black. So we discount A.

If it's B, 10 saw odd... 9 saw even. In this case, 8 can deduce his hat color... must be black. He's right! Yay!

If it's C, 10 saw even... 9 saw odd. In this case, 8 can deduce his hat color... white! Oopsie, wrong.

If it's D, 10 saw even and so did 9... again, not possible since 9's hat was black. Discount D.

So... there are two possibilities. He has a 50/50 chance - same as if he just guessed!

If you extend this, you'll discover that it doesn't matter who knows what - it's all 50/50 in this case.

---------------------------------------------

And that's assuming (big assumption) that they all agree that basing your answer on odd/even number of black or white hats is the optimal solution.

The other solution is exactly the same.

If everyone calls out the color of the hat in front of them, it's STILL 50/50.

----------------------------------------------

I've heard a dozen variants on this puzzle in the past. I have a suspicion that there was one originating black/white hat puzzle, and it has since been so butchered as to be unrecognizable.

----------------------------------------------

There are other possibilities. Since they don't communicate, what if they don't know that there are black AND white hats?

What if the first 9 guys have black hats on? The last guy, even if he has a white hat, must assume that everyone has black hats, and won't even bother trying to escape.

Now once you start getting contrived, you make it more plausible.

Ok, so the captors have told the prisoners:

1. All of you are wearing hats, either black or white.
2. We won't tell you how many hats are black and how many are white.
3. There are a total of 10 of you.
4. You may say "black" or "white". If you're right, we tell everyone you were right and let you go. If not, they hear a bullet and you die.
5. If anyone says anything other than "black" or "white" (like "4 black hats in front of me! woo!") we mix you up, change your hats, and start over.

THAT is the setup. So your question now is - if the prisoners had no prior communication, what strategy can they adopt that boosts their odds past 50/50?

Heaven forbid that Marilyn Idiot Savant were answering this. With her utterly bizarre misunderstanding of probability, she'd say that everyone had an increasingly better chance, and try to back it up with some bizarre theory.

The truth is that I can't think of a way, in the 15 minutes I've spent on this, without prior communication or agreement, to boost the odds above 50/50.

I have spoken.

- Gurm

[Gurm]

Sorry about that. I have neither the time, energy, or inclination to fix it. You can get my gist from that post though.

- Gurm

[Gurm]

Did I bewilder you all so thoroughly that you've gone silent?

I have spoken.

- Gurm

[VJ]

No, it has just been busy...

I still have to work out the A/B/C/D cases, as I'm not convinced about the solution presented... I would expect A and D to be similar, and B and C to be similar also.


Jörg

[Gurm]

I laid it out pretty clearly, Jorg.

There may yet be an optimal case, but that ain't it.

I have spoken.

- Gurm