## Problem: Nine Digit Number

A nine-digit number is formed using each of the digits 1, 2, 3, ..., 9 exactly once.
For n = 1, 2, 3, ..., 9, n divides the first n digits of the number. Find the number.

## Discussion/Solution: Nine Digit Problem

How should one approach solving this problem?

Strategy 1 : Take a random number made up of the nine digits and check for the desired criteria.

For instance, consider the number 123456789 .

Check the criteria: 1 divides 1, 2 divides 12, 3 divides 123,
4 does NOT divide 1234 (i.e. 1234/4 = 308.5)

Therefore, 123456789 is not the number for which we are searching.

Before we continue in this manner let's count the number of possible nine digit numbers. Assuming the digits cannot repeat, we have 9! = 362880 possibilities. Too many to consider. Let's change our strategy.

Strategy 2 : Narrow down the number of possibilities.

We want 5 to divide the first five digits of the number. So the only possibility for the fifth digit is 5 (since we do not have a 0 digit). Also, 2 divides the first two digits, 4 divides the first four digits, 6 divides the first six digits, and 8 divides the first eight digits. So the second, fourth, sixth, and eighth digits must be even. We only have four even digits (2, 4, 6, 8). Thus, these digits must fill the even numbered spaces and the remaining odd digits (1, 3, 7, 9) must fill the odd spaces.

Now let's count the possible nine digit numbers again. Suppose we have nine blanks that represent the nine digits and fill the blank with the number of possible choices for that digit.

4 4 3 3 1 2 2 1 1 = 4! 4! 1 = 576 possibilities

This is much better! Can we reduce this number even further?

Since 4 divides the first four digits, then the third and fourth digit form a number that four divides. The possible two digit numbers are 12, 16, 32, 36, 52, 56, 72, 76, 92, 96. Notice these numbers end in 2 or 6. Thus, the fourth digit must be a 2 or 6. Similarly, since 8 divides the first eight digits and 4 divides 8, then 4 must also divide the first eight digits. Hence, 4 divides the number formed by the seventh and eighth digits. So the eighth digit must be 2 or 6. This forces the second and sixth digits to either be 4 or 8.

Now we have

4 2 3 2 1 1 2 1 1 = 4! 2! 2! 1 = 96 possibilities .

Let's rename our number: abcd5efgh

We know b = 4 or 8 , d = 2 or 6 , e = 4 or 8, and g = 2 or 6.

We also know:
3 divides abc and 6 divides abcd5e, so 3 divides abcd5e and thus 3 divides d5e

We can write an equation: d + 5 + e = 3k where k is some constant
d + e = 3k - 5 with d and e even

If k = 5, then 3k - 5 = 10. So d + e = 10 . Is this the only possible value for k?

Two cases: (1) d = 2 and e = 8, g = 6 and b = 4 or (2) d = 6 and e = 4, g = 2 and b = 8

So we have a 4 c 2 5 8 f 6 h or a 8 c 6 5 4 f 2 h as possible numbers.

This has narrowed our choices even more. There are 4! = 24 possible numbers for case (1) and 4! = 24 possible numbers for case(2). So we now have 48 possible numbers to consider.

What else do we know:

(1) a + 4 + c = 3m or a + 8 + c = 3m for some constant m (a and c are odd)
(2) f + 6 + h = 3n or f + 2 + h = 3n for some constant n (f and h are odd)

Combined Strategy

Now by using algebra with trial and error we discover that we want

d = 6, e = 4, a = 3, c = 1, f = 2, and h = 9.

Therefore, the number we are seeking is 381654729.

Check the criteria:

3 / 1 = 3
38 / 2 = 19
381 / 3 = 127
3816 / 4 = 954
38165 / 5 = 7633
381654 / 6 = 63609
3816547 / 7 = 545221
38165472 / 8 = 4770684
381654729 / 9 = 42406081