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

Home > Just Math
Restoring the erased (Posted on 2010-07-14) Difficulty: 3 of 5
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 ?

No Solution Yet Submitted by Ady TZIDON    
Rating: 4.0000 (5 votes)

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
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information