集合 $S$ 有 $6$ 个元素，$P$ 为集合 $S$ 的所有子集构成的集合，从 $P$ 中分别完全随机地选出 $S$ 的子集 $A$，$B$（两个子集不必不同），设集合 $B$ 包含于 $A$ 或 $S-A$ 中至少一个的概率为 $\frac{m}{{{n}'}}$，其中 $m$，$n$，$r$ 为正整数，$n$ 是素数，$m$，$n$ 互素，试求 $m+n+r$（$S$ 中不属于 $A$ 的所有元素组成的集合定义为 $S-A$）。
【难度】
【出处】
2007年第25届美国数学邀请赛Ⅱ（AIMEⅡ）
【标注】
【答案】
710
【解析】
$S$ 有 ${{2}^{6}}$ 个子集，对于 $0\leqslant K\leqslant 6$，$S$ 共有 $C_{6}^{k}$ 个 $k$ 元子集，因此集合 $A$ 中有 $k$ 个元素的概率为 $\frac{C_{6}^{k}}{{{2}^{6}}}$ 。若 $A$ 有 $k$ 个元素，那么 $S$ 有 ${{2}^{k}}$ 个子集包含于 $A$，${{2}^{6-k}}$ 个子集包含于 $S-A$，而空集同时属于集合 $A$ 和 $S-A$，因此 $B$ 包含于 $A$ 或 $S-A$ 中至少一个的概率为 $\frac{{{2}^{k}}+{{2}^{6-k}}-1}{{{2}^{6}}}$ 。因为所求的概率为
$\displaystyle \sum\limits_{k=0}^{6}{\frac{C_{6}^{k}}{{{2}^{6}}}}\cdot\frac{{{2}^{k}}+{{2}^{6-k}}-1}{{{2}^{6}}}=\frac{1}{{{2}^{12}}}\left(\sum\limits_{k=0}^{6}{{{2}^{k}}}C_{6}^{k}+\sum\limits_{k=0}^{6}{{{2}^{6-k}}}C_{6}^{k}-\sum\limits_{k=0}^{6}{{}}C_{6}^{k}\right)$
$\displaystyle =\frac{1}{{{2}^{12}}}\left(2\sum\limits_{k=0}^{6}{{{2}^{k}}C_{6}^{k}}-\sum\limits_{k=0}^{6}{C_{6}^{k}}\right)=\frac{1}{{{2}^{12}}}\left( 2\cdot {{3}^{6}}-{{2}^{6}} \right)$
$=\frac{{{3}^{6}}-{{2}^{5}}}{{{2}^{11}}}=\frac{697}{{{2}^{11}}}$
故 $m+n+r=697+2+11=710$ 。
【点评】令 $S=\left\{ 1 2 3 \\ 4 5 6 \right\}$，${{S}_{1}}=A$，${{S}_{2}}=B$ 。设 $M$ 为 $6\times 2$ 的矩阵，其中当 $i\in {{S}_{j}}$ 时，${{m}_{ij}}=1$，否则 ${{m}_{ij}}=0$，存在 ${{2}^{12}}$ 个这样的矩阵。注意到 $B\subseteq A$ 时，$M$ 的每一列为 $11$，$10$ 或 $00$ 。共有 ${{3}^{6}}$ 个这样的矩阵。同理，$B\subseteq S-A$ 时 $M$ 的每一列为 $01$，$00$ 或 $10$，同样这样的矩阵有 ${{3}^{6}}$ 个。这两种矩阵的交集是每列为 $00$ 或 $10$，有 ${{2}^{6}}$ 个矩阵。所求的概率为
$\frac{{{3}^{6}}+{{3}^{6}}-{{2}^{6}}}{{{2}^{12}}}=\frac{2\cdot{{3}^{6}}-{{2}^{6}}}{{{2}^{12}}}=\frac{{{3}^{6}}-{{2}^{5}}}{{{2}^{11}}}=\frac{697}{{{2}^{11}}}$，
以下同原解法。
$\displaystyle \sum\limits_{k=0}^{6}{\frac{C_{6}^{k}}{{{2}^{6}}}}\cdot\frac{{{2}^{k}}+{{2}^{6-k}}-1}{{{2}^{6}}}=\frac{1}{{{2}^{12}}}\left(\sum\limits_{k=0}^{6}{{{2}^{k}}}C_{6}^{k}+\sum\limits_{k=0}^{6}{{{2}^{6-k}}}C_{6}^{k}-\sum\limits_{k=0}^{6}{{}}C_{6}^{k}\right)$
$\displaystyle =\frac{1}{{{2}^{12}}}\left(2\sum\limits_{k=0}^{6}{{{2}^{k}}C_{6}^{k}}-\sum\limits_{k=0}^{6}{C_{6}^{k}}\right)=\frac{1}{{{2}^{12}}}\left( 2\cdot {{3}^{6}}-{{2}^{6}} \right)$
$=\frac{{{3}^{6}}-{{2}^{5}}}{{{2}^{11}}}=\frac{697}{{{2}^{11}}}$
故 $m+n+r=697+2+11=710$ 。
【点评】令 $S=\left\{ 1 2 3 \\ 4 5 6 \right\}$，${{S}_{1}}=A$，${{S}_{2}}=B$ 。设 $M$ 为 $6\times 2$ 的矩阵，其中当 $i\in {{S}_{j}}$ 时，${{m}_{ij}}=1$，否则 ${{m}_{ij}}=0$，存在 ${{2}^{12}}$ 个这样的矩阵。注意到 $B\subseteq A$ 时，$M$ 的每一列为 $11$，$10$ 或 $00$ 。共有 ${{3}^{6}}$ 个这样的矩阵。同理，$B\subseteq S-A$ 时 $M$ 的每一列为 $01$，$00$ 或 $10$，同样这样的矩阵有 ${{3}^{6}}$ 个。这两种矩阵的交集是每列为 $00$ 或 $10$，有 ${{2}^{6}}$ 个矩阵。所求的概率为
$\frac{{{3}^{6}}+{{3}^{6}}-{{2}^{6}}}{{{2}^{12}}}=\frac{2\cdot{{3}^{6}}-{{2}^{6}}}{{{2}^{12}}}=\frac{{{3}^{6}}-{{2}^{5}}}{{{2}^{11}}}=\frac{697}{{{2}^{11}}}$，
以下同原解法。
答案
解析
备注
