Problem

Source: Centroamerican and Caribbean Math Olympiad 2024 P6

Tags: OMCC, combinatorics, winning strategy



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.