When I read the OP, the answer was obvious. The first six people were providing conditional probabilities and they were all correct, i.e., the magician said “at least one of your dice is a <some number>”, what’s the probabililty that both coins add up to 7. The seventh person answered without waiting for the magician to provide the conditional event. In that case his correct probability is not 2/11, but 1/6. What’s so hard about that? Even if the seventh person had assumed that the magician will provide the conditional event, he may or may not be correct with his 2/11 answer depending on the probability of the conditional event. That part of the magician’s modus operandi was ambiguous.
Yes, if you can’t show that it is possible to do so when there are uncountably many movies. That’s what I’m asking for.
From post 106
Can you show how to pre-choose an uncountably infinite set of guess-sequences? Or at least show that it is possible to do so?
Ah, ok. Well, this is where I appeal to the axiom of choice, as I mentioned in post #115 (and in accord with the parenthetical disclaimer in my post originally posing the problem). It’s not possible to explicitly specify a particular way of doing it; however, within mainstream mathematics, it is nonetheless postulated that many such ways exist.
I don’t know why you keep emphasizing that there are uncountably many choices to make, though. Would you be perfectly happy if there were only countably infinitely many choices being made? Why the distinction?
Let me try and get an idea of where you’re coming from by rephrasing the axiom of choice in a different way.
The inhabitants of a certain island are faced with a unique challenge: a volcano is about to erupt, the result of which will be the destruction of the island. However, a kindly local deity takes pity upon the inhabitants, and offers them the following deal: if each plucks precisely one hair from his (or her) head, the island will be spared from the volcano. As it happens, no one on this island is bald; beyond that, you don’t have any information about how many islanders there are, nor about their hairs.
Is it possible for the island to be saved?
A) Yes
B) No
C) It depends on how many islanders there are and/or facts about their hair.
If your answer is (A), congratulations: you are embracing the axiom of choice. Now, let’s link this back to the guessing prisoners problem: suppose there is an islander for each potential “winning set”, with his hairs corresponding to that set’s elements. You said it’s possible for the island to be saved, but note: any scenario under which the island is saved corresponds to a winning strategy for the guessing prisoners problem!
If your answer is (B), you’re being foolish. After all, there could be just one inhabitant, with his finger already placed on his one burdensome hair…
If your answer is (C), it looks like you are taking a perspective which does not accept the axiom of choice. This is not the usual mathematical practice, but, very well (indeed, I myself do this in many, perhaps even most, contexts).
However, in this case, let me ask you something else: Suppose the scenario is as above, except you are now also given the information that there are a countable number of islanders. Is it possible to save the island? (A) Yes, (B) No, (C) It depends on facts about their hair.
If you answer (A) this time, then you apparently accept the axiom of countable choice, even while refraining from accepting the full axiom of choice. My question to you is… why?
If you answer (B) this time, you’re a very silly man and I’m not going to interview you further.
If you answer (C) this time, it looks like you don’t even accept the axiom of countable choice. Great. But then, why make such a big deal over emphasizing the “uncountability” of the number of arbitrary choices going into a strategy for the guessing-prisoners-problem, instead of merely the “infiniteness” or something like that?
I think I’ll choose to go back to the original hijack 
Today I came up with a 4 prisoner version of Ximenean’s problem:
Four prisoners are put in separate rooms, and have either a white or a black hat placed on their head, randomly with equal likelihood. They can’t see the colour of their own hat, but can see the other prisoners’ hats by video camera. The prisoners have no way of communicating with each other.
On the stroke of midday, each prisoner must guess the colour of his own hat.
If the prisoners are all correct OR all incorrect then they all go free, otherwise they are executed.
As is usual with these problems, the prisoners are allowed to confer beforehand.
What is the proability that they go free?
100%?
If you see two of one colour and one of the other, guess the same as the single colour. If you see three of the same colour, guess the same colour.
XXXX - all guess correctly
XXXY etc. - first three guess Y, last guesses X, all wrong
XXYY etc. - all guess correctly
Yep, 100%
There is also another solution (which is the opposite of the one you gave):
If you see two of one colour and one of the other, guess the same as the double colour. If you see three of the same colour, guess the other colour.
XXXX - all guess incorrectly
XXXY etc. - first three guess X, last guesses Y, all right
XXYY etc. - all guess incorrectly
These two solutions (“Guess black just in case you see an odd number of black hats”, and the same with “odd” replaced by “even”) generalize to any (finite) number of prisoners. Moreover, in each case, they are the only solutions.
(To see this, note that whenever a prisoner’s hat color is unilaterally changed, he still makes the same guess, but it switches in correctness. Thus, every other prisoner’s guess will have to switch to accomodate. Since any prisoner-hat-configuration is only a finite number of changes apart from the configuration with no black hats, a description of an entire solution can be reduced in the straightforward manner to just a description of what to do in the 0-black case (for which there are, of course, simply the two possibilities of getting it all correct and getting it all incorrect))
Yes. here’s why.
Let’s try a simpler version. The words are limited to “zero”, “one”, …, “nine”. It turns out there’s a hat rack with a big black sphere on top behind the first person. Interpreting this as a decimal point, and all the words as their corresponding digits, we have a decimal number in the range 0.0000… to 0.99999. We will require this number to be a rational number.
In this restricted version, we can show everything you discussed. A rational number eventually repeats with some period P. We’ll spend 1/2 minute checking if P is 1, then 1/4 minute checking if P is 2, 1/8 minute checking if P is 3, and so on. Once we find a period where the digits eventually repeat, we’re done, and can stop checking.
Say we’re checking if P is 2. Start with the count C=0, and the start S=0. Each prisoner N will compare the digits (N+1,N+2) to (N+3,N+4) in the first 1/8 minute, then compare the digits (N+2,N+3) to (N+4,N+5) in the next 1/16 minute, and so forth. If C = 0, set S = the lowest of the four digits being compared. If the digits match set C = C+1, else if the digits don’t match, set C=0. At the end of checking P=2, if the digits repeat with a period of 2, C will be infinite, S will be the start of the repeating portion, and we’re done. If the digits don’t repeat with a period of 2, S will be infinite, and we move on to P=3.
Continuing this, after one minute, we have the period P, and S which is the start of the repeating portion. For every prisoner N prior to the repeating portion, they will have the same value of S, and all the rest will have S = N+1. They can all now take the repeating portion, and extrapolate it backwards and use that for their guess. As you said, they can also say what all the others behind them guess.
So for example, if the words were “nine”, “four”, “seven”, “three”, "two ", “three”, “two”, "three’, … with the "three"s and "two"s continuing to alternate endlessly, the guesses would be “two”, “three”, “two”, “three”, … with only three wrong guesses.
Further, I can list all the representative strings of words in this case (I’m going to just list the digits instead of the words):
000000…
11111…
…
99999…
010101…
020202…
…
989898…
001001…
…
998998…
…
In this restricted case, it’s easy to see how there are only a finite number of incorrect guesses. An infinite number of prisoners are in the repeating tail, and guessing correctly. Only the finite number of prisoners prior to the repeating portion guess incorrectly.
I don’t see how to generalize this to the unrestricted problem. The essential difference between this case and the unrestricted case is that I can explicitly tell you precisely what a complete set of representative strings are. If you remove the restriction that the number corresponding to the string of words be rational, what are the representative strings of words? Obviously you can’t simply list them, but can you somehow specify them unambiguously? (And If so, what are a set?)
(I haven’t had time to read all your posts. Hopefully tonight.)
No, there is no explicit description I can give you in English which will unambiguously specify a particular way of choosing representatives. This is why I appealed to the axiom of choice. But this fact has nothing to do with the fact that the number of choices is specifically uncountable.
There are situations in which one is asked to make an uncountable number of choices, and is able to do so with an explicit rule: e.g., pick one natural number from every non-empty set of natural numbers. One can do this by picking the smallest number from each set. Similarly, suppose you are asked to pick one square root for each real number. One can do this always picking the non-negative one.
There are also situations in which one is asked to make a countable number of choices, and is unable to do so with an explicit rule. Hell, there are situations where one is asked to make even just one choice, and is unable to do so with an explicit rule: in Universe Cyblorgia, there are two planets. Pick one. [Asking for more information about them won’t help: they’re both perfectly spherical, of exactly the same size and color, and so on…]. Or, let’s call a real number “generic” if it satisfies every explicitly describable property which holds with probability 1 of a random real in [0, 1] (thus, it must be irrational, not equal to pi/4, etc.). Pick a generic real (it’s not possible to explicitly describe one, yet, with probability 1, a real drawn at random from [0, 1] will be generic).
You might want to say: without an explicitly describable rule, how could the prisoners ever come to agree on a choice? Well, I don’t know; if asked to select a planet from Cyblorgia, or a generic real, are the prisoners to be like Burridan’s Ass, indecisively paralyzed? Or shall we allow Prisoner #1 to boldly point his finger at a Cyblorgian planet/generic real at random, announce “Let’s go with that one”, and have all the others look on and nod their head in agreement?
Just to clarify what the axiom of choice does and doesn’t do: it doesn’t give me an explicit description singling out a particular way of choosing representatives. It is simply hopeless to look for that. But what the axiom of choice does do is prove that there exist ways to choose representatives, even if no explicit description can be given singling out any particular one of them. (Just as the statement “There exist two planets in Cyblorgia” assures me that there exist planets in Cyblorgia, even if no explicit description can be given singling out any particular one). Without a principle such as the axiom of choice, I could not conclude even this.
I just want to say that I love this thread.
A cool probability paradox leading to riddles, one of whose answers is entirely dependent on an abstract mathematical axiom? Awesome.
Had a chance yet?
(Ah, the problem with going bump in the middle of the night. Let me try this one last time, when there’s actually a chance it might be seen.).
There may be cases with only countably many possibilities where specifying a set of guess sequences is not feasible, but that’s not really the point. The point was to show a non-finite case where it can be done, as an example of what I was asking for back in post 116. The guess sequences the prisoners come up with will need to be specified with similar precision, or else no cake and ponies.
I’ve been emphasizing it being uncountable because I could see how to get a solution for a countable case, but not for your uncountable one. I’m still not convinced that specifying a set of guess sequences for the case we’re interested in is possible. From the Wikipedia link on Axiom of Choice (my bolding),
So assuming the Axiom of Choice, so that you can assume that there exists a set of guess sequences, not only doesn’t tell you how to define a set, it doesn’t tell you that it is possible to define a set. If a set exists, but isn’t definable, then there’s no way for the prisoners to pre-choose the set they’re going to use. The Axiom of Choice does show that my argument back in post 94 is flawed, but it doesn’t show that your problem is solvable.
From what I hear, they’ve all settled on letting prisoner 65404 decide. Hey, that’s you!
Ah, alright. But that’s still not really intrinsically about countability vs. uncountability; I mean, you picked a very specific case you could handle, which just coincidentally happened to be countable. Countability vs. uncountability was a red herring for your point. But whatever; I understand now why you were making the emphasis you did.
That’s correct; it may lack a (finite) definition in English (or whatever language).
The axiom of choice shows that there exists a (deterministic) strategy which, if the prisoners followed it, would guarantee a win. That is, it shows that winning strategies exist. Whether any of those strategies are definable in English or not is a separate question.
But, if you are particularly concerned with that separate question, what we know is this: If we allow non-deterministic strategies, I can define in English the strategy “Have Prisoner 1 pick, at random, one of the winning deterministic strategies. Then have him communicate it to the other prisoners. Then have them all follow it.”
Of course, there is the question of how he is to communicate it to the other prisoners. He probably couldn’t do it in (a finite amount of) English. But, then, part of the problem is that a finite amount of English won’t give him enough time to simply specify the strategy in full (“Our representative sequences are <white, white, white, white, …>, <black, white, white, black, white, white, …>, <black, black, black, white, white, …>, …”). But these guys are supposed to be able to manipulate infinite information like silly putty. Who cares if they can’t communicate the whole thing in a finite string of English? Let them use an infinite string of English. Or, let him just grab a suitably infinite number of black and white pebbles, lay them on the table to form the representative sequences, and have everyone look at it. Or whatever.
Heh, took me a while to understand the significance of 65404. Anyway, like I said, what I would do is pick, at random, one of the winning deterministic strategies (the axiom of choice proves that these exist, while staying mum on the matter of their English-definability). Then, I’ll grab a whole shitload of pebbles and show everyone the strategy without saying a word. (No one’s tying my hands and forcing me to communicate using only short bursts of English).
I don’t mean to say that it’s not also interesting to investigate questions like “What could the prisoners do if they were restricted to ‘finitely-definable’ deterministic strategies?” or “What could they do if they could only communicate ‘finitely-definable’ quantities?”. Indeed, it’s even interesting to investigate questions like “What could the prisoners do if they couldn’t act on the entire infinitude of labels in front of them at once, but, instead, had to each act, in the end, on only finitely much information?”.
And your instinct that the infinitely many arbitrary many choices being made can’t be handled by any finite rule is a good one, in the sense that it’s actually provable that, in the usual formal language of set theory, no finite term defines such a thing. Indeed, even if terms carrying out countable infinities of choices were present, this would still be true. So, in many ways, your instincts were accurate.
But I also think it’s interesting how, in the “These prisoners can manipulate infinities like silly putty” formulation, the game is winnable. I hope you can appreciate that, on this not-unreasonable reading of the problem, the solution I’ve outlined works out fine.
Accidentally elided words reinstated in bold.