Skip to main content
2 of 4
edited title
user44653
  • 271
  • 1
  • 6

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$. Each step either (a) opens a subset of boxes; or (b) if it is the last step, guesses the contents of an unopened box. A strategy is a rule that determines the steps in a play, where each step depends only on the values in the previously opened boxes of that strategy.

Then for every positive integer $k$, there is a set $S$ of $k$ strategies such that, for any initial sequence of 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 some proof that k cannot be countably infinite? For that matter, if k is uncountable, can the number of wrong guesses be bounded?

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.

user44653
  • 271
  • 1
  • 6