1
$\begingroup$

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

$\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$
    – lulu
    Jul 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$
    – Mogul
    Jul 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$
    – lulu
    Jul 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$
    – lulu
    Jul 13, 2021 at 0:43
  • $\begingroup$ I see, now I understand, thank you very much! $\endgroup$
    – Mogul
    Jul 13, 2021 at 0:53

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.