10
$\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$
  • 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$ – Noah Schweber Dec 25 '13 at 21:56
  • 4
    $\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$ – Dan Turetsky Dec 25 '13 at 23:18
  • 2
    $\begingroup$ This is an outcry of mathematical thought: "can an infinite number of mathematicians..." $\endgroup$ – Victor Dec 26 '13 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 '13 at 23:18
  • 2
    $\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 '13 at 10:56
8
$\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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, that's an elegant argument; the result is surprising too. $\endgroup$ – user44653 Jan 1 '14 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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