## 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. Instead of just guessing numbers, one can limit the possibilities by thinking about the number first. One does not have to worry about the first digit because no matter what it is it will be divisible by 1. Likewise for the ninth digit, the sum of the digits 1,2,..9=45 which is divisible by 9. In order for a number to be divisible by 5, it must end in 0 or 5. Since there is no 0 allowed, the fifth digit must be 5 in order for 5 divide into it. Also, since the second, fourth, sixth and eight digits must be divisible by 2, 4, 6 and 8 respectively, each of these four positions must one of the even digits 2, 4, 6, or 8 because an even number does not divide an odd number evenly. This tells us that the other four positions must be filled by the odd digits. Therefore, the third digit must be odd and 4 must divide the third and fourth digits together according the rule for divisibility by 4. Similarly, the sixth, seventh and eighth digits together must be divisible by eight according to the rule for divisibility by eight. Tha table below shows all the combinations of numbers for the third and fourth digits and for the sixth, seventh and eighth positions. The shaded cells represent combinations that are not divisible by 4 and 8 in their respective tables.

 Divisible by 4 Divisible by 8 12 72 214 234 274 294 612 632 672 692 14 74 216 236 276 296 614 634 674 694 16 76 218 238 278 298 618 638 678 698 18 78 412 432 472 492 812 832 872 892 32 92 416 436 476 496 814 834 874 894 34 94 418 438 478 498 816 836 876 896 36 96 38 98

After looking at the none-shaded possibilities for the third and fourth digits, one should notice that the fourth digit must be 2 or 6. This means that both 2 and 6 cannot be to the right of the fifith digit because one of them has to be in the fourth position. Therefore, even though 216 and 296 are divisible by 8, they cannot be possible combinations because they both contain both 2 and 6.

We have narrowed the possibilities down quite a lot already but we can narrow them down even more by considering the first three digits. The first three digits must be divisible by 3; therefore, the sum of the first three digits must be divisible by three. Since the first and third digits must be odd and two odd numbers added together result in an even number and an even number plus the second digit which is even will result in an even number, the sum of the first three digits must be an even number that is divisible by 3. Since 7, 8 and 9 are three largest numbers we can use, 24 is the largest even number that is divisible by 3 that the first three digits can sum to. The first three digits can also sum to 18, 12 or 6.

 Divisible by 3 24 18 12 6 987 927 783 921 381 321 789 963 387 723 129 123 981 369 741 147 729 189 327 183

The cells that are shaded in this table are the ones that would make both 2 and 6 be to the left of the fifth digit. This cannot happen so the shaded cells possibilities cannot occur.

After combining all the tables of divisibility rules above, one would arrive at the following 20 possible solutions to this problem.

 Nine Digit Number Possibilities 987254163 987654321 981654327 981654723 789254163 789654321 783254961 783254169 741258963 741658329 387254961 387254169 381254967 381654729 189654327 189654723 183254967 183654729 147258963 147658329

After going though the calculations, one will determine that 381654729 is the nine-digit that satisfies the requirements of this problem.

It is quite amazing how just by thinking about the number, we were able to decrease the number of possibilities from 362880 down to only 20.

Back to Luke's Problem Solving