Maths Olympiad Prep

Library / /19 of 34

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 a1a100a_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 a505051a_{50} \le \frac{50}{51}; likewise a51151a_{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=(a1a2)++(a49a50)a51+(a52a53)++(a98a99)+a100250151+240+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+(a3a2)++(a49a48)a50+(a52a51)++(a100a99)0+2405051+250=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 D5051|D| \le \frac{50}{51}, as required.

Second proof (Evan Chen) Again we sort the coins in increasing order 0<a1a2a10010 < a_1 \le a_2 \le \dots \le a_{100} \le 1. A large gap is an index i2i \ge 2 such that ai>ai1+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,,ai1<151a_1, \dots, a_{i-1} < \frac{1}{51} and the sum 1100ai<1/5151+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 S25S \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 S25S \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 25C/2S25+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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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