Maths Olympiad Prep

Library / /133 of 377

Combinatorics Difficulty 4.9 AIME Find the answer United States

Problem:

Bob's Rice ID number has six digits, each a number from 11 to 99, and any digit can be used any number of times. The ID number satisfies the following property: the first two digits is a number divisible by 22, the first three digits is a number divisible by 33, etc., so that the ID number itself is divisible by 66. One ID number that satisfies this condition is 123252123252. How many different possibilities are there for Bob's ID number?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

Answer: 324324.

We will count the number of possibilities for each digit in Bob's ID number, then multiply them to find the total number of possibilities for Bob's ID number.

There are 33 possibilities for the first digit given any last 55 digits, because the entire number must be divisible by 33, so the sum of the digits must be divisible by 33.

Because the first two digits are a number divisible by 22, the second digit must be 2,4,62, 4, 6, or 88, which is 44 possibilities.

Because the first five digits are a number divisible by 55, the fifth digit must be a 55.

Now, if the fourth digit is a 22, then the last digit has two choices, 2,82, 8, and the third digit has 55 choices, 1,3,5,7,91, 3, 5, 7, 9.

If the fourth digit is a 44, then the last digit must be a 66, and the third digit has 44 choices, 2,4,6,82, 4, 6, 8.

If the fourth digit is a 66, then the last digit must be a 44, and the third digit has 55 choices, 1,3,5,7,91, 3, 5, 7, 9.

If the fourth digit is an 88, then the last digit has two choices, 2,82, 8, and the third digit has 44 choices, 2,4,6,82, 4, 6, 8.

So there are a total of 34(25+4+5+24)=3427=3243 \cdot 4 (2 \cdot 5 + 4 + 5 + 2 \cdot 4) = 3 \cdot 4 \cdot 27 = 324 possibilities for Bob's ID number.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.