Unter sechs Fremden gibt es immer ein Dreieck: 2^15 Fälle zu prüfen

R(3,3) = 6, die fünfzehn Paare ergeben 32 768 Färbungen, und jede von ihnen verbirgt ein Dreieck.

Statistik und Daten · Niveau: Klassisches Ergebnis · Aktualisiert am 2026-11-10

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.

Dies ist eine unabhängige Tool-Website eines Drittanbieters. Sie ist weder mit Casio, Texas Instruments oder deren Vertriebspartnern verbunden noch von ihnen gesponsert oder autorisiert. Modell- und Produktnamen sind Marken der jeweiligen Inhaber und erscheinen hier nur zur Identifizierung der Geräte.

Die Tastenfolgen in diesen Handbüchern wurden aus den eigenen Layoutdaten dieser Website erstellt — denselben Daten, die der Online-Rechner darstellt — sowie aus öffentlich verfügbaren Produktinformationen. Spezifikationen und regionale Konfigurationen werden am physischen Gerät und anhand der neuesten Unterlagen des Herstellers überprüft.