Riddle: finite set that contains one of the three numbers

Question

A colleague told me this two-part riddle:

PART $\mathbb{N}$:

Three players sit in a circle, each having a positive integer number $x_i$ written on their hat. Every player can see only the numbers of the other two players. Then (without any communication) each of the players writes down a finite set $S_i$ of positive integers. The players win (collectively) iff $x_i\in S_i$ for at least some $1\leq i\leq 3$.

An easy strategy to win is to use

$S_i = \{ n\in\mathbb{N} \mid n \leq M_i \}$ where $M_i$ is the largest of the two numbers that $i$-th player sees. This works because all the initial segments of $\mathbb{N}$ (sets of the form $\{n\in\mathbb{N}\mid n \leq M \}$ for some $M$) are finite.

PART $\mathbb{R}$:

My question is: can the players always win if $x_i\in\mathbb{R}$ (and $S_i\subset \mathbb{R}$)?

---

My thoughts (spoilers for the first case):

This would be possible if one could order the reals so that every initial segment $\{y\in\mathbb{R}\mid y \preceq Y \}$ (where $\preceq$ is the ordering) would be finite. I know that $\mathbb{R}$ can be well-ordered, but this only guarantees that there is no infinite chain $\cdots \prec y_3\prec y_2\prec y_1$. This, however, is not enough: $\mathbb{N}\cup\{\infty \}$ is well-ordered (isomorphic to $\omega + 1$) but the set $\{n \mid n < \infty \} = \mathbb{N}$ is infinite.

Still, $\mathbb{N}\cup\{\infty \}$ can be reordered differently, so that it becomes isomorphic to $1 + \omega =\omega$ (in that case, we should relabel the additional element $\infty$ to $0$), but I do not know how to proceed in the case of $\mathbb{R}$, where only the mere existence of some well-order is given.

Another (slightly more "efficient") solution in the $\mathbb{N}$-case is $S_i = \{n\in\mathbb{N}\mid m_i \leq n \leq M_i\}$, where $m_i$ is the smallest of the two numbers that player $i$ sees, but this does not help me either.

If someone can give a reference/hint/solution (none of which I could find), it would be much appreciated. Hopefully, the tags are appropriate.

Answer 1

Cool puzzle! I've seen a lot of "prisoners and hats" puzzles, but I hadn't seen this one before. I'll use copious spoiler tags since it's not clear which things you'd like to think about yourself vs. read about.

Your solution for part $\mathbb{N}$ would work with just 2 prisoners, so it's pretty suspicious that we're given 3. Indeed, we can show the $\mathbb{R}$ version would be impossible with only 2:

Let $S_j : \mathbb{R} \to \{ A \in \mathcal{P}(\mathbb{R}) : A \text{ is finite} \}$ describe the strategy followed by player $j$. If $x_1$ is an integer then player 2 will always choose some finite subset in $\bigcup_{n \in \mathbb{Z}} S_2(n)$. That's a countable union of finite sets, so the union is countable, so we can select $x_2 \in \mathbb{R} \setminus \bigcup_{n \in \mathbb{Z}} S_2(n)$. Next, we note $S_1(x_2)$ is finite, so we can choose $x_1 \in \mathbb{Z} \setminus S_1(x_2)$. Now both players will guess wrong.

As for actually solving the puzzle, I cheated by finding a Reddit source. That thread is very interesting; it includes several cool puzzles and also links to even more. Anyway I'll reproduce the answer here, but I'll start with some hints and work my way up so you can reveal only what you want.

A related but slightly simpler problem that could be helpful to think about:

Two wizards each have a real number written on their forehead. They simultaneously make countably many guesses, and the goal is for at least one to guess correctly.

A hint for the subproblem:

Assume the continuum hypothesis.

Solution of the subproblem:

Use CH to find a bijection $f: \mathbb{R} \to \omega_1$. Now each player essentially sees a countable ordinal. They should each guess the countable set of all ordinals $\le$ the one they see (translated back to $\mathbb{R}$, of course). Whoever's hat corresponded to the smaller ordinal will guess right.

A hint for the full problem:

Assume the continuum hypothesis and also the axiom of choice.

Finally, the solution to the full problem you asked about:

Use CH to find a bijection from $\mathbb{R} \to \omega_1$. Use AC to choose a bijection $f_\alpha : \alpha \to \mathbb{N}$ for each infinite ordinal $\alpha \in \omega_1$. During the game, each player sees 2 hat values which correspond to ordinals $\alpha$ and $\beta$; assume $\beta \le \alpha$. Let $\tilde \alpha = \max(\alpha, \mathbb{N})$. Now guess all natural numbers $\le f_{\tilde \alpha}(\beta)$ after mapping them back to ordinals using $f_{\tilde \alpha}$ and then to reals using the CH bijection. Proof that this works: Ignore the guesses from the player with the largest ordinal. The other two will both choose the same $\tilde \alpha$, so they're essentially playing the strategy from the hint subproblem above.

Credit to /u/jfb1337 whose solutions I'm paraphrasing. Thanks @Antoine for correcting a minor math error in an earlier version of this answer.

---

Bonus: Here's my own personal favorite prisoners & hats problem. There are $n$ prisoners, each wearing one of $k$ hat colors. Everyone will simultaneously submit a guess for the color of their own hat. You need to maximize the worst-case number of correct guesses. I think finding the right strategy is a little fun, and proving that it's optimal uses a really cool trick that I've benefited from in other problems too :)