- #1
klackity
- 65
- 1
I heard this interesting paradox, which I haven't been able to find anywhere online!
Now, bear with me while I set it up!
Suppose a professor has a countably infinite number of students. This professor secretly assigns to each student a real number in the interval [0,1], and thus ends up with an infinite sequence (s1, s2, s3, s4, ... ), where sk is the real number assigned to student #k.
The professor then tells the class that he will offer each student the opportunity to guess the number he has been assigned. Starting with k=1, the professor will call student #k into his office, and show him the infinite sequence he made earlier, but replacing sk with "___", so as to obscure it. That is, student k will see: (s1, ..., sk-1,___,sk+1, sk+2, sk+3, ...). He will then ask student #k to guess sk (the only number in the sequence he hasn't seen!). After this, student #k must swear not to tell any of the other students what he has seen, and then student #k+1 is called in.
Now assuming the students have the ability to meet before hand, and also have the ability to memorize an uncountably infinite amount of things, is there a strategy that the students can adopt such that all but finitely many guess correctly?
The answer is YES! (And no, I have not left anything out of the problem!)
Proof:
The students all gather in the common room the night before they are to be called in. On tiny sheets of paper, they write down every possible sequence of real numbers that the professor could have chosen. i.e., they write down all possible sequences of the form (x1, x2, x3, ...) where xj is a real number in the interval [0,1].
Now, they gather up a bunch of old shoe-boxes and start sorting all these sequences with the following rule: two sequences (x1, x2, x3, ...) and (y1, y2, y3, ...) will be put in the same shoe box IF AND ONLY IF they differ by only a finite number of terms. (Differing by only a finite number of terms is an equivalence relation, so this is all well-defined).
Now by the Axiom of Choice, the students pick for each box a single "representative" sequence in that box. The students make sure that they all agree upon the choices of representatives. As the evening grows on, the students memorize all the information about which sequences are in which boxes, and which sequence is the representative for each box.
Now, starting with k=1, student #k is called into the office. He sees an infinite sequence with the k-th term omitted, like so:
(s1, ... s,k-1,___,sk+1, sk+2, sk+3, ...)
Student #k notes that whatever his own score happens to be, he knows which shoe-box the sequence (s1, s2, s3, ...) must belong to. We'll call this box Beta. Now student #k recalls what the representative sequence for Beta was. Call this sequence (b1, b2, b3, ...). (This sequence will, of course, differ from (s1, s2, s3, ...) in only a finite number of terms). Student #k then guesses that sk is bk, and then leaves.
When student #k+1 is called in, he will undoubtedly realize also that (s1, s2, s3, ...) belongs in box Beta. He will also recall that (b1, b2, b3, ...) was the representative sequence for box Beta. And thus he will guess bk+1. The same is true for every student.
But (b1, b2, b3, ...) differs from (s1, s2, s3, ...) in only a finite number of places, so all but finitely many students will guess correctly!
So, what do you all think? Counterintuitive, eh?
Now, bear with me while I set it up!
Suppose a professor has a countably infinite number of students. This professor secretly assigns to each student a real number in the interval [0,1], and thus ends up with an infinite sequence (s1, s2, s3, s4, ... ), where sk is the real number assigned to student #k.
The professor then tells the class that he will offer each student the opportunity to guess the number he has been assigned. Starting with k=1, the professor will call student #k into his office, and show him the infinite sequence he made earlier, but replacing sk with "___", so as to obscure it. That is, student k will see: (s1, ..., sk-1,___,sk+1, sk+2, sk+3, ...). He will then ask student #k to guess sk (the only number in the sequence he hasn't seen!). After this, student #k must swear not to tell any of the other students what he has seen, and then student #k+1 is called in.
Now assuming the students have the ability to meet before hand, and also have the ability to memorize an uncountably infinite amount of things, is there a strategy that the students can adopt such that all but finitely many guess correctly?
The answer is YES! (And no, I have not left anything out of the problem!)
Proof:
The students all gather in the common room the night before they are to be called in. On tiny sheets of paper, they write down every possible sequence of real numbers that the professor could have chosen. i.e., they write down all possible sequences of the form (x1, x2, x3, ...) where xj is a real number in the interval [0,1].
Now, they gather up a bunch of old shoe-boxes and start sorting all these sequences with the following rule: two sequences (x1, x2, x3, ...) and (y1, y2, y3, ...) will be put in the same shoe box IF AND ONLY IF they differ by only a finite number of terms. (Differing by only a finite number of terms is an equivalence relation, so this is all well-defined).
Now by the Axiom of Choice, the students pick for each box a single "representative" sequence in that box. The students make sure that they all agree upon the choices of representatives. As the evening grows on, the students memorize all the information about which sequences are in which boxes, and which sequence is the representative for each box.
Now, starting with k=1, student #k is called into the office. He sees an infinite sequence with the k-th term omitted, like so:
(s1, ... s,k-1,___,sk+1, sk+2, sk+3, ...)
Student #k notes that whatever his own score happens to be, he knows which shoe-box the sequence (s1, s2, s3, ...) must belong to. We'll call this box Beta. Now student #k recalls what the representative sequence for Beta was. Call this sequence (b1, b2, b3, ...). (This sequence will, of course, differ from (s1, s2, s3, ...) in only a finite number of terms). Student #k then guesses that sk is bk, and then leaves.
When student #k+1 is called in, he will undoubtedly realize also that (s1, s2, s3, ...) belongs in box Beta. He will also recall that (b1, b2, b3, ...) was the representative sequence for box Beta. And thus he will guess bk+1. The same is true for every student.
But (b1, b2, b3, ...) differs from (s1, s2, s3, ...) in only a finite number of places, so all but finitely many students will guess correctly!
So, what do you all think? Counterintuitive, eh?