東北大学 2024年 理系 第3問 解説

方針・初手

可となる文字列の末尾の形に着目する。

条件

• $AAA$ を含まない
• $BB$ を含まない

を満たす可の文字列は、末尾だけ見れば

• $AA$ で終わるもの
• $BA$ で終わるもの
• $B$ で終わるもの

の3種類に分類できる。そこで、それぞれに次の1文字を付け加えたときにどこへ移るかを調べれば、$p_n,q_n,r_n$ の漸化式が立つ。

その後、（2） と （3） で与えられた線形結合を作ると、等比数列になる。

解法1

長さ $n$ の可の文字列について、末尾の状態を考える。

• 末尾が $AA$ のとき、次に $A$ を付けると $AAA$ となって不可である。$B$ を付けるしかない。
• 末尾が $BA$ のとき、次に $A$ を付ければ末尾は $AA$、$B$ を付ければ末尾は $B$ になる。
• 末尾が $B$ のとき、次に $B$ を付けると $BB$ となって不可である。$A$ を付けると末尾は $BA$ になる。

ここで、1回の試行で $A$ を引く確率は $\frac23$、$B$ を引く確率は $\frac13$ であるから、

$$ p_{n+1}=\frac23 q_n,\qquad q_{n+1}=\frac23 r_n,\qquad r_{n+1}=\frac13(p_n+q_n) $$

が成り立つ。

(1)

まず $n=2$ のときである。

• 右端2文字が $AA$ である確率は

$$ p_2=\left(\frac23\right)^2=\frac49 $$

• 右端2文字が $BA$ である確率は

$$ q_2=\frac13\cdot\frac23=\frac29 $$

• 可でかつ右端が $B$ であるのは $AB$ のみであるから

$$ r_2=\frac23\cdot\frac13=\frac29 $$

したがって、

$$ p_2=\frac49,\qquad q_2=\frac29,\qquad r_2=\frac29 $$

である。

また、上で得た漸化式より、

$$ p_{n+1}=\frac23 q_n,\qquad q_{n+1}=\frac23 r_n,\qquad r_{n+1}=\frac13(p_n+q_n) $$

である。

(2)

$$ u_n=p_n+2q_n+2r_n $$

とおく。

すると漸化式より、

$$ \begin{aligned} u_{n+1} &=p_{n+1}+2q_{n+1}+2r_{n+1} \\ &=\frac23 q_n+2\cdot\frac23 r_n+2\cdot\frac13(p_n+q_n) \\ &=\frac23 p_n+\frac43 q_n+\frac43 r_n \\ &=\frac23(p_n+2q_n+2r_n) \\ &=\frac23 u_n \end{aligned} $$

となる。

初期値は

$$ u_2=p_2+2q_2+2r_2 =\frac49+2\cdot\frac29+2\cdot\frac29 =\frac43 $$

であるから、

$$ u_n=\frac43\left(\frac23\right)^{n-2} =\frac{2^n}{3^{n-1}} $$

となる。

よって、

$$ p_n+2q_n+2r_n=\frac{2^n}{3^{n-1}} $$

である。

(3)

$$ z_n=p_n+iq_n-(1+i)r_n $$

とおく。

すると、

$$ \begin{aligned} z_{n+1} &=p_{n+1}+iq_{n+1}-(1+i)r_{n+1} \\ &=\frac23 q_n+i\frac23 r_n-(1+i)\frac13(p_n+q_n) \\ &=-\frac{1+i}{3}p_n+\frac{1-i}{3}q_n+\frac{2i}{3}r_n \end{aligned} $$

ここで

$$ i\left(-\frac{1+i}{3}\right)=\frac{1-i}{3},\qquad -(1+i)\left(-\frac{1+i}{3}\right)=\frac{2i}{3} $$

であるから、

$$ z_{n+1}=-\frac{1+i}{3}\cdot z_n $$

を得る。

初期値は

$$ \begin{aligned} z_2 &=p_2+iq_2-(1+i)r_2 \\ &=\frac49+i\frac29-(1+i)\frac29 \\ &=\frac29 \end{aligned} $$

である。したがって、

$$ z_n=\frac29\left(-\frac{1+i}{3}\right)^{n-2} $$

となる。

ゆえに、

$$ p_n+iq_n-(1+i)r_n=\frac29\left(-\frac{1+i}{3}\right)^{n-2} $$

である。

(4)

（3） の式より、

$$ p_n-r_n=\Re!\left(\frac29\left(-\frac{1+i}{3}\right)^{n-2}\right) $$

である。

ここで

$$ -(1+i)=\sqrt2,e^{-3\pi i/4} $$

より、

$$ \left(-\frac{1+i}{3}\right)^{n-2} =\left(\frac{\sqrt2}{3}\right)^{n-2} e^{-3(n-2)\pi i/4} $$

となるから、

$$ p_n-r_n =\frac29\left(\frac{\sqrt2}{3}\right)^{n-2} \cos\frac{3(n-2)\pi}{4} $$

を得る。

したがって $p_n=r_n$ であるための必要十分条件は

$$ \cos\frac{3(n-2)\pi}{4}=0 $$

である。これは

$$ \frac{3(n-2)\pi}{4}=\frac{\pi}{2}+k\pi \qquad (k\in\mathbb{Z}) $$

と同値であり、

$$ 3(n-2)\equiv 2 \pmod 4 $$

すなわち

$$ n-2\equiv 2 \pmod 4 $$

である。よって、

$$ n\equiv 0 \pmod 4 $$

が必要十分条件である。

解説

この問題の本質は、可となる文字列全体を直接数えようとせず、末尾の状態を

• $AA$
• $BA$
• $B$

の3状態に整理することである。禁止条件が「$AAA$」「$BB$」という連続部分列に関するものなので、末尾の情報だけで次の遷移が完全に決まる。

（2） と （3） は、漸化式をそのまま解くのではなく、適切な線形結合を作ることで1本の等比数列に落とすのが要点である。特に （3） は複素数を用いた対角化に相当する処理になっている。

答え

$$ p_2=\frac49,\qquad q_2=\frac29,\qquad r_2=\frac29 $$

$$ p_{n+1}=\frac23 q_n,\qquad q_{n+1}=\frac23 r_n,\qquad r_{n+1}=\frac13(p_n+q_n) $$

$$ p_n+2q_n+2r_n=\frac{2^n}{3^{n-1}} $$

$$ p_n+iq_n-(1+i)r_n=\frac29\left(-\frac{1+i}{3}\right)^{n-2} $$

$$ p_n=r_n \iff n\equiv 0 \pmod 4 $$