Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Here is an astounding riddle that at first seems impossible to solve. I'm certain the axiom of choice is required in any solution, and I have an outline of one possible solution, but would like to see how others might think about it.

$100$ rooms each contain countably many boxes labeled with the natural numbers. Inside of each box is a real number. For any natural number $n$, all $100$ boxes labeled $n$ (one in each room) contain the same real number. In other words, the $100$ rooms are identical with respect to the boxes and real numbers.

Knowing the rooms are identical, $100$ mathematicians play a game. After a time for discussing strategy, the mathematicians will simultaneously be sent to different rooms, not to communicate with one another again. While in the rooms, each mathematician may open up boxes (perhaps countably many) to see the real numbers contained within. Then each mathematician must guess the real number that is contained in a particular unopened box of his choosing. Notice this requires that each leaves at least one box unopened.

$99$ out of $100$ mathematicians must correctly guess their real number for them to (collectively) win the game.

What is a winning strategy?

share|improve this question
5  
As I said, at first a solution seems impossible, but it also seems impossible that two unit spheres can be assembled from the pieces of one unit sphere. Strange results are possible with the axiom of choice. Also, to address vonbrand's comment, there is not necessarily any relation between the numbers, and it is only required that at least, and not exactly, one box be left unopened. –  Jared Apr 24 '13 at 15:30
3  
@Alex, but the difference is that the prisoners puzzle allow for an arbitrarily large, but finite, failure. Reducing this failure to a single failure seems... unlikely. –  Asaf Karagila Apr 24 '13 at 17:08
5  
If I fill the boxes with undefinable numbers, then no mathematician can guess the number in any box, since there is no way he can name it :p –  Kundor Apr 24 '13 at 18:43
3  
Since a couple of comments have mentioned the "probability" of correct guesses, I'd like to second (and perhaps amplify) Qiaochu Yuan's comment: There is nothing probabilistic going on in the problem. Furthermore, I don't see anything the mathematicians can gain by randomizing their guesses. –  Andreas Blass Apr 25 '13 at 2:15
3  
@KarolisJuodelė No, he does not ask for some probability to be $\frac{99}{100}$. He asks for a strategy that ensures that 99 of the 100 guesses are correct. –  Andreas Blass Apr 25 '13 at 17:12

3 Answers 3

up vote 19 down vote accepted

Before entering, the mathematicians agree on a choice of representatives for real sequences when two sequence are equivalent if they are equal past some index ; and a re-labeling of $\Bbb N$ into $M \times \Bbb N$ where $M$ is the set of mathematicians.

Once a mathematician $m$ is in the room, he opens every box not labeled $(m,x)$ for $x \in \Bbb N$, and for $m' \neq m$ he carefully notes the greatest index $x(m')$ (which is independant of $m$) where the sequence $(m',x)$ has a different value from that of its corresponding representative, and $x(m') = -1$ if it is the representative.
Then, $m$ computes $y(m) = \max_{m' \neq m} x(m') +1$, and opens every box labeled $(m,x)$ for $x > y(m)$. He finds the representative of that sequence, and guesses what's inside box $(m,y(m))$ according to that representative. He has the risk of guessing wrong if $y(m) \le x(m)$ (he is the only one not knowing the value of $x(m)$).

If there is an $m$ such that $x(m') < x(m)$ for every $m' \neq m$, then $m$ will be the only mathematician that can answer wrongly (for the others, $y(m') > x(m) > x(m')$). If there are several $m$ whose $x(m)$ tie for greatest, then they will all answer correctly.

share|improve this answer
    
This is more or less the solution I know, exposited very nicely! I like the idea to re-label the boxes. The solution I know has mathematician $m$ open all boxes not congruent to $m\operatorname{mod}100$, which is just a specific re-labeling in your solution. –  Jared Apr 25 '13 at 16:18
    
The representative before opening $(m, x)$ for large $x$ can (will) be different from the representative after. Hence you actually have two different values of $x(m')$ and of $y(m)$. After opening the $(m, x)$ boxes, the old values might as well be random numbers. While they can all be recalculated, what guarantee is there, that the box $(m, y_2(m))$ was not opened already? –  Karolis Juodelė Apr 25 '13 at 19:10
    
@KarolisJuodelė: I don't understand. The entire sequence for $m'$ was already opened for each $m' \neq m$, so the values of $x(m')$ (and hence $y(m)$) won't change. –  Kundor Apr 25 '13 at 21:14
    
@Kundor, for simplicity, say $M = \{m_1, m_2\}$ and $n \in N$ is relabled so that even numbers belong to $m_2$. Say after $m_2$ opens boxes for $m_1$, he sees $4?2?0?0?0?0?0\dots$ (where $?$ is an unopened box). He picks the representative $0000000000000\dots$ and thus $y_1(m_2) = 3$. He then opens his own boxes and sees $4?2?0?0101010\dots$, but now the equivalence class has changed and the new representative is $654321010101\dots$ and $y_2(m_2) = 4$ but the box $(m_2, 4)$ is already open. –  Karolis Juodelė Apr 26 '13 at 5:13
    
@KarolisJuodelė: Your example is helpful in understanding where lies the misunderstanding. When the boxes for $m'$ are opened, we view those boxes as an entire real sequence themselves, not as a part of the original real sequence. In a sense, we are partitioning the original sequence into $|M|$ subsequences, so that the representative of each subsequence does not change when opening boxes from other subsequences. –  Jared Apr 26 '13 at 5:47

Found this via Reddit. Here's my writeup of the solution.


The strategy involves the axiom of choice like so: the mathematicians group sequences of real numbers such that two sequences are in the same group if and only if they agree on all but the first few terms. For example, (pi,e,sqrt(2),2^(4/3),1,4,1,5,9...) and (ln(2),phi,-7.8,3,1,4,1,5,9,...) are in the same group, assuming that they both keep repeating the final digits of pi in their sequence.

The axiom of choice is required to choose an arbitrary representative from each group. For example, I can choose (1.49,3,-cos(4),3,1,4,1,5,9,...) to represent the group I described above, but since there's infinitely many groups and I only have a short amount of time, I need a special rule that says I can pick those infinitely many representatives. (That's a clumsy short version of how the axiom works, anyway.)


Alright, so now I'll describe the plan. Let's say I'm mathematician #1. I'm going to open every box except 1, 101, 201, 301, etc. My buddy one room over (mathematician #2) will open every box except 2, 102, 202, 302, etc. And so on.

Back to me. I know what's inside the boxes that my buddy #2 didn't open. Let's pretend the numbers are:

  • 2 -> 1739218.33
  • 102 -> sqrt(5)-sqrt(2)
  • 202 -> Arctan(37.238)
  • 302 -> 382
  • 402 -> -832.019
  • 502 -> 4
  • 602 -> 1
  • 702 -> 5
  • 802 -> 9
  • etc.

Okay, I know the group that falls in. (Coincidentally, it's the group I talked about above.) I'm going to write a note that it started matching the representative from the sixth box onward. Let's write that note like this "x(2)=6".

I'll repeat that process for #3, noting x(3)=5, and for #4 perhaps x(4)=8, and so on. I know x(m) for m=2,...,100, but I don't know x(1) since those are the boxes I haven't opened yet. I'm going to take the biggest of those numbers, add one, and call that y(1), that is: y(1) = max(x(2),x(3),...)+1. It just so happened that x(3)=8 was the biggest, so y(1)=9.

It's finally time to open most of the remaining boxes. I'll open all the boxes in my sequence 1, 101, 201, etc., starting with the y(1)=9^(th) box. (Since every x(m)>=1, y(1) had to be at least 2, so in general there's always some unopened boxes.) Let's see what I got:

  • 1 -> ???
  • 101 -> ???
  • ...
  • 701 -> ???
  • 801 -> 7pi+sqrt(3)
  • 901 -> 2
  • 1001 -> 8
  • 1101 -> 4
  • etc.

Seeing those last digits, I know enough to figure out which group it belongs to: the group with representative (e,2,7,1,8,2,8,1,8,2,8,4,6,...).

I now know enough to make my guess. I'm going to use the representative, and pick the y(1)-1=8^(th) member, which is the maximum value of the x(m)s. In this case, the 8^th member happens to be "1", and I'm going to guess the 8^th unopened box, box #701, holds number "1" inside.


Now, I need to prove to you that this strategy (and similar strategies for the other mathematicians) works. It's okay to assume that I, mathematician #1, am wrong. I just need to prove that if I'm wrong, then everyone else is right! (99/100 ain't bad, according to the rules.)

Okay, I'm wrong, so what happened. Well, obviously, the y(1)-1^(th) term didn't match the representative. That means that $x(1)>y(1)-1$, since x(1) is the first number where it and all later boxes in my sequence match the representative.

With this information, I realize something. $y(1)-1>=x(m)$ for every other number m, since I defined it to be the biggest x(m) plus one! So here's what I now know:

$x(m)<=y(1)-1<x(1)$

Oh man! This is great news. Everyone else defined their own y(m) based on the other x, and x(1) is the biggest x out there. So:

$x(m)<=y(1)-1<x(1)<x(1)+1=y(m)$

So, for each mathematician #m, all boxes x(1) and onward match the representative. Every mathematician #m opened x(1)+1 onward, and guessed the representative's x(1) entry for the x(1) box, which has to match the representative.

Thus, if I'm wrong, everyone else has to be right at least. And that beats the game.

share|improve this answer
    
Nice argument but the paragraph before the conclusion confuses me. Shouldn't it read "for each mathematician #m, all boxes x(m) and onward match the representative"? I am also not sure about the three uses of the x(1) box that follow in the next sentence; wasn't the mathematician #m supposed to guess the y(m)-1 box corresponding to his representative? –  Luke Skywalker Aug 14 '13 at 18:46
1  
Ah! I was forgetting that in the case x(1) is the greatest, then y(m)-1 is actually x(1). I leave the comment as a remark just in case someone else bumps into that confusion. For a moment it looked like everyone was guessing on the first mathematician sequence and not on their own. –  Luke Skywalker Aug 14 '13 at 19:00

What about the case where x(m) is constant and maximal over all m? If you think about it, this isn't really a trivial case either. I'd imagine it would be the most likely case, actually, and here's why. Let us for a moment restrict our universe of discourse to only the first 10^10 natural numbers. Let us now do the same thing and fill these boxes with one of these numbers, and we will try to predict our own (the same as before, but now with only finitely many numbers instead of uncountably many reals). So, let's continue and make the equivalence classes of sequences of these numbers where two sequences are in the same class if they agree on everything past the 5th entry. The choice of the fifth entry was really arbitrary, but I prefer to work with a tangible number for this. Next we pick our representatives for each equivalence class. Okay, so let us compute the odds that even one of the 100 m's will give x(m)<5. If x(m)<5, then clearly the 4th position must agree with the chosen representative sequence. But for each m the odds of that happening are 1/10^10 (1 specific number out of our 10^10 possible numbers). So the odds of that happening for any m would be (1/10^10)*100 (the odds of each m multiplied by the number of m's), which is already negligible and tends to 0 as we increase our universe of discourse.

So, it is most probable that all of our sequences will only agree with their respective representatives at the required index. So this solution doesn't really work, I think.

Let me know if I've overlooked something or if I didn't understand something in your proof.

share|improve this answer
    
Here's a MathJax tutorial :) –  Shaun Jun 10 at 13:45
    
This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post - you can always comment on your own posts, and once you have sufficient reputation you will be able to comment on any post. –  Miha Habič Jun 10 at 14:15
    
@Chewz: no matter how likely it is that all $x$ are the same, the proof works in this case too (note that the maximum need not be unique, i.e. $max(5,5,5,..)=5$) –  Bananach Jun 10 at 18:02
    
as for the probabilities of all $x$'s being the same: for the equivalence classes, sequences are grouped that agree from an arbitrary index on, so $(1,0,\dots), (1,1,0,\dots), (1,1,1,0,\dots), \dots$ are all in the same equivalence class, but there is no index from which on all elements in this class agree on. So there is no "required index" and your argument fails since all indexes are equally non-likely (actually, I doubt the functions $x_m=x(m)$ are measurable (mapping a given box-filling to the corresponding indices) and thus cannot even be talked about in probabilistic terms) –  Bananach Jun 10 at 18:22
    
Note taken miha. –  Chewz Jun 10 at 19:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.