# Can an infinite number of mathematicians guess the number in a box with only one error?

In this question the following observation was made:

Consider a sequence of boxes numbered 0, 1, ... each containing one real number. The real number cannot be seen unless the box is opened.

Define a play to be a series of steps followed by a guess. A step opens a set of boxes. A guess guesses the contents of an unopened box. A strategy is a rule that determines the steps and guess in a play, where each step or guess depends only on the values of the previously opened boxes of that play.

Then for every positive integer $k$, there is a set $S$ of $k$ strategies such that, for any sequence of (closed) boxes, there is at at most one strategy in $S$ that guesses incorrectly.

My question is this: Can $k$ be countably infinite (instead of a positive integer)? If not, is there a proof?

[Edit: the original question also asked whether $k$ can be uncountable; this was answered by Dan Turetsky in the negative in comments].

The best I have been able to show is that, if the function $f:\mathbb{N}\to\mathbb{R}$ defined by the contents of the initial sequence of boxes is recursive (viewing elements of $\mathbb{R}$ as binary sequences), then $k$ can be countably infinite. To see this, call a subset $X$ of $\mathbb{N}$ signature if two recursive functions on $\mathbb{N}$ that eventually agree on $X$ also eventually agree on $\mathbb{N}$. (Two functions "eventually agree" if they differ in finitely many places). Call two Turing Machines equivalent if their associated functions on $\mathbb{N}$ are equivalent (that is, eventually agree). A diagonalization argument on the class representatives of the Turing Machines yields an infinite partition $U$ of $\mathbb{N}$ into signature subsets. The $i$'th strategy in $S$ first opens all the boxes whose indices are not in the $i$'th element $U_i$ of $U$, determines the class representative Turing Machine T that generates the resulting values on the opened boxes for boxes whose indices are greater than $N$ (for some positive $N$), and guesses that a box with index greater than $N$ and in $U_i$ has a value specified by $T$.

However, I have not been able to modify this for the non-computable case.

• Just a quick observation: your argument about the case when $f$ is guaranteed to be computable isn't really about computability theory: a much stronger fact is true, namely if we are guaranteed that $f$ is in some pre-determined countable set of functions $\mathbb{N}\rightarrow\mathbb{R}$, then $k$ can be $\omega$. – Noah Schweber Dec 25 '13 at 21:56
• I have a negative answer to the uncountable question. Notice that the behavior of a strategy doesn't depend on the value of the box it guesses at. If you're faced with uncountably many mathematicians, begin by placing 0 in all the boxes. By pigeon hole, there's some box that uncountably many of the mathematicians guess at. Adjust the value at that box to make most of them wrong. – Dan Turetsky Dec 25 '13 at 23:18
• This is an outcry of mathematical thought: "can an infinite number of mathematicians..." – Victor Dec 26 '13 at 9:12
• Good points about the countable sets of functions and thanks for the uncountability observation. In point of fact, the notion of the boxes being in "sequence" is unnecessary. A better way to describe the puzzle is probably to say there is a set of boxes cardinality $\alpha$, and to ask for the maximum cardinality $\beta$ of a set of strategies guaranteed to make at most $\gamma$ wrong guesses. But of course the countable/countable case is the most natural. – user44653 Dec 26 '13 at 23:18
• Ya know... this is the fourth question on this sort of puzzle over MO and MSE, and I still can't figure out what any of these have to do with the axiom of choice. I mean, sure, it's needed, but the axiom is also needed in constructing maximal ideals, ultrafilters, etc. – Asaf Karagila Dec 27 '13 at 10:56

Partition the natural numbers into countably many sets, $\{S_i\}_{i=0}^\infty$, where each $S_i=\{n_{i_1},n_{i_2},\dots,\}$ is countably infinite. (There are many ways to do this) Since we have countably many mathematicians, we may list them, and assign $S_i$ to the $i^{th}$ mathematician.
If $u_k$ denotes the real number in the $k^{th}$ box, then the $i^{th}$ mathematician will be assigned the sequence of real numbers $u_{n_{i_j}}$, for $j=1,2,3\dots$. Using the axiom of choice, we may chose a representative for each equivalence class of sequences of real numbers under the equivalence relation $\{u_n\}_{n=1}^\infty\equiv\{v_n\}_{n=1}^\infty$ if there exists $M>0$ such that $v_n=u_n$ for all $n>M$. Thus, for the $i^{th}$ mathematician there will exist an integer $M_i$ such that for all $j>M_i$, the sequence $u_{n_{i_j}}$ is equal to the representative of its equivalence class. The goal is to have mathematician $i$ guess an integer $H_i>M_i$ by looking at every box except those in the set $S_i$. If this happens, then mathematician $i$ may look at all of the elements of $u_{n_{i_j}}$ with $j\geq H_i+1$, determine the equivalence class, and guess the box with $j=H_i$. Since $H_i>M_i$, his guess will be correct. It follows that we need all but possibly one mathematician to guess an integer $H_i>M_i$. If the sequence $M_i$ is bounded, then the problem is easy. The difficulty is handling an unbounded sequence $M_i$.
Under the same system of representatives, the sequence $\{M_i\}_{i=0}^\infty$ lies in some equivalence class of real numbers. Since mathematician $i$ knows the value of $M_l$ for all $l\neq i$, each mathematician can determine the equivalence class of the sequence $\{M_i\}_{i=0}^\infty$. Let $\{v_i\}_{i=0}^\infty$ denote the representative of this equivalence class. Then there exists an integer $N$ such that for every $i>N$, $M_i=v_i$. Mathematician $i$ with $i\leq N$ can determine $N$, however each mathematician with $i>N$ only knows that $N\leq i$. The strategy for guessing is as follows: Assign to mathematician $i$ with $i>N$ the integer $$H_i=1+\max\{v_i,M_{i-1},M_{i-2},\dots,M_1,M_0\},$$ and to each mathematician with $i\leq N$, the integer $$H_i=1+\max\{M_{N},M_{N-1},\dots,M_{i+1},M_{i-1},\dots,M_1,M_0\}.$$ Then we must have $H_i>M_i$ for every $i$ except possibly one. Thus, we have set up a strategy which allows every mathematician except possibly one to guess some box correctly.