Maths Olympiad Prep

Library / Baltic Way Shortlist /84 of 92

Baltic Way Shortlist

Algebra Difficulty 8.9 Shortlist Prove it Baltic Way

Consider m≥3m \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=∑k∈Mgk. 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 m≠4m \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 m≥5m \ge 5.
Among all possible partitions A⊔B⊔C={1,…,m}A \sqcup B \sqcup C = \{1, \dots, m\} such that
SA≤SB≤SC, S_A \le S_B \le S_C,
select one for which the difference SC−SAS_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 c∈Cc \in C. We have the inequality
SC−SA≤gc≤12SC. S_C - S_A \le g_c \le \frac{1}{2}S_C.
The first is by the minimality of SC−SAS_C - S_A, the second by the minimality of gcg_c. These two inequalities together yield
SA+SB≥2SA≥2(SC−gc)≥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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.