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.

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. To illustrate this idea, let me give an example that almost works: 9,632,581,470, a ten-digit number that uses each digit exactly once.

1. The first digit is 9, which is clearly a multiple of 1.
2. The first two digits form the number 96, which is clearly a multiple of 2: .
3. The first three digits form the number 963, which is a multiple of 3: .
4. The first four digits form the number 9632, which is a multiple of 4: .
5. The first five digits form the number 96,325, which is a multiple of 5: .
6. The first six digits form the number 963,258, which is a multiple of 6: .
7. The first seven digits form the number 9,632,581, which is a multiple of 7: .
8. Doesn’t work: .
9. The first nine digits for the number 963,258,147, which is a multiple of 9:
10. The ten-digit number is a multiple of 10: .

So, this number works for 9 of the 10 cases… but we need the number that works for all 10 cases.

Here’s the ten-digit number, where the blanks have to be filled in:

___ , ___ ___ ___ , ___ ___ ___ , ___ ___ ___.

Each of the blanks has to be a digit from 0 through 9, and each can only be used once. Therefore, there are 10! = 3,628,800 possible answers, but we’d like to whittle this down to a more tractable number.

Step 1. This ten-digit number has to be a multiple of 10. By the divisibility rules, that means that the last digit has to be 0. So the ten-digit number must have the form

___ , ___ ___ ___ , ___ ___ ___ , ___ ___ 0.

Each of the blanks has to be a digit from 1 through 9, and each can only be used once. Therefore, at this stage, there are 9! = 362,880 possible answers.

Step 2. The number formed by the first five digits has to be a multiple of 5. By the divisibility rules, that means that the fifth digit has to be either 5 or 0. However, the 0 has already been used, so the fifth digit must be 5. So the ten-digit number must have the form

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

Each of the blanks has to be one of the 8 remaining digits, and each can only be used once. Therefore, at this stage, there are 8! = 40,320 possible answers.

Step 3. The number formed by the first nine digits has to be a multiple of 9. By the divisibility rules, that means that the sum of the first nine digits has to be a multiple of 9. However, this isn’t helpful: we know that the first nine digits are going to be 1 through 9 in some order, and we already know that

is a multiple of 9. So considering the first nine digits gives us no new information.

Step 4. The first digit has to be a multiple of 1. However, this isn’t helpful since every digit is a multiple of 1. So considering only the first digit gives us no new information.

I’ll continue this discussion with tomorrow’s post, where I’ll reduce the number of possible answers from 40,320 to only 576.

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?

To illustrate this idea, let me give an example that almost works: 9,632,581,470, a ten-digit number that uses each digit exactly once.

1. The first digit is 9, which is clearly a multiple of 1.
2. The first two digits form the number 96, which is clearly a multiple of 2: .
3. The first three digits form the number 963, which is a multiple of 3: .
4. The first four digits form the number 9632, which is a multiple of 4: .
5. The first five digits form the number 96,325, which is a multiple of 5: .
6. The first six digits form the number 963,258, which is a multiple of 6: .
7. The first seven digits form the number 9,632,581, which is a multiple of 7: .
8. Doesn’t work: .
9. The first nine digits for the number 963,258,147, which is a multiple of 9:
10. The ten-digit number is a multiple of 10: .

So, this number works for 9 of the 10 cases… but we need the number that works for all 10 cases.

In this series, I plan to discuss my solution of this problem using the rules of divisibility. I’ll start my solution with tomorrow’s post.

In the meantime, if you’d like to think about the solution on your own, I offer this green thought bubble to give you some time to think about it on your own.