15
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ 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$. $\endgroup$ Dec 25, 2013 at 21:56
  • 5
    $\begingroup$ 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. $\endgroup$ Dec 25, 2013 at 23:18
  • 2
    $\begingroup$ This is an outcry of mathematical thought: "can an infinite number of mathematicians..." $\endgroup$
    – Victor
    Dec 26, 2013 at 9:12
  • $\begingroup$ 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. $\endgroup$
    – user44653
    Dec 26, 2013 at 23:18
  • 3
    $\begingroup$ 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. $\endgroup$
    – Asaf Karagila
    Dec 27, 2013 at 10:56

2 Answers 2

14
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks, that's an elegant argument; the result is surprising too. $\endgroup$
    – user44653
    Jan 1, 2014 at 23:51
  • $\begingroup$ I think mathematician N cannot determine N since they don't know whether v[N]=M[N]. Therefore what we can actually say is "Mathematician i with i<N can determine N, however each mathematician with i≥N only knows that N≤i." The rest of the proof works anyway but it took me a while to see why; I have set out my reasoning in a new answer. $\endgroup$ Jun 20, 2022 at 11:01
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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