Maths Olympiad Prep

Library / USA Tstst /18 of 33

USA Tstst

Algebra Difficulty 7.0 National Olympiad Prove it United States

Consider coins with positive real denominations not exceeding 11. Find the smallest C>0C > 0 such that the following holds: if we are given any 100100 such coins with total value 5050, then we can always split them into two stacks of 5050 coins each such that the absolute difference between the total values of the two stacks is at most CC.

Solution

The answer is C=5051C = \frac{50}{51}. The lower bound is obtained if we have 5151 coins of value 151\frac{1}{51} and 4949 coins of value 11. We now present two (similar) proofs that this C=5051C = \frac{50}{51} suffices.

First proof (original) Let a1≤⋯≤a100a_1 \le \dots \le a_{100} denote the values of the coins in ascending order. Since the 5151 coins a50,…,a100a_{50}, \dots, a_{100} are worth at least 51a5051a_{50}, it follows that a50≤5051a_{50} \le \frac{50}{51}; likewise a51≥151a_{51} \ge \frac{1}{51}.
We claim that choosing the stacks with coin values
a1,a3,…,a49,a52,a54,…,a100 a_1, a_3, \dots, a_{49}, a_{52}, a_{54}, \dots, a_{100}
and
a2,a4,…,a50,a51,a53,…,a99 a_2, a_4, \dots, a_{50}, a_{51}, a_{53}, \dots, a_{99}
works. Let DD denote the (possibly negative) difference between the two total values. Then
D=(a1−a2)+⋯+(a49−a50)−a51+(a52−a53)+⋯+(a98−a99)+a100≤25⋅0−151+24⋅0+1=5051. \begin{aligned} D &= (a_1 - a_2) + \dots + (a_{49} - a_{50}) - a_{51} + (a_{52} - a_{53}) + \dots + (a_{98} - a_{99}) + a_{100} \\ &\le 25 \cdot 0 - \frac{1}{51} + 24 \cdot 0 + 1 = \frac{50}{51}. \end{aligned}
Similarly, we have
D=a1+(a3−a2)+⋯+(a49−a48)−a50+(a52−a51)+⋯+(a100−a99)≥0+24⋅0−5051+25⋅0=−5051. \begin{aligned} D &= a_1 + (a_3 - a_2) + \dots + (a_{49} - a_{48}) - a_{50} + (a_{52} - a_{51}) + \dots + (a_{100} - a_{99}) \\ &\ge 0 + 24 \cdot 0 - \frac{50}{51} + 25 \cdot 0 = -\frac{50}{51}. \end{aligned}
It follows that ∣D∣≤5051|D| \le \frac{50}{51}, as required.

Second proof (Evan Chen) Again we sort the coins in increasing order 0<a1≤a2≤⋯≤a100≤10 < a_1 \le a_2 \le \dots \le a_{100} \le 1. A large gap is an index i≥2i \ge 2 such that ai>ai−1+5051a_i > a_{i-1} + \frac{50}{51}; obviously there is at most one such large gap.
Claim — If there is a large gap, it must be a51>a50+5051a_{51} > a_{50} + \frac{50}{51}.
Proof. If i<50i < 50 then we get a50,…,a100>5051a_{50}, \dots, a_{100} > \frac{50}{51} and the sum ∑1100ai>50\sum_{1}^{100} a_i > 50 is too large. Conversely if i>50i > 50 then we get a1,…,ai−1<151a_1, \dots, a_{i-1} < \frac{1}{51} and the sum ∑1100ai<1/51⋅51+49\sum_{1}^{100} a_i < 1/51 \cdot 51 + 49 is too small. □\square
Now imagine starting with the coins a1,a3,…,a99a_1, a_3, \dots, a_{99}, which have total value S≤25S \le 25. We replace a1a_1 by a2a_2, then a3a_3 by a4a_4, and so on, until we replace a99a_{99} by a100a_{100}. At the end of the process we have S≥25S \ge 25. Moreover, since we did not cross a large gap at any point, the quantity SS changed by at most C=5051C = \frac{50}{51} at each step. So at some point in the process we need to have 25−C/2≤S≤25+C/225 - C/2 \le S \le 25 + C/2, which proves CC works.

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.