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.)
re(2): No Subject | Comment 6 of 21 |
(In reply to re: No Subject by ed bottemiller)


I agree with your last comment. I probably did not make myself clear enough in my earlier post. I suspect where we part company is in your observation that We need to show that for no set of 20 randomly selected positive integers less than EN, without duplication, can there be any subset abcd which meets the addition test. 

What the question in fact calls for, howver, is the maximal value of EN that guarantees the stipulated duplicate, which is a slightly different problem answered in part by the first section of my previous post; as a matter of logic we can be quite sure that there must be the stipulated duplicate if x is less than 190.

My conjecture is stronger, and is that the smallest possible number for which there is at least one (non-randomly selected) subset, S, having the required number of 20 elements, with no stipulated duplicate, is greater than 190, and is in fact 333. This is of course the same as saying that 332 is the largest possible number for which it is possible to be certain, without further verification, that each and every randomly selected S will surely contain the stipulated duplicate, which is what I believe is what the question was asking for.

I trust that this assists,




Edited on July 15, 2010, 5:25 pm
  Posted by broll on 2010-07-15 17:16:16

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

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

Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information