ゼロからのトライアングルゲーム

16人の人々が3色のいずれかを受け取る接続で、1色のトライアングルを作らずにいること。このアニメーションは、すべてのペア間に接続がある16人を示しています。それは120の接続になり、それぞれが3色のいずれかを受け取ります。着色が完了したとき、3人のグループの3つの相互接続がすべて同じ色であるグループはありません。3色でこれが可能な最大のグループは16人です。GreenwoodとGleasonは1955年にこの例を作成し、17人は不可能であると証明しました。このガイドのすべては、github.com/muchmirul/conjecturesにあるオープンソースリポジトリから来ています。テキスト、すべての図、および各数値の背後にあるテストです。このガイドは、さらに多くの色が利用可能になった場合に何が起こるかを問いかけます。より多くの色があれば、より大きなグループを安全に保つことができますが、追加の色ごとにグループはどれだけ大きくなるでしょうか。Erdősは、その質問に答えるために賞金を提供しました。何十年もの間、最良の構築と最良の限界は非常に離れていたため、研究者は長期的なレートが固定数で停止するかどうかさえ知りませんでした。2026年の結果は、それが決して成長を止めないことを示しました。ガイドは小さなステップで結果を展開します。ほとんどの番号付きセクションには、再生できるページもあり、主な選択を変更して画像が応答するのを見ることができます。すべての図を作成するコードは、このリポジトリに含まれています。テストは数値を再計算し、ここに示されている小さな着色をチェックします。ステートメントが既存の定理から来る場合、テストからではなく、テキストに記載されています。2026年の作業は2つのドキュメントで提示されます。1つは完成した証明を提供します。もう1つは、失敗した以前の試みを含む、アイデアがどのように見つかったかを説明する舞台裏ガイドです。セクション5から7は、古い方法がなぜ停滞したのかを説明します。セクション8から11は、完成した構築を説明します。最後に近い表は、各アイデアが2つのソースドキュメントのどこに現れるかを示しています。まず、ゲームを学びましょう1 ルール2 なぜ6人では安全を保てないのか3 追加の色が何を変えるか次に、質問を見つけましょう4 異なる色の数をどのように比較するか以前のアイデアが停滞した理由5 安全なグループを掛け合わせる6 一般的な上限7 それらの間の広いギャップ完成した構築8 各部屋が省略する色9 到着者を安全なチームに保つ10 すべての選択のための1つの固定されたレフェリー11 部屋をタワーに積み重ねる結果が解決すること12 結果が解決すること画像を変更するには、コントロールを使用してください。アクティビティを独自のページで開く1 · ゲーム人々のグループから始めて、すべてのペアの間に接続を描きます。各接続に色を付けます。3人の任意のグループは、それらの間の各ペアが接続されているため、トライアングルを形成します。3つの接続すべてが同じ色である場合、あなたは負けです。これを1色のトライアングルと呼びます。1色のトライアングルがない完成した着色は安全と呼ばれます。安全な着色を持つグループは、安全なテーブルと呼ばれます。左側に1色のトライアングルがあり、右側に安全な結果がある4人の2つの着色左側の太いトライアングルは、すべての3つの側面で1色を使用しているため、その着色は失われます。右側では、これらの4つのトライアングルのそれぞれが少なくとも2色を使用しているため、着色は安全です。2色で、5人のグループを安全に保つことができます。人々を再命名したり、色を交換したりすることを除けば、それを実行する方法は1つしかありません。5人を円形に配置します。外周の隣接するペアに最初の色を使用し、次に円を横切る5つの接続に2番目の色を使用します。着色された5人の人々の間の10の接続、その後、すべての10のトライアングルのチェック最終的なスキャンは、可能なすべての3人のグループをチェックします。それらは10あり、それぞれが両方の色を使用しています。したがって、安全性は画像の見た目に基づいているわけではありません。それは、短く完全なリストをチェックすることから来ています。このリポジトリのテストは同じチェックを実行します。パターンを理解するための簡単な方法もあります。どちらかの色を単独で見ます。その5つの接続はリングを形成し、リングにはトライアングルが含まれていません。どちらの色も単独でトライアングルを作成できないため、結合された着色は安全です。画像を変更するには、コントロールを使用してください。アクティビティを独自のページで開く2 · 6人は強制される5人は2色で安全を保つことができます。6人はできません。これは、このガイドで完全に証明された唯一の定理であり、すべてのステップをアニメーションで見ることができます。6人のうちの1人を選び、その人から伸びる5つの接続を見てください。利用できる色は2つだけです。2つの接続が各色を占めると4つしか説明できないため、それらの5つの接続のうち少なくとも3つは同じ色でなければなりません。それらの3つが赤だと仮定します。1人からの3つの同じ色の接続が、赤または青のトライアングルを強制する次に、それらの赤い接続の他の端にある3人に焦点を当てます。それらのうちのいずれかのペアが赤で結合されている場合、その接続と最初の人への2つの赤い接続が赤いトライアングルを形成します。その結果を避けるためには、それらの人々間のすべての3つの接続は青でなければなりません。しかし、それらの3つの青い接続は代わりに青いトライアングルを形成します。どちらの場合も1色のトライアングルが現れます。最初のカウントステップは、しばしば鳩の巣原理と呼ばれます。より多くのオブジェクトがより少ないグループに配置されると、1つのグループが複数のオブジェクトを受け取らなければなりません。引数は接続がどのように色付けされたかに依存しなかったため、6人のすべての可能な2色着色をカバーします。コンピュータテストは同じ主張を別の方法でチェックします。6人には15の接続があり、各接続には2つの選択肢があり、合計32768の完全な着色があります。テストはそれらすべてを検査し、安全なものがないことを見つけます。1色のトライアングルの数でグループ化された6人のすべての32768の2色着色ゼロのバーは、すべての着色が1色のトライアングルを含むことを確認します。1のバーも空です。6人の着色のうち最良のものでさえ、正確に2つの1色のトライアングルを含み、1つだけではありません。Goodmanは1959年にこのより強い観察を記録し、網羅的なテストはそれを再び見つけます。2色の物語はこれで完了です。5人は安全を保つことができますが、6人は損失を強制します。6を2色の強制サイズと呼びます。これは、1色のトライアングルが避けられない最初のグループサイズを意味します。画像を変更するには、コントロールを使用してください。アクティビティを独自のページで開く3 · より多くのクレヨン3番目の色を追加すると、さらに大きな安全なグループが可能になります。最良の安全サイズは5人から16人にジャンプします。最初の開示アニメーションは完全な着色を示していました。次の画像は3つの色を分離して、それぞれを単独でチェックできるようにします。三角形を含まない3つの色層に分離された16人の着色各パネルには、1色の接続が含まれています。各人は各パネルで5つの接続を持っていますが、どのパネルにも三角形は含まれていません。1色のトライアングルは、これらのパネルのいずれかに完全に現れる必要があるため、完全な3色のパターンは安全です。GreenwoodとGleasonは1955年にこのパターンを作成しました。このリポジトリは、彼らの指示からそれを再構築し、すべての560の3人のグループをチェックします。彼らはまた、17人は3色で安全を保つことができないと証明しました。直接的なコンピュータスキャンは、136の接続のそれぞれに3つの選択肢を考慮する必要があります。これは、このプロジェクトのケースバイケースチェックをはるかに超えています。したがって、ガイドはそれを検証することを主張するのではなく、彼らの定理を引用します。3色後、正確な強制サイズは知られていません。1、2、3色の正確な答え、その後4色の開いた範囲4色の場合、強制サイズは51から62の間にあることが知られています。つまり、50人の安全な着色が知られており、62人のすべての着色が失敗することが知られていますが、その間の正確な点は未解決のままです。5色の場合、不確実性はさらに広いです。3色を超える色の数については、正確な答えは知られていません。可能な数の数