Maths Olympiad Prep

Library / Argentina competition problems /13 of 20

Argentina competition problems

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 [1810−d,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 17⋅98+2⋅96=1858>181017 \cdot 98 + 2 \cdot 96 = 1858 > 1810, so α\alpha is admissible. Note that α\alpha has exactly two subsequence sums in the interval [1810−48,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 S≥1859S \ge 1859 and T≤1761T \le 1761 for every proper subsequence sum TT. In particular, if tt is any term of β\beta then S−t≤1761S-t \le 1761. Hence the inequalities S≥1859S \ge 1859 and S−t≤1761S-t \le 1761 imply t≥1859−1761=98t \ge 1859-1761=98. Each admissible sequence has at least 1919 terms (having sum >1810> 1810 and terms ≤100\le 100). Therefore S≥98⋅19=1862S \ge 98 \cdot 19 = 1862.

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

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.