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

(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}$$ である。したがってこの場合の寄与は $$4q_{n-1}\cdot \frac{1}{2}=2q_{n-1}$$ である。

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

以上より$$p_n=2q_{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$ の結果とも一致する。

直前まで1行内に閉じ込められていた場合、外側の成分を1つ増やすと
行列式が0でなくなる。列の場合も同様である。

(1) (2) は短い列と第1行だけを使う列を直接数える。(3) は、最初から第k回まで正則にならない札の列全体を数える。全ての接頭列が特異であるための必要十分条件は、選ばれた成分の位置が1本の行または1本の列に含まれることである。行・列4本の列を包除して生存確率を求め、第n-1回までの生存確率から第n回までの生存確率を引く。

(1)
2回目で初めて正則になる列は、2つの対角位置または2つの反対角位置を順序をつけて選ぶ4列である。よって$$p_2=\frac{4}{4^2}=\frac{1}{4}$$である。3回目で初めて正則になる列は、同じ成分を2回選んだ4列から反対側を選ぶ4列と、1行または1列の2成分を選んだ8列から外側を選ぶ16列である。したがって$$p_3=\frac{4+16}{4^3}=\frac{5}{16}$$となる。

(2)
第1行の2成分だけを使う列は $2^{n-1}$ 列であり、そのうち一方だけを使う2列を除けばよい。したがって$$q_{n-1}=\frac{2^{n-1}-2}{4^{n-1}}$$である。

(3)
第 $k$ 回まで一度も正則にならないための必要十分条件は、それまでに選んだ成分の位置が1本の行または1本の列に含まれることである。実際、この状態なら行列式は常に0である。逆に初めて1本の行・列に収まらなくなる瞬間には、直前の2成分を含む行または列の外側が選ばれ、できた $2\times 2$ 小配置の行列式は0でない。

固定した1本の行または列だけを使う長さ $k$ の列は $2^k$ 列で、行・列は合わせて4本ある。ただし1つの成分だけを使う4列は、その成分を含む行と列で2回ずつ数えている。したがって、第 $k$ 回まで正則にならない列は$$4\cdot 2^k-4$$列であり、その確率を $T_k$ とすると$$T_k=\frac{4\cdot 2^k-4}{4^k}$$である。

第 $n$ 回で初めて正則になる確率は$$\begin{array}{rl}{\displaystyle p_n}& {\displaystyle =T_{n-1}-T_n}\\ {\displaystyle }& {\displaystyle =\frac{4\cdot 2^{n-1}-4}{4^{n-1}}-\frac{4\cdot 2^n-4}{4^n}}\\ {\displaystyle }& {\displaystyle =\frac{2^n-3}{4^{n-1}}}\end{array}$$となる。