Difference between revisions of "2004 AIME II Problems/Problem 10"
Jackshi2006 (talk | contribs) (→Solution 3 (modular arithmetic)) |
Jackshi2006 (talk | contribs) (→Solution 3 (similar to 1)) |
||
Line 29: | Line 29: | ||
==Solution 3 (similar to 1)== | ==Solution 3 (similar to 1)== | ||
As mentioned above, there are 780 possible combinations. Since we are essentially adding two powers of two together, thinking about the properties of this sum organizes our solution. All powers of two are even except for <math>2^0</math>, so we begin with labeling an entire group "where one of the 1s is in the rightmost spot". In an equation, <math>2^n+1</math> is congruent to 0 mod 9. Instantly we think of <math>2^3=8</math>, and trial and error soon gives us <math>2^9=512</math>. Notice a pattern? Trying 2^15 = 32768 also works. You could go on, but basically all powers of two 3 mod 6 are 1 mod 9. (This is proven with the fact that <math>2^6</math> is 1 mod 9) There are seven 3 mod 6 powers of 2 from 1-39, so for our first category there are seven "good" combinations. | As mentioned above, there are 780 possible combinations. Since we are essentially adding two powers of two together, thinking about the properties of this sum organizes our solution. All powers of two are even except for <math>2^0</math>, so we begin with labeling an entire group "where one of the 1s is in the rightmost spot". In an equation, <math>2^n+1</math> is congruent to 0 mod 9. Instantly we think of <math>2^3=8</math>, and trial and error soon gives us <math>2^9=512</math>. Notice a pattern? Trying 2^15 = 32768 also works. You could go on, but basically all powers of two 3 mod 6 are 1 mod 9. (This is proven with the fact that <math>2^6</math> is 1 mod 9) There are seven 3 mod 6 powers of 2 from 1-39, so for our first category there are seven "good" combinations. | ||
+ | |||
Next, we look at powers of two exclusive from 1-39. Expressed in an equation, <math>2^n+2^m</math> is congruent to 0 mod 9. Since nine is a relatively small number, we can treat powers of two as remainders of nine, to find "good" combinations quickly. Making a list of powers of two from 1-6 shows that the remainders when divided by nine are 2, 4, 8, 7, 5, and 1. This repeats itself every 6 powers. With simple counting we see there are seven powers of two that give remainders of 2, 4, and 8 each. Also there are six powers of two two that give remainders of 7, 5, and 1 each. Notice that each trio of powers correspond with another in the opposite trio. WLOG, if you choose two, (which there are seven to select) there are six different sevens to pair. This gives <math>7*6</math>. Repeat for the other two pairs. | Next, we look at powers of two exclusive from 1-39. Expressed in an equation, <math>2^n+2^m</math> is congruent to 0 mod 9. Since nine is a relatively small number, we can treat powers of two as remainders of nine, to find "good" combinations quickly. Making a list of powers of two from 1-6 shows that the remainders when divided by nine are 2, 4, 8, 7, 5, and 1. This repeats itself every 6 powers. With simple counting we see there are seven powers of two that give remainders of 2, 4, and 8 each. Also there are six powers of two two that give remainders of 7, 5, and 1 each. Notice that each trio of powers correspond with another in the opposite trio. WLOG, if you choose two, (which there are seven to select) there are six different sevens to pair. This gives <math>7*6</math>. Repeat for the other two pairs. |
Revision as of 15:55, 29 June 2020
Problem
Let be the set of integers between
and
whose binary expansions have exactly two
's. If a number is chosen at random from
the probability that it is divisible by
is
where
and
are relatively prime positive integers. Find
Solution 1
A positive integer has exactly two 1s in its binary representation exactly when
for
nonnegative integers. Thus, the set
is equal to the set
. (The second condition ensures simultaneously that
and that each such number less than
is counted exactly once.) This means there are
total such numbers.
Now, consider the powers of mod
:
.
It's clear what the pairs can look like. If one is of the form
(7 choices), the other must be of the form
(7 choices). If one is of the form
(7 choices) the other must be of the form
(6 choices). And if one is of the form
(7 choices), the other must be of the form
(6 choices). This means that there are
total "good" numbers.
The probability is , and the answer is
.
Solution 2
Note that . Since
, multiplying by
gives
.
The solutions that work are in the form . Since
, all of the solutions are in this form or this form multiplied by
where
.
Now we just do casework:
So, the numerator is . The denominator is just
, so the probability is
, and the answer is
.
Solution 3 (similar to 1)
As mentioned above, there are 780 possible combinations. Since we are essentially adding two powers of two together, thinking about the properties of this sum organizes our solution. All powers of two are even except for , so we begin with labeling an entire group "where one of the 1s is in the rightmost spot". In an equation,
is congruent to 0 mod 9. Instantly we think of
, and trial and error soon gives us
. Notice a pattern? Trying 2^15 = 32768 also works. You could go on, but basically all powers of two 3 mod 6 are 1 mod 9. (This is proven with the fact that
is 1 mod 9) There are seven 3 mod 6 powers of 2 from 1-39, so for our first category there are seven "good" combinations.
Next, we look at powers of two exclusive from 1-39. Expressed in an equation, is congruent to 0 mod 9. Since nine is a relatively small number, we can treat powers of two as remainders of nine, to find "good" combinations quickly. Making a list of powers of two from 1-6 shows that the remainders when divided by nine are 2, 4, 8, 7, 5, and 1. This repeats itself every 6 powers. With simple counting we see there are seven powers of two that give remainders of 2, 4, and 8 each. Also there are six powers of two two that give remainders of 7, 5, and 1 each. Notice that each trio of powers correspond with another in the opposite trio. WLOG, if you choose two, (which there are seven to select) there are six different sevens to pair. This gives
. Repeat for the other two pairs.
In the end there are "good" combinations, for an answer of
.
-jackshi2006
See also
2004 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 9 |
Followed by Problem 11 | |
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.