A game with numbers modulo $N$

Question

Let $N\geq 4$ be a fixed positive integer. Two players, $A$ and $B$ are forming an ordered set $\{x_1,x_2,...\},$ adding elements alternatively. $A$ chooses $x_1$ to be $1$ or $-1,$ then $B$ chooses $x_2$ to be $2$ or $-2,$ then $A$ chooses $x_3$ to be $3$ or $-3,$ and so on. (at the $k^{th}$ step, the chosen number must always be $k$ or $-k$)

The winner is the first player to make the sequence sum up to a multiple of $N.$ Depending on $N,$ find out, with proof, which player has a winning strategy.

My attempt: We know that for $N=4$, the first player wins because he can change the residue modulo $N$ by $1$ or $-1$ at his moves while the other player has much more limited changing capabilities, and it is easy to prove this. I think that by the same logic, we know that when $N$ is a multiple of $4$, the second player cannot win but we still don't know if the first player can win or the game can continue forever.

If $N$ is divisible by 4, the first player can make sure that the second player doesn't win in this way: We will look at the problem modulo $4$ and prove that the second player can never obtain a number divisible by $4$, thus never winning.

We will consider all numbers modulo $4$.

Player $1$ will always add/subtract $1$ or $3$, in other words, always add $-1$ or $1$. The steps go as folows:

At steps of form $4k+1$: Player $1$ adds $-1$ or $1$. At steps of form $4k+2$: Player $2$ adds $2$ (he has no other choice). At steps of form $4k+3$: Player $1$ adds $-1$ or $1$. At steps of form $4k+4$: Player $2$ adds $0$ (he has no other choice).

So at the $4k+2$ the number received by player $2$ before his move is odd, so he can't win here. At the $4k+3$ steps, if player $1$ receives a number of the form $4k+1$, he can add $1$, thus giving to the second player a number that is not divisible by $4$ so player 2 can't win. In the other case, when player $1$ receives a number of the form $4k+3$, he can add $-1$, again blocking player $2$, from winning.

However we only know that player $2$ cannot win, but this does not necessarily mean that player $1$ has a winning strategy.

Source: Romanian TST 2021 Day 3, P2

Answer 1

The result:

• $A$ wins for $N = 4$;
• $B$ wins for $N = 5, 6, 10$;
• neither can win for other $N$.

For the proof, there is slight difference between odd and even $N$. I will treat the case of odd $N$ here as it's simpler.

Thus fix odd $N \geq 9$.

Define $w(s, m)$ as follows: suppose the sum of all previous numbers is congruent to $s$ mod $N$ and the next number to add is $m$ mod $N$ (thus the next player can choose to add $m$ or $-m$). We define $w(s, m) = 1$ if this situation is a win for the next player to move; $w(s, m) = -1$ if this situation is a lose for the next player to move; $w(s, m) = 0$ otherwise.

Claim:

1. $w(m, \pm m) = 1$ for all $m$;
2. $w(0, -2) = w(0, \frac{N - 1}2) = w(\pm 1, 0) = -1$;
3. $w(0, -1) = w(\pm 2, -1) = 1$;
4. all other $w(s, m)$ are equal to $0$.

Proof: It's a tedious routine check.

• $w(m, \pm m) = 1$ is clear;
• $w(0, \frac{N - 1}2) = -1$ because $w(\pm\frac{N - 1}2, \frac{N + 1}2) = 1$;
• $w(\pm1, 0) = -1$ because $w(\pm1, 1) = 1$;
• $w(0, -1) = w(\pm2, -1) = 1$ because $w(\pm1, 0) = -1$;
• $w(0, -2) = -1$ because $w(\pm 2, -1) = 1$;

and for all other $s, m$:

• none of $w(s \pm m, m + 1)$ is equal to $-1$;
• $w(s \pm m, m + 1)$ cannot be simultaneously equal to $1$.

This proves the result.

The case of even $N$ is more complicated (slightly different according to $N \equiv 0, 2$ mod $4$) but similar.