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

The below is likely flawed, but constitutes my suggestions:

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

 Search: Search body:
Forums (0)