Pizza Hut Pi Day Challenge (Part 3)

On March 14, 2016, Pizza Hut held a online math competition in honor of Pi Day, offering three questions posed by Princeton mathematician John H. Conway. As luck would have it, years ago, I had actually heard of the first question before from a colleague who had heard it from Conway himself:

I’m thinking of a ten-digit integer whose digits are all distinct. It happens that the number formed by the first n of them is divisible by n for each n from 1 to 10. What is my number?

I really like this problem because it’s looks really tough but only requires knowledge of elementary-school arithmetic. In yesterday’s post, I described why the solution must have the form

___ , ___ ___ ___ , 5 ___ ___ , ___ ___ 0,

where the blanks have to filled by using the numbers 1, 2, 3, 4, 6, 7, 8, and 9. There are 8 remaining digits, and so there are 8! = 40,320 possible answers left.

Step 5. The number formed by the first two digits has to be a multiple of 2. The number formed by the first four digits has to be a multiple of 4, which means it’s also a multiple of 2. The number formed by the first six digits has to be a multiple of 6, which means it’s also a multiple of 2. The number formed by the first eight digits has to be a multiple of 8, which means it’s also a multiple of 2. By the divisibility rules, that means that the second, fourth, sixth, and eighth digits are even numbers. So the ten-digit number must have the form

___ , E ___ E , 5 E ___ , E ___ 0,

where E is one of 2, 4, 6, and 8. Therefore, the remaining dashes must be odd numbers:

    O , E O E , 5 E O , E O 0,

where O is one of 1, 3, 7, and 9. There are 4! = 24 ways of arranging the four remaining even digits and also 4! = 24 ways of arranging the remaining odd digits. Therefore, there are 24 x 24 = 576 possible answers left.

While it’s now tractable to find this number by brute force by listing and testing the 576 possible numbers, we can use the divisibility rules to reduce the list to only 192. I’ll continue this in tomorrow’s post.