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: ∙ Alice chooses a number a on the blackboard and replaces it with a2 ∙ Bob chooses a number b on the blackboard and replaces it with b3. 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}.