Each of these problems can be solved with the help of the Pigeon Hole Principle and some additional considerations.

1. Are there two powers of 2 that differ by a multiple of 2001?
2. Is there a power of three which ends with the digits 001?
3. Is there a multiple of 2001 which can be written by 1s only (in decimal representation)?

Hint to problem 1. Let powers of 2 be pigeons, and their remainders when they are divided by 2001 be pigeon holes.

Hints to problem 2.

• If you have no clue how to prove what you need to prove, see what you can prove.
• Solving this problem is the same as proving that there is a power of 3 such that a number one less than it is a multiple of 1000.
• Look at powers of 3 as your pigeons and their remainders when divided by 1000 as pigeon holes. This will let you prove the existence of two powers of 3 whose difference is a multiple of 1000. Factor this difference.

Hint to problem 3. Numbers written with 1s only can be pigeons while remainders when these numbers are divided by 2001 can be pigeon holes.

1. Yes.
2. Yes.
3. Yes.

1. There are infinitively many powers of 2 (pigeons), and only 2001 remainders when these numbers are divided by 2001 (pigeon holes). That’s why there are two powers of 2 that give the same remainder when divided by 2001. The difference of these powers is a multiple of 2001.
2. We are looking for 3^k which ends with 001. This is the same as 3^k - 1 being a multiple of 1000.
   Similarly to problem 1 we can prove that there are two powers of 3 that differ by a multiple of 1000. Let’s call these powers 3ⁿ and 3^m. Factor their difference into 3^m is relatively prime with 1000 (it is neither a multiple of 2 nor a multiple of 5), so 3^n-m - 1 must be a multiple of 1000.
3. This problem is simular to problem 2. Using the Pigeon Hole Principle we can prove that there are two numbers, each made of 1s only, whose difference is a multiple of 2001. This difference would look like some 1s followed by some 0s, and so can be written as a product of a number written with 1s only and a power of 10. This product is a multiple of 2001. Since any power of 10 is relatively prime with 2001, the other factor in the product (the number written with 1’s only) must be a multiple of 2001.