Let $n$ $\geq$ $2$ and $k$ $\geq$ $2$ be positive integers. A cat and a mouse are playing Wim, which is a stone removal game. The game starts with $n$ stones and they take turns removing stones, with the cat going first. On each turn they are allowed to remove $1$, $2$, $\dotsb$, or $k$ stones, and the player who cannot remove any stones on their turn loses. A raccoon finds Wim very boring and creates Wim 2, which is Wim but with the following additional rule: You cannot remove the same number of stones that your opponent removed on the previous turn. Find all values of $k$ such that for every $n$, the cat has a winning strategy in Wim if and only if it has a winning strategy in Wim 2.
Problem
Source: Centroamerican and Caribbean Math Olympiad 2024 P6
Tags: OMCC, combinatorics, winning strategy
03.11.2024 20:09
The answer is all $k$ such that $v_2(k+1)$ is even. We will divide the proof into three lemmas. Lemma 1. For a fixed $k$, the cat has the winning strategy in Wim if and only if $n$ is not a multiple of $k+1$. Proof. First, assume that $n$ is not a multiple of $k+1$, that is, it is of the form $m(k+1)+a$, with $m\geqslant0$ and $1\leqslant a\leqslant k$. The cat's strategy is always to leave a multiple of $k+1$ stones for the mouse. Since $1\leqslant a\leqslant k$, the cat can start by removing $a$ stones. Since the mouse always has to remove some stones, it will leave a number of stones that is not a multiple of $k+1$, and the cat can repeat the process. Since the cat can always respond to the mouse’s actions, it will never run out of moves, and thus has the winning strategy (this is a finite game with no ties, so if you have a way not to lose, you win). By the same strategy, if $n$ is a multiple of $k+1$, no matter what the cat does, it will leave a number of stones of the form $m(k+1)+a$ for the mouse, so now it’s the mouse that has the winning strategy. Thus, the lemma is proven. Lemma 2. If $v_2(k+1)$ is odd, the cat has a winning strategy for $n=k+1$ in Wim 2. Proof. Suppose $k+1=2^ab$, with $a$ and $b$ odd. The cat’s strategy will be as follows: Suppose the cat has $2^cb$ stones on its turn, with $c$ odd (as at the start of the game). In this case, the cat removes $2^{c-1}b$ stones, leaving the mouse with $2^{c-1}b$ stones. Since the cat removed $2^{c-1}b$ stones and this is Wim 2, the mouse cannot remove $2^{c-1}b$ stones, so it cannot remove all the remaining stones. If the mouse removes $d\neq2^{c-2}b$ stones, the cat simply removes $2^{c-1}b-d$ stones and wins. If the mouse removes $2^{c-2}b$ stones, the cat will have $2^{c-2}b$ stones, where $c-2$ is odd, and repeats Step 1. Again, since the cat always has a response, it has the winning strategy, as we wanted. Lemma 3. If $v_2(k+1)$ is even, the cat has the winning strategy in Wim 2 if and only if $n$ is not a multiple of $k+1$. Proof. Suppose $k+1=2^ab$ with $a$ even and $b$ odd. First, assume that $n$ is not a multiple of $k+1$. The cat’s strategy is as follows: In its first move, the cat removes enough stones to leave the mouse with a multiple of $k+1$, say $2^abm$ stones. If at any point the mouse has $2^ab\ell$ stones (as at the start of the game) and removes $d\neq2^{a-1}b$ stones, the cat simply removes $2^{a}b-d$ stones, leaving the mouse with $2^{a}b(\ell-1)$ stones. If the mouse removes $2^{a-1}b$ stones, the cat will have $2^ab(\ell-1)+2^{a-1}b$ stones, and then removes $2^{a-2}b$ stones, leaving the mouse with $2^{a}b(\ell-1)+2^{a-2}b$ stones. Suppose at some point the mouse has $2^{a}bp+2^{c}bf$ stones, with $p$ an integer, $c<a$ even, and $f$ odd (as at the end of the previous step). If the cat had just removed $2^{c}bf$ stones (as at the end of the previous step), the mouse cannot remove $2^{c}bf$ stones again. If it removes $e$ stones, with $e\neq 2^{c-1}bf$, $(2^{a-1}+2^{c-1}f)b$, the cat can remove $2^{c}bf-e$ or $2^{a}b+2^{c}bf-e$ stones (depending on whether $e<2^{c}bf$ or $e>2^{c}bf$), leaving $2^{a}bp$ or $2^{a}b(p-1)$ stones, returning the mouse to Step 2. If the mouse removes $2^{c-1}bf$ or $(2^{a-1}+2^{c-1}f)\cdot b$ stones, the cat’s strategy is to remove $2^{c-2}bf$ or $(2^{a-2}+2^{c-2}f)\cdot b$ stones, respectively. This leaves the mouse with $2^{a}b(p-1)+2^{c-2}bf$ or $2^{a}b(p-1)+ (2^{a-c}+f)2^{c-2}b$ stones, respectively, returning the mouse to Step 4. Examining this strategy, the cat always has a response to the mouse, so it has the winning strategy if $n$ is not a multiple of $k+1$. Conversely, if $n$ is a multiple of $k+1$, the cat will start on Step 2 of the mouse in the described strategy, so the roles are reversed and the cat loses. Therefore, the cat wins if and only if $n$ is not a multiple of $k+1$ in this case, as we wanted. Finally, by Lemma 2, we see that the $k$ such that $v_2(k+1)$ is odd do not work, as if they did, by Lemma 1, the cat should lose when $n=k+1$. On the other hand, by Lemma 3, the $k$ with $v_2(k+1)$ even satisfy that the cat has a winning strategy for $n$ in Wim 2 if and only if it has one in Wim. Therefore, the possible values of $k$ are those that satisfy $v_2(k+1)$ is even, as we wanted. $\square$