AIME 2007 II · 第 1 题

Solution 1

There are 7 different characters that can be picked, with 0 being the only number that can be repeated twice.

• If $0$ appears 0 or 1 times amongst the sequence, there are $\frac{7!}{(7-5)!} = 2520$ sequences possible.
• If $0$ appears twice in the sequence, there are ${5\choose2} = 10$ places to place the $0$s. There are $\frac{6!}{(6-3)!} = 120$ ways to place the remaining three characters. In total, that gives us $10 \cdot 120 = 1200$.

Thus, $N = 2520 + 1200 = 3720$, and $\frac{N}{10} = \boxed{372}$.

Solution 2

Another approach is to first falsely assume that the zeros are distinguishable and then correct the over-counting.

We can name the zeros $0_1$ and $0_2$. The first character has 8 choices - $A,I,M,E,2,0_1,0_2,$ and $7$. The second character has $7$ choices, the third has $6$ choices, the fourth has $5$ choices, and the fifth has $4$ choices. Multiplying them all together, there are $6,720$ arrangements where the zeros are distinguishable.

However, some cases with at most 2 zeros are over-counted. We can tackle this by going case by case for the number of zeros. When there are no zeros there will be no arrangements over-counted.

When there is exactly $1$ zero, all the cases are over-counted. This is because there will be another case with the exact same characters but the zero will be switched with the other zero. The number of ways to place the zero is $5$, there are $2$ zeros to choose from, and the remaining spots have $6 \cdot 5 \cdot 4 \cdot 3$ ways to place the non-zero characters. Thus, there are $5 \cdot 2 \cdot 6 \cdot 5 \cdot 4 \cdot 3 = 3,600$ arrangements where there is exactly one zero. However, we need to remove half of these or $1,800$ from the total yielding in $4,920$ arrangements left.

Cases with two zeros would also have to be corrected as the zeros are interchangeable and you can switch the ordering of them. The number of ways to place $0_1$ is $5$, the number of ways to place $0_2$ is $4$, and the remaining places have $6 \cdot 5 \cdot 4$ ways to place the remaining characters. In total, there are $5 \cdot 4 \cdot 6 \cdot 5 \cdot 4 = 2,400$ arrangements with exactly two zeros. However, we need to remove half of these or $1,200$ from the total yielding in $3,720$ arrangements left.

The max number of zeros is two so we have gone through all the cases and removed the over-counted arrangements thus giving, $N = 3,720$ and $\frac{N}{10} = \boxed{372}$.

~ Logicalrhino65