Library / Ukrainian National Mathematical Olympiad /152 of 201

Ukrainian National Mathematical Olympiad

Number theory Difficulty 6.5 National Olympiad Prove it Ukraine

There are numbers $1, 2, 3, \ldots, 100$ on the board. Each is written exactly once. Petryk and Ivasyk are playing in the following game (Petryk starts): each player erases one number from the board. If after player's turn the sum of all erased numbers (by both players) cannot be represented as a difference of squares of integers, the player loses. Who will win in this game if both players want to win?

Solution

Notice that $n$ cannot be represented as a difference of squares of integers iff $n \equiv 2 \pmod{4}$ . Indeed, if $n \equiv 2 \pmod{4}$ , then suppose $n = (x + y)(x - y)$ . If $x, y$ are either both odd or both even, then $n \equiv 0 \pmod{4}$ , otherwise $n \equiv \pm 1 \pmod{4}$ . If $n = 4k$ , then let $x = k + 1, y = k - 1$ , if $n \equiv \pm 1 \pmod{4}$ , then let $x = \frac{n+1}{2}, y = \frac{n-1}{2}$ .

The strategy for Petryk is the following: he erases $100$ first, then if Ivasyk chooses $m$ , then Petryk erases $100-m$ . Since choice of number $50$ leads to loss, then Petryk wins, because if Ivasyk hasn't lost yet then Petryk has a number to erase that will not make him lose.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.