Maths Olympiad Prep

Track / Stage 8 / 177 of 180 #1877 of 1964

Problem 1877

IMO Shortlist mid-range; USAMO P2/P5
Algebra Difficulty 8.9 Prove it Baltic Way shortlist · Baltic Way

Consider m3m \ge 3 positive real numbers g1,,gmg_1, \dots, g_m, each number being less than the sum of the others. For any subset M{1,,m}M \subseteq \{1, \dots, m\}, denote
SM=kMgk. S_M = \sum_{k \in M} g_k.
Find all mm for which it is always possible to partition the indices 1,,m1, \dots, m into three sets A,B,CA, B, C, with the property that
SA<SB+SC,SB<SA+SCandSC<SA+SB. S_A < S_B + S_C, \quad S_B < S_A + S_C \quad \text{and} \quad S_C < S_A + S_B.

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.

Official solution

Answer: The partition is always possible precisely when m4m \ne 4.
For m=3m = 3 it is trivially possible, and for m=4m = 4 the four equal numbers g,g,g,gg, g, g, g provide a counter-example. Henceforth, we assume m5m \ge 5.
Among all possible partitions ABC={1,,m}A \sqcup B \sqcup C = \{1, \dots, m\} such that
SASBSC, S_A \le S_B \le S_C,
select one for which the difference SCSAS_C - S_A is minimal. If there are several such, select one so as to maximise the number of elements in CC. We will show that SC<SA+SBS_C < S_A + S_B, which is clearly sufficient.
If CC consists of a single element, this number is by assumption less than the sum of the remaining ones, hence SC<SA+SBS_C < S_A + S_B holds true.
Suppose now CC contains at least two elements, and let gcg_c be a minimal number indexed by a cCc \in C. We have the inequality
SCSAgc12SC. S_C - S_A \le g_c \le \frac{1}{2}S_C.
The first is by the minimality of SCSAS_C - S_A, the second by the minimality of gcg_c. These two inequalities together yield
SA+SB2SA2(SCgc)SC. S_A + S_B \ge 2S_A \ge 2(S_C - g_c) \ge S_C.
If either of these inequalities is strict, we are finished.
Hence suppose all inequalities are in fact equalities, so that
SA=SB=12SC=gc. S_A = S_B = \frac{1}{2}S_C = g_c.
It follows that C={c,d}C = \{c, d\}, where gd=gcg_d = g_c. If AA contained more than one element, we could increase the number of elements in CC by creating instead a partition
{1,,m}={c}B(A{d}), \{1, \dots, m\} = \{c\} \sqcup B \sqcup (A \cup \{d\}),
resulting in the same sums. A similar procedure applies to BB. Consequently, AA and BB must be singleton sets, whence
m=A+B+C=4. m = |A| + |B| + |C| = 4.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.