共通テストから (3) - ノリの悪い日記

「モンモール (Montmort) のめぐりあいの問題」, もっと一般的には「包除原理 (The Principle of Inclusion and Exclusion; PIE)」——高校でも簡単な場合を習うが, シルヴェスター (Sylvester) は形式論理の定理として証明した*1 ——の応用なのだが, ここでは誘導に忠実に解くことにする.

$n$ 人で交換会が終了する場合の数を $s_n$ とおく. また $n$ 人で交換会が一回で終了する確率 $p_n$ は,

$\displaystyle{ p _n = \frac{s_n}{n!}}$

で与えられる.

$s_1 = 0$ , $p_1 = 0$ は明らか.

(1)(i)
$s_2= 2!- {}_2\mathrm{C}_1\cdot s_1 - {}_2\mathrm{C}_2 =1$
$\displaystyle{p_2=\frac{s_2}{2!}= \frac{1}{2}}$

(1)(ii)
$\begin{align} s_3 &= 3! - {}_3\mathrm{C}_1\cdot s_2 - {}_3\mathrm{C}_2 \cdot s_1 - {}_3\mathrm{C}_3\\ &= 6 - 3 -0-1\\ &= 2 \end{align}$
$\displaystyle{p_3 = \frac{s_3}{3!} = \frac{1}{3}}$

(1)(iii)
求める確率を $p$ とすると,
$\displaystyle{p \\= p_3 + (1-p_3)p_3 \\ \quad + (1-p_3)^2 p_3+ (1-p_3)^3p_3 \\ =1- \left(\frac{2}{3}\right)^4 \\=\frac{65}{81}}$

(2)
$s_4 \\ = 4! - {}_4\mathrm{C}_1\cdot s_3 - {}_4\mathrm{C}_2 \cdot s_2 -_4\mathrm{C}_3 \cdot s_1 - _4\mathrm{C}_4 \\= 24 - 4\cdot 2 - 6-0-1 \\=9$
$\displaystyle{p_4 = \frac{s_4}{4!} = \frac{3}{8}}$

(3)
$s_5 \\ = 5! - {}_5\mathrm{C}_1\cdot s_4 - {}_5\mathrm{C}_2 \cdot s_3 \\ \quad -_5\mathrm{C}_3 \cdot s_2 - _5\mathrm{C}_4 \cdot s_1 - _5\mathrm{C}_5 \\= 120- 5\cdot 9 - 10 \cdot 2 -10- 0-1 \\=44$
$\displaystyle{p_5 = \frac{s_5}{5!}= \frac{11}{30}}$

(4)
$E$ が自分のプレゼントを受け取るのは, $s_4$ 通り. $E$ が自分以外のプレゼントを受け取るのは, $s_5$ 通り. したがって, 求める条件付き確率は,

$\displaystyle{\frac{s_5}{s_4 + s_5} = \frac{44}{9 + 44} = \frac{44}{53}}$

※ 包除原理で求める. この場合, 全体集合 $\Omega$ の要素は任意に並べた $n$ 個のプレゼントの順列 ( $\Omega$ の濃度 $|\Omega| = n!$ ) で, 第 $i$ $\left(i \in \{1,2,\cdots, n\}\right)$ 番目に番号 $i$ のプレゼントがくる順列が部分集合 $P_i$ に入ると考え, どの部分集合 $P_i$ にも属さない要素 (順列)

$x \in \Omega -P_1 \cup P_2 \cup \cdots \cup P_n$

の個数を求めるという設定である.

$s_2 \\= 2!- {}_2\mathrm{C}_1\cdot 1! + {}_2\mathrm{C}_2 \\ =1$

$s_3 \\= 3! - {}_3\mathrm{C}_1\cdot 2! + {}_3\mathrm{C}_2 \cdot 1!- {}_3\mathrm{C}_3 \\= 6 - 6 + 3 -1 \\= 2$

$s_4 \\= 4! - {}_4\mathrm{C}_1\cdot 3! + {}_4\mathrm{C}_2 \cdot 2! - {}_4\mathrm{C}_3 \cdot 1! +{}_4\mathrm{C}_4 \\= 24 - 24 + 12 -4 + 1 \\= 9$

$s_5 \\= 5! - {}_5\mathrm{C}_1\cdot 4! + {}_5\mathrm{C}_2 \cdot 3! \\ \quad - {}_5\mathrm{C}_3 \cdot 2! +{}_5\mathrm{C}_4 \cdot 1! - {}_5\mathrm{C}_5 \\= 120 - 120 + 60-20 + 5 - 1 \\= 44$
//

※ 漸化式で求めると,
$s_1 =0$ , $s_2 = 1$ ,
$s_3 = (3-1)(s_1 + s_2) =2$
$s_4 = (4-1)(s_2 + s_3) =9$
$s_5 = (5-1)(s_3 + s_4) =44$
//

※ 漸化式の一般の証明の代わりに,
$s_5 = (5-1)(s_3 + s_4)$ を示す. 一般の場合の証明も同様にできる.

$s_4 \\= 4! - {}_4\mathrm{C}_1\cdot 3! + {}_4\mathrm{C}_2 \cdot 2! \\ \quad - {}_4\mathrm{C}_3 \cdot 1! +{}_4\mathrm{C}_4 \\= 4! (1 -1/1! + 1/2! - 1/3! + 1/4! )$

$s_3 \\= 3! - {}_3\mathrm{C}_1\cdot 2! + {}_3\mathrm{C}_2 \cdot 1!- {}_3\mathrm{C}_3 \\= 3! (1 -1/1! + 1/2! - 1/3! )$

$s_3 + s_4 \\= 5\cdot 3! (1 -1/1! + 1/2! - 1/3!) \\ +(-1 )^4$

$(5-1)(s_3 + s_4) \\= 5!( 1 -1/1! + 1/2! - 1/3!) \\ \quad + (4 + 1 -1)(-1 )^4 \\= 5!( 1-1/1! + 1/2! - 1/3!) \\ \quad + 5 \cdot (-1 )^4 +(-1)^5 \\= 5!( 1-1/1! + 1/2! - 1/3! \\ \quad + 1/4! - 1/5!) \\= s_5$
//

*1:『初等数学アラベスク』 (高橋進一著,1956) 参照. 包除原理 $\text{PIE}$ の証明は全体集合の要素数についての帰納法を使って, 二項定理からの帰結を利用するものが紹介されている. (他の証明もいろいろあって, 個人的には特性関数を使った証明が気に入っている. というのも, 二つの重要事項であるド・モルガンの法則と包除原理の関係を教えてくれるからだ.) この本は入試問題で取り上げられるようなネタを詳しく読みやすく解説してくれている.