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.)
Some Thoughts No Subject | Comment 4 of 21 |

The below is likely flawed, but constitutes my suggestions:

1 We are given 20 positive integers to start with.      
2 There are 190 different combinations of the 20 integers, in the range 3 to x.      
3 Therefore if x is less than 192, there must be at least one repetition of 2 numbers.      
4 However it doesn't follow from this that there will not be a repeat if x is greater than 192. The largest value that x can in fact take, for it necessarily to be the case that there must be a duplicate, for any choice of integers in S, remains open. 
5 Some posters suggested a 'Fibonnacci limit'of around 11,000 to 17,000; I am not sure this is right.     
6 Without giving it too much thought, 1729, 4104, 20683, 39312 are the smallest numbers expressible as the sum of 2 cubes in at least 2 different ways.      
 1729 = (1,12)(9,10)      
 4104 = (15,9)(16,2)      
 20683 = (1,27)(19,24)      
 39312 = (2,34)(15,33)      
 Therefore if 9^3=721 is eliminated from the list of 20, the cubes from 1 to 21 = 9261 should safely produce non-duplicates.

Edited on July 15, 2010, 5:39 am

7 After a little further thought, I conjecture that x = 333 is the smallest value that x can take that will ensure that there are no duplicates in the list of 20. Contrariwise, if x is <=332, then there must be at least one duplicate. I leave the detailed proof of this to to others better qualified.


Edited on July 15, 2010, 7:48 am
  Posted by broll on 2010-07-15 04:58:26

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 (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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