6秋田大学 2024年 数学 第6問解答・解説

文字ごとの補集合写像と連結の漸化式を用いる。末尾2文字の性質を帰納法で示し、三連続が新しく生じうる連結境界を調べて排除する。

(i) $S_0=\mathrm{a},\quad S_1=\mathrm{ab},\quad S_2=\mathrm{abba}$ であり、$f(S_2)=\mathrm{baab}$ だから、
$$S_3=S_2f(S_2)=\mathrm{abba}\,\mathrm{baab}=\mathrm{abbabaab}.$$

(ii) $k=1$ では $S_1$ の末尾2文字は $\mathrm{ab}$。$S_{k+1}=S_kf(S_k)$ より、$S_{k+1}$ の末尾2文字は $S_k$ の末尾2文字を文字ごとに交換したものになる。交換は $\mathrm{ab}\text{ を }\mathrm{ba}\text{ に、}\mathrm{ba}\text{ を }\mathrm{ab}\text{ に}$移すので、帰納法によりすべての $k\geqq1$ で末尾2文字は $\mathrm{ab}\text{ または }\mathrm{ba}$ である。

(iii) 基底 $S_2=\mathrm{abba}$ には同じ文字3つの連続はない。$S_k$ に $\mathrm{aaa},\mathrm{bbb}$ がないなら、その文字を交換した $f(S_k)$ にもない。$S_{k+1}=S_kf(S_k)$ の中で新たにできる可能性があるのは、2つの部分の境目をまたぐ長さ3の部分だけである。境目をまたぐ部分は、$S_k$ の末尾2文字と $f(S_k)$ の先頭1文字からなるもの、または $S_k$ の末尾1文字と $f(S_k)$ の先頭2文字からなるもののいずれかである。$k\geqq1$ では $S_k$ の先頭2文字は ab（$S_1=\mathrm{ab}$ であり、各項は直前の項から始まる）なので、$f(S_k)$ の先頭2文字は ba であり、後者は同一文字3つにならない。また (ii) より $S_k$ の末尾2文字は $\mathrm{ab}\text{ または }\mathrm{ba}$ で、前者も同一文字3つにならない。したがって境目にも $\mathrm{aaa},\mathrm{bbb}$ は生じない。基底 $S_2\text{から}$の帰納法により、すべての $k\geqq2$ で両方とも現れない。