Difference between revisions of "2012 AIME II Problems/Problem 7"
Williamhu888 (talk | contribs) (Created page with "== Problem 7 == Let <math>S</math> be the increasing sequence of positive integers whose binary representation has exactly <math>8</math> ones. Let <math>N</math> be the 1000th n...") |
m (→Video Solution) |
||
(11 intermediate revisions by 10 users not shown) | |||
Line 1: | Line 1: | ||
== Problem 7 == | == Problem 7 == | ||
Let <math>S</math> be the increasing sequence of positive integers whose binary representation has exactly <math>8</math> ones. Let <math>N</math> be the 1000th number in <math>S</math>. Find the remainder when <math>N</math> is divided by <math>1000</math>. | Let <math>S</math> be the increasing sequence of positive integers whose binary representation has exactly <math>8</math> ones. Let <math>N</math> be the 1000th number in <math>S</math>. Find the remainder when <math>N</math> is divided by <math>1000</math>. | ||
+ | |||
+ | |||
+ | == Solution == | ||
+ | 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>\boxed{032}</math>. | ||
+ | |||
+ | |||
+ | == Video Solution == | ||
+ | [https://youtu.be/d2UTg7OsYuE?si=-s4Ze-bsE2w-J5ij 2012 AIME II #7] | ||
+ | |||
+ | [https://mathproblemsolvingskills.wordpress.com/ Math Problem Solving Skills] | ||
+ | |||
+ | == See Also == | ||
+ | Video Solution: | ||
+ | https://www.youtube.com/watch?v=WRP--6Db1qw | ||
+ | |||
+ | {{AIME box|year=2012|n=II|num-b=6|num-a=8}} | ||
+ | |||
+ | [[Category:Intermediate Combinatorics Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 20:09, 19 July 2024
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.