Das Schubfachprinzip

Verteile mehr Dinge auf Fächer, als es Fächer gibt, und ein Fach erhält zwei. Das ist das ganze Prinzip. Die Kunst liegt darin, die Fächer klug zu wählen. Hier sind drei Probleme, bei denen die Fächer versteckt sind. Wähle selbst die Zahlen oder färbe die Verbindungen, und die Seite zeigt dir, welches Fach überläuft.

Rechenbeispiel — Das Schubfachprinzip

Zahlen in Fächern	Kollision erzwungen
Fach mit zwei Zahlen	5 \| 10
Fach 9	9
Fach 11	11
Fach 13	13
Fach 15	15

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Das Schubfachprinzip

Das Schubfachprinzip: Wenn N Dinge auf k Fächer verteilt werden und N > k gilt, enthält mindestens ein Fach zwei Dinge. Genauer gesagt enthält ein Fach mindestens ⌈N/k⌉, die kleinste ganze Zahl, die mindestens N/k ist.

Was die einzelnen Symbole bedeuten

N: die Anzahl der verteilten Dinge
k: die Anzahl der Fächer
⌈N/k⌉: N/k aufgerundet: das Minimum, das das vollste Fach enthalten muss

Woher die Formel kommt

Warum ⌈N/k⌉. Wenn jedes Fach weniger als N/k Dinge enthielte, würden die k Fächer zusammen weniger als k × N/k = N fassen. Dennoch enthalten sie alle N Dinge. Ein Fach enthält also mindestens N/k, und da es eine ganze Zahl von Dingen fasst, mindestens ⌈N/k⌉. Fünf Verbindungen in zwei Farben liefern ⌈5/2⌉ = 3 einer Farbe; sechzehn Verbindungen in drei Farben liefern ⌈16/3⌉ = 6.
Die Fächer für die Teiler wählen. Jede ganze Zahl ist, auf genau eine Weise, eine ungerade Zahl mal eine Zweierpotenz, m × 2ᵃ; lege sie in Fach m. Zwei Zahlen in einem Fach sind m × 2ᵃ und m × 2ᵇ mit a < b, und die erste teilt die zweite. Die ungeraden Zahlen von 1 bis 2n sind 1, 3, …, 2n − 1. Das sind n Fächer, weshalb n + 1 Auswahlen zwei in dasselbe Fach zwingen. Die Schranke ist exakt: n + 1, …, 2n sind n Zahlen, eine pro Fach, und keine teilt eine andere. Denn selbst die kleinste von ihnen verdoppelt übersteigt bereits 2n.
Von gleichen Summen zu disjunkten Gruppen. Zwei verschiedene Gruppen A und B mit derselben Summe können gemeinsame Zahlen haben. Entferne die geteilten Zahlen aus beiden. Jede Summe sinkt um denselben Betrag, die Summen bleiben also gleich. Keine der Gruppen wird leer, denn wenn A vollständig in B läge, hätte B die größere Summe, da alle Zahlen positiv sind. Übrig bleiben zwei disjunkte, nicht-leere Gruppen mit gleichen Summen, und genau das zeichnet die Seite.

Neun Zahlen von 1 bis 16: Eine teilt immer eine andere 🖖

Schreibe jede Zahl als eine ungerade Zahl mal eine Zweierpotenz: 12 = 3 × 4, 10 = 5 × 2. Zahlen mit demselben ungeraden Anteil kommen in dasselbe Fach, und die kleinere teilt die größere, weil sie sich nur um Zweierpotenzen unterscheiden. Von 1 bis 16 gibt es acht ungerade Zahlen. Das ergibt acht Fächer, und neun gewählte Zahlen befördern zwei in dasselbe Fach. Klick auf 9 bis 16, um acht Zahlen zu sehen, die entkommen, eine pro Fach: Nur 10 der 12.870 Auswahlen von acht Zahlen tun dies. Klick danach auf 9 bis 16 und 5. Alle 11.440 Auswahlen von neun Zahlen enthalten ein teilendes Paar, und die Fächer beweisen es, ohne auch nur eine einzige zu prüfen.

Unter sechs Personen sind drei untereinander Freunde oder drei sind sich fremd 🖖

Klick auf Sechs Personen und betrachte Person 1. Ihre fünf Verbindungen kommen in zwei Farben. Mindestens drei teilen sich also eine Farbe; sagen wir, sie sind befreundet. Wenn zwei dieser drei miteinander befreundet sind, bilden sie und Person 1 drei gemeinsame Freunde. Ist das bei keinem Paar der Fall, sind diese drei einander völlig fremd. So oder so taucht ein Dreieck auf, und dieses Argument hat sich die Färbung nicht einmal angesehen. Fünf Personen können dem entgehen, mit Freunden entlang eines Fünfecks und Fremden quer hindurch. Von den 1.024 Möglichkeiten, die Verbindungen von fünf Personen zu färben, vermeiden 12 ein einfarbiges Dreieck. Jede davon ist dieses Fünfeck in irgendeiner Anordnung. Keine der 32.768 für sechs tut dies. Greenwood und Gleason formulierten dieses Argument im Jahr 1955.

Zehn zweistellige Zahlen verbergen immer zwei gleiche Summen, und neun tun das auch 🖖

Klick auf Zehn Zahlen. Zehn verschiedene zweistellige Zahlen bilden 2¹⁰ − 1 = 1.023 nicht-leere Gruppen. Eine solche Gruppe kann nur eine Summe von 10 bis 90 + 91 + … + 99 = 945 annehmen, was 936 Werten entspricht. Zwei Gruppen teilen sich also eine Summe. Nimm die gemeinsamen Zahlen weg, und die Summen bleiben gleich, während die Gruppen disjunkt werden. Das war das erste Problem der Internationalen Mathematik-Olympiade 1972. Bei neun verschiedenen Zahlen stehen 511 Gruppen höchstens 846 Summen gegenüber, und bloßes Zählen bringt uns nicht weiter. Die Wahrheit geht über das Zählen hinaus: Neun Zahlen mit lauter verschiedenen Gruppensummen erfordern, dass eine davon mindestens 161 ist (eine Berechnung von J. P. Grossman). Neun zweistellige Zahlen kollidieren also ebenfalls immer. Acht können entkommen; klick auf Acht, die entkommen.

Aufgabe vollständig gelöst

Wie viele Personen erzwingen ein einfarbiges Dreieck bei drei Farben? 4 Schritte
Jedes Paar ist nun befreundet, sich fremd oder verfeindet: drei Farben statt zwei. Wie viele Personen garantieren drei, die alle in einer einzigen Farbe verbunden sind?

Öffne diese Aufgabe im Tool
1. Mit zwei Farben beginnt das Argument der Seite bei den Verbindungen einer Person:
  
  $6 people : 5 links, 2 colours \Rightarrow ⌈ \frac{5}{2} ⌉ = 3 share a colour$
2. Bei drei Farben betrachte eine Person unter 17. Ihre 16 Verbindungen fallen in drei Farben:
  
  $17 people : 16 links, 3 colours \Rightarrow ⌈ \frac{16}{3} ⌉ = 6 share a colour$
3. Wenn zwei dieser sechs in genau dieser Farbe verbunden sind, bilden sie und die erste Person ein einfarbiges Dreieck:
  
  $a link of that colour among the 6 \Rightarrow a triangle through person 1$
4. Ist dies nicht der Fall, nutzen die sechs nur die anderen beiden Farben. Die Party mit sechs Personen auf dieser Seite garantiert dann bereits ein Dreieck unter ihnen:
  
  $no such link \Rightarrow the 6 use 2 colours \Rightarrow a triangle, since R (3, 3) = 6$
Antwort

Siebzehn Personen reichen immer aus. Greenwood und Gleason zeigten 1955, dass sechzehn nicht genügen: Sie färbten die Verbindungen von sechzehn Personen in drei Farben ohne ein einfarbiges Dreieck. Bei vier Farben kennt niemand die Antwort. Sie liegt zwischen 51 und 62.

$R (3, 3, 3) = 17; 51 \leq R (3, 3, 3, 3) \leq 62$

Lernpfad

Beweismethoden

Quellen (5)

The party problem solved exactly as this page solves it, the pentagon with red sides and blue diagonals for five and one person's five links for six, and Theorem 4, three colours need exactly 17 people, which is the worked problem: R. E. Greenwood and A. M. Gleason, "Combinatorial Relations and Chromatic Graphs", Canadian Journal of Mathematics 7, 1–7 (1955).
The equal-sums problem as it was set, ten distinct two-digit numbers, with the count of 1,023 groups against sums of at most 945: 14th International Mathematical Olympiad, 1972, Problem 1; problem and solution in J. Scholes's IMO archive (Kalva).
Why nine two-digit numbers cannot escape either: nine numbers with all their subset sums different need one at least as large as 161: OEIS Foundation, "A276661: Least k such that there is a set S in {1, 2, ..., k} with n elements and the property that each of its subsets has a distinct sum", The On-Line Encyclopedia of Integer Sequences.
Three colours are settled at 17; four are not, and the answer lies between 51 and 62: OEIS Foundation, "A003323: Multicolor Ramsey numbers R(3,3,...,3), where there are n 3's", The On-Line Encyclopedia of Integer Sequences.
The principle stated and used, including its generalised form, ⌈N/k⌉ in some box: E. Lehman, F. T. Leighton and A. R. Meyer, Mathematics for Computer Science, MIT, revised 6 June 2018, §15.8, The Pigeonhole Principle.

Vom 42Math-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.