Maths Olympiad Prep

Library / /27 of 92

Combinatorics Difficulty 6.1 National olympiad Prove it 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.

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. ■

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.