### Instruction: Let $S$ be the set of integers between $1$ and $2^{40}$ whose binary expansions have exactly two $1$'s. If a number is chosen at random from $S,$ the probability that it is divisible by $9$ is $p/q,$ where $p$ and $q$ are relatively prime positive integers. Find $p+q.$.### Response: I need to find the size of $S,$ the number of elements in $S$ that are divisible by $9,$ and then the ratio of these two numbers.
To find the size of $S,$ I can use the fact that every element of $S$ has exactly two $1$'s in its binary expansion.
That means that every element of $S$ is of the form $2^a + 2^b,$ where $a$ and $b$ are distinct nonnegative integers less than $40.$
There are $\binom{40}{2}$ ways to choose $a$ and $b,$ so that is the size of $S.$
To find the number of elements in $S$ that are divisible by $9,$ I can use the fact that $9 = 2^3 + 2^0.$
That means that $2^a + 2^b$ is divisible by $9$ if and only if $a$ and $b$ are both multiples of $3.$
There are $14$ multiples of $3$ between $0$ and $40,$ so there are $\binom{14}{2}$ ways to choose $a$ and $b$ that are both multiples of $3.$
That is the number of elements in $S$ that are divisible by $9.$
The probability that a randomly chosen element of $S$ is divisible by $9$ is then the ratio of these two numbers.
I can simplify this ratio by canceling out common factors.
The ratio is $\frac{\binom{14}{2}}{\binom{40}{2}} = \frac{91}{780}.$
The numerator and denominator are already relatively prime, so I don't need to reduce the fraction further.
The answer is the sum of the numerator and the denominator, which is $91 + 780 = 871.$