$2n$ 個の文字を各文字の候補として $n$ 文字のパスワードを作るとき, 重複する文字がない確率は \[\frac{{}_{2n}\mathrm P_n}{(2n)^n} = \frac{(2n)\cdots (n+1)}{(2n)^n}\] である. これが $\dfrac{1}{2}$ より小さいとき, 重複する文字がある確率が重複する文字がない確率より高くなる. よって, \[\frac{(2n)\cdots (n+1)}{(2n)^n} < \frac{1}{2}\] つまり \[ (2n)\cdots (n+1) < 2^{n-1}n^n \quad \cdots [1]\] を満たす正の整数 $n$ を求めればよい. \[\begin{aligned} &2 > 2^0\cdot 1^1, \quad 4\cdot 3 > 2^1\cdot 2^2, \quad 6\cdot 5\cdot 4 > 2^2\cdot 3^3, \\ &8\cdot 7\cdot 6\cdot 5 < 2^3\cdot 4^4 \end{aligned}\] であるから, この不等式を満たす最小の正の整数は $n = 4$ である. さらに, 与えられた $4$ 以上の整数 $n$ に対して $[\ast ]$ が成り立つとすると, \[ \frac{2n+1}{n+1} = 2-\frac{1}{n+1} < \left( 1+\frac{1}{n}\right)^n = \frac{(n+1)^n}{n^n} \quad \cdots [2]\] (二項定理により $\left( 1+\dfrac{1}{n}\right)^n > 1+n\cdot\dfrac{1}{n} = 2$) から \[\begin{aligned} &(2n+2)(2n+1)(2n)\cdots (n+2)(n+1) \\ &< (2n+2)(2n+1)2^{n-1}n^n \quad (\because [1]\times (2n+2)(2n+1)) \\ &= (n+1)2^n(2n+1)n^n \\ &< (n+1)2^n(n+1)^{n+1} \quad (\because [2]) \end{aligned}\] よって \[ (2n+2)\cdots (n+2) < 2^n(n+1)^{n+1}\] となる. ゆえに, $n \geqq 4$ のとき $[\ast ]$ が成り立つ.

　$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\] のときである.

(1)

$n$ チームが参加する総当たりのリーグ戦において, 全チームの勝敗の数が異なる場合の数は, $n$ チームを $1$ 位 ($n-1$ 勝 $0$ 敗) から最下位 ($0$ 勝 $n-1$ 敗) まで順位順に並べる方法の総数に等しく,

$n!$ 通り.

(2)

試合数は $\dfrac{n(n-1)}{2}$ であるから, 星取表の書き方は

$2^{\frac{n(n-1)}{2}}$ 通り.

(3)

ゆえに, 求める確率は, \[\frac{n!}{2^{\frac{n(n-1)}{2}}}\] である.

(1)

全チームが $n$ 勝 $n$ 敗で引き分ける星取表の書き方の総数を求める.

• まず, $1$ チーム ($\mathrm T_0$ と呼ぶ) の星取と, 残りのチームの $\mathrm T_0$ との試合の星取のみを書くとき, その場合の数は ${}_{2n}\mathrm C_n$ 通り.
• このとき, ちょうど $n-1$ チームが $1$ 勝 $0$ 敗になる. そのうちの $1$ チーム ($\mathrm T_1$ と呼ぶ) の星取と, 残りのチームの $\mathrm T_1$ との試合の星取のみを書き加えるとき, それは $\mathrm T_1$ の行の空欄 $2n-1$ 箇所のうち $n-1$ 箇所に白星を記すことで決まるから, その場合の数は ${}_{2n-1}\mathrm C_{n-1}$ 通り.
• これを続けていき, $r$ チーム $(1 \leqq r \leqq n)$ の空欄が埋まったとき, ちょうど $n-r+1$ チームが $r$ 勝 $0$ 敗になる (実際, 表を並べ替えると次のようになり, 右端の $(2n+1)-r-n = n-r+1$ 列には黒星のみが並ぶから, 表の対称性により下端の $n-r+1$ 行には白星のみが並ぶ).
  
  そのうちの $1$ チーム ($\mathrm T_r$ と呼ぶ) の星取と, 残りのチームの $\mathrm T_r$ との試合の星取のみを書き加えるとき (表の配列は元に戻しておく), それは $\mathrm T_r$ の行の空欄 $2n-r$ 箇所のうち $n-r$ 箇所に白星を記すことで決まるから, その場合の数は ${}_{2n-r}\mathrm C_{n-r}$ 通り.

この操作を $n$ チーム分繰り返せばそれらのチームと対戦した残り $n+1$ チームの星取も確定するから, 条件を満たす星取表の書き方は \[\begin{aligned} &{}_{2n}\mathrm C_n\cdots{}_{2n-r}\mathrm C_{n-r}\cdots{}_{n+1}\mathrm C_1 \\ &= {}_{2n}\mathrm C_n\cdots{}_{n+k}\mathrm C_k\cdots{}_{n+1}\mathrm C_1 \quad \cdots [1] \end{aligned}\] 通りある.

(2)

$2n+1$ チームが参加する総当たりのリーグ戦において, 試合数は $\dfrac{(2n+1)\cdot 2n}{2} = n(2n+1)$ であるから, 星取表の書き方は \[ 2^{n(2n+1)} \quad \cdots [2]\] 通りある.

(3)

$[1]\div [2]$ から, 求める確率は \[\frac{{}_{2n}\mathrm C_n\cdots{}_{n+k}\mathrm C_k\cdots{}_{n+1}\mathrm C_1}{2^{n(2n+1)}}\] である.

(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}$ 通りある.

(i), (ii) は同時に起こらないから, \[ a_n = (n-1)(a_{n-1}+a_{n-2}) \quad \cdots [1]\] が成り立つ.

(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}\] である.

(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}\] である.

(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}\] である.

　A, B の切り分け方で, $n$ 回ナイフを入れたときにできるピースの個数をそれぞれ $a_n,$ $b_n$ とおく.

(1)

A の切り分け方では, ナイフを入れる度に各ピースが $2$ 個のピースに分かれるから, $a_n = 2^n$ である.

(2)

B の切り分け方では, $n$ 回ナイフを入れた状態から新たに $1$ 回ナイフを入れていくと, 新たな切断面が既存の切断面との交線 $n$ 本により分割されてできる平面領域の個数 $p_n$ だけピースが増える.

(i)

まず, $1$ つの面が $n$ 本の直線により分割されてできる領域の個数の最大値 $p_n$ を求める. $n$ 本の直線をかいた状態から新たに $1$ 本の直線をかいていくと, 既存の直線と交わる度に領域が $1$ 個ずつ増え, 全部で $n+1$ 個の平面領域が増えるので, \[ p_{n+1}-p_n = n+1\] が成り立つ.

また, $p_1 = 2$ であるから, $n \geqq 2$ のとき \[\begin{aligned} p_n &= p_1+\sum_{k = 1}^{n-1}(p_{k+1}-p_k) \\ &= 2+\sum_{k = 1}^{n-1}(k+1) \\ &= 2+\frac{(n-1)n}{2}+(n-1) \\ &= \frac{1}{2}(n^2+n+2) \end{aligned}\] が成り立つ. これは $n = 1$ のときも成り立つ.

(ii)

次に, $b_n$ を求める. 上記の考察により, \[ b_{n+1}-b_n = p_n = \frac{1}{2}(n^2+n+2)\] が成り立つ. また, $b_1 = 2$ であるから, $n \geqq 2$ のとき \[\begin{aligned} &b_n = b_1+\sum_{k = 1}^{n-1}(b_{k+1}-b_k) \\ &= 2+\sum_{k = 1}^{n-1}\frac{1}{2}(k^2+k+2) \\ &= 2+\frac{1}{2}\left(\sum_{k = 1}^{n-1}k^2+\sum_{k = 1}^{n-1}k+\sum_{k = 1}^{n-1}2\right) \\ &= 2+\frac{1}{2}\left\{\frac{1}{6}(n\!-\!1)n(2n\!-\!1)+\frac{1}{2}(n\!-\!1)n+2(n\!-\!1)\right\} \end{aligned}\] であり, 展開して整理すると, \[\begin{aligned} b_n &= \frac{1}{6}(n+1)(n^2-n+6) \end{aligned}\] が得られる. これは $n = 1$ のときも成り立つ.

(3)

不等式 $a_n > b_n$ を解く. \[\begin{aligned} a_1 &= b_1 = 2, \quad a_2 = b_2 = 4, \quad a_3 = b_3 = 8, \\ a_4 &= 16 > 15 = b_4 \end{aligned}\] であるから, この不等式の最小の解は $n = 4$ である. さらに, 与えられた $4$ 以上の整数 $n$ に対して $a_n > b_n$ が成り立つとすると, \[ 2b_n-b_{n+1} = n(n-1)(n-2) > 0\] から得られる不等式 \[ 2 > \frac{b_{n+1}}{b_n}\] と辺々を掛け合わせることで \[ a_{n+1} = 2a_n > \frac{b_{n+1}}{b_n}\cdot b_n = b_{n+1}\] が得られる. よって, $a_n > b_n$ の解は $n \geqq 4$ である.