Show that, given any subset A of more than 1+½n numbers from the set {1,...,n}, for some three of the given numbers, one is the sum of the other two.

Lower half: numbers below (½n, rounded up)<o:p></o:p>

Upper half: numbers including and above (½n, rounded up)<o:p></o:p>

first show that if in subset A there are m numbers in lower half then at least m-1 numbers cannot exist in upper half.<o:p></o:p>

this is shown by: let's choose one number out of these m numbers which leaves m-1 numbers left......since these m numbers are all unique and in lower half....adding the chosen number with any of the m-1 numbers will give a unique number that exist in the upper half. Since there will be m-1 pairs with the chosen number, m-1 numbers cannot exist in the upper half. <o:p></o:p>

Thus if in A there exists more than m numbers in lower half, there will m-1 numbers that cannot be chosen from upper half. This means that after the first number is chosen from the lower half, each subsequent number from lower half will restrict us at least 1 number from upper half. Thus in order to maximize the amount of numbers chosen before a number is the sum of 2 other numbers, we can choose as many upper half numbers. <o:p></o:p>

Having this in mind, 1+(½n,rounded down) numbers are chosen and are all as high as possible.....which means if n is 4 the numbers chosen are 2,3,4 and if n is 5 the numbers are 3,4,5. As you will notice any of these numbers are not the sum of any other two numbers. However, if one more number is chosen it must come from the lower half. This number when added to (½n, rounded up), will yield a number that already exists. <o:p></o:p>

Thus the maximum possible amount in A such that any number is not a sum of any 2 numbers is 1+(½n,rounded down). This implies that above 1+½n numbers chosen, one number is the sum of the other two numbers.

Posted by leoj on 2005-07-31 18:59:51