16
$\begingroup$

You and your friend's new favorite game is "topological nim": You take your favorite compact metric space $X$ and a radius $r$. Each player removes an open disk of radius $r$ from the space on their turn (only the center of the disk must not have been removed in a prior move), until one player—the winner—removes what remains of the space on his turn.

Intro question: For each $n$ and $r$, who (if anyone) wins topological nim on $S^n = \{\bf{x}\in \mathbb{R}^{n+1}~|~|\bf{x}| = 1\}$ with the standard metric?

Real question: For each $n$ and $r$, who (if anyone) wins topological nim on $\mathbb{RP}^n$ with the standard metric? This is equivalent to playing the same game on $S^n$, but where a move at $\bf{x}$ necessarily removes the disks around both $\bf{x}$ and $-\bf{x}$.

$\endgroup$
10
  • $\begingroup$ Do we take it that the winning player is the first one who is unable to remove a disc? Like, if what remains of the space is greater in measure than a disc or radius $r$ but does not contain a disc of radius $r$, they can still remove the whole thing? $\endgroup$
    – hexomino
    Jul 11 '20 at 0:08
  • 2
    $\begingroup$ @hexomino Let the current remains of the space be denoted by $Y$. Then a move consists of choosing any point $x \in Y$, whereupon he hands the game over to his opponent with remains $Y \setminus D_x$, where $D_x = \{ y \in Y ~|~ d(y,x) \leq r \}$. The loser is the first one unable to make a move (as in nim under standard play), i.e. $Y = \varnothing$. There is nothing to do with measure; $X$ may not even be a measure space. $\endgroup$
    – Feryll
    Jul 11 '20 at 3:37
  • $\begingroup$ This makes much more sense to me, thanks. The definition of $D_x$ has really cleared things up. $\endgroup$
    – hexomino
    Jul 11 '20 at 11:18
  • $\begingroup$ I guess what confused me before is that I thought the disc had to be closed in $Y$, but I see now it's just closed in $\mathbb{RP}^n$. $\endgroup$
    – hexomino
    Jul 11 '20 at 11:21
  • $\begingroup$ Wouldn't it be more natural to remove open disks, in view of the definition of compactness? Another comment is that the same game could be played on $p$-adic fields, e.g. on $\Bbb P^n_{\Bbb Q_p}$, and it would be much simpler... $\endgroup$
    – WhatsUp
    Jul 11 '20 at 13:23
7
+200
$\begingroup$

Intro question:

For any $n$, Player 2 wins using a mirroring strategy of responding to a move $x$ with the antipodal move $-x$ (except in the corner case where $r>\sqrt 2$ where Player 1's first move removes everything and wins). Because each of Player's 2 move maintains the set of remaining points as symmetrical around the origin, as long as Player 1 has a valid move, so does Player 2. Since Player 2 can never lose and the game eventually ends, they win the game.

The strategy for the intro question suggests a generalized version that can apply to topological nim on different spaces.

For a metric space $X$ and radius $r$, say that a map $m$ from $X \to X$ is a mirror map if:
- $m$ is an isometry: it is preserves distances on $X$
- $m$ is self-inverse: $m^{-1}=m$
- $m$ moves each point at least distance $r$ away: $d(x, m(x)) \geq r$ for all $x\in X$

For the intro question, the mirror map is $m(x)=-x$.

We find that if a mirror map $m$ exists on $X$ with radius $r$, then Player 2 wins topological nim. They do this by responding to any move $x$ of of Player 1 with $m(x)$, maintaining the $m$-symmetry of the remaining space.

Because $d(x, m(x)) \geq r$, the point $m(x)$ is not removed following $x$ and so remains a legal move. Moreover $m(x)$ cannot have been removed by any earlier move $y$ or $m(y)$ because $m$ is distance-preserving and self-inverse: if $d(m(x),y)<r$ then $d(x,m(y))<r$, so $x$ would already have been an illegal move. Similarly if $d(m(x),m(y))<r$, then $d(x,y)<r$.

We can apply this general argument to the main problem to first show that:

Player 2 wins when $n$ is odd, except in the trivial case $r > \sqrt{2}$ when Player 1's first move removes everything and wins.

For $\mathbb{RP}^n$ with $n+1=2k$ even, the mirror map $m$ that rotates each adjacent pair of coordinates 90 degrees as $(x,y) \to (y,-x)$, which is self-inverse because a 180-degree rotation is the identity. That is, $m$ sends $(x_1,y_1,x_2,y_2,\dots,x_k,y_k)$ to $(y_1,-x_1,y_2,-x_2,\dots,y_k,-x_k)$. It's easy to see that $m$ is an isometry.

The Euclidian distance-squared from $(x,y)$ to $(y,-x)$ is always $2$, and likewise to its antipode $(-y,x)$. So the total distance-squared $d(x,m(x))^2$ is twice the sum of the coordinates-squared, which is $2$ because the points lie on a unit sphere. So, this satisfies the distance property of a mirror map as long as $r \leq \sqrt 2$. If $r>\sqrt 2$, then Player 1's first move trivially wins by removing everything.

For the other case, we can draw inspiration from the strategy for a modified "intro question", where the players play on a disk of radius $1$ in $\mathbb{R}^2$. For this game:

Player 1 wins by placing their first move in the center point $p=0$, then continuing to a mirror strategy of $m(x)=-x$. After their first move, Player 1 takes on the role of the new Player 2 to win with the mirror strategy on the remaining space. Note that while $m(x)=-x$ is not a mirror map on the original space due to points near the origin remaining near the origin, the first move removes such points, and ensures that no play interferes with its mirror.

This same type of argument lets us handle the other case (edit: this doesn't work, see Jaap Scherphuis's comment):

Player 1 wins when $n$ is even.

Player 1 starts by moving to $p=\pm (1,0,0 \dots)$, or really to anywhere and rotating their coordinates appropriately. They play on the remaining space as the new second player using mirror map $m$ like before of applying a 90 degree rotation $(x,y) \to (y,-x)$ on each pair of adjacent coordinates, except the unpaired first coordinate remains unchanged. That is, $m$ sends $(a, x_1,y_1,x_2,y_2,\dots,x_k,y_k)$ to $(a, y_1,-x_1,y_2,-x_2,\dots,y_k,-x_k)$. (Recall that the total number of coordinates $2k+1=n+1$ is odd.) This map is still distance-preserving and self-inverse as before.

The intuition here is that after removing the "ice caps" near the poles $p= \pm (1,0,0 \dots)$, the remaining space is all sufficiently far-moved by a rotation $m$ whose fixed points are the poles. We will show that the distance moved by the 90-degree rotation is at least the distance to the pole $p$: $d(x,m(x)) \geq d(p,x)$. This implies that as long as $x$ was a legal move, so is $m(x)$.

We can express $d(x,m(x))^2$ by looking at the sum of the coordinate differences squared, which is $2(x_1^2+y_1^2+\cdots+x_k^2+y_k^2)=2(1-a^2)$, so we have $d(x,m(x))^2= 2(1-a^2)$. (Flipping $a$ to $-a$ only gives a bigger distance). Similarly looking coordinate-wise, and assuming WLOG that $a \geq 0$, we have the distance squared to the initial move is $d(x,p)^2 =(1-a)^2 + 1-a^2$, which is smaller or equal on the interval $a \in [0,1]$ as desired.

$\endgroup$
7
  • $\begingroup$ The rotation map is not self-inverse any more when the number of dimensions is odd, because of that extra coordinate, so I don't think the argument works there. For even dimensions it looks good to me. $\endgroup$ Jul 13 '20 at 12:40
  • $\begingroup$ @JaapScherphuis What goes wrong with the extra coordinate? Surely if $m$ is self-inverse, than so is the map taking $(a,x)$ to $(a,m(x))$. $\endgroup$
    – xnor
    Jul 13 '20 at 12:41
  • $\begingroup$ The map takes $(a,b,c)$ to $(a,-c,b)$, and then that maps to $(a,-b,-c)$. You want that to be equivalent to $(a,b,c)$ (i.e. equal or opposite), but it isn't. $\endgroup$ Jul 13 '20 at 12:44
  • $\begingroup$ @JaapScherphuis Darn, you're right, I was taking too many liberties with equivalences. I'll see if some argument like this still holds. $\endgroup$
    – xnor
    Jul 13 '20 at 12:47
  • 1
    $\begingroup$ Thank you for this beautiful answer, it's been hurting my brain today. Hopefully, you can work out $n$ even (I made a suggestion in a previous comment but I don't think it actually works). $\endgroup$
    – hexomino
    Jul 13 '20 at 15:03
3
$\begingroup$

Wrong answer (see comments for some refutations). I'm leaving the wrong answer below because I don't believe in hiding my mistakes :-).


It's

a first-player win for any values of $n$ and $r$

because

after removing the first disc, the first player can mirror the opponent's moves in the centre of that disc. (If it isn't obvious how to do this, think of $\Bbb{RP}^n$ as a quotient of $S^n$, so we're just removing antipodal pairs of discs from $S^n$; when player 2 makes a move, rotate it through $180^\circ$ about the diameter through your initial disc-pair.)

$\endgroup$
5
  • 2
    $\begingroup$ How do you rotate about a line except in S2 (3 dimensional Euclidean space)? Also, in S2, if the second player chooses a perpendicular line, rotating by 180 degrees will give the same line which will not be a valid move? In RP1 I also disagree with your conclusion; I thought the opposite player would win (using a similar strategy). $\endgroup$
    – tehtmi
    Jul 11 '20 at 10:47
  • $\begingroup$ From the way the question is phrased it looks like a win for player 2 in $\mathbb{RP}^1$ when $r \geq \frac{1}{2} diam(X)$ because no matter what player 1 does, player 2 can just "remove what remains of the space" because it is smaller than a disc of radius $r$. I think, similar to @tehtmi I need to be convinced that such a strategy works for $\mathbb{RP}^1$ as this is the one case we can definitely all visualize. $\endgroup$
    – hexomino
    Jul 11 '20 at 11:15
  • $\begingroup$ I also agree with tehtmi's point, that in $\mathbb{RP}^2$ player 2 will have the option to play a move that is it's own mirror. $\endgroup$
    – hexomino
    Jul 11 '20 at 11:44
  • 1
    $\begingroup$ Sorry Gareth, this is good thinking but incorrect. As others have pointed out, a "mirror"/rotation strategy as you pointed out actually wins for the second player (who will always have a second move) in $\mathbb{RP}^1$, which is iso to $S^1$. Yet it's not clear for $n > 1$ which spatial rotation one is interested in. $\endgroup$
    – Feryll
    Jul 11 '20 at 12:38
  • $\begingroup$ Hmm, yup, my answer is all wrong for the reasons others have given above. Will add a cautionary note to it. $\endgroup$
    – Gareth McCaughan
    Jul 11 '20 at 15:43

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.