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): Low 300s ?? | Comment 12 of 21 |
(In reply to re: Low 300s ?? by broll)

Broll,

This is an interesting theory, and the Golomb Ruler does in fact lead to a set of numbers with no duplicate sums, but your statement in part 3:

"It seems to follow that for any order, x, (here, 20) the last mark on a Golomb Ruler of order (x+1) represents the  smallest possible number for which there is at least one (non-randomly selected) subset, S, having the required number of x elements, with no stipulated duplicate."

Has me wondering, how did you arrive at this conclusion? For all values of x <= 12, I have already posted sequences that fail which have EN values lower than those smallest values that you're proposing. In case you missed it, here's an updated list of the sets I've found so far:

x = 4; EN = 5; {1, 2, 3, 5}
x = 5; EN = 8; {1, 2, 3, 5, 8}
x = 6; EN = 13; {1, 2, 3, 5, 8, 13}
x = 7; EN = 21; {1, 2, 3, 5, 8, 13, 21}
x = 8; EN = 25; {1, 2, 3, 5, 9, 15, 20, 25}
x = 9; EN = 35; {1, 2, 3, 5, 9, 16, 25, 30, 35}
x = 10; EN = 46; {1, 2, 8, 11, 14, 22, 27, 42, 44, 46}
x = 11; EN = 58*; {1, 2, 6, 10, 18, 32, 34, 45, 52, 55, 58}
x = 12; EN = 72*; {1, 2, 3, 8, 13, 23, 38, 41, 55, 64, 68, 72}
x = 13; EN = 89*; {1, 2, 3, 13, 22, 28, 43, 50, 57, 73, 81, 86, 89}
x = 14; EN = 108*; {1, 2, 3, 5, 8, 25, 39, 48, 57, 67, 75, 83, 96, 108}
x = 15; EN = 136*; {1, 2, 3, 5, 8, 14, 27, 41, 56, 71, 87, 108, 118, 128, 136}
x = 16; EN = 182*; {1, 2, 3, 5, 9, 16, 26, 31, 43, 61, 70, 79, 116, 132, 163, 182}
x = 17; EN = 214*; {1, 2, 3, 5, 9, 16, 26, 31, 43, 61, 70, 79, 116, 132, 163, 182, 214}
x = 18-20; 246*, 283*, 333*; Golomb Ruler of order x + 1

* denotes best so far, without exhausting all possible combinations.

As the Golomb Ruler discards values that are the same distance apart as other pairs, it throws away a lot of possible combinations for which our failure requirements can be fulfilled. For example the best solution for x = 9 ends with two pairs of values with a distance of 5 between them, and would have been discarded in the corresponding Golomb Ruler. One final note, some of the "rules" can be reduced further when the leading non-zero value is greater than 1. We can decrease all values in the set by the same amount to reduce this value to 1, and still have no duplicate sums. For example, {5, 6, 7, 9, 12}, reduces to {1, 2, 3, 5, 8}. So several of the "rulers" you've proposed had the lowest value of EN could in turn be reduced further, to get a lower value of EN.

Like I said, interesting theory, and I wish it were that simple, but it seems that we're still stuck with the number crunching approach for trying to improve these solutions further.

Edited on July 17, 2010, 2:27 pm
  Posted by Justin on 2010-07-17 14:24:12

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