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.
Problem
Source:
Tags: combinatorics, game, romania, Romanian TST, TST
JG666
04.10.2022 04:58
Bump this problem.
demmy
30.12.2023 08:10
Bump
Kaimiaku
17.01.2024 11:47
bump this one.
demmy
19.01.2024 07:00
Assume that for some odd $N :$ there exists winning strategy.
Then at some point no matter how that one guy choosed. He still losing as well.
WLOG Let the current sum at that moment is $n$, and he will losing after finished $k^{th}$ step ; $n \not\equiv 0 \pmod{N}$
then for all $x \in \{n+k,n-k\}$ there exists some $e \in \{k+1,-k-1\}$ which $ x+e \equiv 0 \pmod{N}$
Consider $x=n+k$ ,
case 1 . $e = k+1$
then $n+k+k+1 \equiv 0 \pmod{N} \implies n \equiv -2k-1 \pmod{N}$
then there exists $e_1 \in \{k+1,-k-1\}$ which $n-k+e_1 \equiv 0 \pmod{N}$
implies either $2k \equiv 0 \pmod{N}$ or $4k+2 \equiv 0 \pmod{N}$
but if $4k+2 \equiv 0 \pmod{N}$ then $n \equiv -2k-1 \equiv 0 \pmod{N}$ which is clearly absurd.
then $2k \equiv 0 \pmod{N}$ or $N \mid k$
We can assume that $k = N$ since we consider only modulo.
Let $n_1$ be number after ${k-3}^{th}$ step, observed that $n-1 \not\equiv 0 \pmod{N}$
Observed that he can choose $x_{k-2} \in \{k-2,-k+2\}$ wisely, to prevent losing in future turn
otherwise, $N \mid 4$ or $N \mid 8$ which is clearly absurd
for case 2 . $e= -k-1$ implies $N \mid k$ which implied same results.
Thus there is no winning strategy for odd $N$
asbodke
20.01.2024 08:44
Tedious. This is also definitely wrong. The answer is as follows: if $N=4$, then $A$ wins; if $N=5$ or $N=6$, $B$ wins; and if $N>6$, then there is no winning strategy for either player. We can rewrite the game so that all additions/subtractions, along with all game states, lie in the set $\{0,1,\dots,n-1\}$. Strategies are in order: if $N=4$, then $A$ plays to $1$. $B$ is forced to move to $3$, after which $A$ can win. if $N=5$, then WLOG $A$ moves to $1$. $B$ goes to $4$, then if $A$ goes to $1$, $B$ easily wins by adding $4$. So $A$ moves to $2$, after which $B$ moves to $1$. $A$ is forced to stay at $1$, after which $B$ easily wins by subtracting $1$. if $N=6$, WLOG $A$ goes to $1$. $B$ goes to $5$, then $A$ is forced to go to $2$. Then $B$ adds $4$ and wins. Now we show that if $N>6$, then no player wins. Note that with optimal play all games must last at least $4$ moves. Suppose that some player wins. Then on the losing player's last move, both adding and subtracting must result in a direct loss. Otherwise, the game will continue and this is not the losing player's last move. There are only $3$ ways this can happen: for any $N$, if the losing player is at either $1$ or $N-1$ and is forced to stay, for even $N$, if the losing player is at either $1$ or $N-1$ and is forced to move by $N/2$, for $N\equiv 2\pmod 4$, if the losing player is at $N/2$ and must move by $(N-2)/4$. We go through these cases in order. Suppose a winning player can win using the first ``method''. Then on the winning player's second to last turn, they must add or subtract $N-1$ and be able to move to either $1$ or $N-1$. That is (since they're obviously not on $0$), they must be on $2$ or $N-2$. So the losing player must be forced to move to $1$, $2$, $N-2$, or $N-1$ by adding or subtracting $N-2$, otherwise they would just move out of this ``trap''. Thus, we have \[ 2(N-2)\equiv -4,-3,-2,-1,0,1,2,3,4\pmod N\implies N=7,8.\] For $N=7$, a detailed analysis is omitted for brevity, but it is noted that an optimal game looks like \[ 0\to 1\to(6\to2\to6\to4\to3\to3\to4),\]where the part in parentheses is looped over and over again with slight variations such as $6\to2\to6\to4\to5\to5\to4$. Note in particular that the push \[ 4\to5\to5\to6\to1\to5\to2\to4\]does not win. When $N=8$, note that in this case the losing player must be at $4$ while about to add or subtract $6$. In particular, the number they are at must be equivalent to \[ \frac{(8k+5)(8k+6)}{2}=(8k+5)(4k+3)\equiv 1\pmod 2,\]so it can't be $4$, contradiction. Now let's look at the second case. Recall that $N$ must be even. The winning player must be at $N/2-2$, $N/2$, or $N/2+2$ by their second to last turn, so the losing player must be unable to avoid $N/2-2$, $N/2-1$, $N/2$, $N/2+1$, or $N/2+2$. That is, \[ N-4\equiv \pm1,\pm 2,\pm3,\pm 4 \pmod N.\]So $N=8$. Note that once again, we require the losing player to move $4$ while being at $1$ or $N-1$, impossible by parity. Our last case requires $N\equiv 2\pmod 4$. The winning player must be at $(N+6)/4$ or $(3N-6)/4$ on their second to last move, so the losing player must be unable to avoid $(N-6)/4$, $(N+6)/4$, $(3N-6)/4$, $(3N+6)/4$ while moving $(N-10)/4$. So \[ \frac{N+6}{4}\equiv \frac{N-10}{4}\pmod N\implies N\mid 16,\]obvious contradiction.