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.)
 Low 300s ?? | Comment 10 of 21 |

Broll in comment 4 suggests than EN might be 333, but no clue to the path to reach that (except that perhaps it was an extension of the logic he earlier used to show that any set of 20 will produce 190 sums so at least two must be identical if EN is low enough).  Justin in comment 8 offers a "failed set" for a set S from 1..349 which shows that any EN 350 or larger would fail on that test set (I checked that specific set, and indeed there are no duplicate sums).  So far Ady, the proposer, has not intervened to suggest whether he has a provable answer.  As Justin points out, brute force searches are time consuming.  What we really need is a demonstrably efficacious construction system which can build to a set of 20 members; the Fibonacci set does this, but gives values of EN which are much too high to be plausible as maximal.  I give the problem high rating for being provocative and challenging.  Perhaps there is a (relatively) simple solution which can settle the matter.

 Posted by ed bottemiller on 2010-07-16 20:06:42

 Search: Search body:
Forums (0)