2008 iTest Problems/Problem 72
Problem
On the last afternoon of the Kubik family vacation, Michael puts down a copy of and goes out to play tennis. Wendy notices the book and decides to see if there are a few problems in it that she can solve. She decides to focus her energy on one problem in particular:
Given 69 distinct positive integers not exceeding 100, prove that one can choose four of them such that and . Is this statement true for 68 numbers?
After some time working on the problem, Wendy finally feels like she has a grip on the solution. When Michael returns, she explains her solutions to him. "Well done!" he tells her. "Now, see if you can solve this generalization. Consider the set . Find the smallest value of such that given any subset of where , then there are necessarily distinct for which ." Find the answer to Michael's generalization.
Solution
The statement is FALSE for . The set contains positive integers and the sum of any three is at least 33+34+35=102>100. So given any four, the sum of a subset of three exceeds the possible value for the fourth.
The assertion is TRUE for . The proof is as follows:
let be the minimum and be the maximum and the set is thus missing the terms and we have 2 cases:
case 1 : is even
we have the following potential solutions for the statement:
for the set not to contain an solution, it must be missing either the or term (or both) in each of the above equations. The number of equations above is which must satisfy . This implies .
Thus the total number of missing values from the set S is at least the size of the missing beginning terms plus the size of the missing ending terms plus the terms missing in the above equations. This simplifies to .
If the set contains terms, then and which implies (or more) terms are missing which contradicts the assumption that only terms are missing.
case 2 : is odd
we have the following potential solutions for the statement:
for the set not to contain an a+b+c=d solution, it must be missing either the or the term (or both) in each of the above equations. The number of equations above is which must satisfy . This implies .
Thus the total number of missing values from the set S is at least the size of the missing beginning terms plus the size of the missing ending terms plus the terms missing in the above equations. This simplifies to .
If the set contains 68 terms, then and which is possible if and
For the case we find that the set has elements any three of which sum to at least
But for missing terms, we see from the argument above that the assumption of no solutions leads to at least 669 missing terms - a contradiction.