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

各文字位置には$a,b$の2通りの選び方があるので、長さ$n$の文字列は全部で$2^n$個ある。くり返し列は、長さ$n$を割り切る長さ$d<n$のブロックを反復したものに限られる。以下では、反復の最短ブロックごとに分けて数える。

(i) $3$の真の約数は$1$だけである。長さ$1$のブロックを3回くり返した文字列は$aaa,bbb$の2個なので、
$$2^3-2=6$$
個が非くり返し列である。

(ii) 長さ$6$のくり返し列の最短ブロック長は$1,2,3$のいずれかである。最短ブロック長が$1$のものは2個。長さ$2$のブロックが非くり返しであるものは$ab,ba$の2個で、それぞれ3回くり返す。長さ$3$の非くり返しブロックは(i)より6個で、それぞれ2回くり返す。これらは最短ブロック長で分けた互いに重ならない場合である。したがってくり返し列は
$$2+2+6=10$$
個であり、非くり返し列は
$$2^6-10=64-10=54$$
個である。

(iii) 長さ$8$のくり返し列の最短ブロック長は$1,2,4$のいずれかである。長さ$1$の最短ブロックは2個、長さ$2$の非くり返しブロックは2個である。長さ$4$の非くり返しブロックは、全16個から最短ブロック長が$1$または$2$のものを除いて
$$2^4-(2+2)=12$$
個となる。最短ブロック長ごとの場合は互いに重ならないため、長さ$8$のくり返し列は
$$2+2+12=16$$
個である。よって非くり返し列は
$$2^8-16=256-16=240$$
個である。