「数学コラム Tree3の停止性の証明2-1 （2021/01/11)」


Kruskalのツリー定理。およびTree3の停止性の証明　第02話 パート1。

停止性証明へのロードマップ

これが結構時間かかりそうなので・・・
まずはTree3のおさらいから始めることにしましょう。


Treeゲームのルールはシンプルです。



ルール1.
使うのはn色のおはじき

ルール2.
Mターン目に置けるおはじきの数は最大M個(M未満を置いても良い)。それでツリーを作る。

ルール3.
以前作ったツリーからの「ノード拡張(※)」を作ったらゲームオーバー

※「ノード拡張」とは：
ツリーAの好きな場所に、好きな色のおはじきを挿入して
ツリーBを作れる時。
(つまり一方的な拡張。ノードの変形や削除はできない)

この時ツリーBはツリーAのノード拡張と呼び
　　A≦B
と記述します。

この3つのシンプルなルールで
「プレイヤーが最善を尽くした場合、
最長何手までツリーを作り続けられるか？」
を競うのがTreeゲームです。

n色おはじきで構築できる
最長手数の長さを
TREE(n)と呼びます。