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
01.06.2021 05:11
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
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}$.