Browse · MathNet
PrintEstonian Math Competitions
Estonia counting and probability
Problem
Natural numbers through are written on a blackboard. On each move, one erases from the blackboard or more numbers whose sum is divisible by any of the chosen numbers and writes their sum on the blackboard. Two players make moves by turns and the player who cannot move loses the game. Which player can win the game against any play by the opponent, if:
a. ;
b. ?
a. ;
b. ?
Solution
a. The first player can replace numbers , , , with . After that, the blackboard contains numbers , , . In this state, the sum of no two or three numbers on the blackboard is divisible by all the added numbers. Thus the second player cannot move and the first player wins immediately.
b. The first player can replace numbers , , , , , with . After that, the blackboard contains numbers , , , , , , which sum up to . Among numbers , , , , , the l.c.m. of any two numbers is greater than . Thus when choosing two or more numbers from among the mentioned numbers, and perhaps also the number , the sum of the chosen numbers is less than their l.c.m. and cannot be divisible by all of them. Also when choosing one of the mentioned numbers together with , the sum of the chosen numbers is not divisible by the larger one. Hence the second player cannot move and the first player wins immediately.
b. The first player can replace numbers , , , , , with . After that, the blackboard contains numbers , , , , , , which sum up to . Among numbers , , , , , the l.c.m. of any two numbers is greater than . Thus when choosing two or more numbers from among the mentioned numbers, and perhaps also the number , the sum of the chosen numbers is less than their l.c.m. and cannot be divisible by all of them. Also when choosing one of the mentioned numbers together with , the sum of the chosen numbers is not divisible by the larger one. Hence the second player cannot move and the first player wins immediately.
Final answer
a: first player; b: first player
Techniques
Games / greedy algorithmsInvariants / monovariantsLeast common multiples (lcm)