All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Restoring the erased (Posted on 2010-07-14)
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 ?

Comments: ( Back to comment list | You must be logged in to post comments.)
 re: No Subject | Comment 5 of 21 |
(In reply to No Subject by broll)

I agree with Broll that for any 20 distinct members of a set, there are 190 sums (20 * 19 / 2) and that the lowest possible sum would be 3 (if set includes 1 and 2).  This gives a lower bound for EN.

The Fibonacci sets show only that if all 20 members of the set are distinct Fibonacci numbers, that NO two pairs of that set will have the same sum; a fortiori the lowest such set [F(2) .. F(21)] is an upper bound for maximal EN.

Broll calls attention to the cube pairs, the first made famous by the Hardy-Ramanujan anecdote (that 1729 is the lowest number expressible in two ways as the sum of two cubes). But we already know how to assure that at least one subset [abcd] meets the test, e.g. just by including (1,2,3,4) in the set.  We need to show that for no set of 20 randomly selected positive integers less than EN, without duplication, can there be any subset abcd which meets the addition test.

I just spotted Broll's edit suggesting that for every subset of 20 distinct integers from set (1..332) there must be at least one duplicated sum of pairs (details not given), and asserting that hence 333 is the MAXIMAL value of EN.  Hmmmm...

(These double and triple negatives surely are confusing!)

 Posted by ed bottemiller on 2010-07-15 12:30:53

 Search: Search body:
Forums (0)
Random Problem
Site Statistics
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox: