2012 AIME II Problems/Problem 7
Contents
Problem 7
Let 
be the increasing sequence of positive integers whose binary representation has exactly 
ones. Let 
be the 1000th number in . Find the remainder when is divided by 
.
Solution
Okay, an exercise in counting (lots of binomials to calculate!). In base 2, the first number is 
, which is the only way to choose 8 1's out of 8 spaces, or 
. What about 9 spaces? Well, all told, there are 
, which includes the first 1. Similarly, for 10 spaces, there are 
which includes the first 9. For 11 spaces, there are 
, which includes the first 45. You're getting the handle. For 12 spaces, there are 
, which includes the first 165; for 13 spaces, there are 
, so we now know that has exactly 13 spaces, so the 
digit is 1.
Now we just proceed with the other 12 spaces with 7 1's, and we're looking for the 
number. Well, 
, so we know that the 
digit also is 1, and we're left with finding the 
number with 11 spaces and 6 1's. Now 
which is too big, but 
Thus, the 
digit is 1, and we're now looking for the 
number with 9 spaces and 5 1's. Continuing the same process, 
, so the 
digit is 1, and we're left to look for the 
number with 8 spaces and 4 1's. But here 
, so N must be the last or largest 7-digit number with 4 1's. Thus the last 8 digits of must be 
, and to summarize, 
in base 
. Therefore, 
, and the answer is 
.
Video Solution
See Also
Video Solution: https://www.youtube.com/watch?v=WRP--6Db1qw
| 2012 AIME II (Problems • Answer Key • Resources) | ||
| Preceded by Problem 6 |
Followed by Problem 8 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
