あります。Ａ氏にはこだわりがあり、散歩のコースの選択が[連続しての]繰り返しにならない
ように気をつけています。
いくつか例をあげましょう。散歩のコースを並べたときにＯＫなケースとダメなケースとを例
示します。
例 ダメ：2012011021 ・・・ (途中で1と1とが連続して繰り返されているからです)
例 ダメ：2012012021 ・・・ (途中で012と012とが連続して繰り返されているからです)
例 ＯＫ：2012101201 ・・・ (途中で012と012とが繰り返されているようにみえますが、間に
1が挟まれていますから[連続して]の繰り返しではありません)
例 ダメ：210120210121012101201 ・・・ （2101が連続してくりかえされています）
さて、あなたはＡ氏の秘書です。Ａ氏のこだわりに従うような向こう３６５日間の犬の散歩コ
ースの予定表を作れと言われました。
なにかよい方法をみつけてください。
ヒントになるかどうか不明ですけれども……、問題の背景を説明します。
散歩のコースが、0、1の２通りあった場合に、同一パターンの２連続を回避する方法はあ
りません。4日めでダメになります。
0
01
010
0101
散歩のコースが 0、1の２通りあった場合に、同一パターンの【３連続】を回避する方法なら
ばあります。
この事実は、形を変えてですが、チェスや将棋のプレイヤーたちにとって広く知られていま
した。
将棋では、かつて大雑把にいうと、千日手とは同一手順が三回繰り返されることでした。
そして、千日手模様ではありながら、ルール上の千日手成立を回避しつつ考慮時間（持ち
時間）のルール上での減少を抑制し、タップリと読みふける時間を実質的にもうけるテクニ
ック…これが実際に公式戦で登場しました。 その後、千日手成立の基準があらためられ
ました。
《散歩のコースが 0、1 の２通りあった場合に、同一パターンの【３連続】を回避する方法な
らばあります。》（…の変形版）が実戦で登場したのでした。
さて、先にも触れた通りに、散歩のコースが 0、1 の２通りあった場合に、同一パターンの
【２連続】を回避する方法はないのでした。
では、散歩のコースが 0、1、2 の３通りあった場合に、同一パターンの【２連続】を回避す
る方法はあるのか、あるとしたならば、それはどのようなものかについて、ご考察頂きたく、
出題させて頂きました。
DD++さんからのコメントです。（平成３０年１２月３１日付け）
年をまたぐのもなんなので、知ってる答えを。
最初に文字列「0」を用意します。文字列の0と1を反転したものを後ろにくっつけることを9回
繰り返します。
01
0110
01101001
0110100110010110
（以下略）
同じ数が2回連続したところの2つめを2に変更し、最初の0を切り落とします。
120102120210120……
これで511日分のコースができました。
実は、かつてほぼ同じ問題が出題されたことがあります。
（→ 数学感動秘話「新単語作り」）
ハンニバル・フォーチュンさんからのコメントです。（平成３０年１２月３１日付け）
ありがとうございます。既出でしたか……残念です。一応、私なりに噛み砕いた構成方法
の一例をば。以下、スラッシュは見やすさのためですので、無視してください。
（ルール１） 0 をみたら 01 に変身させます。
0 → 01
（ルール２） 01 を見たら 011/0 に変身させます。
01 → 011/0
（ルール３） 011 を見たら 011/01/0 に変身させます。
011 → 011/01/0
＃スラッシュは再帰的にルールを適用できることを明らかにするためでした。
以上の三つのルールに従いながら、初期値 0 からスタートし、次々にルールを再帰的に
適用していきます。
0
01
0110
01101001
0110100110010110
上のように再帰的に作成されていく文字列は、パターンが三連続しないようになっています。
そのことの証明は、こちらに書かれています。
さて、上で作られた文字列におきまして、
0 → 0 、01 → 1 、011 → 2
と置換してやれば、目的とする、パターンが２連続しない文字列となっています。OEIS にも関
連情報があります。
また、以前調べた、再帰的に文字列が増殖するテクニックの一覧を下記にまとめておきま
す。
・Axel Thue (1906)
a→abc 、b→ac 、c→b
・Thue (1906)
a→abcab 、b→acabcb 、c→acbcacb
・Thue (1912)
a→abacb 、b→abcbac 、c→abcacbc
・Leech (1957)
a→abcbacbcabcba 、b→bcacbacabcacb 、c→cabacbabcabac
・Dejean (1972)
a→abcacbcabcbacbcacba 、b→bcabacabcacbacabacb 、c→cabcbabcabacbabcbac
ハンニバル・フォーチュンさんからのコメントです。（平成３１年１月１日付け）
再帰的な置換では、下記のような強烈な増殖技があるようです。まず、例によって下記の
ようなものを用意します。
01101001100101101001011001101001...
まず、下ごしらえをします。階差をとるイメージで、
00 → a 、01 → b 、10 → c 、11 → d
と置換します。さきほどの２進列の冒頭では、
0b1d1c0b1c0a0b1... から、 bdcbcab...
を得るイメージです。次に、a、b、c、d について、下記の置換を行います。
a → 01021012021020102101210201202101201021201210201202101210212010210121020
10212012102012021012102010210120210201210212010210121020120210120102120
121020102101210212
b → 01021012021020102101210201202101201021201210201202101210201021012021020
12102120102101210201021201210201202101210212010210121020120210120102120
121020102101210212
c → 01021012021020102101210201202101201021201210201021012021020121021201021
01210201021201210201202101210201021012021020102120121020120210120102120
121020102101210212
d → 01021012021020102101210201202101201021201210201021012021020102120121020
12021012102010210120210201210212010210121020102120121020120210120102120
121020102101210212
a b c d ひともじあたり、160 字の 0 1 2 文字列が得られるようです。
一年分ならば、bdcbcab... の冒頭三文字にて、bdc を対象に置換して、480日分の散歩コ
ースの計画をたてられます。
010210120210201021012102012021012010212012102012021012102010210120210201210
212010210121020102120121020120210121021201021012102012021012010212012102010
210121021201021012021020102101210201202101201021201210201021012021020102120
121020120210121020102101202102012102120102101210201021201210201202101201021
201210201021012102120102101202102010210121020120210120102120121020102101202
102012102120102101210201021201210201202101210201021012021020102120121020120
210120102120121020102101210212
強烈な増殖率ですね……。
ハンニバル・フォーチュンさんからのコメントです。（平成３１年１月２日付け）
たびたび登場する「0110100110010110...」は Thue Morse sequence と名付けられています。
これはパターンの三連続が無いもので、将棋の千日手の解説にも使われたことがあります。
0,1 からなり、やはりパターンの三連続が無いものとして、Kolakoski sequence なるものが
あります。これは、OEISの「A000002」ですから、著名中の著名ともいえます。
1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,2,1,1,2,1,2,2,1,2,2,1,1,2,1,2,2,1,2,1,1,2,1,1,2,2,1,
2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,1,2,2,1,2,1,1,2,2,1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2...
なのですが、Thue Morse sequenceとは異なり、この Kolakoski sequence を加工しての、パ
ターンの三連続が無いものの作製は、私には全くできません。クリスマスの頃から挑戦して
おります。
ハンニバル・フォーチュンさんからのコメントです。（平成３１年１月９日付け）
平成３０年１２月３１日付けに於いて、以下のように、3文字からなる、ブロック2連続がない
もの各種をご紹介いたしましたけれども、追加情報があります。
・Axel Thue (1906)
a→abc 、b→ac 、c→b
・Thue (1906)
a→abcab 、b→acabcb 、c→acbcacb
・Thue (1912)
a→abacb 、b→abcbac 、c→abcacbc
・Leech (1957)
a→abcbacbcabcba 、b→bcacbacabcacb 、c→cabacbabcabac
・Dejean (1972)
a→abcacbcabcbacbcacba 、b→bcabacabcacbacabacb 、c→cabcbabcabacbabcbac
2007ないし2008に、日本人名 Kurosaki をもつかたが発表なさったものがありました。
Kurosaki さん御本人による定式化ではありませんが、以下のようなものです。
まず、６文字からなる文字列について、文字列操作関数 f を何回か通して再帰的に文字
列を増殖させます。ついで、最後に１回だけ、文字列操作関数 g を通して(mod 3)文字の個
数を６個から３個に減らします。
f:(0→042, 1→231, 2→150, 3→513, 4→405, 5→324)
g:(0→0, 1→1, 2→2, 3→0, 4→1,5→2 )
初期値として与える文字列は '0' とします。
具体的に再帰回数を４として、g(f(f(f(f(0))))) を求めてみます。
0
↓
042
↓
042405150
↓
042405150405042324231324042
↓
042405150405042324231324042405042324042405150513150405150513231513150405042405150
↓
012102120102012021201021012102012021012102120210120102120210201210120102012102120
文字列の長さは 81 となりました。「A217522」にて、
「Squarefree ternary sequence derived from bi-infinite squarefree ternary sequence of Kurosaki.」
として載っている数列がこれです。
「 derived from bi-infinite squarefree ternary sequence of Kurosaki」とありますが、 Kurosaki
氏によるオリジナルの定式化は次のようなものです。
a を 1, 2, 3 からなる文字列とします。文字列に作用する関数 σ,ρ,φ を以下のように定
めます。（プログラム言語風にしました。オリジナルは数学的に書いてあります。）
・σ(a) 1 を 2 に、 2 を 1 に置き換える。
・ρ(a) 2 を 3 に、 3 を 2 に置き換える。
・φ(a) = σ(a) + a + ρ(a)
例
φ("123") = σ("123") + "123" + ρ("123") = "213" + "123" + "132" = "213123132"
初期値を "2" として、この φ() に再帰的に作用させると以下のようになります。
2
→
123
→
213123132
→
123213231213123132312132123
→
種から左右方向ともに文字列が成長していきます。このことが"bi-infinite"のことなのでしょ
うか？このままですと OEIS には載りにくいですね……。詳しくは、「A217522」からリンクされ
ている２本の論文を御参照ください。
※ Kurosaki オリジナルが、平衡３進数を意識していて、２進数からなる「A010060」の
Thue-Morse sequence の自然な拡張になっている…らしいのですが… 私には飲み込めま
せんでした。
ハンニバル・フォーチュンさんからのコメントです。（平成３１年１月１５日付け）
上記で、"bi-infinite squarefree ternary sequence of Kurosaki"およびに（等価ですが）そ
れから derive されたOEIS「A217522」をご紹介させて頂きました。
さて、次のように、0, 1, 2, 3, 4, 5 からなる文字列（数列）を作成してみます。
まず、0, 1, 2, 3, 4, 5 はサイクリックであると考えます。すなわち、 0 の次が 1 であるのと
同様に 5 の次を 0 であると見なします。また「次」の対義語として「前」も使います。「前」ま
たは「次」であるとき、「隣」とも言うことにします。
これから数列を作るにあたり、n番目の数と(n+1)番目の数とは、互いに「隣」 の値をもつ
ことといたします。
例えば、「123234505...」は、ずっと「隣」の数を並べていっています。
このように、「隣」でつなげていった数列（文字列）を「穏やか」な数列と呼ぶこととします。
５項からなる穏やかな数列のなかでも、特に以下のふたつの性質をもつものをそれぞれ、
「上に凸」「下に凸」と言うことにします。
a を 0, 1, 2, 3, 4, 5 のうち、どれかとしましょう。
「上に凸」とは、 a, aの次, aの次の次, aの次, a となる5項を言います。
「下に凸」とは、 a, aの前, aの前の前, aの前, a となる5項を言います。
例えば、「50105」は、上に凸、「05450」は、下に凸 となります。
上に凸な穏やかな5項の最後の項の値と、下に凸な穏やかな5項の最初の項の値とが同
一の場合には、これを接合して、9項からなる数列を作ることができるものとします。これを
「凸凹波」と呼ぶこととします。無論「凸凹波」は穏やかです。
たとえば、「501054345」は、「凸凹波」です。
同様に、下に凸な穏やかな5項の最後の項の値と、上に凸な穏やかな5項の最初の項の
値とが同一の場合には、これを接合して、9項からなる数列を作ることができるものとします。
これを「凹凸波」と呼ぶこととします。
たとえば、「543450105」は、「凹凸波」です。
0, 1, 2, 3, 4, 5 のそれぞれにつき、次のように波（凹凸波または凸凹波）を割り当てます。
a を 0, 1, 2, 3, 4, 5 のどれかだとします。
a が奇数のとき、a を初項とする凹凸波を割り当てます。
a が偶数のとき、a を初項とする凸凹波を割り当てます。
具体的には、
0 → 012105450,
1 → 105012321,
2 → 234321012,
3 → 321234543,
4 → 450543234,
5 → 543450105
※ どの割り当て/対応も穏やかな波にみえるところが今回の趣向です。この対応を文字列
に対しての写像とみなして再帰的に繰り返していって、「穏やかな」数列を作成していくこと
とします。初期値は 0 とします。
0
↓
012105450
↓
012105450105012321234321012105012321012105450543450105450543234543450105012105450
↓
……
穏やかであることは見ての通りです。興味深いことに、3,4,5 に替えて mod 3 で置き換える
と、OEIS「A217522」に一致します。実質的に Kurosaki sequence に等価です。
文字列長が729のものを作成し、実際に squarefree (文字列のブロックが２連続しない)で
あることを確認しました。
プログラミング言語の正規表現を使えば一発で 長さが 729 ぐらいのものは 作れることで
しょう。私は手作業でやりました。とほほ。(;´д｀) 本当のモトネタは以下のようなものです。
f:(
0 → 105 ,
1 → 012 ,
2 → 321 ,
3 → 234 ,
4 → 543 ,
5 → 450
)
穏やかです。偶奇でもって、単調増加か単調現象かが決めてあります。また、写像を作る
にあたり、出力文字列の真ん中に入力文字が保存されているようにしてあります。それはな
ぜかといえば、
【* bi-infinite *】 squarefree ternary sequence of Kurosaki
の【* bi- *】を意識してみました。左右両方に増殖していくイメージです。
ただし、大元の sequence of Kurosaki ではグローバルに変換方法を決める必要がありま
すが、今回の投稿のやりかたは、ローカル（局所的）に一文字づつ変換していけばよいので、
初心者でも正規表現で書きやすいですね。
ハンニバル・フォーチュンさんからのコメントです。（平成３１年１月１８日付け）
その後もいじっていましたところ、 OEIS「A217522」の数列を導く別の方法がみつかりまし
た。これまでのものと同工異曲かもしれませんけれども。
文字列操作関数 f を考えます。 f は、文字列長が 3 の文字列を入力し、文字列長が 27
の文字列を出力します。 a, b, c をそれぞれ 長さが 1 の文字列とします。 f の具体的な姿
は以下のようなものです。
f:("abc") = "abcbacbcabacabcacbcabacbabc"
文字列の初期値として "012" を与えて f を１回作用させると以下のようになります。
f("012") = "012102120102012021201021012"
この出力結果は、OEIS「A217522」の数列の最初の 27 文字に一致します。
次に、 "012102120102012021201021012" を、３文字づつに区切ります。すなわち、
"012" "102" "120" "102" "012" "021" "201" "021" "012"
この並びの順に、おのおのを f に入力し、得られた出力を結合します。
f("012")+f("102")+f("120")+f("102")+f("012")+f("021")+f("201")+f("021")+f("012")
上記のように３文字づつ区切っては再帰的に f を作用させることで、OEIS「A217522」の数
列を得ることができます。ひいては、 sequence of Kurosaki を得ることができました。
最初の 243 項を以下に記します。
012102120102012021201021012102012021012102120210120102120210201210120102012
102120102012021012102120210120102012102120102012021201021012021201210201021
012102012021201021012021201210120210201021201210201021012102012021012102120
102012021201021012
OEIS「A00002」の書き方を真似ると、次のようになります。
(a(n)) is the unique fixed point of the 3-block substitution beta
012 -> 012102120102012021201021012
021 -> 021201210201021012102012021
102 -> 102012021012102120210120102
120 -> 120210201210120102012102120
201 -> 201021012021201210120210201
210 -> 210120102120210201021201210
A 3-block substitution beta maps a word w(1)...w(3n) to the word
beta(w(1)w(2w(3)))...beta(w(3n-2)w(3n-1)w(3n)).
ハンニバル・フォーチュンさんからのコメントです。（平成３１年１月２４日付け）
「犬の散歩コース」の条件を満たす（と思われる）、これまでとは別の文字列（数列）の作成
方法があります。
OEIS「A250005」 は以下のような数列です。
1 1 2 1 1 2 1 2 2 1 1 2 1 1 2 2 ...
これを使って以下のような作業用のテーブルをつくります。
xxx 1 xxx 1 xxx 2 xxx 1 xxx 1 xxx 2 xxx 1 xxx 2 xxx 2 xxx 1 xxx 1 xxx 2 xxx 1 xxx 1 xxx 2 xxx 2 ...
最初のxxxに 012 をいれます。
012 1 xxx 1 xxx 2 xxx 1 xxx 1 xxx 2 xxx 1 xxx 2 xxx 2 xxx 1 xxx 1 xxx 2 xxx 1 xxx 1 xxx 2 xxx 2 ...
012 の次には 1 があります。こうしたときには、abc を bac におきかえたものを 次の xxx に
いれます。
012 1 102 1 xxx 2 xxx 1 xxx 1 xxx 2 xxx 1 xxx 2 xxx 2 xxx 1 xxx 1 xxx 2 xxx 1 xxx 1 xxx 2 xxx 2 ...
同様にして
012 1 102 1 012 2 xxx 1 xxx 1 xxx 2 xxx 1 xxx 2 xxx 2 xxx 1 xxx 1 xxx 2 xxx 1 xxx 1 xxx 2 xxx 2 ...
今度は 012 の次に 2 があります。こうしたときには、abc を acb におきかえたものを 次の
xxx にいれます。
012 1 102 1 012 2 021 1 xxx 1 xxx 2 xxx 1 xxx 2 xxx 2 xxx 1 xxx 1 xxx 2 xxx 1 xxx 1 xxx 2 xxx 2 ...
こうして次次に xxx に数字をいれていきます。
012 1 102 1 012 2 021 1 201 1 021 2 012 1 102 2 xxx 2 xxx 1 xxx 1 xxx 2 xxx 1 xxx 1 xxx 2 xxx 2 ...
OEIS「A250005」 の最初の200項について作業をすると以下のようになっています。
012 1 102 1 012 2 021 1 201 1 021 2 012 1 102 2 120 2 102 1 012 1 102 2 120 1 210 1
120 2 102 2 120 1 210 2 201 1 ... （略）...
201 2 210 1 120 1 210 2 201 1 021 1 201 2 210 2 201 1 021 2 012 1 102 1 012
上記から「A250005」に由来するものを取り払い整理すると 以下のような、603日分の犬の
散歩コースが得られます。
012102012021201021012102120102012102120210120102120210201021201210120210201
210120102120210120102012021012102120210120102012102120102012021201021012102
120102012102120210120102120210201210120102012102120210120102120210201021201
210120102120210120102012102120210201210120102012102120102012021012102012021
201021012102120102012021012102012021201210201021012102012021201021012021201
210201021201210120102120210201210120210201021201210120102120210120102012102
120102012021201021012102120102012021012102012021201021012102120102012102120
210120102120210201210120102012102120210201210120210201021201210201021012102
012
上記の散歩コースは、題意のように、２連続となる繰り返しを含まないことを確認済みです。
ところが、なぜこんな作り方でうまくいってしまうのか、私には皆目見当もつきません。無限
に続けられるかどうかも全くわかりませんが、ここまでできれば有望ではあります。でもやっ
ぱりわからない……。変なオチですみません。(≧∇≦)
ハンニバル・フォーチュンさんからのコメントです。（平成３１年２月５日付け）
上記でのやり方を踏襲して、OEIS「A00002」から(squarefreeなternary)犬の散歩コースを
作れるようですが、理由がよくわかりません。こんな感じです。
012 1 105 2 450 2 105 1/012 1 105 2 450 1 543 2 234 2 543 1 450 2 105 2 450 1 543 1
450 2 105 1/012 1 105 2 450 2 105 1/012 2 321 1 234 1 321 2/012 1 105 2 450 2 10
5 1/012 1 105 2 450 1 543 1 450 2 105 1/012 2 321 2/012 1 105 2 450 2 105 1/012 1
105 2 450 1 543 2 234 2 543 1 450 2 105 1/012 1 105 2 450 1 543 1 450 2 105 2 450 1
543 2 234 2 543 1 450 1 543 2 234 1 321 2/012 2 321 1 234 2 543 2 234 1 321 1 234 2
543 1 450 1 543 2 234 1 321 2/012 2 321 1 234 2 543 1 450 1 543 2 234 2 543 1 450 2
105 2 450 1 543 1 450 2 105 1/012 2 321 2/012 1 105 2 450 2 105 1/012 1 105 2 450 1
543 1 450 2 105 2
ここから「A00002」の要素を消し、更に、6進数について mod 3 を施して squarefreeな
ternary を得られます。
「A250005」のときよりも「A00002」のほうが証明しやすいはずと思いましたが…… あー。
ハンニバル・フォーチュンさんからのコメントです。（平成３１年２月１２日付け）
さて、012 や 105 450 など、3字づつのブロックを OEISの「A00002」 を糊にして接着してい
く方法が 上記で触れた方法でした。
今回は、ふと、012 や 105 450 など、3字づつのブロックの真ん中の字、すなわち
012->1 105->105->0 450->5
だけを抜き出してみましたところ、それでも犬の散歩コースの性質を持っているらしいことに
気がつきました。
少しく整理したところ、以下のような予想を立てることとなりました。OEIS の数列を引くこと
になりますが……。
modulo 3 of A074272
( Partial alternating sums modulo 3 of the Kolakoski sequence A000002
which is a cubefree sequence )
is a squarefree sequence.
そのこころは、以下の通りです。
「A00002」の Kolakoski数列 は以下の通りです。cubefree な"binary" sequence であること
が知られています。
Kolakoski数列: 1,2,2,1,1,2,1,2,2,1,2,2,1,1
これを交代級数のようにして部分和をとったもの( Partial alternating sums )が「A074272」
の数列です。
A074272:1,-1,1,0,1,-1,0,-2,0 ...
A074272 の mod 3 をとったものを a(n) とすると、 a(n):1,2,1,0,1,2,0,1,0 ...
となりますが、この a(n) が、どうやら squarefree な ternary sequence になっていそうです。
（予想：未証明）
最初の 100 項だけを以下に示します。
121012010212021012102120121012021020121012010210120212010201202101210201202
1020102120210201210120212
なかなか不敵な面構えです……。
ハンニバル・フォーチュンさんからのコメントです。（平成３１年２月２０日付け）
OEISに「A323989」として登録された模様です。（←おめでとうございます！）
A074272:1,-1,1,0,1,-1,0,-2,0 ...
A074272 の mod 3 をとったものを a(n) とすると、 a(n):1,2,1,0,1,2,0,1,0 ...
となりますが、この a(n) が、どうやら squarefree な ternary sequence になっていそうです。
（予想：未証明）
《緩募》squarefree であることの証明、宜しくお願いいたします。
