Maths Olympiad Prep

Library / /15 of 299

Combinatorics Difficulty 5.4 AIME, harder Prove it Iran

There is a sequence of nn distinct positive integers. Prove that these numbers can be fixed on a circle such that the sum of any two adjacent numbers is different from the other sums.

Solution

Without loss of generality assume that a1<a2<<ana_1 < a_2 < \dots < a_n. Consider these numbers on a circle, in the ascending order. All sums, other than a1+ana_1 + a_n can be ordered as
a1+a2<a2+a3<<an2+an1<an1+an a_1 + a_2 < a_2 + a_3 < \dots < a_{n-2} + a_{n-1} < a_{n-1} + a_n
We're done if there's no two sums that are equal. But if there is, the only sum that can be equal to another one is a1+ana_1 + a_n so we would have a1+an=ai1+aia_1 + a_n = a_{i-1} + a_i for some 1<i<n1 < i < n. Now let's replace aia_i and ai+1a_{i+1}.

an+a1=ai1+ai<ai1+ai+1<ai+1+ai<ai+2+ai. a_n + a_1 = a_{i-1} + a_i < a_{i-1} + a_{i+1} < a_{i+1} + a_i < a_{i+2} + a_i.
So the new sums can be ordered as
a1+a2<a2+a3<<ai2+ai1<an+a1<ai1+ai+1<ai+1+ai<<an1+an. a_1 + a_2 < a_2 + a_3 < \dots < a_{i-2} + a_{i-1} < a_n + a_1 < a_{i-1} + a_{i+1} < a_{i+1} + a_i < \dots < a_{n-1} + a_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.