「Tree3の停止性証明 まとめ1 （2023/12/16)」



数学には
　　Tree(3)
と言う。
とてつもなく、すさまじく、ウルトラ巨大な数が
存在しています。

(その大きさを説明するだけで数十ページの本が必要になる）


ですが、Tree(3)は巨大だが
決して∞ではない。

必ず有限の長さで終了する事も証明されています。

それをマンガで説明したのが、
↓のシリーズです。


Kruskalのツリー定理。およびTree3の停止性の証明　第0章。











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



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

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

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

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

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

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

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











ここから証明スタート

Tree3の停止性の証明　第01章。




簡単な用語ノート



Tree3の停止性の証明　第02章。








Tree3の停止性の証明　第03章。










Tree3の停止性の証明　第3.5章。






Tree3の停止性の証明　第4章。







Tree3の停止性の証明　第5章。







続く。