Maths Olympiad Prep

Library / /52 of 299

Combinatorics Difficulty 5.8 AIME, harder Prove it Iran

2n12n-1 distinct positive real numbers with sum SS are given. Prove that there are at least (2n2n1)\binom{2n-2}{n-1} nn-tuples among these numbers such that the sum of each nn-tuple is at least S2\frac{S}{2}.

Solution

Let's place these 2n12n-1 numbers around a circle and label them by π(1),π(2),,π(2n1)\pi(1), \pi(2), \dots, \pi(2n-1) respectively and let
Si=π(i)+π(i+1)++π(i+n1),i2n1 S_i = \pi(i) + \pi(i+1) + \dots + \pi(i + n - 1), \quad i \le 2n-1
(Numbers are considered modulo 2n12n-1.) We claim that at least nn of SiS_i's have a value not less than S2\frac{S}{2}.

Assume the contrary which means at least nn of these SiS_i's have a value less than S2\frac{S}{2}. Let the indices of these SiS_i's be i1,i2,,ini_1, i_2, \dots, i_n. Note that, by the pigeonhole principle there are two indices is,iti_s, i_t such that
itis2n1n i_t - i_s \stackrel{2n-1}{\equiv} n
(Because there is a total of n1n-1 sets of the form of {i,i+n}\{i, i+n\} (mod 2n12n-1), and we have chosen nn indices, each one exists in a set.) So we can get
S2×2>Sis+Sit=π(is)+π(is+1)++π(is+n1)+π(it)+π(it+1)++π(it+n1)=π(1)+π(2)++π(2n1)+π(is)>S \begin{align*} \frac{S}{2} \times 2 > S_{i_s} + S_{i_t} &= \pi(i_s) + \pi(i_s + 1) + \dots + \pi(i_s + n - 1) \\ &\quad + \pi(i_t) + \pi(i_t + 1) + \dots + \pi(i_t + n - 1) \\ &= \pi(1) + \pi(2) + \dots + \pi(2n - 1) + \pi(i_s) > S \end{align*}
Which is a contradiction. Hence the claim.

Now there is a total of (2n2)!(2n-2)! ways to place these numbers around the circle. Also according to the claim, in each permutation we have at least nn sums satisfying the condition. Each sum exists in n!×(n1)!n! \times (n-1)! permutations. So there's a total of at least
(2n2)!×nn!×(n1)!=(2n2n1) \frac{(2n-2)! \times n}{n! \times (n-1)!} = \binom{2n-2}{n-1}
ways to choose an nn-tuple with sum greater or equal to S2\frac{S}{2}.

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.