Higmanしりとり (絶対に有限回で終わるしりとり)

皆さんは、「しりとり」をやったことがあるだろうか？
言葉を覚えたばかりの幼児でもルールを理解できる、トップレベルに簡単な言葉遊びである。おそらくルールを知らない人はいないだろう。
しかし、ルールが簡単すぎて、ある程度語彙力が備わった人同士で行うと、1プレイに数時間かかってしまう。そのため、言葉のジャンルを決めたり、派生ルールであえて難易度を高めたりする。
今回は、そのような派生ルールの1種として、「既に宣言した言葉は再び宣言してはいけない」という禁止事項を強める方向で考える。

定義

しりとりの定義

まず、しりとりの定義を述べよう。なお、通常は複数人でも行えるゲームだが、後ほどの考察のために今回は2人プレイとさせてもらう。
有限集合$\Sigma$と、$\Sigma$の部分集合$\Delta$と、空列をもたない$\Sigma$-有限列の非空な有限集合$W$と、$W$の元$w_0$に対して、$(\Sigma,\Delta,W,w_0)$-しりとりとは、以下のルールで進める二人零和有限確定完全情報ゲームである。

• 先攻と後攻が交互に$W$の元$w_1,w_2,\cdots$を宣言する。
• 各$i \in \mathbb N$に対して、$w_i$の末尾と$w_{i+1}$の先頭は等しくなければならない。
• 各$i,j \in \mathbb N$に対して、$i < j$ならば$w_i = w_j$であってはならない。
• 各$i \in \mathbb N$に対して、$w_i$の末尾は$\Delta$の元であってはならない。
• 先に上記のルールにそぐわない列を宣言したプレイヤーが敗北となる。

$\Sigma$をひらがな全体の集合、$\Delta$を「ん」のみをもつ1元集合、$W$を単語として認められているひらがな列全体の集合、$w_0$を「しりとり」とすれば、通常のしりとりの定義と一致することがわかるだろう。
(単語として認められているひらがな列全体の集合は実際は有限集合ではなく再帰的な無限集合であるかもしれないが、ここでは大目に見てほしい。)

二人零和有限確定完全情報ゲームなので、先手か後手のどちらかに必勝法が存在する。

Higmanしりとりの定義

次に、Higmanしりとりの定義を述べよう。こちらも複数人でも行えるゲームだが、今回は2人プレイとさせてもらう。
有限集合$\Sigma$と、$\Sigma$の部分集合$\Delta$と、空列をもたない$\Sigma$-有限列の非空な集合$W$と、$W$の元$w_0$に対して、$(\Sigma,\Delta,W,w_0)$-Higmanしりとりとは、以下のルールで進める二人零和確定完全情報ゲームである。

• 先攻と後攻が交互に$W$の元$w_1,w_2,\cdots$を宣言する。
• 各$i \in \mathbb N$に対して、$w_i$の末尾と$w_{i+1}$の先頭は等しくなければならない。
• 各$i,j \in \mathbb N$に対して、$i < j$ならば$w_i$は$w_j$の部分列であってはならない。
• 各$i \in \mathbb N$に対して、$w_i$の末尾は$\Delta$の元であってはならない。
• 先に上記のルールにそぐわない列を宣言したプレイヤーが敗北となる。

例えば、「しりとり」「りす」「すいり」「りんす」のようにゲームを進めた場合、「りんす」は「りす」を部分列にもつため、「りんす」と宣言した先手の負けである。
「すいり」は並べ替えると「りす」を部分列にもつようになりますが、そのままでは部分列にもたないので敗北条件を満たさない。
また、宣言する順番を変えて「しりとり」「りんす」「すいり」「りす」のようにした場合、「りす」は敗北条件を満たさない。既に宣言された列を部分列にもつものを宣言すると敗北となるが、逆に既に宣言された列の部分列を宣言しても敗北条件は満たさない。

Higmanしりとりの有限性

さて、Higmanしりとりは通常のしりとりよりも敗北条件が強くなっているので、$\Sigma,\Delta,W,w_0$を固定したとき、$(\Sigma,\Delta,W,w_0)$-しりとりよりも$(\Sigma,\Delta,W,w_0)$-Higmanしりとりの方が早くゲームが終了するはずである。
しかし、$(\Sigma,\Delta,W,w_0)$-Higmanしりとりの定義を見てもらえるとわかるように、$\Sigma$-列の集合$W$が有限集合であるという条件は課していない。
$W$の異なる元を取り続けるゲームなので、「$W$が無限集合ならゲームは終わらない可能性があるんじゃないのか？」という疑問が生まれる。
実は、「各$i,j \in \mathbb N$に対して、$i < j$ならば$w_i$は$w_j$の部分列であってはならない」を満たす無限列$w_0,w_1,\cdots$は存在しないことが知られている。この命題はHigmanの補題という名前で知られている。
よって、どのようにゲームを進めても必ず有限手で終了する。

ただし、$W$が無限集合である場合、各ゲームは有限手で終了するものの、ゲームの手数に上限は存在しない場合がある。
このような場合でも、(流儀によっては有限ゲームとは呼ばれないが、)先手か後手のどちらかに必勝法が存在する。

Higmanしりとりの必勝法についての考察

Higmanしりとりのうち、$\Delta$は空であっても問題ない。$W$を末尾が特定の文字にならないもの全体とすればよいからだ。
また、$\Sigma$は濃度さえ等しければゲームとしては同型になるので、以降は$\Sigma$の代わりに$\Sigma$の濃度で表すことにする。
更に、一般の$W$について考えるとなると、$W$が取りうる値は非可算種類もあるので流石に難しいだろう。そこで、以降は$W$を「長さが$2$以上の$\Sigma$-列全体の集合」とする。
($W$を「長さが$1$以上の$\Sigma$-列全体の集合」とすると、$w_0$の長さが$1$の場合や、そうでなくともはじめに先手が長さ$1$の列を宣言することでゲームが終わってしまうので、なんの面白みもない。)

このようにして、前述の定義を特殊化して$(k,w_0)$-Higmanしりとりが定義できた。この必勝法を判定したい。

$w_0 = xx$を満たす文字$x$が存在する場合

$w_0 = xx$を満たす文字$x$が存在する場合は、先手はまず$x$から始まる列$w_1$を宣言しなければならない。しかし、後手は$w_2$として$w_1$を反転させた列を宣言できてしまう。すると先手は再び先頭が$x$である列を宣言しなければならなくなる。
同様に、先手が$w_{2i+1}$を宣言したとき、後手は$w_{2i+2}$として$w_{2i+1}$を反転させたものを宣言すればよい。

このようにしたとき、本当に$w_{2i+2}$が敗北条件を満たさないのかをちゃんと確かめてみよう。
もし$w_{2i+2}$が$w_{2i+1}$を部分列にもつならば、$w_{2i+1},w_{2i+2}$の長さは等しいので、$w_{2i+1} = w_{2i+2}$である。しかし、そうすると$w_{2i+1}$は長さが$2$以上であり先頭も末尾(つまり反転した$w_{2i+2}$の先頭)も$x$であるため、$w_0 = xx$を部分列にもってしまい、先手が先に敗北条件を満たしたことになってしまう。
もし$w_{2i+2}$が$w_0 = xx$を部分列にもつならば、$w_{2i+1}$も$w_0 = xx$を部分列にもつので、この場合も先手が先に敗北条件を満たしている。
もし$w_{2i+2}$がある$1 \le j \le 2i$について$w_j$を部分列にもつならば、$w_{j+1},w_{j-1}$のいずれかが$w_j$の反転となり、これは$w_{2i+1}$の部分列となるので、やはり先手が先に敗北条件を満たしている。

以上により、後手は先手が宣言した列を反転したものを宣言し続ければ負けることはない。これが後手の必勝戦略である。

$w_0 = \cdots x \cdots x$を満たす文字$x$が存在する場合

$w_0$の長さが$3$以上であり、$w_0$の末尾を$x$としたとき、$w_0$に$x$が末尾以外にも表れる場合、先手は次に$w_1$として$xx$を宣言できる。
以降は、後手が宣言した列を反転させたものを先手が宣言し続ければ、前述の$w_0 = xx$の場合を$w_1 = xx$にずらしたものになり、先手が負けることはない。
これが先手の必勝戦略となる。

$w_0 = y \cdots x$かつ$x \neq y$である場合

$w_0$の先頭の文字と末尾の文字が異なる場合も、先手必勝である。今回は、$w_0$の末尾の文字を$x$とする。
まず、先手は$w_1$として$xx$を宣言する。以降、先頭も末尾も$x$となるような文字列は宣言できない。
以降しばらくは、後手に先頭が$x$となる文字列を宣言させ続ける。具体的には、後手が直前に宣言した文字列に対して、その末尾の文字を先頭に、$x$を末尾にもつ$2$文字の文字列を返し続ける。
このような$2$文字の文字列が宣言できなくなった場合、代わりに後手が直前に宣言した文字列の末尾を$2$つつなげた文字列を宣言する。

上記の戦略を使って、最後に宣言した文字列を$zz$とおく。上記の戦略に則れば、$zx$及びそれを部分列にもつ文字列は以降宣言できないはずであり、また最後に$zz$を宣言したので、$zz$及びそれを部分列にもつ文字列は以降宣言できない。
更に、ここまで$zz$以外の文字列は全て文字$x$を含む。

さて、先手が$zz$を宣言した後、後手は$z$から始まり$z$以外で終わる文字列を宣言しなければならず、また先頭が$z$なので$zx$を部分列に持たないよう$x$をもたない文字列を宣言しなければならない。
なので、以降は先手が後手が直前に宣言した文字列を反転したものを宣言するだけで勝てる。

更なる問題

今回はかなり大雑把に、文字列集合を長さが$2$以上の文字列全体の集合として固定したが、ここを変えればもちろん上記の必勝法は破綻する。
また、文字列集合が長さが$2$以上の文字列全体の集合である場合も、この記事内では必勝法を明確化しただけにすぎず、つまるところ弱解決しかできていない。
果たして強解決はできるのだろうか？文字列集合をもう少し変えた場合も弱解決はできるのだろうか？などと派生問題がいくらでも作れそうだが、難易度が非常に高そうなのでこの辺りで一旦やめにする。

なお、強解決について考える場合、文字列集合に対して列の埋め込み順序を全順序化したものの順序型のうち最大のものを求め続ける苦行が必須になるので、順序数計算に自身のある方はぜひ挑戦してみてほしい。

余談

通常はHigmanしりとりは2人以上による対戦ゲームであるが、「なるべく長い手数続けられる」ことを目標とした1人用ゲームとしても遊べる。
さて、$w_i$の長さが高々$2+i$となるように、Higmanしりとりの条件に合うように1人でしりとり$w_0,w_1,w_2,\cdots$を続ける。
このように各手番で長さを有限に制限したとき、実はKonigの補題によりしりとりの手数に上限が生じる。
さて、$k$種類の文字を使えるとき、上記のルールで行うHigmanしりとりはどの程度の長さになるだろうか？

タイトルに「絶対に有限回で終わるしりとり」と書いたが、このタイトル、及び数学における有限が嘘ではないものの到底信用に値しないものであることがご理解いただけただろうか。