Maths Olympiad Prep

Library / Croatia Mathematical Competitions /21 of 25

Croatia Mathematical Competitions

Combinatorics Difficulty 6.6 National Olympiad Prove it Croatia

The first nn positive integers are written on a board (n≥3n \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, ..., 4k−34k-3 and 4k−14k-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 n−2n-2, 44 and 44 by n−4n-4, ..., n−2n-2 and n−2n-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, ..., n−2n-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 3n−12\frac{3n-1}{2}. Finally, he increases 22 and 22 by 3n−52\frac{3n-5}{2}, 44 and 44 by 3n−92\frac{3n-9}{2}, ..., n−1n-1 and n−1n-1 by n+12\frac{n+1}{2}. Now all numbers on the board are equal to 3n−12\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, k∈Nk \in \mathbb{N}.

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

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