Maths Olympiad Prep

Library / /29 of 31

Algebra Difficulty 8.9 Shortlist Prove it 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.

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.

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.