Track / Stage 5 / 244 of 400 #1324 of 2444

Problem 1324

AIME late

Combinatorics Difficulty 5.6 Prove it Harvard-MIT November Tournament · United States

Three not necessarily distinct positive integers between $1$ and $99$ , inclusive, are written in a row on a blackboard. Then, the numbers, without including any leading zeros, are concatenated to form a new integer $N$ . For example, if the integers written, in order, are $25$ , $6$ , and $12$ , then $N=25612$ (and not $N=250612$ ). Determine the number of possible values of $N$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution:

Answer: $825957$

We will divide this into cases based on the number of digits of $N$ .

- Case 1: $6$ digits. Then each of the three numbers must have two digits, so we have $90$ choices for each. So we have a total of $90^{3} = 729000$ possibilities.

- Case 2: $5$ digits. Then, exactly one of the three numbers is between $1$ and $9$ , inclusive. We consider cases on the presence of $0$ s in $N$ .

- No $0$ s. Then, we have $9$ choices for each digit, for a total of $9^{5} = 59049$ choices.

- One $0$ . Then, the $0$ can be the second, third, fourth, or fifth digit, and $9$ choices for each of the other $4$ digits. Then, we have a total of $4 \times 9^{4} = 26244$ choices.

- Two $0$ s. Then, there must be at least one digit between them and they cannot be in the first digit, giving us $3$ choices for the positioning of the $0$ s. Then, we have a total of $3 \times 9^{3} = 2187$ choices.

So we have a total of $59049 + 26244 + 2187 = 87480$ choices in this case.

- Case 3: $4$ digits. Again, we casework on the presence of $0$ s.

- No $0$ s. Then, we have $9^{4} = 6561$ choices.

- One $0$ . Then, the $0$ can go in the second, third, or fourth digit, so we have $3 \times 9^{3} = 2187$ choices.

So we have a total of $6561 + 2187 = 8748$ choices in this case.

- Case 4: $3$ digits. Then, we cannot have any $0$ s, so we have a total of $9^{3} = 729$ choices.

Hence, we have a total of $729000 + 87480 + 8748 + 729 = 825957$ choices for $N$ .

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