Here's a little coffee-time challenge puzzle
ABCDEFGHI
Arrange the digits 1-9 to make a nine digit number such that:
The first digit, A is divisible by one.
The first two digits, AB is divisible by two.
The first three digits, ABC is divisible by three.
The first four digits, ABCD is divisible by four.
The first five digits, ABCDE is divisible by five …
… All nine digits, ABCDEFGHI is divisible by nine.
 |
When I first saw this puzzle, I immediately thought of a brute force approach; a few lines of code and you can permute through every possible combination of the digits in a few seconds, but by applying a couple of the simple divisibility rules we're taught in schools, you can solve this with pen, paper, and a half a cup of coffee. If you need a refresher on simple divisibility tests, you can find one here. |
Give it a go, then check your solution below:
Show me the answers
Answers
Here is the Answer:
381654729
Derivation
ABCDEFGHI
First of all, there is a 'gimmie'. As we're using the digits 1-9, then whatever arrangement we select it will be divisible by nine. 1+2+3+4+5+6+7+8+9=45, which is divisible by nine. (A divisibility rule for nine is that digit root is divisible by nine). So, we don't care what digit goes at the end!
ABCDEFGHI
Next, we can apply the divisibility by five rule. Every number that is divisible by five has to end in a zero or five. As we're not using zero, the fifth digit has to be five.
ABCD5FGHI Used: 1 2 3 4 5 6 7 8 9
Next, we know that, at minimum, digits: B,D,F,H need to be even {2,4,6,8} as these need to be divisible by even numbers; this reduces down the solution set but we need more help. From the divisibility of three rule, A+B+C must be divisible by 3, as must D+5+F (all numbers divisible by six are also divisible by three).
Combing these, as we know D,F need to be from the set {2,4,6,8}, and that D+5+F needs to be divisible by three, out of all the combinations, only four are possible: 254 256 258 452 456 458 652 654 658 852 854 856.
Out of the four solutions: 258 456 654 852 we can eliminate two of these through application of the divisibility by four test (To be divisible by four, the last two digits must also be divisible by four). So, for ABCD to be divisible by four, then CD also needs to be divisible by four. As we need four even digits in positions B,D,F,H this means that A,C,E,G,I must be odd. For CD to be divisible by four, and with C being odd, then D cannot be 8 or 4. There are now just two possibilities: 258 456 654 852.
Let's investigate both of these:
ABC258GHI Inserting one of the two remaining even digits in B,H {4,6}, then making sure A+B+C add up to multiple of three leads to just eight possible choices:
147258369 The divisibility test for eight is that the last three digits must be divisible by eight also. This rules out the arrangements ending -836, -814, and -874.
The remaining two fail the division test for seven digits. This path is a dead end with no solution.
|
ABC654GHI The divisibility by eight test we used on the left (last three digits also divisible by eight), means than 4GH needs to be divisible by eight. H must be from the set {8,2}, but it can't be 8 as G is odd; in fact G has to be {3,7}. With these constraints, there are eight potential solutions: 987654321789654321 381654729 183654729 981654327 189654327 981654723 189654723 Manually applying the divisibility by seven test, only one solution survives. 381654729 We have a winner! 
|
This problem has a unique solution: 381654729
More
 |
If you liked this puzzle, check out a similar one I posted last year where you have to arrange the same digits to complete an equation. |