8
$\begingroup$

In this game, you start with a square. Alice tries to connect the top side to the bottom side, and Bob tries to connect the left side to the right side, like in Hex. Unlike in Hex, Alice and Bob use points instead of hexagons.

Now you might say that neither Alice nor Bob can win, since it is impossible to form a line using only finitely many points. Not so, for Alice and Bob can move infinitely many times!

In particular, let $S_\alpha$ be the state of the board, where $n$ is an ordinal. Then:

  • If $\alpha=0$, then $S_n=\emptyset$.
  • If $\alpha$ is a successor ordinal, then Alice adds $(n,p,Alice)$, where $p$ is some point in $[0,1] \times [0,1]$ that has not already been played, to $S_{\alpha-1}$, unless $S_{n-1}=[0,1] \times [0,1]$. She can use $S_{\alpha-1}$ to inform her discussion (in other words, Alice has a strategy function that given $S_{\alpha-1}$, gives her move). Bob does likewise.
  • If $n$ is a limit ordinal, then $S_\alpha = \bigcup_{\beta<\alpha}S_\beta$.

We say Alice has won if there for some $\alpha$, there is a path in $[0,1] \times [0,1]$, composed of points corresponding to Alice's moves, connecting the top and bottom. Bob wins likewise, (connecting the left and right side of the boards).

Since there are ordinals $\alpha$ such that $|\alpha| > |[0,1]\times[0,1]|$, the board must eventually be filled (in particular, it will happen before such an ordinal).

One thing to note is that Alice and Bob can not both win, due to the Jordan curve theorem. On the other hand, it is possible for neither of them to win. In this case, Alice would have no curve connecting the top and bottom, and Bob would have no curve connecting the sides.

My question is:

  • Does Alice have a winning strategy? (Bob doesn't, due to a strategy stealing argument.)
  • Does Alice or Bob have a drawing strategy (a strategy that guarantees either a win or a draw)? (If Bob does, so does Alice.)
$\endgroup$
11
$\begingroup$

Let $\mathfrak{c}$ denote the cardinality of real numbers and let $(C_{\alpha}: \alpha < \mathfrak{c})$ be an enumeration of uncountable closed subsets of the unit square.

Let Bob's strategy be playing a point $q_{\alpha} \in C_{\alpha}$ not already chosen at stage $\alpha$ for $\alpha < \mathfrak{c}$. This is possible since, at stage $\alpha < \mathfrak{c}$, the players could have chosen only less than $\mathfrak{c}$ many points of the set $C_{\alpha}$ which has cardinality $\mathfrak{c}$. Bob can do whatever he feels like for other ordinals.

Note that the game will proceed at least $\mathfrak{c}$ stages since any curve connecting opposite sides contains $\mathfrak{c}$ many points. Any curve $C$ witnessing the victory of a player would be necessarily of the form $C_{\beta}$ for some $\beta < \mathfrak{c}$ and hence contains the point $q_{\beta}$. Thus Bob guarantees not losing if he plays with this strategy. (Of course, by using this strategy, Alice can guarantee not losing as well.)

$\endgroup$
  • $\begingroup$ This answer needs AC - I wonder if the ultimate answer depends on choice. $\endgroup$ – Steven Stadnicki Sep 27 '17 at 22:22
  • 4
    $\begingroup$ @StevenStadnicki: Without AC, then it is possible that neither player can win even if the players are cooperating. Indeed, a victory for either player gives a well-ordering of a set of cardinality $\mathfrak{c}$, and it is consistent with ZF that no such well-ordering exists. $\endgroup$ – Eric Wofsey Sep 27 '17 at 22:54
  • 4
    $\begingroup$ In fact, a well-ordering of $\mathfrak{c}$ is exactly what this answer needs to work, so this shows in ZF that no matter what, neither player has a winning strategy (for rather different reasons, depending on whether a well-ordering of $\mathfrak{c}$ exists!). $\endgroup$ – Eric Wofsey Sep 27 '17 at 23:07
  • $\begingroup$ @EricWofsey Oh, that makes perfect sense - I'd missed that the definition itself(!) needs AC. Thank you! $\endgroup$ – Steven Stadnicki Sep 27 '17 at 23:14
  • $\begingroup$ @StevenStadnicki what if you require Bob to have some sort of "constructive" strategy, so he can't make use of the axiom of choice? $\endgroup$ – PyRulez Sep 28 '17 at 15:14

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.