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

Question

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.

Answer 1

It is possible to have every mathematician guess the number in one of the boxes with at most one error.

---

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.

Answer 2

I didn't think this would be possible with an infinite number of mathematicians, but Eric's solution is fantastic. It did take me a while to understand how it works, and I was confused because I think some of its inequalities are not quite right. So I have created this answer to fill in the gaps and clarify his great solution. If you get the urge to upvote this answer, please upvote Eric's first.

We take up Eric's solution at the line that says:

Then there exists an integer $N$ such that for every $i>N$, $M_i=v_i$.

And we continue:

---

Mathematician $i$ with $i<N$ can determine $N$. However mathematician $N$ cannot determine $N$ since they don't know whether $v_N=M_N$. So each mathematician with $i\geq N$ only knows that $N\leq i$.

Now if $i>N$, then $M_i=v_i$ by definition of $N$ so we know that mathematician $i$ could guess $P_i$ where

$$P_i = 1+v_i$$

and be correct. However, mathematician $i$ does not know this since they only know that $i\geq N$.

If $i\leq N$, then we know mathematician $i$ could guess $Q_i$ where

$$Q_i=1+\max\{M_{N},M_{N-1},\dots,M_{i+1},M_{i-1},\dots,M_1,M_0\}$$

and only one at most will be wrong. (This is a solution for the finite-mathematician version of this problem.) But mathematician $i$ only knows this if $i<N$.

Therefore for mathematician $i$, the strategy for guessing is as follows.

If there is a $K>i$ such that $M_K\neq v_K$, then $N>i$ and mathematician $i$ can determine $N$. They should guess $Q_i$:

$$H_i=1+\max\{M_{N},M_{N-1},\dots,M_{i+1},M_{i-1},\dots,M_1,M_0\}$$

If there is no such $K$ then they know that either $i>N$ or $i=N$. If $i>N$ then they could guess $P_i$ and be correct. If $i=N$ then they could guess $Q_i$ (and maybe end up making the only wrong guess). And since $i=N$, we get $Q_i=Q_N=R_i$ where $R_i = 1+\max\{M_{i-1},M_{i-2},\dots,M_1,M_0\}$.

Since they don't know which of these cases holds, they should just guess $max\{P_i,R_i\}$:

$$H_i=1+\max\{v_i,M_{i-1},M_{i-2},\dots,M_1,M_0\}$$

With this strategy, all mathematicians $i$ where $i>N$ will guess correctly; and all mathematicians $i$ where $i\leq N$ will guess correctly, except possibly one.

---

And that solution is exactly Eric's, just spelled out a bit more explicitly.

For me, the finite-mathematicians version of the problem is mindblowing; this infinite version even more so. I think more people should have their minds blown by it, and I hope this presentation will help.