0809.6: Solution

Puzzle #6: ID Numbers (April 2009)


The winner of the sixth logic puzzle contest is:

Tom Helmuth '09! Congratulations, Tom!

Other correct answers were submitted by:

Andrew Beyler '10, Matt Eichenfeld '09, and Chris Weitzman'11


The Puzzler's solution:

All whole numbers are divisible by 1. Any number using all the digits will be divisible by both 3 and 9. Since the numbers have to be divisible by both 2 and 5, they must end in 0. Any number divisible by 3 and 2 will be divisible by 6. And, if a number is divisible by 8, then it will be divisible by 4. So, if the number ends in 0, we only have to worry about making it divisible by 7 and 8.

Any number whose last three digits are divisible by 8 will be divisible by 8. Furthermore, since the numbers end in 0, for the last three digits to be divisible by 8, the two-digit number formed by the hundreds and tens digits (in that order) must be divisible by 4.

Let’s start with the small number, and let’s say that the number is 123456***0. The number is only missing 7, 8 and 9. But, there are no two-digit numbers formed by 7, 8, and 9 which are divisible by 4. So, we have to choose a slightly larger lead, swapping the 7 for the 6: 123457***0. Now, our missing digits are 6, 8, and 9, which yield two two-digit numbers divisible by 4: 68 and 96. So, we can test 1234579680 and 1234578960 for divisibility by 7. There’s no easier way to test for divisibility by 7. Do it by hand or use a calculator; either way both number fail. Continuing in this manner, choosing slightly larger leads each time, we get to the solution: 1234759680.

For the largest number, start with 987654***0, and work up. The solution is 9876351240.


An Alternate Method

One easy way to solve the problem is to use a computer in conjunction with the observation that the least common multiple of the nine digits (excluding 0) is 2520. Then, one merely has to check all numbers with all ten digits to see if they are divisible by 2520. It's not a pretty method, and you wouldn't want to do it by hand, but it will lead you to an answer to the bonus question as well.