16

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}$.

Feryll
  • 2,369
  • 11
  • 28
  • 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? – hexomino Jul 11 '20 at 00:08
  • 2
    @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. – Feryll Jul 11 '20 at 03:37
  • This makes much more sense to me, thanks. The definition of $D_x$ has really cleared things up. – hexomino Jul 11 '20 at 11:18
  • 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$. – hexomino Jul 11 '20 at 11:21
  • 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... – WhatsUp Jul 11 '20 at 13:23
  • @WhatsUp I don't believe it makes a difference to the answer (or the solution!) in our spaces, and in either case, a game is guaranteed to end in a finite number of moves (why is that?). If it's more natural to you that the intermediate spaces also be compact, feel free to think of it that way. – Feryll Jul 11 '20 at 13:27
  • I'm not complaining about your wording. I also totally understand that, as long as $r > 0$ (which is anyway necessary here), there is not much of a difference. But for me it is indeed more natural to cover compact things by open sets, rather than closed ones... – WhatsUp Jul 11 '20 at 13:32
  • Since the two formulations are basically equivalent, and as you said, it's slightly more intuitive to consider open disks, I've gone and made the change. – Feryll Jul 11 '20 at 14:25
  • Do you have a solution for the even case? I haven't been able to fix the issue with my solution there. – xnor Jul 22 '20 at 17:13
  • @xnor No, I do not know of a solution for the even case. I'll admit that when I formulated this problem, my intended solution was that which you produced, and so I fell victim to the same mistake you did! Hence why I awarded your answer the bounty. I'm convinced an actual solution would be very difficult, and likely depend intimately on the choice of $r$ (unlike the odd case). It is, of course, the question of topological nim on the Mobius strip (keep in mind, as well, the transformation of metrics). – Feryll Jul 22 '20 at 17:19

2 Answers2

7

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.

xnor
  • 26,756
  • 4
  • 85
  • 144
  • 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. – Jaap Scherphuis Jul 13 '20 at 12:40
  • @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))$. – xnor Jul 13 '20 at 12:41
  • 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. – Jaap Scherphuis Jul 13 '20 at 12:44
  • @JaapScherphuis Darn, you're right, I was taking too many liberties with equivalences. I'll see if some argument like this still holds. – xnor Jul 13 '20 at 12:47
  • @JaapScherphuis I guess it now works to rotate 180 degrees instead. Does that seem right to you? (Edit: wait, no it doesn't of course) – xnor Jul 13 '20 at 12:50
  • I don't think so. $(0,1,0)$ maps to $(0,-1,0)$, i.e. onto itself, not a distance of $r$ away. – Jaap Scherphuis Jul 13 '20 at 12:53
  • 1
    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). – hexomino Jul 13 '20 at 15:03
2

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.)

Gareth McCaughan
  • 119,120
  • 7
  • 313
  • 454
  • 2
    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). – tehtmi Jul 11 '20 at 10:47
  • 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. – hexomino Jul 11 '20 at 11:15
  • 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. – hexomino Jul 11 '20 at 11:44
  • 1
    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. – Feryll Jul 11 '20 at 12:38
  • Hmm, yup, my answer is all wrong for the reasons others have given above. Will add a cautionary note to it. – Gareth McCaughan Jul 11 '20 at 15:43