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.
consider the largest number k that is in your chosen subset.
consider the pairs
(1, k - 1)
(2, k - 2)
.
.
.
((k-1)/2, (k+1)/2) or (k/2) depending on whether k is odd or even
If we pick more than one from each pairing, then we are done. If
not, we would have picked at most k/2 from each pair, plus the largest
number k. that gives us k/2 + 1≤ n/2 + 1. but since we pick more than n/2 + 1, we must definitely choose 2 from one pair.
solution?
