Eddie denkt über die Aufgabe A2 der IMO 85 nachJoutsa, 4. Juli 1985
Ich höre das Kratzen von dreißig Bleistiften gleichzeitig und finde es plötzlich beruhigend. Das ist mein Element: Regeln lesen, Muster finden, fertig.
Hier geht’s nicht um Linien und Kreise, sondern um eine Reihe von Zahlen, die man in zwei Farben anstreicht. Klingt wie Kinderkram – aber die Aufgabe legt zwei fiese Regeln fest. Die erste sorgt dafür, dass Zahlen, die “spiegelbildlich” zueinander stehen, dieselbe Farbe haben müssen. Die zweite kettet noch mehr Zahlen zusammen: Sobald du eine Zahl anders färbst als eine ganz bestimmte Lieblingszahl, zwingt dich die Regel, andere mit ihr gleich zu färben.
Und dann kommt der eigentliche Punch: Du sollst zeigen, dass diese Regeln am Ende alles einfärben, ohne dass du noch Wahlfreiheit hast. Egal wie du anfängst – du landest bei “alle gleich”.
Hier zeige ich dir die einfache Logik dahinter, Schritt für Schritt, mit Formelkram.
Teil 1 — Aufgabenstellung
IMO 1985 – Aufgabe A2: „Am Ende hat alles eine Farbe“
Seien teilerfremde positive ganze Zahlen mit . Die Menge
werde so gefärbt, dass jede Zahl entweder blau oder weiß ist.
Regel 1 (Spiegel): Für jedes haben und dieselbe Farbe.
Regel 2 (Abstand zu ): Für jedes mit haben und dieselbe Farbe.
Zu zeigen: Alle Zahlen in müssen dieselbe Farbe haben.
Teil 2 — Idee (ein Rundgang, der alle besucht)
Stell dir die Zahlen wie Punkte auf einer Uhr vor (Rechnen modulo ):
- Nach kommt wieder .
- bedeutet: Wir schauen nur auf den Rest beim Teilen durch .
Jetzt machen wir einen Rundgang in Sprüngen der Länge :
Warum ist das spannend? Weil genau heißt, dass die Sprünge so günstig sind, dass man dabei alle Reste trifft (nur in anderer Reihenfolge).
Und wenn wir zeigen, dass jede zwei aufeinanderfolgenden besuchten Zahlen dieselbe Farbe haben, dann haben am Ende alle dieselbe Farbe.
Teil 3 — Beweis in klaren Schritten
Schritt 1 — Die -Sprünge treffen alle Zahlen
Behauptung: Die Reste
sind (bis auf Reihenfolge) genau die Zahlen .
Begründung: Angenommen, zwei Sprünge landen auf demselben Rest:
Dann gilt
also teilt das Produkt . Weil und teilerfremd sind, folgt
Für bedeutet das . Also sind alle Reste verschieden — und damit eine Umordnung von .
Schritt 2 — Zwei aufeinanderfolgende Sprünge haben dieselbe Farbe
Für sei der Rest von modulo , als Zahl in . Aus Schritt 1 wissen wir: sind genau (kein ).
Vergleiche zwei Nachbarn und . Weil
gilt modulo :
Das heißt: entweder kein Überlauf oder Überlauf.
Fall A: Kein Überlauf
Dann ist
Also
Da außerdem gilt (denn aus würde folgen, also . Dann teilt das Produkt . Wegen muss daraus folgen – das ist für unmöglich.), dürfen wir Regel 2 anwenden: und haben dieselbe Farbe.
Fall B: Überlauf
Dann ist
Setze
In diesem Fall ist , also und .
Jetzt kommen die Regeln:
- Aus Regel 1 folgt: und haben dieselbe Farbe.
- Aber .
Also hat dieselbe Farbe wie .
Und aus Regel 2 folgt (weil ): hat dieselbe Farbe wie .
Damit sind sowohl als auch gleichfarbig zu , also auch zueinander gleichfarbig.
Zwischenergebnis: Für alle haben und dieselbe Farbe.
Schritt 3 — Dann sind alle Zahlen gleichfarbig
Die Folge enthält (aus Schritt 1) jede Zahl aus genau einmal.
Aus Schritt 2 wissen wir: Jede Nachbarzahl hat dieselbe Farbe. Also hat die ganze Kette dieselbe Farbe — und damit haben alle Zahlen in dieselbe Farbe.
- Teilerfremd () sorgt dafür, dass die -Sprünge alle Zahlen besuchen.
- Die beiden Regeln sorgen dafür, dass bei jedem Sprung die Farbe gleich bleibt (direkt oder über den Spiegel).
- Wenn alle auf einer Route miteinander verbunden sind, kann es am Ende nur eine Farbe geben.
Spielplatz: Prüfe es für konkrete n und k
Ich baue die „gleichfarbig“-Regeln als Graph: Kante bedeutet „muss gleiche Farbe haben“. Wenn der Graph zusammenhängend ist, erzwingt das eine einzige Farbe.
Die k-Sprung-Kette (mod n)
O2