「数学コラム Tree3の停止性の証明2-1 (2021/01/11)」
Kruskalのツリー定理。およびTree3の停止性の証明 第02話 パート1。
停止性証明へのロードマップ
これが結構時間かかりそうなので・・・
まずはTree3のおさらいから始めることにしましょう。
Treeゲームのルールはシンプルです。
ルール1.
ルール2.
ルール3.
使うのはn色のおはじき
ルール2.
Mターン目に置けるおはじきの数は最大M個(M未満を置いても良い)。それでツリーを作る。
ルール3.
以前作ったツリーからの「ノード拡張(※)」を作ったらゲームオーバー
※「ノード拡張」とは:
ツリーAの好きな場所に、好きな色のおはじきを挿入して
ツリーBを作れる時。
(つまり一方的な拡張。ノードの変形や削除はできない)
この時ツリーBはツリーAのノード拡張と呼び
A≦B
と記述します。
ツリーAの好きな場所に、好きな色のおはじきを挿入して
ツリーBを作れる時。
(つまり一方的な拡張。ノードの変形や削除はできない)
この時ツリーBはツリーAのノード拡張と呼び
A≦B
と記述します。
この3つのシンプルなルールで
「プレイヤーが最善を尽くした場合、
最長何手までツリーを作り続けられるか?」
を競うのがTreeゲームです。
n色おはじきで構築できる
最長手数の長さを
TREE(n)と呼びます。