‘Have you seen this latest crazy Aha! problem?’ asked Ros.

‘Listen to this:
2 x 5 = 10, 3 x 37 = 111, 4 x 25 = 100, 5 x 2 = 10, 6 x 185 = 1110

Now, given any integer n, can we always find a multiple which has only the digits 0 and 1?’

Lyn was feeding her pigeons and only half listening. One of the holes in the loft was bigger than the others, and held two pigeons. ‘This is the principal pigeon hole!’ she laughed.

‘Well,’ said Ros thoughtfully, ‘it does illustrate the pigeon hole principle: n + 1 pigeons and n pigeon holes means two birds in the one hole.’

‘I don’t see what is so special about that,’ Lyn answered. ‘Surely that’s obvious.’

‘I think it is important,’ said Ros. ‘For example, if we have n + 1 numbers and we divide them by n, then two of the remainders must be equal. In fact ... terrific Lyn! I can solve this Aha!’

Can you?

Hint 1

This is obviously a problem with a strong hint included!

Hint 2

For given n, consider the n + 1 numbers 1, 11, 111, ... , 111...11, and think about the remainders on division by n.

Solution

Let n be a given integer. Now consider the n + 1 numbers 1, 11, 111, ... , 111...11, and think about what happens when we divide each by n. The possible remainders are 0, 1, 2, ... , n – 1; that is, there are n possible different remainders. Since we are carrying out n + 1 divisions, by the pigeon hole principle, at least two of the remainders will be the same.

For example, with n = 2,

   1 = 2 x 0 + 1
   11 = 2 x 5 + 1.
When we subtract these, the remainders cancel out, and the difference d is exactly divisible by 2:

   11 – 1 = 10 = 2 x 5.

This is true in general. As another example, take n = 3. Then

      1 = 3 x 0 + 1
    11 = 3 x 3 + 2
  111 = 3 x 37 + 0
1111 = 3 x 370 + 1.

So 1111 – 1 = 1110 = 3 x 370.  In fact here we have the simpler 111 = 3 x 37, corresponding to the zero remainder.

How could we arrive at the hint unaided? The natural tendency is to look at multiples of n. It is more helpful to think of the given form of the answer (0s and 1s), and to observe that such answers occur as differences of numbers which are made up of strings of 1s.

Extensions

1. Given any integer n, can we always find a multiple which has only the digits 0 and 2?  0 and 3? ...

2. The original problem asks for a multiple which contains only 0s and 1s. In fact, our solution provides a multiple which satisfies a rather stronger condition. What is it? Does this extend to the extension above?

Hint 1

Hint 2

Solution

Extensions