The Hamilton Puzzler The Continental Conundrum The Befuddled Blue

Puzzle #6: ID Numbers (April 2009)

The winner of the sixth logic puzzle contest is:

Tom Helmuth '09! Congratulations, Tom!

Click to go to:

The Puzzle

The Puzzler's solution

An Alternate Solution

Other correct answers were submitted by:

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

The last puzzle of the term will appear on May 1.

Until fairly recently, many people thought of logic as the study of the laws of thought. All the basic rules of logic are supposed to be obvious, and they apply to all inferences and implications. In contrast, mathematics is the study of specific domains of objects: numbers, cylinders, differential equations. In the late nineteenth- and early twentieth-centuries, Gottlob Frege, in Germany, and Alfred North Whitehead and Bertrand Russell, in England, attempted to prove that mathematics was really just logic in a complicated disguise. Since 1931, when Kurt Gödel published his two (in)famous incompleteness theorems, the logicist project of Frege and Whitehead and Russell has been considered a failure, though there has been renewed interest in different versions of logicism. This month’s logic puzzle is a bit more mathematical than previous ones, but it requires no more mathematics than simple division.

The Puzzle

Once upon a time, the Hamilton College administration was taken over by a rogue band of number theorists intent on developing a new system of student ID numbers. The number theorists wanted the new ID numbers to have ten digits in which each of the numerals from 0 to 9 appeared exactly once. They also wanted each ID number to be divisible by each of the digits (except 0!).

Questions

1. What would be the smallest possible new ID number?
2. What would be the largest possible new ID number?

Bonus Question

3. How many new ID numbers conforming to the number theorist’s constraints are possible?

Go to the Puzzler's solution, an Alternate solution, or the Top

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.

Go to the Puzzle, an Alternate solution, or the Top

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.

Go to the Puzzle, the Puzzler's solution, or the Top