Question

设 $\mathcal{S}$ 是 $1$ 到 $2^{40}$ 之间、二元展开中恰有两个 $1$ 的整数集合。从 $\mathcal{S}$ 中随机选一个数，它能被 $9$ 整除的概率为 $\frac{p}{q}$ ，其中 $p$ 和 $q$ 是互质正整数。求 $p + q$ 。

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.$

答案

答案：913

知识点：进制模幂运算乘法阶数对计数

难度评级：2920

解答：

集合 $\mathcal{S}$ 由 $\binom{40}{2} = 780$ 个数 $2^a + 2^b$ 组成，其中 $0 \le a \lt b \le 39$ 。由于 $2^a$ 与 $9$ 互质， $9 \mid 2^a(2^{b-a} + 1)$ 当且仅当 $2^{b-a} \equiv -1 \pmod{9}$ 。 $2$ 的幂模 $9$ 依次循环为 $2, 4, 8, 7, 5, 1$ ，周期为 $6$ ，所以 $2^d \equiv 8 \equiv -1$ 当且仅当 $d \equiv 3 \pmod{6}$ 。

对每个差值 $d = b - a$ 有 $40 - d$ 个数对，所以 $\mathcal{S}$ 中 $9$ 的倍数个数为 $\begin{aligned} &\sum_{d = 3, 9, \ldots, 39} (40 - d) \\ &= 37 + 31 + 25 \\ &\quad {}+ 19 + 13 + 7 + 1 \\ &= 133. \end{aligned}$

概率为 $\frac{133}{780}$ 。因为 $133 = 7 \cdot 19$ ，而 $780 = 2^2 \cdot 3 \cdot 5 \cdot 13$ ，该分数已最简。因此 $p + q = 133 + 780 = 913$ 。

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 $\begin{aligned} &\sum_{d = 3, 9, \ldots, 39} (40 - d) \\ &= 37 + 31 + 25 \\ &\quad {}+ 19 + 13 + 7 + 1 \\ &= 133. \end{aligned}$

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 第 10 题

答案：913

难度评级：2920

解答：

其他年份的第 10 题