東北大学 2024年度理系数学第3問解答・解説

問題

$n$ を2以上の整数とする。それぞれA，A，Bと書かれた3枚のカードから無作為に1枚抜き出し，カードをもとに戻す試行を考える。この試行を $n$ 回繰り返し，抜き出したカードの文字を順に左から右に並べ， $n$ 文字の文字列を作る。作った文字列内にAAAの並びがある場合は不可とする。また，作った文字列内にBBの並びがある場合も不可とする。これらの場合以外は可とする。たとえば $n = 6$ のとき，文字列AAAABAやABBBAAやABBABBやBBBAAAなどは不可で，文字列BABAABやBABABAなどは可である。作った文字列が可でかつ右端の2文字がAAである確率を $p_{n}$ ，作った文字列が可でかつ右端の2文字がBAである確率を $q_{n}$ ，作った文字列が可でかつ右端の文字がBである確率を $r_{n}$ とそれぞれおく。

(1) $p_{2}, q_{2}, r_{2}$ をそれぞれ求めよ。また， $p_{n + 1}, q_{n + 1}, r_{n + 1}$ を $p_{n}, q_{n}, r_{n}$ を用いてそれぞれ表せ。

(2) $p_{n} + 2 q_{n} + 2 r_{n}$ を $n$ を用いて表せ。

(3) $p_{n} + i q_{n} - (1 + i) r_{n}$ を $n$ を用いて表せ。ただし， $i$ は虚数単位である。

(4) $p_{n} = r_{n}$ を満たすための， $n$ の必要十分条件を求めよ。

出典：東北大学 2024年度前期日程第2次学力試験理系第3問

方針

文字列の最後の形を $AA, B A, B$ の3状態に分ける。次にAを引く確率は $2/3$ ，Bを引く確率は $1/3$ であることを使い，AAAとBBを作らない遷移だけを残す。(2)と(3)は，問題で指定された一次結合が遷移によって何倍になるかを直接代入で確認する。(4)は(3)の複素数の実部が $p_{n} - r_{n}$ であることを使い， $- (1 + i)$ の累乗の実部が0になる周期を読む。

解答

(1)

$n = 2$ のとき，右端の2文字が $AA$ で可となる確率は，2回ともAを引く確率であるから $p_{2} = (\frac{2}{3})^{2} = \frac{4}{9}$ である。右端の2文字が $B A$ となるには1回目にB，2回目にAを引けばよいので $q_{2} = \frac{1}{3} \cdot \frac{2}{3} = \frac{2}{9}$ である。また，右端の文字がBで可となる2文字列は $A B$ だけであり， $B B$ は不可である。よって $r_{2} = \frac{2}{3} \cdot \frac{1}{3} = \frac{2}{9}$ である。

次に遷移を考える。可で右端が $AA$ の文字列にAを続けると $AAA$ ができて不可である。可で右端が $B A$ の文字列にAを続けると右端が $AA$ になる。したがって $p_{n + 1} = \frac{2}{3} q_{n}$ である。

右端が $B A$ になるには，もとの可な文字列の右端がBで，次にAを引けばよい。よって $q_{n + 1} = \frac{2}{3} r_{n}$ である。

右端がBになるには，次にBを引く必要がある。ただし，もとの右端がBなら $B B$ ができて不可であるため，もとの右端は $AA$ または $B A$ でなければならない。よって $r_{n + 1} = \frac{1}{3} (p_{n} + q_{n})$ である。

(2)

$U_{n} = p_{n} + 2 q_{n} + 2 r_{n}$ とおく。(1)の漸化式より

U_{n + 1} = p_{n + 1} + 2 q_{n + 1} + 2 r_{n + 1} = \frac{2}{3} q_{n} + 2 \cdot \frac{2}{3} r_{n} + 2 \cdot \frac{1}{3} (p_{n} + q_{n}) = \frac{2}{3} p_{n} + (\frac{2}{3} + \frac{2}{3}) q_{n} + \frac{4}{3} r_{n} = \frac{2}{3} (p_{n} + 2 q_{n} + 2 r_{n}) = \frac{2}{3} U_{n}

である。また $U_{2} = p_{2} + 2 q_{2} + 2 r_{2} = \frac{4}{9} + 2 \cdot \frac{2}{9} + 2 \cdot \frac{2}{9} = \frac{4}{3}$ である。したがって $U_{n} = \frac{4}{3} (\frac{2}{3})^{n - 2} = \frac{2 ^{n}}{3 ^{n - 1}}$ である。よって $p_{n} + 2 q_{n} + 2 r_{n} = \frac{2 ^{n}}{3 ^{n - 1}}$ である。

(3)

$Z_{n} = p_{n} + i q_{n} - (1 + i) r_{n}$ とおく。(1)の漸化式を代入すると

Z_{n + 1} = p_{n + 1} + i q_{n + 1} - (1 + i) r_{n + 1} = \frac{2}{3} q_{n} + i \frac{2}{3} r_{n} - (1 + i) \frac{1}{3} (p_{n} + q_{n}) = - \frac{1 + i}{3} p_{n} + (\frac{2}{3} - \frac{1 + i}{3}) q_{n} + \frac{2 i}{3} r_{n} = - \frac{1 + i}{3} p_{n} + \frac{1 - i}{3} q_{n} + \frac{2 i}{3} r_{n}

である。一方，

- \frac{1 + i}{3} Z_{n} = - \frac{1 + i}{3} p_{n} - \frac{i ( 1 + i )}{3} q_{n} + \frac{( 1 + i ) ^{2}}{3} r_{n}

であり， $- i (1 + i) = 1 - i, (1 + i)^{2} = 2 i$ だから，これは上の式と一致する。よって $Z_{n + 1} = - \frac{1 + i}{3} Z_{n}$ である。

初期値は $Z_{2} = \frac{4}{9} + i \frac{2}{9} - (1 + i) \frac{2}{9} = \frac{2}{9}$ であるから， $Z_{n} = \frac{2}{9} (- \frac{1 + i}{3})^{n - 2}$ である。すなわち $p_{n} + i q_{n} - (1 + i) r_{n} = \frac{2}{9} (- \frac{1 + i}{3})^{n - 2}$ である。

(4)

左辺の実部は $Re {p_{n} + i q_{n} - (1 + i) r_{n}} = p_{n} - r_{n}$ である。したがって $p_{n} = r_{n}$ は，(3)で得た複素数の実部が0であることと同値である。

定数 $\frac{2}{9} \cdot 3^{- (n - 2)}$ は正の実数なので，実部が0になるかどうかは ${- (1 + i)}^{n - 2}$ だけで決まる。ここで $- (1 + i) = - 1 - i$ であり，その累乗は

k (mod 4) {- (1 + i)}^{k} 0 実数 1 実部あり 2 純虚数 3 実部あり

となる。実際，

{- (1 + i)}^{0} = 1, {- (1 + i)}^{1} = - 1 - i, {- (1 + i)}^{2} = 2 i, {- (1 + i)}^{3} = 2 - 2 i

であり，4乗ごとに実数倍されるだけである。

よって実部が0となるのは $n - 2 \equiv 2 (mod 4)$ のときである。したがって $n \equiv 0 (mod 4)$ が必要十分条件である。

【許される状態遷移】

$AA \to AA$ は $AAA$ を、 $B \to B$ は $B B$ を作るため禁止される。

東北大学 2024年度理系数学 第3問

問題

方針

解答

(1)

(2)

(3)

(4)

【許される状態遷移】

東北大学 2024年度
理系数学第3問