Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2012 AIME II Problems/Problem 7"

m (→‎Solution)
m (→‎Solution)
Line 6: Line 6:
 
Okay, an exercise in counting (lots of binomials to calculate!).  In base 2, the first number is <math>11111111</math>, which is the only way to choose 8 1's out of 8 spaces, or <math>\binom{8}{8}</math>.  What about 9 spaces?  Well, all told, there are <math>\binom{9}{8}=9</math>, which includes the first 1.  Similarly, for 10 spaces, there are <math>\binom{10}{8}=45,</math> which includes the first 9.  For 11 spaces, there are <math>\binom{11}{8}=165</math>, which includes the first 45.  You're getting the handle.  For 12 spaces, there are <math>\binom{12}{8}=495</math>, which includes the first 165; for 13 spaces, there are <math>\binom{13}{8}=13 \cdot 99 > 1000</math>, so we now know that <math>N</math> has exactly 13 spaces, so the <math>2^{12}</math> digit is 1.   
 
Okay, an exercise in counting (lots of binomials to calculate!).  In base 2, the first number is <math>11111111</math>, which is the only way to choose 8 1's out of 8 spaces, or <math>\binom{8}{8}</math>.  What about 9 spaces?  Well, all told, there are <math>\binom{9}{8}=9</math>, which includes the first 1.  Similarly, for 10 spaces, there are <math>\binom{10}{8}=45,</math> which includes the first 9.  For 11 spaces, there are <math>\binom{11}{8}=165</math>, which includes the first 45.  You're getting the handle.  For 12 spaces, there are <math>\binom{12}{8}=495</math>, which includes the first 165; for 13 spaces, there are <math>\binom{13}{8}=13 \cdot 99 > 1000</math>, so we now know that <math>N</math> has exactly 13 spaces, so the <math>2^{12}</math> digit is 1.   
  
−
Now we just proceed with the other 12 spaces with 7 1's, and we're looking for the <math>1000-495=505th</math> number.  Well, <math>\binom{11}{7}=330</math>, so we know that the <math>2^{11}</math> digit also is 1, and we're left with finding the <math>505-330=175th</math> number with 11 spaces and 6 1's.  Now <math>\binom{10}{6}=210,</math> which is too big, but <math>\binom{9}{6}=84.</math>  Thus, the <math>2^9</math> digit is 1, and we're now looking for the <math>175-84=91st</math> number with 9 spaces and 5 1's.  Continuing the same process, <math>\binom{8}{5}=56</math>, so the <math>2^8</math> digit is 1, and we're left to look for the <math>91-56=35th</math> number with 8 spaces and 4 1's.  But here <math>\binom{7}{4}=35</math>, so N must be the last or largest 7-digit number with 4 1's.  Thus the last 8 digits of <math>N</math> must be <math>01111000</math>, and to summarize, <math>N=1101101111000</math> in base <math>2</math>.  Therefore, <math>N = 8+16+32+64+256+512+2048+4096 \equiv 32 \pmod{1000}</math>, and the answer is <math>032</math>.
+
Now we just proceed with the other 12 spaces with 7 1's, and we're looking for the <math>1000-495=505th</math> number.  Well, <math>\binom{11}{7}=330</math>, so we know that the <math>2^{11}</math> digit also is 1, and we're left with finding the <math>505-330=175th</math> number with 11 spaces and 6 1's.  Now <math>\binom{10}{6}=210,</math> which is too big, but <math>\binom{9}{6}=84.</math>  Thus, the <math>2^9</math> digit is 1, and we're now looking for the <math>175-84=91st</math> number with 9 spaces and 5 1's.  Continuing the same process, <math>\binom{8}{5}=56</math>, so the <math>2^8</math> digit is 1, and we're left to look for the <math>91-56=35th</math> number with 8 spaces and 4 1's.  But here <math>\binom{7}{4}=35</math>, so N must be the last or largest 7-digit number with 4 1's.  Thus the last 8 digits of <math>N</math> must be <math>01111000</math>, and to summarize, <math>N=1101101111000</math> in base <math>2</math>.  Therefore, <math>N = 8+16+32+64+256+512+2048+4096 \equiv 32 \pmod{1000}</math>, and the answer is <math>\boxed{032}</math>.
  
 
== See Also ==
 
== See Also ==
 
{{AIME box|year=2012|n=II|num-b=6|num-a=8}}
 
{{AIME box|year=2012|n=II|num-b=6|num-a=8}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 15:29, 28 May 2018

Problem 7

Let $S$ be the increasing sequence of positive integers whose binary representation has exactly $8$ ones. Let $N$ be the 1000th number in $S$. Find the remainder when $N$ is divided by $1000$.


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}$.

See Also

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2012_AIME_II_Problems/Problem_7&oldid=94781"