AoPS - Problem

Source: Austrian MO 2024, Final Round P3

Tags: game, game strategy, winning strategy, combinatorics, combinatorics proposed

Tintarn

01.06.2024 15:26

Initially, the numbers $1, 2, \dots, 2024$ are written on a blackboard. Trixi and Nana play a game, taking alternate turns. Trixi plays first. The player whose turn it is chooses two numbers $a$ and $b$, erases both, and writes their (possibly negative) difference $a-b$ on the blackboard. This is repeated until only one number remains on the blackboard after $2023$ moves. Trixi wins if this number is divisible by $3$, otherwise Nana wins. Which of the two has a winning strategy? (Birgit Vera Schmidt)

Answer: Nana Notice we only care about how many numbers fall into each residue class $\pmod{3}$ namely $(674,675,675)$. We show that Nana can ensure that on each turn at exactly two of the residues contain an odd number of elements each time she hands her turn over. It is not hard to show that if their are two odd elements then Trixi will have to hand over at least one odd element. If all three elements are odd then Nana can make any move if exactly one element is odd then Nana can take the difference of two elements belonging to the other piles. Clearly when Nana hands over the final two numbers she has won.