continuous variant of Nim

143 Views Asked by At

let B be a bounded real subset. Define "continuous Nim" as the following two-player game: each player removes alternately an open interval of length 1, the first that can't loses (actually it could be more interesting to rather choose the misere variant, since for intervals there is an obvious symmetric winning strategy...).

Do you think it is possible to reduce the study of this variant on a discrete set? I guess that replacing open by closed in the rule will change the game, but I don't know which choice is better (in terms of complexity of the game).

I am pretty sure I am not the first one to consider this, maybe there is a (well-known?) reference ?

Thanks in advance for any comment :)

1

There are 1 best solutions below

1
On

We analyze the variant with removing open intervals as follows. The game on $B$ is equivalent to the game on the interior of $B$, so we may assume that $B$ is open, hence that it is a disjoint union of open intervals. We may assume further that there are finitely many such intervals since we cannot move in an interval of length less than $1$. Then the game on $B$ is the sum of the games on its intervals.

I claim that the game on an open interval of length $x > 0$ is identical to a game of Kayles (octal game $.77$) of size $\lfloor x \rfloor$. We may prove this by induction on $\lfloor x \rfloor$. Suppose $x = k + c$ for an integer $k$ and $0 \le c < 1$. The game on an interval of length $z$ is to replace that interval with two (possibly zero length) intervals whose lengths sum to $x-1$. Suppose the lengths of these intervals are $n + a$ and $m + b$, where $n$ and $m$ are integers and $0 \le a,b < 1$. By induction, the games on these intervals are identical to Kayles of size $n$ and $m$ respectively. Now, $$(n+a) + (m+b) = x - 1.$$ Hence, $$n+m = x - 1 - a - b > x - 3 \ge k - 3.$$ Also, $n+m \le (k - 1) + c$. Since $n+m$ is an integer, its value must be either $k-1$ or $k-2$. Thus all available moves correspond to moves that may be made in Kayles. Conversely, all moves in Kayles can be done, for $$n + m = k-1 \implies (n + c) + m = x - 1$$ and $$n + m = k-2 \implies \left(n + \frac{1+c}2\right) + \left(m + \frac{1+c}2\right) = x-1.$$

So we are simply studying Kayles (or misère Kayles).