The following text represents a valid contest question
in which I have erased one number :

Let S be a set of 20 distinct positive integers,
each less than EN(=THE ERASED NUMBER).
Show that there exist four distinct elements a, b, c, d , all in S,
such that a + b = c + d.

What maximal value of EN guarantees the existence of these elements ?

(In reply to re(2): No Subject by broll)

Broll,

We are seeking the SMALLEST value of EN for which no set S of 20 members -- each distinct, > 0, and < EN -- lacks the property that at least four members are related such that a+b = c+d.   "no set lacks" = "every set satisfies"erNoNo

Your original posting showed a method to prove easily that for certain values of EN the addition test is always satisfied.  If there are 20 members in S, then there are n*(n-1)/2 = 190 sums the largest of which could be (EN-1 + EN-2) and the smallest of which could be 3 (i.e. 1+2).  If EN were 21, there would be 190 sums, but all in the range 3..39 -- obviously forcing many duplicate sums.  If EN = 98, then the 190 sums could be in the range 3..193, so duplication might be avoidable -- but if EN=97 then the range shrinks to 3..191, so some duplication would always occur.

Does this prove that EN=97?  It only shows the lower limit for a possible largest EN.  But some other analysis would have to defend a larger value -- and exhaustive enumeration of all 20-subsets of a larger EN would quickly become a computational monster.  If we tried to introduce the Fibonacci element, we are avoiding the requirement that S may be any subset of the numbers from 1 to EN-1.  Now what??

 

Posted by ed bottemiller on 2010-07-15 21:25:30