Maths Olympiad Prep

Library / /70 of 82

Combinatorics Difficulty 5.6 AIME, harder Prove it United States

Problem:

Three not necessarily distinct positive integers between 11 and 9999, inclusive, are written in a row on a blackboard. Then, the numbers, without including any leading zeros, are concatenated to form a new integer NN. For example, if the integers written, in order, are 2525, 66, and 1212, then N=25612N=25612 (and not N=250612N=250612). Determine the number of possible values of NN.

Solution

Solution:

Answer: 825957825957

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

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

- Case 2: 55 digits. Then, exactly one of the three numbers is between 11 and 99, inclusive. We consider cases on the presence of 00s in NN.

- No 00s. Then, we have 99 choices for each digit, for a total of 95=590499^{5} = 59049 choices.

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

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

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

- Case 3: 44 digits. Again, we casework on the presence of 00s.

- No 00s. Then, we have 94=65619^{4} = 6561 choices.

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

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

- Case 4: 33 digits. Then, we cannot have any 00s, so we have a total of 93=7299^{3} = 729 choices.

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

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.