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

 Search: Search body:
Forums (0)