本格数学クイズ (組合せ論)
確率に関する問題でも, 組合せ論的な意味合いが強い問題はこちらに掲載しています.
場合の数
クイズ《試合数》
総当たりのリーグ戦の試合数, トーナメント戦で優勝チームを決めるのに必要な試合数を比較するとき, 前者が後者を上回るのは, 参加チームが何チーム以上のときか.
(有名問題)
答え
$3$ チーム以上.
解説
$n$ を $2$ 以上の整数とする.
- (1)
- $n$ チームが総当たりのリーグ戦を行うときの試合数を求める. 各チームの試合数は $n-1$ である. のべ $n(n-1)$ チームが出場するが, 各試合で $2$ チームが出場するから, 試合数は全部で $\dfrac{n(n-1)}{2}$ である.
- (2)
- $n$ チームがトーナメント戦で優勝チームを決めるのに必要な試合数を求める. トーナメント戦では, $1$ 試合ごとにちょうど $1$ チームの敗者が決まり, 最後に $1$ 度も負けなかった $1$ チームが優勝するから, 必要な試合数は $n-1$ である.
- (3)
- (1), (2) の試合数を比較する. \[\frac{n(n-1)}{2}-(n-1) = \frac{(n-1)(n-2)}{2}\] から \[\frac{n(n-1)}{2} > n-1 \iff n < 1,\ 2 < n\] であり, $n$ は $2$ 以上の整数であるから, (1) の試合数が (2) の試合数を上回るのは \[ n \geqq 3\] のときである.
クイズ《完全順列の割合》
$n$ 人 $(n \geqq 2)$ の席替えで全員の席が替わる確率 $p_n$ の最大値, 最小値はいくらか (高校生向け).
また, $n$ が大きくなるにつれて $p_n$ はどのような値に近づいていくか (大学生向け).
(有名問題)
答え
最大値は $\dfrac{1}{2},$ 最小値は $\dfrac{1}{3},$ 近づいていく値は $\dfrac{1}{e}$ ($e$: ネイピア数).
解説
- (1)
- まず, $n$ 人の席替えで全員の席が替わる場合の数 $a_n$ について, 数列 $\{ a_n\}$ の漸化式を導く.
便宜的に $a_1 = 0$ と定め, $n \geqq 3$ とする.
特定の人物 A, 残った $n-1$ 人の順に行っても, 場合の数は変わらない.
A が移動する方法は $n-1$ 通り.
A の移動先にいる人物を B として, いったん A と B の席を入れ替える.
- (i)
- 最後に A と B が入れ替わらない場合. 全員の席が替わる方法は, A 以外の $n-1$ 人全員の席が替わる $a_{n-1}$ 通りある.
- (ii)
- 最後に A と B が入れ替わる場合. 全員の席が替わる方法は, 残りの $n-2$ 人全員の席が替わる $a_{n-2}$ 通りある.
- (2)
- 次に, 数列 $\{ p_n\}$ の一般項を求める. 便宜的に $p_1 = 0$ と定める. $n$ 人が席替えをする方法は $n!$ 通りあるから, \[ p_n = \dfrac{a_n}{n!}\] である. $n \geqq 3$ のとき, $[1]$ の両辺を $n!$ で割ると, \[\begin{aligned} p_n &= \frac{(n-1)(a_{n-1}+a_{n-2})}{n!} \\ &= \frac{n-1}{n}\cdot\frac{a_{n-1}}{(n-1)!}+\frac{1}{n}\cdot\frac{a_{n-2}}{(n-2)!} \\ &= \left( 1-\frac{1}{n}\right) p_{n-1}+\frac{1}{n}p_{n-2} \\ p_n-p_{n-1} &= -\frac{1}{n}(p_{n-1}-p_{n-2}) \quad \cdots [2] \end{aligned}\] が得られる. $p_2-p_1 = \dfrac{1}{2} \neq 0,$ $[2]$ と数学的帰納法により, \[ p_n-p_{n-1} \neq 0\] である. $[2]$ において $n$ を $3$ 以上 $n$ 以下の各整数に置き換えながら辺々を掛け合わせて $p_k-p_{k-1}$ $(3 \leqq k \leqq n-1)$ で割ると, \[ p_n-p_{n-1} = (-1)^{n-2}\frac{p_2-p_1}{n(n-1)\cdots 3} = \frac{(-1)^n}{n!}\] となる. $0! = 1$ であるから, $n \geqq 2$ のとき \[ p_n = \sum\limits_{k = 0}^n\frac{(-1)^k}{k!}\] が成り立つ.
- (3)
- 数列 $\{ p_n\}$ の最大値, 最小値を求める. \[\begin{aligned} (-1)^k\frac{1}{k!}+(-1)^{k+1}\frac{1}{(k+1)!} &= (-1)^k\frac{(k+1)-1}{(k+1)!} \\ &= (-1)^k\frac{k}{(k+1)!} \end{aligned}\] は $k$ が偶数のとき正, $k$ が奇数のとき負であるから, $\{ p_{2n}\}$ は単調増加, $\{ p_{2n-1}\}$ は単調減少である. よって, $n \geqq 2$ において $p_n$ は, $n = 2$ のとき最大値 $\dfrac{1}{2},$ $n = 3$ のとき最小値 $\dfrac{1}{2}-\dfrac{1}{3!} = \dfrac{1}{3}$ をとる.
- (4)
- 数列 $\{ p_n\}$ の極限値を求める. 指数関数のマクローリン展開 \[ e^x = \displaystyle\sum_{n = 0}^\infty\frac{x^n}{n!}\] (こちらを参照) から, \[\lim_{n \to \infty}p_n = \sum_{n = 0}^\infty\frac{(-1)^n}{n!} = e^{-1} = \frac{1}{e}\] である.
参考
- それぞれをもとの位置と異なる位置に並べ替える順列は「完全順列」または「攪乱順列」(derangement) と呼ばれる. $n$ 個のものの「完全順列」の総数は「モンモール数」(Montmort number) と呼ばれ, $!n$ で表すことが多い ($n \leqq 15$ のときの値はこちらを参照). その値 \[ !n = n!\sum\limits_{k = 0}^n\frac{(-1)^k}{k!}\] を求める問題は「モンモールの問題」として知られている.
- $n$ 個のものの順列全体に占める「完全順列」の割合は, $n$ が大きくなるにつれて \[\frac{1}{e} = 0.3678794411\cdots\] に近づいていく.
クイズ《番勝負が最終戦までもつれ込む確率》
A, B の $2$ 人が $2n−1$ 番勝負 ($n$: 正の整数) を行うとき, 対戦が最終戦までもつれ込む確率はいくらか.
ただし, A, B の実力は互角であり, 引き分けはないとする.
(オリジナル)
答え
$\dfrac{n}{2n-1}.$
解説
- (1)
- まず, 最終戦までもつれ込む場合の数を求める. 最終戦で A が優勝するには第 $2n-2$ 戦目までに A が $n-1$ 勝して最終戦で A が勝てばよいから, その場合の数は ${}_{2n-2}\mathrm C_{n-1}$ である. 最終戦で B が優勝する場合の数もこれに等しい. よって, 最終戦までもつれ込む場合の数は, \[ 2\cdot{}_{2n-2}\mathrm C_{n-1} \quad \cdots [1]\] である.
- (2)
- 次に, A, B の勝ち星の取り方の総数を求める. 第 $m$ 戦 $(n \leqq m \leqq 2n-1)$ で A が優勝するには第 $m-1$ 戦までに A が $n-1$ 勝して第 $m$ 戦で勝てばよいから, その場合の数は ${}_{m-1}\mathrm C_{n-1}$ である. 第 $m$ 戦で B が優勝する場合の数もこれに等しい. よって, A, B の勝ち星の取り方の総数は, \[ 2\sum_{m = n}^{2n-1}{}_{m-1}\mathrm C_{n-1} = 2\sum_{k = n-1}^{2n-2}{}_k\mathrm C_{n-1} = 2\cdot{}_{2n-1}\mathrm C_n \quad \cdots [2]\] である. ここで,「ホッケー・スティック恒等式」 \[\sum\limits_{k = r}^N{}_k\mathrm C_r = {}_{N+1}\mathrm C_{r+1}\] を使った (こちらを参照).
- (3)
- $[1]\div [2]$ から, 求める確率は \[\frac{{}_{2n-2}\mathrm C_{n-1}}{{}_{2n-1}\mathrm C_n} = \frac{(2n-2)!}{(n-1)!(n-1)!}\div\frac{(2n-1)!}{n!(n-1)!} = \frac{n}{2n-1}\] である.
参考
\[\lim\limits_{n \to \infty}\frac{n}{2n-1} = \lim\limits_{n \to \infty}\frac{1}{2-\dfrac{1}{n}} = \frac{1}{2}\]
であるから, $n$ が大きくなるにつれて $2n-1$ 番勝負が最終戦までもつれ込む確率は $\dfrac{1}{2}$ に近づいていく.
クイズ《番勝負でリードを許さずに優勝する確率》
A, B の $2$ 人が $2n−1$ 番勝負 ($n$: 正の整数) を行うとき, A が B に $1$ 度もリードを許さずに優勝する確率はいくらか.
ただし, A, B の実力は互角であり, 引き分けはないとする.
(オリジナル)
答え
$\dfrac{1}{2n}.$
解説
- (1)
- A が B に $1$ 度もリードを許さずに優勝する場合の数は, 優勝者が決まった後は両者が $n$ 勝 $n$ 敗になるまで優勝者が勝ちを譲るという取り決めのもとで $2n$ 回の勝負をするとき, A の負けが先行しない場合の数に他ならず, $n$ 番目の「カタラン数」 \[ C_n = \frac{{}_{2n}\mathrm C_n}{n+1} = \frac{(2n)!}{(n+1)!n!} \quad \cdots [1]\] (こちらを参照) に等しい.
- (2)
- A, B の勝ち星の取り方の総数は, $0$ 以上 $n-1$ 以下の各整数 $l$ に対して, A が $n$ 勝 $l$ 敗で優勝する場合の数も B が $n$ 勝 $l$ 敗で優勝する場合の数も ${}_{n+l}\mathrm C_n$ であることから, \[\begin{aligned} 2\sum\limits_{l = 0}^{n-1}{}_{n+l}\mathrm C_n &= 2\sum\limits_{k = n}^{2n-1}{}_k\mathrm C_n = 2\cdot{}_{2n}\mathrm C_{n+1} \\ &= \frac{2(2n)!}{(n+1)!(n-1)!} \quad \cdots [2] \end{aligned}\] である. ここで, 前問でも使った「ホッケー・スティック恒等式」 \[\sum\limits_{k = r}^N{}_k\mathrm C_r = {}_{N+1}\mathrm C_{r+1}\] を使った (こちらを参照).
- (3)
- $[1]\div [2]$ から, 求める確率は, \[\frac{(2n)!}{(n+1)!n!}\div\frac{2(2n)!}{(n+1)!(n-1)!} = \frac{1}{2n}\] である.
参考
互いに区別のできない $2n$ 個のものを A, B に $1$ 個ずつ配っていき, 両者が合計 $n$ 個ずつもつようにするとき,
どの時点でも A の個数が B の個数を下回らないような場合の数 $C_n$ は, $n$ 番目の「カタラン数」(Catalan number) と呼ばれ,
\[ C_n = \frac{{}_{2n}\mathrm C_n}{n+1}\]
であることが知られている.