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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information