Question

令 $S$ 为一个有六个元素的集合。令 $P$ 为 $S$ 的所有子集组成的集合。令 $A$ 和 $B$ 为 $S$ 的两个子集，两者可以相同，并从 $P$ 中相互独立地随机选取。 $B$ 是 $A$ 或 $S - A$ 中至少一个集合的子集，这一事件的概率为 $\frac{m}{n^r}$ ，其中 $m$ 、 $n$ 、 $r$ 是正整数， $n$ 是质数，且 $m$ 与 $n$ 互质。求 $m + n + r$ 。（集合 $S - A$ 是 $S$ 中不属于 $A$ 的所有元素组成的集合。）

Let $S$ be a set with six elements. Let $P$ be the set of all subsets of $S.$ Subsets $A$ and $B$ of $S,$ not necessarily distinct, are chosen independently and at random from $P.$ The probability that $B$ is contained in at least one of $A$ or $S - A$ is $\frac{m}{n^r},$ where $m,$ $n,$ and $r$ are positive integers, $n$ is prime, and $m$ and $n$ are relatively prime. Find $m + n + r.$ (The set $S - A$ is the set of all elements of $S$ which are not in $A.$ )

答案

答案：710

知识点：子集基本概率容斥原理二项式定理

难度评级：2840

小提示：

按 $|A| = k$ 分类，并数集合 $B$ ：它满足 $B \subseteq A$ 或 $B \subseteq S - A$ ；只有空集同时满足两者。

Condition on $|A| = k$ and count the sets $B$ with $B \subseteq A$ or $B \subseteq S - A;$ only the empty set satisfies both

大提示：

对 $k$ 求和 $\binom{6}{k}\left(2^k + 2^{6-k} - 1\right)$ ，并使用 $\sum_k \binom{6}{k} 2^k = 3^6$ 。

Sum over $k$ the expression $\binom{6}{k}\left(2^k + 2^{6-k} - 1\right)$ using $\sum_k \binom{6}{k} 2^k = 3^6$

解答：

固定集合 $A$ ，并设 $|A| = k$ 。有 $2^k$ 个子集满足 $B \subseteq A$ ，有 $2^{6-k}$ 个子集满足 $B \subseteq S - A$ ，且只有空集被重复计算，所以有 $2^k + 2^{6-k} - 1$ 种 $B$ 成功。因为共有 $\binom{6}{k}$ 个集合 $A$ ，其大小为 $k$ ，且各有 $2^6$ 种选择来确定 $A$ 和 $B$ ，所以概率为 $\begin{aligned} &\frac{1}{2^{12}}\sum_{k=0}^{6} \binom{6}{k}\left(2^k + 2^{6-k} - 1\right) \\ &= \frac{2 \cdot 3^6 - 2^6}{2^{12}} \end{aligned}\text{，}$ 这里用到了 $\sum_k \binom{6}{k} 2^k = \sum_k \binom{6}{k} 2^{6-k}$ $= (1+2)^6 = 3^6$ 。

化简为 $\frac{3^6 - 2^5}{2^{11}} = \frac{697}{2^{11}}$ 。因为 $697 = 17 \cdot 41$ 是奇数，所以 $m = 697$ 、 $n = 2$ 、 $r = 11$ ，因而 $m + n + r = 710$ 。

Fix $A$ with $|A| = k.$ There are $2^k$ subsets $B \subseteq A$ and $2^{6-k}$ subsets $B \subseteq S - A,$ and only the empty set is counted twice, so $2^k + 2^{6-k} - 1$ choices of $B$ succeed. Since there are $\binom{6}{k}$ sets $A$ of size $k$ and $2^6$ choices for each of $A$ and $B,$ the probability is $\begin{aligned} &\frac{1}{2^{12}}\sum_{k=0}^{6} \binom{6}{k}\left(2^k + 2^{6-k} - 1\right) \\ &= \frac{2 \cdot 3^6 - 2^6}{2^{12}}, \end{aligned}$ using $\sum_k \binom{6}{k} 2^k = \sum_k \binom{6}{k} 2^{6-k}$ $= (1+2)^6 = 3^6.$

This simplifies to $\frac{3^6 - 2^5}{2^{11}} = \frac{697}{2^{11}}.$ Since $697 = 17 \cdot 41$ is odd, we take $m = 697,$ $n = 2,$ $r = 11,$ and $m + n + r = 710.$

2007 AIME II 第 10 题

答案：710

难度评级：2840

小提示：

大提示：

解答：

其他年份的第 10 题