100 mathematicians, 100 rooms, and a sequence of real numbers

[Jrthedawg]

I am a collector of math and logic puzzles, and this must be the best I've ever seen.

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?

[TimeSpaceLightForce]

Nice puzzle ..

Can we label the rooms, boxes, real number - 00 to 99 ?

So that room 50 has a box with "50" written outside and "50" written inside..

[plasmid]

I get the feeling this will depend on how exactly you define communication.

Mathematician #1 could open boxes 2-100, see the numbers inside, then stack boxes just outside the room in 99 rows so they form the numbers that the other mathematicians need to guess. Leave a 1-unit space between boxes to represent a decimal point. There's a possibility that he might not be able to form some of the numbers if he already used a necessary box to form a different number, but since he has all natural numbers at his disposal, he could always use a box with N extra un-needed digits at the end and then lay N boxes sideways immediately afterward -- the other mathematicians would know that seeing N sideways numbers is the signal for removing N trailing digits from the previous number.

Since this is one of the best puzzles you've seen, your definition of communication would probably prohibit such a straightforward approach. But if you take an ultimately strict interpretation of communication, like "no mathematician can leave any evidence of their existence to any other mathematician after the game starts", then this should be indistinguishable from sending each mathematician into the game completely alone and there would clearly be no solution. So there must be some form of communication.

We'll need to know what's allowed and what isn't: whether mathematicians can rearrange boxes or see the boxes that other mathematicians have rearranged, whether the other mathematicians hear a guess that any other mathematician makes or whether or not it was correct, etc.

[Rainman]

No form of communication is necessary once they have entered their rooms. They can not see, hear, or otherwise perceive anything another mathematician does. We do need to allow some other wild stuff though.

1. There is a countably infinite number of boxes in each room.

2. The mathematicians can open an infinite amount of boxes.

3. The mathematicians can input and output uncountably infinite amounts of information, as needed to fully grasp and form a strategy over the set of real numbers.

4. We also need the axiom of choice.

[bonanova]

No form of communication is necessary once they have entered their rooms. They can not see, hear, or otherwise perceive anything another mathematician does. We do need to allow some other wild stuff though.

1. There is a countably infinite number of boxes in each room.

2. The mathematicians can open an infinite amount of boxes.

3. The mathematicians can input and output uncountably infinite amounts of information, as needed to fully grasp and form a strategy over the set of real numbers.

4. We also need the axiom of choice.

I think uncountably countably is all that's needed.

[Rainman]

No form of communication is necessary once they have entered their rooms. They can not see, hear, or otherwise perceive anything another mathematician does. We do need to allow some other wild stuff though.

1. There is a countably infinite number of boxes in each room.

2. The mathematicians can open an infinite amount of boxes.

3. The mathematicians can input and output uncountably infinite amounts of information, as needed to fully grasp and form a strategy over the set of real numbers.

4. We also need the axiom of choice.

I think uncountably countably is all that's needed.

The boxes themselves would only contain countable amounts of information, but I think the information the mathematicians need to bring into their rooms (i.e. their strategy) is uncountably infinite. Unless I'm missing a simpler solution.

[DeGe]

Do they hear the guesses of other mathematicians?

[bonanova]

Do they hear the guesses of other mathematicians?

DeGe,

No.

To answer plasmid's question about communicating, let's frame the question this way:

When a mathematician enters his room, the door locks behind him.

Consider the room to be an information black hole, except that each box communicates to a central computer.

Each box has a keypad capable of transmitting any real number (along with its box number) to the computer.

If and only if the computer receives correct (real number - box number) pairs from 99 or 100 rooms, the doors unlock themselves.

Otherwise, ... the world loses 100 mathematicians.

That is, it's not like the 100 prisoners with red or blue hats: they do hear each other.

Here, the strategy is so cool that they don't need to know each other's guesses.

[spoiler=A similar strategy will also solve this puzzle]An infinite number of people will receive hats bearing a distinct real number unseen to the wearer but seen by all the others. When all the hats have been placed, each will shout a number, to guess the one on his own particular hat. There may be incorrect guesses but, to win, only finitely many. Before they receive their hats they craft a strategy that may require infinite resources. After that, they may not communicate.

[plasmid]

This reminds me of the "Team of 15" problem, although it doesn't look like it can really be approached the same way.

Are you working under the premise that all boxes must contain a different number? It doesn't look like that's the case.

And if you were to try to map all the real numbers to the set of natural numbers and have the mathematicians open boxes until they've exhausted all real numbers except for one, then I'd call shenanigans.

[bonanova]

No shenanigans.

I don't think the real numbers have to all be different. OP just says each box contains a real number.
The probability of any two being the same is zero, but it could happen, and still solve the problem.

Edit:

When the OP says "countably" it has to mean "countably infinite."

There must be a box in each room for every counting number for the strategy to work.

Edited July 27, 2013 by bonanova
Clirify "countably" as used in OP has to mean "countably infinite"

[plasmid]

No shenanigans.

I'll be the judge of that

That is, if I decide I've had enough of this problem and just ask for the solution you two seem to have in mind. Which is not yet.

[bonanova]

has all the additional conditions necessary to solve.

(Including the Edit in my previous post.)

[plasmid]

I finally had enough and went ahead and googled the OP. I've got to say, after looking at the solution they proposed, I would definitely place it in the category of "shenanigans". But maybe I'm missing something.

Each mathematician is assigned a number from 0 to 99. Every box that is congruent to the mathematician's number modulo 100 will "belong" to that mathematician, so each one of them will have an infinite subset of the sequence of boxes that they "own". Think of this as arranging the boxes in a grid that is 100 boxes wide and infinity boxes tall, and each column belongs to a different mathematician.

Before the game starts, the mathematicians decide on some infinite sequence of real numbers and call it their "template" sequence -- they used the digits of pi as an example where the sequence would be [3, 1, 4, 1, 5, 9 ...]. The mathematicians would then each open every box that doesn't "belong" to them. For each sequence of boxes that "belongs" to some other mathematician, they will find the point in that sequence at which it completely matches the template sequence (perhaps starting at some point in the middle of the template sequence) for the remainder of the sequence. Call the box at which their sequence starts matching the template sequence N (here we're counting the number of boxes in that mathematician's subsequence and not in the original sequence of all boxes -- that is, if mathematician 5 starts matching the sequence from his third box which is box #205 from the original sequence, then his value of N would be 3). Each mathematician's sequence could start matching the template at a different point so they could each have a different value of N for their sequence.

Since there are 100 mathematicians, there must either be one mathematician whose sequence has the largest value of N or multiple mathematicians who are tied for the highest value of N.

Now each mathematician looks at the sequences for every other mathematician and records the value of N for those sequences, and calls the largest of these N values Nmax. He then opens each of the boxes in their sequence from Nmax+1 onward. If he is not the mathematician with the largest value of N, then his sequence will match the template sequence from box Nmax onward. So he can simply see what his sequence from Nmax+1 onward is, align that to the template sequence, and then figure out what the preceding number on the template sequence is, and guess that his last unopened box is that number. If his value of N is smaller than Nmax+1 then his sequence will match the template sequence at that point and he will guess correctly. If his value of N is larger than Nmax+1 then this technique will fail for him, but since there can be only one mathematician whose sequence has the largest value of N, he would be the only one for whom this would fail and all the other 99 mathematicians will guess correctly.

I call shenanigans because I see no reason to presume that an infinite sequence of real numbers can be guaranteed to have a value of N at which it starts matching a template sequence for all elements >= N. And it's easy to give a counterexample. To use the example of the digits of pi as a template sequence, define the value of box X to be one plus the value of box X-1. This sequence will clearly never have a point where it will start matching the template sequence for the rest of its length. (The digits of pi must be 0-9 and this sequence will become >10 at some point and for all elements thereafter). Perhaps there's something I'm missing like a way to define infinitely many template sequences such that you're guaranteed to match one at some point (and a way of extending the solution to accommodate infinitely many possible templates), or some way of defining a template sequence based on the values in the boxes that have been opened so it's guaranteed to occur.

[Rainman]

You're missing that they are not just using one template sequence. They define equivalence classes by how a sequence ends, so that two sequences belong to the same class if and only if they are different in only finitely many places. Then they choose one template sequence from each equivalence class.

[Rainman]

Let S

_x = (x₁, x₂, x₃, ...) and S_y = (y₁, y₂, y₃, ...) be two infinite sequences of real numbers. Define a relation between such sequences as follows: S_x ~ S_y if and only if there exists a number N, such that x_i=y_i for all i>N. Let's verify that this is an equivalence relation. Reflexivity and symmetry are obvious.

Transitivity: If S_x ~ S_y and S_y ~ S_z, we want to prove S_x ~ S_z. Let N₁ be a number such that x_i=y_i for all i>N₁, and let N₂ be a number such that y_i=z_i for all i>N₂. Now set M=max(N₁,N₂) and we have x_i=y_i=z_i for all i>M.

Now, through this relation we can form equivalence classes on the set of infinite sequences of real numbers. There is an uncountably infinite number of such equivalence classes, so it's a lot for the mathematicians to keep in mind. By the axiom of choice, they can choose a representative sequence from each equivalence class. This means that for any sequence S_x, there is exactly one representative sequence S_R which matches S_x except in a finite number of places.

The mathematicians are also numbered from 0 to 99 before entering their rooms. (This is the only part of their strategy which could be performed in real life, everything else is purely theoretical)

As they enter their rooms, the mathematicians open every box that is not congruent to their own assigned number modulo 100. For example, mathematician 3 opens every box except numbers {3, 103, 203, 303, ....}. The mathematician will eventually guess the value of one of these unopened boxes.

Let x_i be the real number contained in box number i. Consider the 100 sequences S₀ = (x₀, x₁₀₀, x₂₀₀, ...), S₁ = (x₁, x₁₀₁, x₂₀₁...), ..., S₉₉ = (x₉₉, x₁₉₉, x₂₉₉, ...). Each of these sequences has exactly one representative sequence which matches it except in a finite number of places. Let R_i be the representative sequence that corresponds to S_i. Each mathematician has already seen 99 of these sequences S_i, and finds the 99 representative sequences R_i to match them. He takes note of exactly where each sequence starts matching its representative sequence perfectly. For example, S₀ might start matching R₀ from the 1042nd place onward. S₁ might start matching R₁ from the 54897294581924th place onward. In particular, he takes note of the smallest number N such that S_i matches R_i for all the 99 sequences he has seen, from the N-th place onward. He will then make a guess that his sequence also matches his representative sequence in the N-th place. This guess is wrong if and only if his sequence is the one which takes the absolute longest to start matching its representative sequence. If so, everyone else will make a correct guess. So how does he make this guess? He opens all the boxes in his own sequence from the (N+1)-th place onward. This allows him to find the representative sequence of his own sequence. Now he simply recalls the N-th number of that representative sequence and guesses that the N-th box in his sequence contains that number.

[bonanova]

I call shenanigans because I see no reason to presume that an infinite sequence of real numbers can be guaranteed to have a value of N at which it starts matching a template sequence for all elements >= N. And it's easy to give a counterexample.

This touches on a crucial idea required by the mathematicians' strategy. It must be understood before being used. It's the idea of equivalence classes. We'll first explore what they are by finding a way to construct them. Then we'll see how the math guys used them. So, let's take a minute to gather all the infinite sequences of real numbers of infinite length that exist, and lay them out here on my dining room table.

Pick a sequence at random; call it sequence A. Quickly glance at all the other sequences, ignoring the initial finite number of terms. When a sequence, (call it sequence X) is found for which the remaining infinite terms agree with the corresponding terms in A, then we group X with A. Put that process into an infinite set of infinite DO loops [my FORTRAN is showing] and finally we get an infinite number of classes of infinite sequences. These are the equivalence classes needed to implement the math guys' strategy. Mull over that process so that you can define these classes in your own words.

The classes by themselves are too clumsy to use. We have to simplify matters. Enter the Axiom of Choice. Without it, the math guys remain locked in their rooms. AC is just this: There is a particular sequence, chosen from each class, that can be used to represent that class. So, for every infinite sequence of real numbers, it belongs to a unique equivalence class, and there exists a single, unique infinite sequence that can be used to represent it. Those are the vital ingredients: classes and their uniquely chosen representatives.

AC has importance only for infinite sets. Unique representatives of finite sets are not troublesome. But for infinite sets unique representatives are problematical. It cannot be proven. It must be inserted into the process as an axiom. And by the way, asserting a unique representative is not the same as finding it. So our math guys are only theoretical winners by this strategy. We don't get picky about that, even though the numbers in the boxes are real, the math guys aren't. This is only a puzzle.

Without AC, the math guys can't translate an infinite sequence into a unique representative sequence. So they can't predict any term of any real sequence they encounter in their rooms. But with AC, they can. They just run a quick check of the final infinite number of terms. When they find congruence, they know its equivalence class. Using AC they find [but see the above disclaimer as to how they do this] the representative of that class. That identifies all the remaining real numbers that follow a finite number of differing ones. They just have to get sufficiently far out into the sequence to know that have skipped the differing numbers.

The rest of the strategy is easy to understand. One of them might have the wrong cutoff point, where the differing numbers end, and give the wrong number contained in a selected box. But there is at most one such guy. And 99 out of 100 is a win.

[plasmid]

Ah, thanks Rainman and Bonanova. That actually makes sense (which is sort of frightening).

Suppose we want to make things easier for the poor mathematicians who don't have infinite memories. For each equivalence class, we choose the representative sequence in that class such that x1 = 1, x2 = 2, x3 = 3 .... until we reach a point N out in infinity-land where it starts matching every subsequent term in the class. We know that such a point must lie infinitely far out since for any N if your representative sequence stops following x(N) = N and starts following the equivalence class' sequence, you can define a sequence which has x(N) = N and then starts matching the equivalence class for all subsequent terms. Since there is thus no finite limit to how large N can be, each representative sequence will be x1 = 1, x2 = 2, x3 = 3 ... for an infinite number of terms.

If the proposed solution using the axiom of choice works, then it should work using these representative sequences.

So if a mathematician guesses the value in any box numbered M in his subsequence, he must guess that it contains the value M.

Now I'm going to set up the boxes so they all contain negative numbers.

Edited July 30, 2013 by plasmid

[Rainman]

Ah, thanks Rainman and Bonanova. That actually makes sense (which is sort of frightening).

Suppose we want to make things easier for the poor mathematicians who don't have infinite memories. For each equivalence class, we choose the representative sequence in that class such that x1 = 1, x2 = 2, x3 = 3 .... until we reach a point N out in infinity-land where it starts matching every subsequent term in the class. We know that such a point must lie infinitely far out since for any N if your representative sequence stops following x(N) = N and starts following the equivalence class' sequence, you can define a sequence which has x(N) = N and then starts matching the equivalence class for all subsequent terms. Since there is thus no finite limit to how large N can be, each representative sequence will be x1 = 1, x2 = 2, x3 = 3 ... for an infinite number of terms.

If the proposed solution using the axiom of choice works, then it should work using these representative sequences.

So if a mathematician guesses the value in any box numbered M in his subsequence, he must guess that it contains the value M.

Now I'm going to set up the boxes so they all contain negative numbers.

Unfortunately foor the mathematicians, that doesn't work. But it is a good example illustrating the difference between arbitrarily large and infinite. You are right that the mathematicians can choose a number N, and let each representative sequence begin with (1, 2, 3, ..., N). And you are right that there is no finite limit to how large N can be. They can make N arbitrarily large. But perhaps surprisingly, that doesn't mean they can go on like that infinitely. They still must choose a number N, and there are no infinite numbers. In terms of sequences, infinity means forever. And forever means the sequence can't change at some point to match another sequence. There is only one sequence which goes x₁=1, x₂=2, x₃=3, and so on for infinitely many terms.

As for the mathematicians, the unfortunate part is that no matter how large they make N, the probability is still 0 that their sequence matches its representative sequence at the N-th place. No matter how large they make N, it will still be infinitely small compared to the concept of infinity.

[DeGe]

Aha, now I know why couldn't figure it out!

I was reducing the problem to 2 mathematicians, 2 rooms and say 5 or 10 boxes; where as if I understand correctly the explanation from Bonanova, I should have considered all the mathematicians in the world, matching number of rooms, and a much larger number of boxes