There is a pile with 2022 rocks. Ana y Beto play by turns to the following game, starting with Ana: in each turn, if there are $n$ rocks in the pile, the player can remove $S(n)$ rocks or $n-S(n)$ rocks, where $S(n)$ is the sum of the the digits of $n$. The person who removes the last rock wins. Determine which of the two players has a winning strategy and describe it.
Problem
Source: 2022 Centroamerican and Caribbean Mathematical Olympiad, P1
Tags: game strategy, combinatorics
01.12.2022 15:32
Solved with mxlcv Rename Ana and Beto with bisexual characters $A, B$. We claim that $A$ wins. Observe that this can be done WLOG. First, observe that if at any point of time the number of rocks is between $1$ and $9$, both inclusive, then the player in that turn wins. Also observe that if in any player's turn they are left with $18$ rocks then they lose, since they must perform $18 \mapsto 9$ no matter what. Due to the first observation, the initial moves (due to optimal play) are $2022 \overset{A}{\mapsto} 2016 \overset{B}{\mapsto} 2007 \overset{A}{\mapsto} 1998$. Now $B$ has two choices. They can either perform $1998 \mapsto 27$ which loses since $A$ can convert $27 \mapsto 18$. In the other case, they perform $1998 \mapsto 1971$ in response to which $A$ performs $1971 \mapsto 18$ and wins.
01.12.2022 17:37
Ana wins. The only observation is that a player won't ever leave a single digit number of rocks on the pile since the other player would immediately win afterwards. Thus the following moves are all forced: 1. Ana reduces $2022$ to $2016$. 2. Beto reduces $2016$ to $2007$. 3. Ana reduces $2007$ to $1998$. Now if Beto leaves $27$ rocks on the pile then Ana leaves $18$, at which point they wins as Beto will leave $9$ rocks on the pile on their next turn. Otherwise Beto leaves $1971$ rocks on the pile, at which point Ana may leave $18$ and win, same as the previous case.
05.07.2023 14:28
another solution if $n \equiv (0,2,4,6,8) mod 10$ then Ana wins