Maths Olympiad Prep

Library / /11 of 17

Combinatorics Difficulty 6.0 AIME, harder Prove it Argentina

A sequence of natural numbers is admissible if its terms are less or equal to 100100 and its sum is greater than 18101810. Find the least dd such that each admissible sequence has a subsequence sum in the interval [1810d,1810+d][1810-d, 1810+d].

Solution

Consider the sequence α\alpha with 1717 terms equal to 9898 and 22 terms equal to 9696. Its sum is 1798+296=1858>181017 \cdot 98 + 2 \cdot 96 = 1858 > 1810, so α\alpha is admissible. Note that α\alpha has exactly two subsequence sums in the interval [181048,1810+48]=[1762,1858][1810-48, 1810+48] = [1762, 1858]. They are its extremes: 18581858 the sum of the entire sequence and 17621762, the sum of all terms except one 9696. This example shows that the minimum dd in question is at least 4848.

We show that each admissible sequence has a subsequence sum in the interval [1762,1858][1762,1858], implying that the answer is dmin=48d_{\min} = 48. Suppose on the contrary that this is false for an admissible sequence β\beta. Still more is it false for any subsequence of β\beta. So by possibly removing terms one may assume that β\beta is minimal, with sum S>1810S > 1810 but with sum 1810\le 1810 of each proper subsequence. In fact the assumption then implies S1859S \ge 1859 and T1761T \le 1761 for every proper subsequence sum TT. In particular, if tt is any term of β\beta then St1761S-t \le 1761. Hence the inequalities S1859S \ge 1859 and St1761S-t \le 1761 imply t18591761=98t \ge 1859-1761=98. Each admissible sequence has at least 1919 terms (having sum >1810> 1810 and terms 100\le 100). Therefore S9819=1862S \ge 98 \cdot 19 = 1862.

On the other hand, we proved the inequality St1761S-t \le 1761 for any term tt. Since t100t \le 100 by hypothesis, it follows that S1761+100=1861S \le 1761+100=1861, which yields a contradiction.

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.