Maths Olympiad Prep

Library / /22 of 27

Combinatorics Difficulty 6.6 National Olympiad Prove it Croatia

The first nn positive integers are written on a board (n3n \ge 3). Ante repeats the following procedure: first he chooses two numbers on the board, and then he increases them both by the same arbitrary positive integer.
Determine all positive integers nn such that Ante can, by repeating this procedure, achieve that all numbers on the board are equal.
(Ilko Brnetić)

Solution

Assume n=4kn = 4k. Then Ante can achieve that all numbers on the board are equal in the following way: he will increase by 11 the numbers 11 and 33, 55 and 77, ..., 4k34k-3 and 4k14k-1. By doing that, he gets that the numbers on the board are all even numbers smaller than or equal to nn, and each is written twice. Finally, he increases 22 and 22 by n2n-2, 44 and 44 by n4n-4, ..., n2n-2 and n2n-2 by 22, and he gets that all numbers on the board are equal to nn.

Assume n=2k+1n = 2k+1. Then Ante can achieve that all numbers on the board are equal in the following way: he will increase by 11 the numbers 11 and nn, 33 and nn, ..., n2n-2 and nn. By doing that, he gets that the numbers on the board are all even numbers smaller than or equal to nn, each written twice, and the number 3n12\frac{3n-1}{2}. Finally, he increases 22 and 22 by 3n52\frac{3n-5}{2}, 44 and 44 by 3n92\frac{3n-9}{2}, ..., n1n-1 and n1n-1 by n+12\frac{n+1}{2}. Now all numbers on the board are equal to 3n12\frac{3n-1}{2}.

Assume n=4k+2n = 4k + 2. Then Ante cannot achieve that all numbers are equal. The sum of all numbers on the board is initially odd, because
1+2++n=n(n+1)2=(2k+1)(4k+3). 1 + 2 + \dots + n = \frac{n(n+1)}{2} = (2k+1)(4k+3).
Since there is an even number of numbers on the board, if they were equal their sum would be an even number. On the other hand, in each step the sum of numbers on the board is increased by an even number, so the sum will never be even.

Therefore, Ante can achieve that all numbers are equal if and only if nn is not of the form 4k+24k + 2, kNk \in \mathbb{N}.

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.