名古屋大学 2011年度理系数学第2問解答・解説

問題

$A_{0} = (0000)$ とする．整数 $n ≧ 1$ に対して，次の試行により行列 $A_{n - 1}$ から行列 $A_{n}$ を定める．

「数字の組 $(1, 1)$ ， $(1, 2)$ ， $(2, 1)$ ， $(2, 2)$ を1つずつ書いた4枚の札が入っている袋から1枚を取り出し，その札に書かれている数字の組が $(i, j)$ のとき， $A_{n - 1}$ の $(i, j)$ 成分に1を加えた行列を $A_{n}$ とする．」

この試行を $n$ 回 $(n = 2, 3, 4, \dots)$ くり返した後に， $A_{0}$ ， $A_{1}$ ， $\dots$ ， $A_{n - 1}$ が逆行列をもたず $A_{n}$ は逆行列をもつ確率を $p_{n}$ とする．

(1) $p_{2}$ ， $p_{3}$ を求めよ．

(2) $(n - 1)$ 回 $(n = 2, 3, 4, \dots)$ の試行をくり返した後に， $A_{n - 1}$ の第1行の成分がいずれも正で第2行の成分はいずれも0である確率 $q_{n - 1}$ を求めよ．

(3) $p_{n}$ $(n = 2, 3, 4, \dots)$ を求めよ．

出典：名古屋大学 2011年度前期日程第2次学力試験理系第2問

方針

各試行は4つの成分のうち1つを1増やす操作であり、 $2 \times 2$ 行列が正則になるかは行列式で判定する。(1) は短い列を直接数える。2回目で初めて正則になるには対角または反対角の2成分を1回ずつ選ぶ。3回目では、2回後に同じ1成分だけが正の場合と、同じ行または同じ列の2成分が正の場合から、3回目に外側を選ぶ場合を数える。(2) は第1行の2成分だけが正になる確率で、 $(1, 1), (1, 2)$ だけを使い、かつ両方が少なくとも1回出る場合を数える。(3) は初めて正則になる直前の状態が、1つの行・列に限られる場合、または1成分だけの場合に分かれることを使って一般項を出す。

解答

(1)

2回の試行後に初めて正則になる場合を考える。1回後の行列は1つの成分だけが1で、必ず正則でない。2回後に正則になるには、選ばれた2つの成分が対角成分 $(1, 1), (2, 2)$ であるか、反対角成分 $(1, 2), (2, 1)$ であればよい。それぞれ順序が2通りあるので、有利な列は $2 + 2 = 4$ 通りである。全体は $4^{2}$ 通りだから $p_{2} = \frac{4}{4 ^{2}} = \frac{1}{4}$ である。

次に $p_{3}$ を求める。3回目で初めて正則になるには、2回後までは正則でなく、3回目で正則になればよい。

2回後に同じ成分だけが2回選ばれている場合は4通りである。この状態から正則にするには、反対側の対角成分を選ぶしかないので、3回目の選び方は1通りである。したがってこの型は $4$ 通りである。

2回後に同じ行または同じ列の2成分が1回ずつ選ばれている場合を考える。行は2本、列は2本あり、それぞれ2成分の選ばれる順序が2通りあるので $4 \cdot 2 = 8$ 通りである。この状態からは、その行または列の外側にある2成分のどちらを選んでも行列式は0でなくなる。したがって3回目の選び方は2通りで、この型は $8 \cdot 2 = 16$ 通りである。

よって有利な3回の列は $4 + 16 = 20$ 通りであり、全体は $4^{3} = 64$ 通りだから $p_{3} = \frac{20}{64} = \frac{5}{16}$ である。

(2)

$(n - 1)$ 回後に第1行の成分がいずれも正で、第2行の成分がいずれも0であるためには、 $(n - 1)$ 回のすべてで $(1, 1)$ または $(1, 2)$ の札を選び、しかも $(1, 1)$ 、 $(1, 2)$ の両方が少なくとも1回ずつ選ばれればよい。 $(1, 1), (1, 2)$ だけを使う列は $2^{n - 1}$ 通りである。このうち $(1, 1)$ だけ、または $(1, 2)$ だけの列がそれぞれ1通りずつあるので、両方が少なくとも1回出る列は $2^{n - 1} - 2$ 通りである。全体は $4^{n - 1}$ 通りだから $q_{n - 1} = \frac{2 ^{n - 1} - 2}{4 ^{n - 1}}$ である。

(3)

$A_{0}, A_{1}, \dots, A_{n - 1}$ がすべて正則でないまま進んだとする。このとき $(n - 1)$ 回後の正の成分の位置は、1つの行に含まれるか、1つの列に含まれるか、または1つの成分だけである。実際、2つの行にも2つの列にもまたがる正の成分が現れると、どこかの時点で行列式が0でなくなる。

まず、1つの行または1つの列の2成分がともに正である場合を数える。行2本、列2本の合計4通りがあり、それぞれの確率は (2) と同じく $q_{n - 1} = \frac{2 ^{n - 1} - 2}{4 ^{n - 1}}$ である。この状態から次の1回で正則になるには、その行または列の外側の成分を選べばよい。外側の成分は2個なので、その確率は $\frac{2}{4} = \frac{1}{2}$ である。したがってこの場合の寄与は $4 q_{n - 1} \cdot \frac{1}{2} = 2 q_{n - 1}$ である。

次に、同じ1成分だけが $(n - 1)$ 回選ばれていた場合を数える。成分の選び方は4通りで、それぞれの確率は $(1/4)^{n - 1}$ である。この状態から次の1回で正則になるには、反対側の対角成分を選ぶ必要があり、その確率は $1/4$ である。よってこの場合の寄与は $4 (\frac{1}{4})^{n - 1} \cdot \frac{1}{4} = \frac{1}{4 ^{n - 1}}$ である。

以上より

p_{n} = 2 q_{n - 1} + \frac{1}{4 ^{n - 1}} = 2 \cdot \frac{2 ^{n - 1} - 2}{4 ^{n - 1}} + \frac{1}{4 ^{n - 1}} = \frac{2 ^{n} - 3}{4 ^{n - 1}}

である。これは $n = 2, 3$ の結果とも一致する。

名古屋大学 2011年度理系数学 第2問

問題

方針

解答

(1)

(2)

(3)

名古屋大学 2011年度
理系数学第2問