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.)
 solution for n=12 | Comment 15 of 21 |
Well, thanks for the explanation Ady, it certainly makes sense how you arrived at the problem and didn't foresee the issues that would arise. It was definitely an easy mistake to make, and either way, I enjoyed working on trying to find the best solution for n=20.

Now that you've changed it over to n=12, I can say with a fair amount of confidence, having searched a large set of combinations that for n=12, EN = 72.

The "worse" set I found as far as failing at the lowest possible EN value was my previously stated {1, 2, 3, 8, 13, 23, 38, 41, 55, 64, 68, 72}.

While I did limit the 2nd and 3rd terms of the set to not exceed 10 and 20 respectively, to speed up the search, it seems highly unlikely that any solution exceeding those given values at the 2nd and 3rd positions would be able to fill the 9 remaining spots with distinct values less than 72. If Charlie were to show up, I'm sure he'd have a search program superior to that which I was using, that could either confirm or improve upon this suspected value for EN rather quickly. For now, I'll double check with a full search to confirm that 72 is in fact our maximal value for EN.
 Posted by Justin on 2010-07-19 22:36:13

 Search: Search body:
Forums (0)