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.)
 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

 Search: Search body:
Forums (0)