Counting to 100 game with a twist (A Nim Variation?)

Question

So the premise is the classic two-player counting to 100 game: players alternate picking an integer between 1 and 10 (inclusive), and the first to let the cumulative sum be greater than or equal to 100 loses.

However the twist is this (and it defeats the normal solution of adding to multiples of 11) - no two consecutive moves in the game can add to 11. That is, if Player A says an integer k, Player B cannot in the next turn say an integer m that would make k + m = 11. With this additional rule, what's the new winning strategy?

Answer 1

Player A has a winning strategy, which begins with the unique move of choosing $3$.

Every game state after the starting state can be represented by an ordered pair $(r,m)$, where $r$ is the remaining distance to $100$ (that is, $r$ equals $100$ minus the cumulative total) and $m$ is the previous move.

A brute-force calculation reveals that the losing positions are precisely these:

• when $r\equiv1\pmod{12}$ and $m$ is anything;
• when $r+m\equiv0\pmod{12}$.

In other words, player A wants to end every turn in one of those positions. Note that A's choices for the first move leave the game states $(99,1)$, $(98,2)$, ..., $(90,10)$, and of these only $(97,3)$ is a losing position, which is why A should choose $3$ as their first move.

Note that if A starts their turn in a non-losing position, then they can always choose to move to a losing position:

• if A starts with the state $(r,m)$ where $r\equiv2,3,\dots,11\pmod{12}$, then A chooses the move that makes the new value of $r$ congruent to $1\pmod{12}$; the possibility that this move is prohibited by the previous move is ruled out by assuming that $(r,m)$ is a non-losing position. For example, if A starts their turn in a non-losing position with $r=53$, then $m$ cannot equal $7$, which means that A is allowed to play the move $4$ to reach the losing position $(49,4)$ for B;
• if A starts with the state $(r,m)$ where $r\equiv0\pmod{12}$, then A chooses any legal move $\ell$—they all yield a state of the form $(r-\ell,\ell)$, where the two coordinates will add to a multiple of $12$, making it a losing position for B.

On the other hand, if B starts their turn in a losing position, every possible move results in a winning position for A:

• if B starts with the state $(r,m)$ where $r\equiv1\pmod{12}$, then any move $1\le\ell\le10$ results in the state $(r-\ell,\ell)$ where $r-\ell\not\equiv1\pmod{12}$ and where the coordinates add to $r$ which is not a multiple of $12$, hence leaving a non-losing position for $A$;
• if B starts with the state $(r,m)$ where $r+m\equiv0\pmod{12}$ (so that in particular $r\not\equiv0\pmod{12}$), then the legal moves are $1\le\ell\le10$, $\ell\ne 11-m$, resulting in the states $(r-\ell,\ell)$. Note that $r-\ell\not\equiv r-(11-m)\pmod{12}$ while $1 \equiv r+m+1 \equiv r-(11-m)\pmod{12}$, and that $(r-\ell)+\ell = r\not\equiv0\pmod{12}$; therefore the new state is a non-losing position for A.

(The reason for phrasing this in terms of $r$, the remaining distance to the largest non-terminal total, is that if the terminal total is changed from $100$ to some other number then the entire analysis remains the same, other than player A's first move: it is a win for player A unless the terminal total is congruent to $1\pmod{12}$.)

Answer 2

A wins as follows. I will use @GregMartin's notation $(r,m)$, where $r$ is 100 minus the cumulative sum and $m$ is the previous move.

A's strategy is to run $r$ through 97, 85, 73, 61,..., until it reaches 1, with its being B's turn each time. When $r$ reaches 1, B has lost. These are all values of $r$ satisfying $1\leq r\leq 99$ and $r\equiv 1 \pmod{12}$.

A starts by playing 3 to take $r$ to 97. Thereafter, they can always decrease $r$ by 12, either in one pair of turns (BA) or two (BABA).

• If B plays $t\not=1$, A plays $t$'s 12-complement; BA=12.
• If B plays $t=1$, A needs two steps: first A plays $1$; then whatever B plays (which is not allowed to be 10), A plays its 10-complement; BABA=1+1+10=12.

A's needed move is always legal because each of the three moves they might need, namely $t$'s 12-complement (needed when $t\not=1$), its 10-complement (never needed when $t=10$), and 1 (needed in answer to B's having played $t=1$ when $r$ had one of its target values), are always both between 1 and 10 inclusive and different from $t$'s 11-complement.

Answer 3

Call the running total R. Player A wins. Here is how:

If possible, play to make $R\equiv 3 \pmod{12}$; otherwise, play 1.

And that's it! That's all you need!

Readers may like to know that I shortened that down from this:

• if possible, play to make $R\equiv 3 \pmod{12}$
• if that is not possible, play 1, then wait for B to play, then play the 10-complement of what B just played.

Answer 4

I didn’t quite follow the arguments above but I’m pretty confident that Player A wins by playing 4 to start. Here's how I worked backwards to that answer:

Let “Player A” refer to the player whose turn it is in each of the following situations.

If there is a total of 89, player A wins. Since 89 is exactly 11 less than 100, the total cannot jump from 89 to 100 in two moves. Whatever player A adds to 89, player B must keep the total less than 100, and player A can swoop in for the kill.

If there is a total of 88, player A loses. He cannot add 1 or he gives his opponent 89 (a guaranteed win - shown above). If he adds two or more, the total will be in the 90s and his opponent will be within striking distance of 100; his opponent can legally win the game since the final two moves would add to 12.

If there is a total of 77, player A wins. Since 77 is exactly 11 less than 88, the total cannot jump from 77 to 88 in exactly two moves. Whatever player A adds to 77, player B has two choices: -Make the total less than 88 (in which case player A can make the total 88 on his following turn) -Make the total 89 or above, in which case player A can jump straight to 100.

If the total is 76, player A loses. He cannot add 1 or he gives his opponent 77. If he adds 2-10, he’ll make the total 78-86. In any of these cases, player B can respond by making the total 88 (a 12-point jump in two moves). As seen above, 88 is a loss for player A.

This reasoning shows that all the losing (and winning) positions occur 12 points apart. The losing positions are: 88-76-64-52-40-28-16-4 and the winning positions are 5-17-29-41-53-65-76-89.

Player A should pick ‘4’ to start, and proceed to force his opponent into the above positions. If Player B adds 2 or more after a losing position, player A should add enough to get to the next losing position. If player B adds ‘1’ after a losing position, then player A adds anything. Player B will be unable to force player A into a losing position, and this will continue until it is player A’s turn with 89 or above.