Question

Let $\mathcal{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 $\mathcal{S},$ the probability that it is divisible by $9$ is $\frac{p}{q},$ where $p$ and $q$ are relatively prime positive integers. Find $p + q.$

答案

Solution:

The set $\mathcal{S}$ consists of the $\binom{40}{2} = 780$ numbers $2^a + 2^b$ with $0 \le a \lt b \le 39.$ Since $2^a$ is coprime to $9,$ we have $9 \mid 2^a(2^{b-a} + 1)$ exactly when $2^{b-a} \equiv -1 \pmod{9}.$ The powers of $2$ modulo $9$ cycle through $2, 4, 8, 7, 5, 1$ with period $6,$ so $2^d \equiv 8 \equiv -1$ exactly when $d \equiv 3 \pmod{6}.$

For each difference $d = b - a$ there are $40 - d$ pairs, so the number of multiples of $9$ in $\mathcal{S}$ is $\sum_{d = 3, 9, \ldots, 39} (40 - d) = 37 + 31 + 25 + 19 + 13 + 7 + 1 = 133.$

The probability is $\frac{133}{780},$ and since $133 = 7 \cdot 19$ while $780 = 2^2 \cdot 3 \cdot 5 \cdot 13,$ it is in lowest terms. Thus $p + q = 133 + 780 = 913.$

2004 AIME II Problem 10

Solution:

Problem 10 in Other Years