Find all ten digit numbers each containing the digit from 0 to 9 once and only once, with the property that the successive pairs of digits from left to right are divisible by 2,3,4,5,6,7,8,9 and 10.

[In other words: The two-digit number formed with the 'N'th digit and the '(N+1)'st digit is divisible by '(N+1)', where N = 1,2,3,4,....,9].

For the last two digits to be divisible by 10 the number must end in zero. The third and second from the right must be divisible by 9, but the first digit must be even to accommodate the next pair's (to the left) being divisible by 8. The possibilities are
270
450
630
810

Prepending digits to complete multiples of 8 gives
3270
2450
6450
1630
9630
4810

(multiple-of-8 '72' left out as that involves repetition of the 7)

Prepending a digit to make a multiple of 7, without producing a duplication of digits leaves
63270
91630
49630

The next digit on the left must be the end of a multiple of 5 but can't be 0, to avoid repetition and so must be 5. 56 and 59 are not multiples of 6, so the rightmost 6 digits must be
549630

Multiples of 4 that don't repeat digits already present are 12, 72 and 28, giving us
12549630
72549630
28549630

For the last one, beginning with 2, only 12 and 72 fit as multiples of 3, but the first digit of each is odd, preventing a multiple of 2 for the leftmost pair, so that last sequence is out.

That leaves
12549630
72549630

The only possible ways of fitting the remaining digits work out as
7812549630
1872549630

these last being the two answers.

Posted by Charlie on 2003-05-27 03:39:19