设 $S$ 为所有介于 $1$ 与 ${{2}^{40}}$ 之间，且二进制表示式中恰有两个 $1$，其余为 $0$ 的整数组成的集合。从 $S$ 中随机取出一个数，设这个数被 $9$ 整除的概率为 $\frac{p}{q}$，其中 $p q$ 是互素的正整数。试求 $p+q$ 的值。
【难度】
【出处】
2004年第22届美国数学邀请赛Ⅱ（AIMEⅡ）
【标注】
【答案】
913
【解析】
$S$ 中的元素形如 ${{2}^{a}}+{{2}^{b}}$，其中 $0\leqslant a$，$b\leqslant 39$ 且 $a\ne b$，因此 $S$ 有 $C_{40}^{2}=780$ 个元素。不妨设 $ab$，注意到 $9$ 整除 ${{2}^{a}}+{{2}^{b}}={{2}^{a}}\left({{2}^{b-a}}+1 \right)$ 当且仅当 $9$ 整除 ${{2}^{b-a}}+1$，即当且仅当 ${{2}^{b-a}}\equiv 8\left(\bmod 9 \right)$ 时，有 $9\left|{{2}^{a}}+{{2}^{b}} \right.$ 。因为 ${{2}^{6}}\equiv 1\left( \bmod 9 \right)$，${{2}^{3}}\equiv 8\left(\bmod 9 \right)$，故当且仅当 $b-a=3\left(\bmod 6 \right)$ 时，有 $9\left|{{2}^{a}}+{{2}^{b}} \right.$ 。 $0$，$1$，$2$ …，$39$ 中被 $6$ 除余 $0$，$1$，$2$，$3$，$4$，$5$ 的数分别有 $7$，$7$，$7$，$7$，$6$，$6$ 个，故有 $7\times 7+7\times 6+7\times6=133$ 对 $\left(a b \right)$ 满足 $9\left|{{2}^{a}}+{{2}^{b}} \right.$ 。故从 $S$ 中随机取出一数可被 $9$ 整除的概率为 $\frac{133}{780}$，所以 $p+q=913$ 。
答案
解析
备注
