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 ?

(In reply to re(2): Low 300s ?? by Justin)

You are quite right. As you say, the 'x+1' can be dispensed with, if we start with a ruler of order x and simply add 1 to each element, to get rid of the leading zero. So we can reduce x=18 to 20 to EN: 217,247,284, presumably with some confidence; we may also surmise that the figures for x=16 and 17 may be amended to EN 178 and 200 respectively, by following the Golomb elements for the corresponding Rulers, plus 1:

1 2 5 12 27 33 57 69 77 116 118 135 151 164 169 178

1 6 8 18 53 57 68 81 82 101 123 139 160 166 169 192 200

Even so, I now agree it has to be accepted that Golomb just gives an upper bound, below which serious searching can begin, rather than a definite answer, as I'd hoped. Given the amount of computation required, no doubt every bit helps!

 

 

 

Posted by broll on 2010-07-17 15:57:22