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 | |||||||||||
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.
24 | 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.
Questions, Comments or
Suggestions
©1998 by Luke Rapley