On a blackboard, there are $17$ integers not divisible by $17$. Alice and Bob play a game. Alice starts and they alternately play the following moves: $\bullet$ Alice chooses a number $a$ on the blackboard and replaces it with $a^2$ $\bullet$ Bob chooses a number $b$ on the blackboard and replaces it with $b^3$. Alice wins if the sum of the numbers on the blackboard is a multiple of $17$ after a finite number of steps. Prove that Alice has a winning strategy. (Daniel Holmes)
Problem
Source: 2021 Austrian Federal Competition For Advanced Students, Part 1 p4
Tags: game, combinatorics, game strategy
leibnitz
01.06.2021 05:11
Alice chooses the first number on the board $\not\equiv1\pmod{17}$ and squares it continuously until it becomes $1\pmod{17}$ regardless of what Bob does and then moves on to the next number $\not\equiv1\pmod{17}$ and repeats this until she has done this to all numbers $\not\equiv1\pmod{17}$ on the board.
proofNote that the Quadratic residues of 17 form the set $\pm1,\pm2\pm4\pm8$ so if Alice keeps squaring a number it will eventually be $1\pmod{17}$ moreover note that if Bob cubes a number which Alice squared in the previous move then since the residues of $n^6$ form the exact same set $\pm1,\pm2\pm4\pm8$ Bob can do nothing to stop Alice from making a number $1\pmod{17}$ (in the next move of Alice that number has to be $\pm1\pm4\pmod{17}$ so we can guarantee it) hence making the sum of all numbers divisible by 17.
Mahan2006
25.12.2021 20:50
We can say that if now the sum of them has a remaining like r that is not r: 1)In this condition first player will win:Well first player win win 2)The second player will win: Well first player can make first number to be 1(mod 17) by squaring it
megarnie
26.07.2024 15:58
We claim that if there is a number that isn't $1\pmod{17}$, Alice can make a finite number of moves to make the number of numbers on the board equal to $1\pmod{17}$ increase. Suppose the number is $x$. Let Alice make $4$ moves on $x$. Suppose Bob makes $k$ moves on $x$. Then $x$ will become $x^{2^4 \cdot 3^k} \equiv 1\pmod{17}$. Notice that anything $1\pmod{17}$ on the board must stay $1\pmod{17}$, so thus the number of numbers $1\pmod{17}$ will increase. Now just repeatedly do this until everything is $1\pmod{17}$.