Alright, so, we basically defined the “germ” of a label-sequence to be all and only the information about its “long-term” properties; thus, two label-sequences have the same germ if and only if they are equal from some point on (i.e., if they only differ for finitely many prisoners).
Now remember, I gave the hint that, in Round 2, every prisoner should be able to figure out what every other prisoner’s guess was. That is to say, every prisoner should be able to figure out the entire sequence of guesses made. [To figure out the guesses of those in front of you is easy… you have all the same information available to you that they had in making their guess. But figuring out the guesses of those behind you? Hm…]
Well, a function of the prisoners’ head-label sequence can be calculated by every prisoner just in case it depends only on “long-term” information about the sequence. That is to say, such functions are those which can be calculated from the germ of the head-label sequence.
So what we know is that the sequence of guesses made is some function of the germ of the head-label sequence. We’ll call it GuessFunction. In order to be able to guarantee a win, it must be the case that GuessFunction(germ of HeadLabelSequence) is guaranteed to differ from HeadLabelSequence itself in only finitely many places.
Well, I’ve left you at just about the doorstep of the solution. Can anyone take it from here? [Of course, what’s clear to me might not be clear to others; feel free to ask me to explain or clarify my “hand-holding”]
As perhaps the simplest example of this phenomenon, consider the following game: there are two people wearing hats, either black or white. They can each see the other’s hat, but not their own. The warden will ask each to guess their own hat color; if they both get it wrong, they are slaughtered, but if at least one gets it right, not only are they set free, but the torturous warden is finally relieved of duty and imprisoned in their stead for his rampant abuse of power.
As usual, they can prearrange a plan but will have no later communication or feedback. You might think “Neither one can possibly gain any information about their own hat”. You would be right about that. You might think “Therefore, there isn’t any good plan they can come up with.” You would be wrong about that. They can actually guarantee success rather easily: have Prisoner #1 guess the opposite of the color he sees, while Prisoner #2 guesses the same color he sees. Voila!
For every particular prisoner, the odds are just the usual 50/50 that they’ll guess correctly. And yet, all the same, they can guarantee that at least one of them pulls it off.
A similar thing happens in my problem, just with more prisoners.
Indistinguishable, I’ve thought about this all day and I’m still stuck. I can see how to do better than random, for example (going back to the hats) 'if the next X hats have a majority of white, say “white”, otherwise say “black” ’
However, I simply can’t see how to only get a finite number of wrong guesses.
For every sequence of head-labels, there are many different guess-sequences which will win. Call the collection of all of these the “winning set” (of that head-label-sequence).
The key observation is this: once the labels are assigned and the prisoners are put in line, every prisoner is fully capable of determining what the “winning set” is. The finitely many heads they can’t see won’t matter, since the team is allowed arbitrarily large finite leeway in their wrongness.
So, when they meet beforehand to plan their strategy, this is what they’ll do: for every possible winning set, they’ll pre-choose some particular guess-sequence from it. Once placed in line, the prisoners will each determine what the winning set actually is, and then make their guess in accordance with the pre-chosen guess-sequence for that winning set.
Thus, by design, the sequence of guesses the prisoners make will be an element of the winning set; therefore, they will win. FIN.
(For those who have been following the discussion in the hints, “winning sets” are just another way of looking at “germs”.)
You defined the winning set as the collection of all guess-sequences that will win. So this means that they don’t actually know the winning set. They only know an infinite number of elements of the winning set, but they don’t know at least n elements of the winning set, where n is their prisoner number. I don’t see at the moment how they can choose all choose the same guess-sequence from the winning set when they don’t all know the winning set.
Prisoner n with word m can say, “Shit, (…, m+1, m+2, m+3, m+4,….) is a winning guess-sequence! Whoo!”
And prisoner n+1 can say, “Shit, (…, m+2, m+3, m+4,….) is a winning guess-sequence! Whoo!”
But I don’t see at the moment how they can all choose the same guess-sequence from the winning set when they don’t all know the complete winning set. For any guess-sequence with an arbitrarily large but finite number of mistakes, there seems to be an infinite number of prisoners who don’t know that guess-sequence, and so don’t share knowledge of the complete winning set. So how could they possible choose the same guess-sequence?
They do all know the complete winning set. I’m not sure what your reasoning is that they don’t.
Suppose I’m a prisoner, and I see in front of me some particular sea of hats. I can reason to myself “If a guess-sequence is wrong only finitely often, then, in particular, it has to match up with the sea of hats in front of me at all but finitely many locations. Conversely, if a guess-sequence is wrong infinitely often, then it must mismatch with the sea of hats in front of me at infinitely many locations. Thus, a guess-sequence will win if and only if it matches up with the sea of hats in front of me at all but finitely many locations. Thus, even though I don’t know what the hats behind me are, I am perfectly well capable of determining which guess-sequences do and don’t win. Thus, I know exactly what the winning set is, in its entirety, even though I don’t know what the hats behind me are.”
That is to say, if I told you what the guess-sequence was, and I told you all but finitely many terms of the head-label-sequence, you would have enough information to figure out whether this was a win or not. The ability to do this is all you need to determine the winning set.
Maybe I’m confused about what a “guess-sequence” is.
If I’m prisoner 1, and there is a sea of black hats in front of me, then I know many correct guess-sequences that give a win. But there is at least one guess-sequence that I’m not sure about: the perfect guess. Do I have a white hat or a black hat?
w, b, b, b,…
b, b, b, b,…
One of these is a correct guess-sequence (if I’m not misunderstanding the term). One of them delivers a infinite number of correct answers and a finite number of incorrect answers, namely zero incorrect answers. So this guess-sequence should, I believe, belong to the winning set, which you said is a collection of all correct guess-sequences. But technically, I don’t know which sequence is part of the winning set, which would mean that my winning set is not complete.
I know we’re dealing with infinite sets of mathematically-inclinded prisoners, but this almost seems like a cheat. They can each learn an infinite number of infinite sequences in a finite amount of time?
I can’t see it as a cheat, since it’s been clear from the beginning that every prisoner sees, comprehends, and could potentially plan to deal with the infinite number of people in front of them. It’s only fair that they be able to stretch their minds without limit, have a plan for limitless contingencies, and then decide on one limitless answer for each and every contingency. A finite amount of time is all that’s needed when we consider how fast these felons can think.
This is a group of folks who can see beyond forever.
My mind is officially blown for today. I’m going to have to rely on alcohol to bring soothing comfort.
I’m still thinking about this, but I don’t see how this helps anyone guess the right answer. So for any person numbered N, even with the only possible words being “white” and “black”, and following Indistinguishable’s procedure, that person has a 50 percent chance of guessing wrong. For the set of people 1 to N, an expected number of wrong guesses is N/2. Since there are an infinite number of people, the expected number of wrong guesses is larger than any finite number you can name. How is this anything but infinite?
Right-ho. One gets 0 wrong and one gets 1 wrong, and you don’t know which is which, but you still know that both win, which is all you need.
C’mon… like Hellestal said, it’s been clear from the beginning that these people can act on infinite quantities of information with no problem.
Besides, who said anything about a finite amount of time?
The expected number of wrong guesses is infinite. That doesn’t mean it’s possible to make infinitely many wrong guesses.
If this is confusing, consider an analogy: suppose I am granted money at random with a 1/2 probability of earning $2, a 1/4 probablity of earning $4, a 1/8 probability of earning $8, a 1/16 probability of earning $16, and so on.
But all the same, no matter what, I will earn only a finite amount of money (maybe two bucks, maybe four, maybe just over a thousand, who knows?, but it’ll definitely be finite).
Finite time was suggested in the problem statement with respect to the lifetime of the earth (though not explicit).
I did say it was only almost a cheat. As the solution seems to depend on being able to process infinite sets.
Which makes me wonder - are they required to actually all agree on a particular guess-sequence? Given the infinite number of players, could any member of the winning set be chosen?
Two pages dedicated to a 1 in 6 chance of the roll of the dice! Forget the magician, and the scenario, they are not relevant! What are the odds of rolling a particular number from a di? One in six.
Yes, yes, whatever; there’s also the question of how to fit infinitely many prisoners within the finite volume of the Earth, and how long it would take for one warden to write labels on all their heads, and let’s not forget that the imaging abilities of the eye are unlikely to be able to discern an infinite number of labels at arbitrarily large distance, …
Any member of the winning set wins. But if they don’t all coordinate, it’s likely the sequence they produce won’t actually be a member of the winning set; every prisoner is always capable of saying "“Yeah, there’s at least one winning sequence where I guess ‘aardvark’, so I’ll guess ‘aardvark’”, but the sequence of all "aardvark"s usually doesn’t win.
The discussion has long since moved on to different topics, so it’s not really fair to count all two (as yet, incomplete) pages. And even apart from that:
The OP was not unaware of the fact that the answer is 1 in 6. The OP was asking for an explanation of the apparent paradox, that a different, superficially valid argument would produce a conflicting answer. There is nothing ridiculous about the fact that such an explanation may take more than a couple glib lines. Certainly, saying “Well, the answer is obviously 1 in 6, by the standard reasoning” does nothing helpful in terms of what was actually being sought.
“…The OP was asking for an explanation of the apparent paradox…”
It was not a paradox. It was a question posed with a number of mis-directions. The use of a magician was evident. Nowhere is magic cited–a misdirection.
Kinda like the old “paradox”: If a brick weighs 7 pounds, plus half a brick. How much does a brick and a half weigh?
The “half” is a misdirection, and meant to confuse.
The answer—21 pounds.
If you can’t dazzle with brilliance, baffle with bull-shit.
Let me put it this way: the OP knew the correct answer was 1/6. Yet, to his surprise, he discovered an argument which produced a different answer. He knew there must be a flaw in this argument, yet he sincerely could not tell where it was. For that matter, the flaw was not obvious to many posters here. So it was a matter of great interest to them to know what the flaw was (though they never doubted that there was a flaw somewhere). Telling them “Well, duh, the correct answer is obviously 1/6, for all the standard reasons” would not have been helpful; it would fail to address their actual concerns, and it would not be telling them anything they were not already quite aware of.
