AIME 2012 II · 第 7 题

Solution

Okay, an exercise in counting (lots of binomials to calculate!). In base 2, the first number is $11111111$, which is the only way to choose 8 1's out of 8 spaces, or $\binom{8}{8}$. What about 9 spaces? Well, all told, there are $\binom{9}{8}=9$, which includes the first 1. Similarly, for 10 spaces, there are $\binom{10}{8}=45,$ which includes the first 9. For 11 spaces, there are $\binom{11}{8}=165$, which includes the first 45. You're getting the handle. For 12 spaces, there are $\binom{12}{8}=495$, which includes the first 165; for 13 spaces, there are $\binom{13}{8}=13 \cdot 99 > 1000$, so we now know that $N$ has exactly 13 spaces, so the $2^{12}$ digit is 1.

Now we just proceed with the other 12 spaces with 7 1's, and we're looking for the $1000-495=505th$ number. Well, $\binom{11}{7}=330$, so we know that the $2^{11}$ digit also is 1, and we're left with finding the $505-330=175th$ number with 11 spaces and 6 1's. Now $\binom{10}{6}=210,$ which is too big, but $\binom{9}{6}=84.$ Thus, the $2^9$ digit is 1, and we're now looking for the $175-84=91st$ number with 9 spaces and 5 1's. Continuing the same process, $\binom{8}{5}=56$, so the $2^8$ digit is 1, and we're left to look for the $91-56=35th$ number with 8 spaces and 4 1's. But here $\binom{7}{4}=35$, so N must be the last or largest 7-digit number with 4 1's. Thus the last 8 digits of $N$ must be $01111000$, and to summarize, $N=1101101111000$ in base $2$. Therefore, $N = 8+16+32+64+256+512+2048+4096 \equiv 32 \pmod{1000}$, and the answer is $\boxed{032}$.

Video Solution

2012 AIME II #7

Math Problem Solving Skills