Question

对集合 $U = \{1, 2, 3, \ldots, 18\}$ 的每个子集 $T$ ，令 $s(T)$ 为 $T$ 中元素之和，并规定 $s(\emptyset)$ 为 $0.$ 若从 $U$ 的所有子集中随机选取 $T$ ，则 $s(T)$ 能被 $3$ 整除的概率为 $\frac{m}{n}$ ，其中 $m$ 与 $n$ 是互质正整数。求 $m$ 。

For each subset $T$ of $U = \{1, 2, 3, \ldots, 18\},$ let $s(T)$ be the sum of the elements of $T,$ with $s(\emptyset)$ defined to be $0.$ If $T$ is chosen at random among all subsets of $U,$ the probability that $s(T)$ is divisible by $3$ is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m.$

答案

答案：683

知识点：子集模运算组合范德蒙德卷积

难度评级：3060

解答：

集合 $U$ 在模 $3.$ 的每个剩余类中各有六个元素。若 $T$ 包含 $a$ 个 $\equiv 1$ 的元素和 $b$ 个 $\equiv 2 \pmod 3,$ 的元素，则 $s(T) \equiv a + 2b \equiv a - b \pmod 3,$ 所以 $3 \mid s(T)$ 当且仅当 $a \equiv b \pmod 3;$ 六个 $3$ 的倍数可自由选择，对有利数与总数都贡献因子 $2^6$ 。

由范德蒙德恒等式，选择这些 $a$ 与 $b$ 时，满足 $a - b = 0$ 的选法数为 $\sum_a \binom{6}{a}^2 = \binom{12}{6} = 924;$ 满足 $a - b = \pm 3$ 的选法数为 $2\sum_a \binom{6}{a}\binom{6}{a - 3} = 2\binom{12}{9} = 440;$ 满足 $a - b = \pm 6$ 的选法数为 $2.$ 有利选法为 $924 + 440 + 2 = 1366$ ，总数为 $2^{12}.$

概率为 $\frac{1366}{4096} = \frac{683}{2048}$ ，由于 $683$ 是奇数，已经最简。因此 $m = 683$ 。

The set $U$ contains six elements in each residue class modulo $3.$ If $T$ contains $a$ elements $\equiv 1$ and $b$ elements $\equiv 2 \pmod 3,$ then $s(T) \equiv a + 2b \equiv a - b \pmod 3,$ so $3 \mid s(T)$ exactly when $a \equiv b \pmod 3;$ the six multiples of $3$ may be included freely, contributing a factor $2^6$ to both the favorable and total counts.

By Vandermonde's identity, the number of ways to choose the $a$ s and $b$ s with $a - b = 0$ is $\sum_a \binom{6}{a}^2 = \binom{12}{6} = 924;$ with $a - b = \pm 3$ it is $2\sum_a \binom{6}{a}\binom{6}{a - 3} = 2\binom{12}{9} = 440;$ and with $a - b = \pm 6$ it is $2.$ The favorable choices number $924 + 440 + 2 = 1366$ out of $2^{12}.$

The probability is $\frac{1366}{4096} = \frac{683}{2048},$ which is in lowest terms since $683$ is odd. Thus $m = 683.$

2018 AIME I 第 12 题

答案：683

难度评级：3060

解答：

其他年份的第 12 题