2019 March 13
The following puzzle comes from Beeminder user Fiona Skerman’s email signature (2019-02-13).
We play a game. The aim of the game is to save 99 of the prisoners (they are strangely altruistic and each prisoner is happy if 99 of them are saved — regardless of whether they are saved). The warden thinks of their favorite sequence of real numbers. In each of 100 cells, a copy of this sequence is placed in boxes. The first real number in the sequence in the first box, the ith real number in the sequence in the ith box. The game begins. Each prisoner is let into their cell which contains [countably] infinitely many boxes. In each cell, that prisoner opens boxes in whatever order they like leaving only one box unopened (e.g., box 1, then 7, then all evens, then all remaining boxes except box 3). The prisoner then guesses the real number in the box they haven’t opened. The prisoner lives if they are correct. How do you ensure 99 of them live? Clarification: They can discuss the strategy before the game begins (they know the full rules, but not the contents of any box) but do not hear the guesses of the other prisoners. The cells are identical in every way, i.e., box i in cell a has the same number as box i in cell b.
I shamefully gave up and googled it and ended up having to brush up on the Axiom of Choice. It was fun so I wanted to share!
(Which also reminds me that everyone should read Logicomix! It does not require any familiarity with foundations of math to appreciate but is a beautiful story about philosophers and mathematicians, especially Bertrand Russell and Wittgenstein. Also Cantor and others.)
Anyway, I have a new appreciation for how the Axiom of Choice is kind of a wild leap of faith that leads to preposterosities like Banach-Tarski.
Here’s my write-up of the solution to the puzzle:
Consider the infinite sequence {1,2,3,…}. Now consider all the infinite number of infinite sequences that eventually fall in line with {1,2,3,…}. Like {0,9,0,0,5,6,7,…} which matches starting at the 5th element. Or {… a million zeros …, 1M+1, 1M+2, 1M+3, …} which matches starting at a million and one.
When the prisoners see one of those they have to have pre-agreed on one specific canonical representative sequence. That’s weird for that to be possible! Like for the set of sequences that eventually match {1,2,3,…} you could just choose {1,2,3,…} as the canonical sequence. Fine so far. You can’t choose “the one with all zeros until they all start matching” because there’s no such thing. Like there’s the one with a million zeros at the beginning but there’s also the sequence that starts with a million and one zeros that also eventually matches.
Can you see how weird this is about to get? Consider a completely arbitrary infinite sequence — no rhyme or reason to it at all. We’ll call it “whackadoodle”. The Axiom of Choice means that if I replace the first googol elements of whackadoodle with zeros and hand it to each of the prisoners they’ll all magically be able to choose the same sequence without those googol elements zeroed out! Not necessarily the original whackadoodle but something.
Wouldn’t the obvious thing for them to pick be the one that actually does have the first googol elements as zero, you ask? No! Or, sure, but that googol zeroing was arbitrary. Like, fine, they all agree on a canonical sequence that happens to have a googol initial zeros. But if I replace the first googolplex elements with zeros, that’s also in the set of things that eventually match whackadoodle. So whatever they all said for whackadoodle-but-googol-zeroed, they have to also say when any number of initial elements are zeroed. Which means they’re basically able to magically reproduce the beginning of whackadoodle by seeing the (infinite) tail of it.
For every possible arbitrary sequence of real numbers, if you show them the tail of it, they’ll all magically infer the same part that comes before the tail!
Given that superpower, solving the puzzle is fairly (well, relatively) straightforward. They each assign themselves a subsequence, like prisoner 1 gets the 1st, 101st, 201st, etc boxes; prisoner 2 gets the 2nd, 102nd, 202nd, etc, boxes; and so on. Prisoner i looks at everyone else’s subsequence and infers the magical canonical version of it. Which means they know, for each other prisoner, the box number where that prisoner’s subsequence starts matching its canonical version.
Maybe one prisoner’s subsequence happens to be the canonical one, another one starts matching after a few hundred boxes, some take thousands, and there’s one outlier that only starts matching on the gajillion-and-seventh box. So, great, for my own subsequence, I’ll just open all my boxes except the gajillion-and-seventh. I can infer the canonical version of my own subsequence based on that — the tail of my subsequence starting at box gajillion-and-eight — and thus guess the contents of box gajillion-and-seven. The only way I’m wrong is if I’m an even bigger outlier than that gajillion-and-seven prisoner. Which means only the single biggest such outlier in that sense (how long before their subsequence starts matching the canonical version of their subsequence) can be wrong.
QED
PS: There’s a simpler puzzle that better gets at the heart of the weirdness that the Axiom of Choice is adding here. It also includes Terence Tao chiming in in the comments adding a lot of clarity and insight, to the extent I can follow him, which is not a large extent so far…
PPS: Why doesn’t this work for a single prisoner to guess the contents of a box? Can you start extremely far down the sequence, open every box from there on, and hope you’ve started past the point where the sequence matches the canonical sequence, since it must do so eventually? Well, you can hope, but that point — call it the matching point — could be any box from 1 to infinity. So no matter how large a number you pick, the probability is zero that the sequence happens to start matching before that number. To spell that out, your sequence’s matching point could be any natural number and so you can be certain that that’s bigger than whatever finite number you picked, even something ridiculous like a googolplexplexplex. (Fun paradox: something can simultaneously be possible yet have probability zero.) But if two of us do this and each use the other’s matching point? Well, either my matching point is smaller than yours or vice versa. If mine is smaller then by using yours I’ve indeed started far enough out. If yours is smaller then by using mine you’ve started far enough out! (Or by uncanny coincidence our matching points are the same and we’re both golden.)