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.

One situation is to simultaneously maximize and minimize the difference between the numbers. Assume we pick the numbers 1-250 and 750-1000. This gives you 501 numbers, with the internal differences being between 1 and 250, and the maximum differences being between 500 and 999, inclusive. Obviously, 666 falls in that range.

Similarly, if we start at 1 and eliminate all numbers starting at 335, then we have the numbers 1-334, and 669 to 836. This makes the difference between 335 and 835, which includes 666.

Basically, eliminating the subset of numbers that differs by 334 from any arbitrarily chosen set of numbers guarantees you will have a pair of numbers that differs by 666 since you are selecting more than 50% of the numbers.

Posted by Eric on 2005-08-22 20:54:38