単語ゲーム

有限のアルファベット（例えば26個の英文字）を使って単語のリストを作るゲームを想定します。ルールは「リストの後に来る単語は、前に出たどの単語も包含してはいけない」というものです（ここでいう「包含」とは、長い単語の一部を消去したとき、文字の順番を変えずにその短い単語が作れる状態を指します）。このゲームには文字数の制限もあり、例えば最初の単語は2文字、次は3文字。というように続きます。 驚くべきことに、このゲームをどうプレイしても、必ず最大スコア（つまりリストの最大の長さ）が存在します。

第一段階として、非構造的な方法を用いて「ルールを満たす無限の長さのリストは絶対に存在しない」ことを証明します。 もし無限に続くリストが存在すると仮定するなら、「最も極限の」無限リストを構築してみましょう。最も短い単語を w1 として選び、w1 の後に続いて無限に書き続けられるすべての単語の中から最も短いものを w2 として選びます。これを繰り返します。注意すべきは、w1、w2 は毎回、その位置で選べる最も短い単語を選んでいるという点です。 アルファベットの種類は有限ですが、リストは無限に長いため、鳩の巣原理により、少なくとも一つの文字（ここでは「Q」とします）が最初の文字として無限回出現することが必然となります。 ここで、ある操作を行います。

w1 から順に探していき、最初の文字がQである「最初の単語」を見つけます。この単語以降にあるすべての「Qで始まる単語」を抜き出し、それらの先頭のQをすべて削除します。そして、これらQを削除した単語群を、「最初のQの単語」が現れる直前の位置にそのまま繋げ合わせます。 不思議なことが起こります。この新しくつなぎ合わせたリストも、依然としてゲームのルールを満たす無限リストなのです。なぜなら、もし前の単語が「Qを取り除いた単語」を包含していたり、逆に「Qを取り除いた単語」が後ろの単語を包含していたりする場合、Qを元に戻せば、元のリストにも必ず「包含」関係が存在することになります。しかし、それでは元のリストがルールを満たしていたことと矛盾するからです。 新しいリストがルールを満たしているとなると、致命的な矛盾が生じます。新しいリストにおいて、元の「最初のQの単語」があった位置に来た単語は、文字Qが一つ減ったことでより短くなっているのです。しかし、これは不可能です。なぜなら、私たちは最初から、元のリストのその位置では「選べる最も短い単語」を選んだと規定していたからです。

この仮定は論理的な崩壊を引き起こしました。したがって、ルールを満たす無限に長いリストなど、最初から存在しない。