Maths Olympiad Prep

Track / Stage 6 / 131 of 400 #1131 of 1964

Problem 1131

National Olympiad, first round
Combinatorics Difficulty 6.1 Prove it Iranian Mathematical Olympiad · Iran

Suppose that there are nn distinct real numbers on the board. We write all pairwise differences of these numbers and clear all the previous numbers. Prove that if nn is odd, it is possible to divide these (n2)\binom{n}{2} obtained numbers into two sets with equal sum.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Let nn be an odd number and a1<a2<<ana_1 < a_2 < \dots < a_n be the given real numbers. Put aiaja_i - a_j (where i>ji > j) into the first set if ii and jj have the same parity and put them into the second set if they have different parity. We claim that

the coefficient of aia_i's in both sets are the same. Suppose ii is even (the second case is similar). The first set contains the elements
an1ai,an3ai,,ai+2ai,aiai2,aiai4,,aia2, a_{n-1} - a_i, a_{n-3} - a_i, \dots, a_{i+2} - a_i, a_i - a_{i-2}, a_i - a_{i-4}, \dots, a_i - a_2,
that have aia_i appeared in them. Thus the coefficient of aia_i in the first set is
i22ni12=2in12 \frac{i-2}{2} - \frac{n-i-1}{2} = \frac{2i-n-1}{2}
Similarly, the second set contains the elements
anai,an2ai,,ai+1ai,aiai1,aiai3,,aia1 a_n - a_i, a_{n-2} - a_i, \dots, a_{i+1} - a_i, a_i - a_{i-1}, a_i - a_{i-3}, \dots, a_i - a_1
that also have aia_i appeared in them. So the coefficient of aia_i in the second set is
i2ni+12=2in12, \frac{i}{2} - \frac{n-i+1}{2} = \frac{2i-n-1}{2},
Hence aia_i's coefficient in all member's sum of both sets are same and we are done. ■

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