Evolton

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

A0=(0000)とする.
整数n≧1に対して,次の試行により行列An−1から行列Anを定める.

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

この試行をn回(n=2,3,4,⋯ )くり返した後に,
A0,A1,⋯,An−1が逆行列をもたず
Anは逆行列をもつ確率をpnとする.

(1) p2,p3を求めよ.

(2) (n−1)回(n=2,3,4,⋯ )の試行をくり返した後に,
An−1の第1行の成分がいずれも正で第2行の成分はいずれも0である確率qn−1を求めよ.

(3) pn (n=2,3,4,⋯ )を求めよ.

難易度7/ 10計算量6/ 10目安28分

確率、行列 状態分類、確率漸化式、数え上げ

方針

各試行は4つの成分のうち1つを1増やす操作であり、2×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 通りである。全体は 42 通りだから p2=442=14 である。

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

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

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

よって有利な3回の列は 4+16=20 通りであり、全体は 43=64 通りだから p3=2064=516 である。

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

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

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

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

以上よりpn=2qn−1+14n−1=2⋅2n−1−24n−1+14n−1=2n−34n−1である。これは n=2,3 の結果とも一致する。

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

別解

解法2

方針

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

解答

(1)
2回目で初めて正則になる列は、2つの対角位置または2つの反対角位置を順序をつけて選ぶ4列である。よってp2=442=14である。3回目で初めて正則になる列は、同じ成分を2回選んだ4列から反対側を選ぶ4列と、1行または1列の2成分を選んだ8列から外側を選ぶ16列である。したがってp3=4+1643=516となる。

(2)
第1行の2成分だけを使う列は 2n−1 列であり、そのうち一方だけを使う2列を除けばよい。
したがってqn−1=2n−1−24n−1である。

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

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

第 n 回で初めて正則になる確率はpn=Tn−1−Tn=4⋅2n−1−44n−1−4⋅2n−44n=2n−34n−1となる。

総評

「初めて正則になる」条件を、直前までの非正則な履歴として分類する問題である。目安時間は28分。行列式を直接追い続けるより、正の成分の位置が1つの行・列に閉じ込められている限り非正則で、そこから外へ出ると正則になる、という構造で見るとよい。ただし、1成分だけが繰り返し選ばれている場合は、(2) の qn−1 には含まれないため別に足す必要がある。p3 の20通りを丁寧に数えておくと、一般式の係数 4,1/2 の意味も確認しやすい。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る名大の確率の問題で問題集を作る

出典: 名古屋大学 2011年度 前期日程 数学(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。