2004 AIME II Problems/Problem 10
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
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 .
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 .
|2004 AIME II (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|