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) digits ; b) digits ?
Solution
a) Let us show that Vasyl' can achieve the situation that after each his move, the board contains some odd number and numbers . Then, after pairs of moves, only number 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 and writes down number . Vasyl' makes number . If at some point an odd number is written on the board, and numbers , then Petryk can either erase two and write , after which Vasyl' erases and and writes , or he exchanges and for , after which Vasyl' erases and and writes , 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: , , and . If Petryk leaves the numbers , and , then Vasyl' turns it into and , and Petryk cannot make a move. If Petryk leaves the numbers , and , then Vasyl' again turns it into and , and Petryk cannot make a move.