トップ› 東京大学› 1989年› 理系第6問

東京大学 1989年理系第6問解説

方針・初手

円順列の確率問題において、条件を方程式の整数解の個数に帰着させるのが定石である。無作為に環状に並べるため、すべての席を区別して赤玉を入れる場所を選ぶ組合せを全事象とし、それぞれの配置が等確率で起こると考える。3個の赤玉によって白玉は3つの区画に分割されるため、各区画の白玉の個数を $x, y, z$ とおき、和が $n$ になる非負整数解の条件に言い換えて処理する。

解法1

円形に並んだ $n+3$ 個の場所に番号をつけ、赤玉を置く3か所を選ぶ。この選び方は ${}_{n+3}\mathrm{C}_{3}$ 通りあり、無作為に並べることからこれらは同様に確からしい。

3つの赤玉によって白玉は3つの区画に分けられる。基準となる1つの赤玉を指定し、そこから時計回りに見た3つの区画の白玉の個数を順に $x, y, z$ とすると、$x+y+z=n$ ($x, y, z \geqq 0$) を満たす。

赤玉の配置 ${}_{n+3}\mathrm{C}_{3}$ 通りと、基準とする赤玉の選び方 3通りの組は、全体で $3 \times {}_{n+3}\mathrm{C}_{3}$ 通りある。一方で、$x+y+z=n \ (x, y, z \geqq 0)$ を満たす非負整数解 $(x,y,z)$ 1組に対して、基準の赤玉を $n+3$ 個の場所のどこに置くかを決めれば残りの赤玉の場所も自動的に決まるため、対応する配置の組は $n+3$ 通りある。これにより $3 \times {}_{n+3}\mathrm{C}_{3} = (n+3) \times {}_{n+2}\mathrm{C}_{2}$ が成り立ち、各非負整数解 $(x,y,z)$ は実際の配置において等しい重みを持つ。

したがって、求める確率は「方程式 $x+y+z=n \ (x, y, z \geqq 0)$ の解の総数のうち、条件を満たす解の割合」として計算できる。

方程式 $x+y+z=n \ (x, y, z \geqq 0)$ の解の総数を $N$ とすると、

$$ N = {}_{n+2}\mathrm{C}_{2} = \frac{(n+2)(n+1)}{2} $$

白玉が連続して $k+1$ 個以上並ばないための条件は、どの区画の白玉も $k$ 個以下となることである。すなわち、

$$ x \leqq k, \quad y \leqq k, \quad z \leqq k $$

この条件を満たす解の個数を $M$ とする。変数 $X, Y, Z$ を $X = k-x, Y = k-y, Z = k-z$ とおくと、元の条件は以下のように書き換えられる。

$$ (k-X) + (k-Y) + (k-Z) = n \iff X+Y+Z = 3k-n $$

ここで、問題の条件 $\frac{n}{3} \leqq k \leqq \frac{n}{2}$ を用いる。 $\frac{n}{3} \leqq k \iff n \leqq 3k$ より $3k-n \geqq 0$ であるため、非負整数解 $(X,Y,Z)$ は存在する。さらに、$k \leqq \frac{n}{2} \iff 2k \leqq n$ より $3k-n \leqq k$ であるため、解は $X+Y+Z \leqq k$ を満たす。

$X, Y, Z$ が非負整数であり、その和が $k$ 以下であるならば、それぞれの変数が $k$ を超えることはない。よって $X \leqq k, Y \leqq k, Z \leqq k$ は常に満たされ、同時に元の変数の条件 $x = k-X \geqq 0, y = k-Y \geqq 0, z = k-Z \geqq 0$ も自動的に満たされる。

ゆえに、求める解の個数 $M$ は、方程式 $X+Y+Z = 3k-n \ (X, Y, Z \geqq 0)$ の解の総数に等しい。

$$ M = {}_{(3k-n)+2}\mathrm{C}_{2} = \frac{(3k-n+2)(3k-n+1)}{2} $$

したがって、求める確率は以下のようになる。

$$ \frac{M}{N} = \frac{(3k-n+2)(3k-n+1)}{(n+2)(n+1)} $$

解法2

余事象と包除原理を用いて条件を満たす解の個数 $M$ を求める。全事象の解の個数 $N = \frac{(n+2)(n+1)}{2}$ である。

以下の3つの事象を考える。 $A$: $x \geqq k+1$ となる事象 $B$: $y \geqq k+1$ となる事象 $C$: $z \geqq k+1$ となる事象

事象 $A$ に含まれる解の個数 $n(A)$ は、$x' = x-(k+1)$ とおくと $x'+y+z = n-k-1 \ (x', y, z \geqq 0)$ の解の個数に等しい。

$$ n(A) = {}_{n-k+1}\mathrm{C}_{2} = \frac{(n-k+1)(n-k)}{2} $$

対称性より $n(A) = n(B) = n(C)$ である。

事象 $A \cap B$ に含まれる解の個数 $n(A \cap B)$ は、$x' = x-(k+1), y' = y-(k+1)$ とおくと $x'+y'+z = n-2k-2 \ (x', y', z \geqq 0)$ の解の個数に等しい。ここで $m=n-2k$ とおくと、式の形は $\frac{m(m-1)}{2}$ となる。問題の条件より $n-2k \geqq 0$ であるが、$n-2k=0, 1$ のときは $A \cap B = \emptyset$ となる。しかし、このとき式 $\frac{m(m-1)}{2}$ の値も自動的に $0$ となるため、場合分けをせずにそのまま解の個数として用いることができる。

$$ n(A \cap B) = \frac{(n-2k)(n-2k-1)}{2} $$

対称性より $n(A \cap B) = n(B \cap C) = n(C \cap A)$ である。

事象 $A \cap B \cap C$ は $x+y+z \geqq 3k+3$ を意味するが、条件より $n \leqq 3k < 3k+3$ なので空集合である。よって $n(A \cap B \cap C) = 0$。

包除原理より、求める個数 $M$ は以下のようになる。

$$ \begin{aligned} M &= N - n(A \cup B \cup C) \\ &= N - \{n(A)+n(B)+n(C)\} + \{n(A \cap B)+n(B \cap C)+n(C \cap A)\} - n(A \cap B \cap C) \\ &= \frac{(n+2)(n+1)}{2} - 3 \times \frac{(n-k+1)(n-k)}{2} + 3 \times \frac{(n-2k)(n-2k-1)}{2} \end{aligned} $$

この式の分子を $n$ について整理する。

$$ \begin{aligned} 2M &= (n^2+3n+2) - 3\{n^2-(2k-1)n+k^2-k\} + 3\{n^2-(4k+1)n+4k^2+2k\} \\ &= n^2 - (6k+3)n + 9k^2 + 9k + 2 \\ &= (3k-n)^2 + 3(3k-n) + 2 \\ &= (3k-n+1)(3k-n+2) \end{aligned} $$

したがって、求める確率は

$$ \frac{M}{N} = \frac{(3k-n+2)(3k-n+1)}{(n+2)(n+1)} $$

解説

円順列における確率を「方程式の非負整数解の個数」に帰着させる典型的な考え方がベースとなっている。同じ色の玉を区別せずに並べるモデルと、方程式の解が1対1で対応するように事象を設定することが重要である。

解法1で用いた「変数の上限」を「変数の下限（$0$以上）」に変換するテクニック（変数変換 $X = k-x$）は、場合の数の難問で非常に有効である。与えられた $\frac{n}{3} \leqq k \leqq \frac{n}{2}$ という条件が、この変換後に「すべての変数が $0$ 以上かつ和が $k$ 以下」になるように見事に設定されており、場合分けや包除原理の煩雑な計算を回避できる。作問者の意図が色濃く反映された鮮やかな解法である。