I was thinking in this kind of game:
Two players start from 0 and alternately add a number from 1 to 10 to the sum. The player who reaches 100 wins. The winning strategy is to reach a number in which the digits are subsequent (e.g., 01, 12, 23, 34,...) and control the game by jumping through all the numbers of this sequence. Once a player reaches 89, the opponent can only choose numbers from 90 to 99, and the next answer can in any case be 100.
And I wonder if there is a winning strategy
for a number $n$ and any maximum number that can be added
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ It's all the same as your example. The losing states are $N$, the desired end, $N-(M+1)$, where $M$ is the max you can add, $N-2(M+1)$, and so on. $\endgroup$– luluJul 12, 2021 at 23:36
-
$\begingroup$ I am not sure if I understood the method correctly, but I think this does not hold for N = 153 and M = 9 $\endgroup$– MogulJul 13, 2021 at 0:34
-
$\begingroup$ Of course it does. In that case the losing states are those $\equiv 3 \pmod {10}$. So, player $1$ always makes whatever move is needed to get to a number ending in $3$. $\endgroup$– luluJul 13, 2021 at 0:36
-
$\begingroup$ In general: start by computing the remainder of $N$ divided by $M+1$. In your case, $M+1=10$ so the remainder is $3$. That is the least losing state. As it happens, player one is starting in state $0$, which is not a losing state. Thus, all player one has to do is to leave player two with a losing state. This player one starts by adding $3$, then always adds $10-$(whatever player two last did). $\endgroup$– luluJul 13, 2021 at 0:43
-
$\begingroup$ I see, now I understand, thank you very much! $\endgroup$– MogulJul 13, 2021 at 0:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Let the final number be $n$ and the current number be $i \leq n$. Then the player whose turn it is will win with perfect play iff $n - i$ is a multiple of 11.
Proof: Suppose $n - i = k \cdot 11$. It is clear that the non-current player will always win by picking $11 - z$ immediately after the current player picks $z$.
Now suppose $n - i$ is not a multiple of 11. That is, pick $k$ such that $n - i \equiv k \mod 11$ and $1 \leq k \leq 10$. Then the current player should play $k$; by the previous direction, the current player is then guaranteed a victory.
So if we start at $0$ and end at $n$, player 2 wins iff $n$ is a multiple of 11.
answered Jul 12, 2021 at 23:39