Browse · MathNet
PrintArgentina_2018
Argentina 2018 counting and probability
Problem
A sequence of natural numbers is admissible if its terms are less or equal to and its sum is greater than . Find the least such that each admissible sequence has a subsequence sum in the interval .
Solution
Consider the sequence with terms equal to and terms equal to . Its sum is , so is admissible. Note that has exactly two subsequence sums in the interval . They are its extremes: the sum of the entire sequence and , the sum of all terms except one . This example shows that the minimum in question is at least .
We show that each admissible sequence has a subsequence sum in the interval , implying that the answer is . Suppose on the contrary that this is false for an admissible sequence . Still more is it false for any subsequence of . So by possibly removing terms one may assume that is minimal, with sum but with sum of each proper subsequence. In fact the assumption then implies and for every proper subsequence sum . In particular, if is any term of then . Hence the inequalities and imply . Each admissible sequence has at least terms (having sum and terms ). Therefore .
On the other hand, we proved the inequality for any term . Since by hypothesis, it follows that , which yields a contradiction.
We show that each admissible sequence has a subsequence sum in the interval , implying that the answer is . Suppose on the contrary that this is false for an admissible sequence . Still more is it false for any subsequence of . So by possibly removing terms one may assume that is minimal, with sum but with sum of each proper subsequence. In fact the assumption then implies and for every proper subsequence sum . In particular, if is any term of then . Hence the inequalities and imply . Each admissible sequence has at least terms (having sum and terms ). Therefore .
On the other hand, we proved the inequality for any term . Since by hypothesis, it follows that , which yields a contradiction.
Final answer
48
Techniques
Coloring schemes, extremal arguments