|
|
|
|
|
|
|
|
|
 The proof is by William A McWorter Jr.. Induction on n. Brute force shows that the result is true for n=4 and n=5. Assume the result for n>4. If (n+1) is odd, then the greatest integer in (n+1+2)/2 is (n/2+1). If the more than (n/2+1) selected integers don't contain (n+1), then the result follows because we've assumed the result holds for n. Otherwise, the selected set contains (n+1). Form the n/2 pairs {a,n+1-a}, for a=1,...,n/2. Then some two of the remaining at least (n/2+1) selected integers belong to one pair. Those two sum to (n+1), one of the selected integers. If (n+1) is even, then the greatest integer in (n+1+2)/2 is (n+3)/2. Hence, if more than (n+3)/2 integers are selected, more than (n+1)/2 must be selected from {1,2,...,n}. By induction, some three of those selected from {1,2,...,n} must contain three with the property that one is the sum of the other two. Here is another proof. Let m be the largest integer in (n+2)/2 and let x be the smallest of the m+1 selected integers. Form the m differences between x and the other selected integers. We claim that one of these m differences is a selected integer other than x, thus showing that some selected integer is the sum of two other selected integers. To see this, the differences are, of course, between 1 and n. There are n-(m+1) unselected integers plus the integer x. That's n-m integers. But m>n-m because 2m>n. Hence one of the differences must be a selected integer other than x.
|
| 30746477 |  |
|