## Divisible By 99

#### Problem

Find the smallest number that is made up of each of the digits 1 through 9 exactly once and is divisible by 99.

#### Solution

The first thing we note is that 1 + 2 + ... + 9 = 45 and as the sum of the digits is divisible by 9 then any arrangement of those digits will produce a number that is divisible by 9. So our challenge reduces to finding the smallest number that is divisible by 11.

To test if a number is divisible by 11 we find $a$, the sum of digits in the odd positions, and $b$, the sum of digits in the even positions. If $a$ $b$ is divisible by 11 then so too is the number; for example, 95953: 9 + 9 + 3 = 21, 5 + 5 = 10, and as 21 10 = 11 then we know that 95953 is divisible by 11.

Let us begin with the smallest 9-digit number using each of the digits 1 through 9: 123456789. The first set, {1, 3, 5, 7, 9}, has sum 25 and the second set, {2, 4, 6, 8}, has sum 20. As the difference is 5 we know that the number is not divisible by 11.

However, for the difference to increase from 5 to 11 we need to increase the sum of the first set by 3 and decrease the sum of the second set by 3. This can be achieved by swapping 1 and 4, 3 and 6, or 5 and 8.

Swapping 1 and 4 gives the two sets {4, 3, 5, 7, 9} and {2, 1, 6, 8}. But before we merge these numbers we must place them in ascending order to keep the number as small as possible: {3, 4, 5, 7, 9} and {1, 2, 6, 8}. This produces the number 314256789.

By swapping 3 and 6 we get {1, 5, 6, 7, 9} and {2, 3, 4, 8}, producing the number 125364789.

Finally by swapping 5 and 8 we get {1, 3, 7, 8, 9} and {2, 4, 5, 6}, producing the number 123475869.

Hence the smallest number using the digits 1 through 9 which is divisible by 99 is 123475869.

Using 1, 2, and 3, we can see that 132 is divisible by 11. By considering numbers made up of each of the digits 1 through $n$, which $n$-digit numbers can be made to be divisible by 11?