Färben Sie jede der Linien, die sechs Punkte verbinden, rot oder blau. Irgendwo im Ergebnis gibt es ein Dreieck, dessen drei Seiten alle dieselbe Farbe haben, und sechs ist die kleinste Punktzahl, für die das garantiert ist. Der Beweis ist das Party-Argument: Wählen Sie eine Person, die fünf Beziehungen hat, und mindestens drei davon sind nach dem Schubfachprinzip von derselben Art; kennen sich zwei dieser drei untereinander, haben Sie Ihr Dreieck, und kennt sich keine, sind diese drei einander fremd, und Sie haben das andere. Die sechs Personen ergeben 6 × 5/2 = 15 Paare (zweiter Link), eine Maschine kann es also durch vollständige Enumeration in 2^15 = 32 768 Fällen erledigen (erster Link) – klein genug, dass niemand eine Ausrede hat, es nicht zu tun, und die Schärfe prüft man am Fünferzyklus, einem roten Fünfeck mit einem blauen Stern darin, das auf fünf Punkten beide Dreiecke vermeidet.
Die nächste Diagonalzahl, R(4,4) = 18, kostet 2^153 Färbungen: Achtzehn Punkte haben 18 × 17/2 = 153 Paare untereinander (dritter Link), und 2^153 ist 1.1417981541648⋅10+46 (vierter) – keine Zahl, über die man durch Abzählen streitet. Greenwood und Gleason erhielten 1955 die 18 mit einer Mischung aus Schranken und von Hand geprüften Fällen; R(5,5), die ersten drei Farben derselben Frage, ist seither offen, bekannt ist nur, dass es in einem schmalen Band liegt, das sich in siebzig Jahren ein wenig verschoben hat. Ramseys eigener Satz von 1930 handelte von der logischen Maschinerie unter all dem, und er wurde bewiesen, weil man ihn für eine Frage der Mathematikphilosophie brauchte: die Gewissheit, dass jede hinreichend große Struktur ein großes geordnetes Stück ihrer selbst enthält.
Antwort
32768
So lesen Sie sie
2^15 auf der Rechenfläche: jede Zweifärbung der fünfzehn Paare von sechs Personen. Der zweite Link sind die fünfzehn Paare selbst.
Quelle
Frank P. Ramsey, 'On a Problem of Formal Logic', 1930; R(3,3) = 6 is the party theorem, R(4,4) = 18 was proved by Greenwood and Gleason in 1955, and R(5,5) is still unknown
Im Rechner durchrechnen
Diese Links öffnen den passenden Rechner mit den bereits eingegebenen Zahlen dieser Aufgabe. Die Zeile darüber ist das, was der Bildschirm anzeigen sollte – prüfen Sie selbst.