One is the sum of the other two (Posted on 2005-07-31)

	Submitted by McWorter
Rating: 2.3333 (3 votes)
Solution:	(Hide)
Alexander Bogomolny's 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. Second proof. We may assume that A contains n; for, otherwise the problem reduces to looking at A as a subset of {1,...,m}, where m is the largest number in A, with |A|>(n+2)/2>(m+2)/2. Split the numbers 1 to n-1 into pairs {i,n-i}, for i=1 to the largest integer less or equal (n-1)/2. If n is odd, that's (n-1)/2 pairs. If n is even, that's (n-2)/2 pairs with the singleton {n/2}. Thus, in either case that's no more sets than the greatest integer less or equal n/2. Since |A|>(n+2)/2, there are more than (n/2)+1 numbers in A among these sets. Hence, by the pigeonhole principle, at least two numbers in A belong to one of these sets. These two numbers sum to n, which we assumed is in A, so we are done.

	Subject	Author	Date
	re: solution? Nicely done!	McWorter	2005-07-31 21:33:52
	solution?	Tan Kiat Chuan	2005-07-31 19:15:21
	a possible soln?	leoj	2005-07-31 18:59:51
	re: more than? or more than and equal	McWorter	2005-07-31 17:57:15
	more than? or more than and equal	Tan Kiat Chuan	2005-07-31 16:31:39
	?	Richard	2005-07-31 05:06:34