Nine Digit Number

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