Competition problem — Combinatorics

Library / /84 of 86

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Estonia

Natural numbers $1$ through $n$ are written on a blackboard. On each move, one erases from the blackboard $2$ 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. $n = 6$ ;

b. $n = 11$ ?

Solution

a. The first player can replace numbers $1$ , $2$ , $3$ , $6$ with $12$ . After that, the blackboard contains numbers $4$ , $5$ , $12$ . 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 $1$ , $2$ , $3$ , $4$ , $6$ , $8$ with $24$ . After that, the blackboard contains numbers $5$ , $7$ , $9$ , $10$ , $11$ , $24$ , which sum up to $66$ . Among numbers $7$ , $9$ , $10$ , $11$ , $24$ , the l.c.m. of any two numbers is greater than $66$ . Thus when choosing two or more numbers from among the mentioned numbers, and perhaps also the number $5$ , 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 $5$ , 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.

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 and solution reproduced as published; topic and difficulty added by this site.