Consider the set {1,11,111, …, ((10^2007) – 1)/9}.

Prove at least one of these numbers is divisible by 2007.

Is the same true for 2008 (replacing 10^2007 with 10^2008, of course)?

Communicated by Michael Varnava.

To approach this problem, we will use a technique which is often used in math: proof by contradiction. In a proof by contradiction, we assume that the conclusion we wish to prove is in fact false, and show that this leads to a contradiction with the other premises. For this problem, we will assume that none of the numbers is divisible by 2007.

We next observe that our set {1,11,111, …, ((10^2007) – 1)/9} has 2007 elements. This suggests that we may be able to make use of the Pigeonhole Principle, although it is not immediately obvious how. Since we are checking for divisibility, we decide to try dividing each of the elements by 2007. Furthermore, because we have assumed that 2007 does not divide any of the numbers, we know that dividing by 2007 will leave a nonzero remainder. This leaves 2006 possible remainders. As we suspected, we are able to employ the Pigeonhole Principle here to say that since we are trying to fit 2007 elements in to 2006 ‘boxes’ (the remainders), at least two elements must have the same remainder. Let’s call these two elements x and y, with x being the larger of the two.

The next step that seems most likely to bring us closer to the proof seems clear when we consider what it means for two numbers x and y to have the same remainder upon division by 2007: it means that x – y is divisible by 2007. If we write x = (10^a – 1)/9 and y = (10^b – 1)/9, or x = 111…111 (a times) and y = 111….111 (b times), we see that x – y = 111…11000…00. That is, x – y is 1 repeated a-b times followed by 0 repeated b times. But this numbers is really just one of the elements of our set, let’s call it z, multiplied by 10^b. Since 2007 is relatively prime to 10 (neither 5 nor 2 divides 2007), we see that 2007 divides x – y if and only if 2007 divides z. Therefore, we have found a contradiction, since z is an element of our set.

As the last step of our proof, we observe that our contradiction arose from assuming that 2007 divided none of the elements of our set. It follows that there must be an element in the set that is divisible by 2007 (although this is not necessarily the same z from our proof. This is tricky to grasp, so make sure you understand why.)

The preceding proof breaks down when we use 2008 instead of 2007 because 10 is not relatively prime to 2008. 2 divides both of these numbers. This means that 2008 divides x – y if and only if 1004 divides z, which is not sufficient to prove our desired end.