(And, though it amounts to just an instance of the same thing, different “information” being conditionalized upon)
Fantome: Do you agree that the following is true? A game wherein the magician rolls once for each contestant and then flips a fair coin to choose which die reports from (or equivalently, chooses always to report from the (say) red die) means that all six contestants should be answering “1/6” as P(7)?
If so, one easy way to resolve the paradox is to say that the above is the magician’s algorithm, and everyone in the story screwed up their calculation. (Regardless of the algorithm, someone somewhere in the story screwed up. I figure why not pick the [cleanest? fairest? least sly?] algorithm.)
If you don’t agree that above “1/6” is correct, this should get clarified. (Post 27 is on this point.)
Since the magician’s choice of algorithm affects the correct answers, either the magician must specify it or the contestants must weight their answers (via Bayes’ theorem) across the space agorithms they believe the magician might be using, which will involve their subjective speculation about what kind of guy he is, etc.
Interesting problem. It took me a while, but I finally found a solution with a 75% probablity of the prisoners going free:
If a prisoner sees that the other two hats are the same colour, then guess the other colour, otherwise keep silent.
This works in all cases except where they all have the same colour hat.
This was actually an easier problem: whoever goes first counts the number of black hats: if odd he guesses black, if even he guesses white. This tells everybody else what colour their own hat is, so they will now all guess correctly. The first guy has a 50% chance of surviving. So if there are n prisoners, the ecpected number of survivors is n-0.5.
Well done, that is the optimal solution.
The interesting thing about this puzzle is that, like the OP, it involves an apparent paradox, and the solution involves overlapping probabilities.
Obviously, each prisoner has a 50% chance of correctly guessing the colour of his own hat, without any other information to go on. Seeing the other prisoners’ hats doesn’t tell a prisoner anything about his own hat, and one intuitively feels that it ought make no difference. And yet somehow they can increase their chance of getting a correct guess to 75%.
No, I’m going to let them start from zero like we did. And that includes figuring out what are the right questions to ask about assumptions.
Are the prisoner examples assuming that the first guy is talking in some sort of simple prearranged code? Y’all danced around this point without being explicit about it.
No pre-arranged code. There are eight combinations the three prisoners can wear black and red hats. If they follow their pre-arranged solution (if a prisoner sees that the other two hats are the same colour, then guess the other colour, otherwise keep silent) they have a 75% chance of surviving.
In zut’s puzzle the first prisoner is, in effect, using a pre-arranged code. He is describing the “parity” of the hat colours, i.e. whether he can see an even or odd number of white hats.
The two prisoner puzzles mentioned above are quite different, despite their superficial similarity. In zut’s puzzle, communication occurs, albeit one-way communication (in fact, in the usual presentation of this puzzle, the prisoners stand facing forward in a line and can only see the hats in front of them. The parity information is still enough for them to be able to deduce the colour of their own hats).
In the puzzle I mentioned, no communication takes place at all.
Further continuing the hijack, here is an interesting further prisoner puzzle that uses no communication at all:
There are infinitely many prisoners standing in a line (Prisoner 1 at the back, Prisoner 2 in front of Prisoner 1, Prisoner 3 in front of both of them, etc.). Each has a word written on their head. Each can see the heads of the prisoners in front of them, but no others. Each prisoner is asked to guess the word on their own head (though none others can hear this whispered guess). If infinitely many prisoners guess wrong, the Earth is destroyed; otherwise, if only finitely many prisoners guess wrong, everyone is given cake and a pony.
Before the head-words are assigned, the prisoners meet to discuss a strategy, as usual. What should they do?
(Hint: You can do really, really well… at least, according to mainstream mathematics)
Just to clarify, when I say “Each can see the heads of the prisoners in front of them”, I mean they can see the heads of all the higher-numbered prisoners, not just the one immediately in front of them.
Indistinguishable, I’m a bit stumped by your puzzle. I mean, there’s no communication (the guesses are whispered), so I’m having trouble seeing what useful information the people have. Well, they can see an infinite number of words on the people in front of them, but I can’t see how that helps. In fact, even if the words are limited to “black” or “white” (so we’re back to the hats again), I still can’t see a method.
I think I’m going to need another hint.
(One clarification: do the others know if a whispered guess was right or wrong?)
No, the prisoners are not informed if a whispered guess is right or wrong. Just as in Ximenean’s puzzle, there is no communication or feedback, and no prisoner has any means of gaining any information about their own head, and yet, counterintuitively, the team can still, nonetheless, strategize to do better than naive guessing.
It is very tricky, though. Here’s another hint, which may or may not be of any use: let’s consider an ostensible hardening of the problem. Specifically, let’s say prisoners not only have to guess their own head-label, but also have to guess the head-label of everyone behind them. Just as before, if infinitely many prisoners get something wrong, bad, but if only finitely many prisoners get something wrong, good.
As it turns out, this actually doesn’t make the problem any harder; the same optimal solution transfers to this case just as well. I know; it’s hard to believe you can do anything, but, well… Just as in Ximenean’s puzzle, the counterintuitive turns out to be possible.
Ack, I’m sorry, I wasn’t thinking properly when I wrote that hint. It’s incorrect. Ignore everything in the above post except the first paragraph. Replace the rest with:
It is very tricky, though. [Hint forthcoming]
Alright, here’s a proper hint: let’s consider an ostensible hardening of the problem (and this time, I’m not fucking it up). Specifically, start off by running the game exactly as described in post #69. After that, if the world has not yet been destroyed, then enter Round 2: in this round, each prisoner is asked “What do you think each person behind you guessed in Round 1?”. If any prisoner makes any mistakes, the world is destroyed. Otherwise, more cake and ponies.
As it turns out, the optimal solution to Round 1 immediately yields an optimal approach to Round 2 as well. I know; hard to believe, but…
Hmmm
There is one piece of information that people have: they know whether they are person #1, 2, 3 etc. (or is this an incorrect assumption?)
So if they adopt a strategy of person 1 saying “aardvark”, person 2 saying “aardwolf” etc then in round 2 everyone will know what those behind them guessed. But that strategy doesn’t guarantee a finite number of wrong guesses in round 1.
Again, even limiting it to “black” and “white”, I still can’t see a solution.
A question: does your solution still work if they can only see a finite number of those in front of them (say 1000)?
New hint: In case it’s not explicit yet, the prisoners can, amazingly enough, guarantee a win.
This is a correct assumption.
Nope. However, the solution does still work if each prisoner can’t see the first 1000 people in front of them (as long as they can still see the rest).
I wouldn’t be embarrassed; the problem stumps almost everyone. (Incidentally, your simplifying instincts are good; it really makes no difference if we limit ourselves to “black” and “white”. I’ve just tossed in the added generality because I can and it looks more impressive that way, but the solution is all the same, either way). So, after your next post, I’ll start holding your hand and walking you towards a solution. But until then:
Right. But this leads me to one last hint:
This time, let’s look at a slightly easier game with the same setup (prisoners with head-labels, can only see forward, no communication, etc.). Instead of asking each prisoner to guess their head-label, the warden just asks each prisoner to say something, anything. If every prisoner says the same thing, hooray; otherwise, boo.
Of course, this is easy; the prisoners could just prearrange to all say “aardvark”. Apart from just prearranging a constant response, though, are there any other strategies that work for this game?
Well, I slept on this problem. Then I saw your latest hint and thought about it a bit more during my Saturday morning run.
And I’m still stuck.
Other than agreeing on a specific word, they could have a strategy like 'looking at the infinity of hats, if we see (something) then say “black”, otherwise say “white” ’
Now in a sense they are all looking at the “same” infinity of hats/words, but I can’t think what that (something) could be.
So unless anyone else has some ideas, It’s now time for some hand holding.
Sorry, don’t yet have time to launch into the hand-holding proper, but:
You have the right idea. For example, one strategy the prisoners could use is "If anyone in front of you can only see white hats, say ‘It eventually turns all white.’ Otherwise, say ‘It never turns all white’ ". Similarly, they could answer questions like “Do the colors eventually just keep alternating?” or “Does the three-hat sequence <black, white, white> appear infinitely often?”. (If we don’t restrict ourselves to colors, we might choose to look at questions like “Do the labels’ lengths eventually keep increasing?”. Departing from yes/no questions, we might even use the strategy “If the labels eventually become a sequence of numbers with a rational limit, announce the limit. Otherwise, say ‘pineapple’.”)
As these examples illustrate, there are many properties and functions of label-sequences which depend only on “long-term” behavior, in the sense of being unaltered by changing any particular individual label. (Or even any finite number of labels). Every prisoner will be fully capable of calculating any such “long-term” function of the head-label sequence of all prisoners, since it won’t actually matter what the finitely many labels they can’t see are.
Note that two label-sequences have all the same long-term properties if and only if they’re equal from some point on. In this case, we’ll say the two label-sequences “have the same germ”. (This perhaps corresponds to your idea that all the prisoners are looking at the “same” infinity of hats/words)
[To be continued…]
Indistinguishable, you aren’t assuming (in the original problem) that each prisoner can see at what time the other prisoners make a guess, are you? I would take that as violating the “no communication at all” rule, but otherwise I just don’t see how seeing all the words of the higher-numbered prisoners provides any information to a given prisoner about their own number. That would be true for every prisoner.
I like to think of the case where the words all happen to be one of “zero”, “one”, …, “nine”. Then the set of words can be thought of as decimal number between 0 and 0.9999999… But that number could have all its digits selected randomly, so there’d be no relation between any of the digits, and no predictable long term behavior.
I’m not assumng that each prisoner can see at what time the other prisoners can make a guess, or any such thing. This isn’t some kind of trick question; the “no communication at all” rule is hewed to entirely.
You are correct that no prisoner can receive any information about their own label. Yet the task I’ve set out for them can be accomplished nonetheless. It’s just like Ximenean’s problem in this respect (see the solution to his problem and his explanation here. As he says, “Obviously, each prisoner has a 50% chance of correctly guessing the colour of his own hat, without any other information to go on. Seeing the other prisoners’ hats doesn’t tell a prisoner anything about his own hat, and one intuitively feels that it ought make no difference. And yet somehow they can increase their chance of getting a correct guess to 75%.” The intuition that some prisoner needs information about their own hat in order to accomplish the task is erroneous. No particular prisoner can have any confidence at all that they will guess their own hat correctly. And yet, the team can have the utmost confidence that many of them will guess correctly, all the same. The former does not actually contradict the latter, erroneous intuition notwithstanding.)