470 replies to this topic

[Ploper]

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.

Spoiler for solution

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]

Spoiler for solution

1

[Ploper]

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

[unreality]

Spoiler for solution

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?

[PDR]

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

Spoiler for solution

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.