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.)
Assurance it is ... | Comment 18 of 21 |
(In reply to re: solution for n=12 by ed bottemiller)


I let my computer run overnight, searching for lower sets than that previously mentioned. What I did was the following, for a set of 12 numbers {a, b, c, d, e, f, g, h, i, j, k, l}:

1.) Set a = 1, as any set starting with >1 can be reduced as mentioned in a previous post
2.) Set the limit I'd like to start my search at (in this case, 72)
3.) Set l = limit, this fixed our 1st and 12th values, to make the looping process less time consuming
4.) Began looping through all values for b - k, beginning at b+1, c+1, .... and ending at our set limit
5.) If a set was found, with all values less than or equal to limit, I displayed that set, and broke out of the loop, reduced limit to limit - 1, and restarted the loop

I continued the above process, until a result wasn't found for our given limit. After displaying the solution {1, 2, 3, 8, 13, 23, 38, 41, 55, 64, 68, 72} already proposed, it failed to find a solution for a limit of 71.

So, that means EN = 72, and any set of 12 values < 72 will result in at least one duplicate sum.

  Posted by Justin on 2010-07-20 14:18:14
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 (5)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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