Olympiad Maths Prep

Track / Stage 5 / 306 of 400 #906 of 2000

Problem 906

AIME late
Combinatorics Difficulty 5.7 Prove it

3. Let AA be a finite set of real numbers, and A1,A2,,AnA_{1}, A_{2}, \cdots, A_{n} be non-empty subsets of AA, satisfying:
(1) The sum of all elements in AA is 0;
(2) For any xiAi(i=1,2,,n)x_{i} \in A_{i} (i=1,2, \cdots, n), we have x1+x2++xn>0x_{1}+x_{2}+\cdots+x_{n}>0.
Prove: There exist 1i1<i2<<ikn1 \leqslant i_{1}<i_{2}<\cdots<i_{k} \leqslant n, such that Ai1Ai2Aik<knA\left|A_{i_{1}} \cup A_{i_{2}} \cup \cdots \cup A_{i_{k}}\right|<\frac{k}{n}|A|,

where X|X| denotes the number of elements in the finite set XX.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

3. Let A={a1,a2,,am},a1>a2>>amA=\left\{a_{1}, a_{2}, \cdots, a_{m}\right\}, a_{1}>a_{2}>\cdots>a_{m}. Then, by condition (1), we have
a1+a2++am=0. a_{1}+a_{2}+\cdots+a_{m}=0 .

Consider the smallest number in each AiA_{i}, and let A1,A2A_{1}, A_{2}, ,An\cdots, A_{n} contain exactly kik_{i} sets whose smallest number is ai(i=1a_{i}(i=1, 2,,m2, \cdots, m ).
Thus, i=1mki=n\sum_{i=1}^{m} k_{i}=n, and by condition (2) we have
j=1mkjaj>0 \sum_{j=1}^{m} k_{j} a_{j}>0 \text {. }

For s(1sm1)s(1 \leqslant s \leqslant m-1), there are i=13ki\sum_{i=1}^{3} k_{i} sets, all of whose smallest numbers are greater than or equal to axa_{x}. Therefore, the union of these sets is contained in {a1,,a3}\left\{a_{1}, \cdots, a_{3}\right\}, and the number of elements is at most ss.
Next, we prove by contradiction:
There exists s(1sm1)s(1 \leqslant s \leqslant m-1), such that
k=i=1ski>snm. k=\sum_{i=1}^{s} k_{i}>\frac{s n}{m} .

Assume that for s(1sm1)s(1 \leqslant s \leqslant m-1), we have
i=13kisnm \sum_{i=1}^{3} k_{i} \leqslant \frac{s n}{m} \text {. }

By Abel's transformation (note that a1a1+1>0a_{1}-a_{1+1}>0, 1sm11 \leqslant s \leqslant m-1 )
\begin{aligned} 0 & \frac{s n}{m}

There are kk sets, and the union of these sets has at most ss elements, i.e.,
Ai1Ai2Aiks<kmn=knA. \left|A_{i_{1}} \cup A_{i_{2}} \cup \cdots \cup A_{i_{k}}\right| \leqslant s<\frac{k m}{n}=\frac{k}{n}|A| .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.