末尾の文字に着目します。

[1] \(S\) の末尾の文字が A のとき

このとき \(f(S)\) の末尾の文字が A であることが示せます。まず \(S={}\)AA...AA のときは明らかです。\(S\) が B を含むとき、\(S_i={}\)B が成り立つ最大の \(i\) を \(x\) とします。 \(S\) の末尾は A であることから \(x\neq N\) であり、\(f(S)\) の末尾の文字は \(S_{x+1}={}\)A になります。以上より示されました。

このことから末尾が A の文字列 \(S\) を \(N-1\) 回 \(f(S)\) で置き換えると、 \(S={}\)A になることがわかります。

[2] \(S\) の末尾の文字が B のとき

\(S={}\)BB...B のとき、答えは明らかに B です。以下これ以外の \(S\) について考えます。

末尾が B の文字列 \(S\) に対し \(f(S)\) の末尾の文字が A になるのはどのようなときか考えると、\(S_i={}\)B \(,S_{i+1}={}\)A をみたす \(i\) が存在していることが必要です。このような \(i\) が存在するかで場合分けしてみます。

[2-1] 上記のような \(i\) が存在しない場合

このような \(i\) が存在しないのは、 \(S\) が A を \(x\ (1\leq x)\) 文字、B を \(y\ (1\leq y)\) 文字つなげた文字列になっているときです。このとき、 \(f(S)\) はA を \(x-1\) 文字、B を \(y\) 文字つなげた文字列になっています。特に

• 末尾が B である
• \(i\) 文字目が B であり、\(i+1\) 文字目が A であるような \(i\) が存在しない

という条件は \(f(S)\) も満たします。よって \(S\) を \(N-1\) 回 \(f(S)\) で置き換えた後も末尾の文字は B であり、\(S={}\) B になっています。

[2-2] 上記のような \(i\) が存在する場合

上記のような \(i\) の最大値を \(x\) とします。\(S\) は \(S={}\)...BA...ABB...BB という構造になっています。このような \(S\) に対する \(f(S)\) について、\(S\) の末尾に連続している B の個数を \(y\) とすると以下が成り立ちます。

• \(f(S)\) の末尾には B がちょうど \(y-1\) 個連続している
• \(f(S)\) の末尾から \(y\) 文字目は \(S_{x+1}={}\)A である
• \(S_{i}={}\)A をみたす最大の \(i\) に対し \(S_{i+1}={}\)B であり、これは \(f(S)\) の末尾から \(y+1\) 文字目以降に存在する

\(2\) 番目と \(3\) 番目から、\(i\) 文字目が B であり \(i+1\) 文字目が A であるような \(i\) は \(f(S)\) でも存在することがわかります。さらに、\(f(S)\) の末尾に連続している B の個数は \(S\) とくらべて \(1\) 個減っています。よって \(S\) を \(y\) 回 \(f(S)\) で置き換えると、 \(S\) の末尾の文字は A になっています。

以上よりこのような文字列 \(S\) を \(N-1\) 回 \(f(S)\) で置き換えると \(S={}\)A になることがわかります。