2004 AIME II Problems/Problem 10
Contents
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 .
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.