Maths Olympiad Prep

Library / /205 of 220

Combinatorics Difficulty 7.4 National Olympiad, round 2 Prove it Ukraine

Petryk and Vasyl' are playing a game with the numbers written on the board. In a single one move – Petryk goes first – the player chooses two co-prime numbers out of the ones written on the board, erases them, and writes down their sum instead. The one who can't make the move loses. Who will win if both players play correctly and if the numbers written initially are:
a) 20192019 digits 11; b) 20202020 digits 11?

Solution

a) Let us show that Vasyl' can achieve the situation that after each his move, the board contains some odd number nn and 2019n2019-n numbers 11. Then, after 10091009 pairs of moves, only number 20192019 remains on the board, and Petryk will not be able to make a move and will lose. As his first move, Petryk wipes two numbers 11 and writes down number 22. Vasyl' makes number 33. If at some point an odd number nn is written on the board, and 2019n2019-n numbers 11, then Petryk can either erase two 11 and write 22, after which Vasyl' erases nn and 22 and writes n+2n+2, or he exchanges nn and 11 for n+1n+1, after which Vasyl' erases n+1n+1 and 11 and writes n+2n+2, and wins.

b) Here Vasyl' follows a strategy similar to a) except for the last move. Before the last move of Petryk, four numbers are written on the board: 20172017, 11, 11 and 11. If Petryk leaves the numbers 20182018, 11 and 11, then Vasyl' turns it into 20182018 and 22, and Petryk cannot make a move. If Petryk leaves the numbers 20172017, 22 and 11, then Vasyl' again turns it into 20182018 and 22, and Petryk cannot make a move.

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

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