Originally Posted by

**SlipEternal** Suppose we are trying to pick numbers that are relatively prime. For every number we pick in the 1 to 1000 range, there is at least one number in the 1001 to 2000 range that is a multiple:

In the 501 to 1000 range, multiply by 2

In the 334 to 500 range multiply by 3

In the 226 to 333 range, multiply by 4

In the 201 to 225 range, multiply by 5,

Etc.

So, for each number you pick in the 1 to 1000 range, there is one fewer numbers available in the 1001 to 2000 range to pick. By the Pigeonhole principle, you must pick at least one number in the 1 to 1000 range and at least one number in the 1001 to 2000 range. This is the start of the proof. You will need to construct the logic as to why this matters, but if you try to pick all numbers 1001 to 2000, any number you pick less than that is going to divide one of the numbers in the 1001 to 2000 range. And if you try to "shift" one of the numbers from the 1001 to 2000 range, each number you shift will divide a different number in the 1001 to 2000 range (causing you to need to shift even more numbers). Each time you shift a number from the "upper" range to the "lower" range, you wind up causing another divisor to be added.