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
Return to Susie Lanier's Class Page.