Suppose you select 501 numbers from 1 to 1000, inclusive. Show that if no two of the selected numbers differ by 334, then some two of the selected numbers differ by 666.
Consider partitioning the numbers 1 - 1000 into groups C1 .. C334 according to their values mod 334 (remainder when divided by 334). The vast majority of these subsets will contain 3 numbers (with the exceptions of C333 and C334, which only have 2 each). Clearly, a set where no two differ by 334 cannot contain any of these subsets in their entirety.
Let S be a set of numbers for which no two differ by 334. Each set Ca with three numbers takes the form (a, b = a+334, c = a+668) for some a < 333. For an arbitrary set Ca, both a and c can be in S, but if b is in S, neither of the other two can be.
To achieve 501 numbers in S, 501-334 = 167 Ca's must each contribute two numbers. If Ca and C(a+2) each contribute two numbers to S, then a+2 and a + 668 are in S, which differ by 666.
Presume S contains no two numbers that differ by 334 or 666. This means that for every set of four consecutive numbers between 1 and 332 (inclusive), at least two can only provide one number to S. Since 332 is divisible by 4, this means at most exactly half of the Ca's can provide two numbers for a between 1 and 332. Since we know C333 and C334 can provide at most one, the maximum size of S is 334 + 332/2 = 500.
Therefore, a set of 501 numbers between 1 and 1000 inclusive with no two that differ by 334 must have at least one pair that differs by 666.
the devil made me do it...
