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 ?

 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.)
 running some numbers ... | Comment 8 of 21 |
Running through for all possible sets of size X from X = 4 to 10, I found the following EN values for the given sizes:

X = 4, EN = 5
, Failed Set = {1, 2, 3, 5}
X = 5, EN = 8
, Failed Set = {1, 2, 3, 5, 8}
X = 6, EN = 13
, Failed Set = {1, 2, 3, 5, 8, 13}
X = 7, EN = 21
, Failed Set = {1, 2, 3, 5, 8, 13, 21}
X = 8, EN = 25
, Failed Set = {1, 2, 3, 5, 9, 15, 20, 25}
X = 9, EN = 35
, Failed Set = {1, 2, 3, 5, 9, 16, 25, 30, 35}
X = 10, EN = 46
, Failed Set = {1, 2, 8, 11, 14, 22, 27, 42, 44, 46}

In addition, I found for:
X = 11, EN <= 58, Failed Set = {1, 2, 6, 10, 18, 32, 34, 45, 52, 55, 58}
X = 12, EN <= 72, Failed Set = {1, 2, 3, 8, 13, 23, 38, 41, 55, 64, 68, 72}

From my current best for X = 12
, I began expanding towards X = 20, by using the next available number for each position. As of right now, the best I've found for X = 20, EN <= 349, Failed Set = {1, 2, 3, 5, 9, 16, 26, 31, 43, 61, 70, 79, 116, 132, 163, 182, 214, 257, 300, 349}

I'm attempting to narrow it down further through brute force, but that process likely won't arrive at any further improvements due to the vast quantity of combinations it has to test. Hopefully someone can come up with a proof, as my computer would greatly appreciate the break from number crunching.

Edited on July 16, 2010, 12:54 am

Edited on July 16, 2010, 1:30 am
 Posted by Justin on 2010-07-16 00:53:57

 Search: Search body:
Forums (0)