Eddie denkt über die Aufgabe A3 der IMO 85 nachJoutsa, 4. Juli 1985
Ich grinse, als ich das Wort “Polynom” sehe. Das ist wie ein alter Bekannter. Ich fühle mich wach, schnell, fast übermütig – als könnte ich mit einem Blick erkennen, wo der Trick liegt.
Die Aufgabe ist eigentlich eine Frage nach “gerade oder ungerade”, aber versteckt in einer ganzen Familie von Ausdrücken. Stell dir vor, du hast Rechenausdrücke, die aus vielen Zahlen bestehen, die an verschiedene “Stellen” gehören. Manche dieser Zahlen sind gerade, manche ungerade. Jetzt nimmst du ein paar ganz besondere Ausdrücke, die alle nach dem gleichen Bauplan entstehen (so wie beim Aufklappen von Klammern), und addierst sie.
Was soll passieren? Du sollst beweisen, dass beim Addieren etwas nicht “weggezaubert” werden kann: Die Anzahl der ungeraden Zahlen in dieser Liste wird nicht kleiner, als sie am Anfang schon war.
Hier übersetze ich das in Bilder im Kopf: Muster, Schichten, und warum sich “ungerade” nicht so leicht verstecken lässt.
Teil 1 — Aufgabenstellung
Für ein Polynom mit ganzzahligen Koeffizienten bezeichne die Anzahl der ungeraden Koeffizienten. Für sei .
Zu zeigen ist: Für ganze Zahlen gilt
In Worten: Wenn wir mehrere dieser Polynome addieren, hat die Summe mindestens so viele ungerade Koeffizienten wie schon der erste Summand allein.
Teil 2 — Kernidee (nur „ungerade/gerade“ zählt)
Wir interessieren uns nur dafür, ob ein Koeffizient ungerade oder gerade ist. Dafür reicht es, alles modulo 2 zu betrachten.
- ungerade
- gerade
Beim Addieren gilt modulo 2: , . Das ist ein „entweder-oder“: Der Koeffizient der Summe ist genau dann ungerade, wenn genau einer der beiden Koeffizienten ungerade ist.
Ein Bild, das man kennen darf: Pascalsches Dreieck modulo 2
Die Binomialkoeffizienten erfüllen:
Modulo 2 heißt das: Ein Eintrag ist ungerade genau dann, wenn die beiden darüber verschiedene Parität haben. So entsteht ein auffälliges dreieckiges Muster (man sieht es gut, wenn man das Pascalsche Dreieck nur nach ungerade/gerade färbt).
Zwei Rechenregeln für
Lemma 1 (Verdoppeln):
Warum? und .
Lemma 2 (Verdoppeln + 1):
Damit kann man ohne Spezialwissen bestimmen
Schreibe in Binärdarstellung und sei die Anzahl der Einsen. Dann gilt:
- Aus Lemma 1 folgt : Bei bleiben nur Lücken in den Exponenten, die Anzahl ungerader Koeffizienten bleibt gleich.
- Aus Lemma 2 folgt : Multiplikation mit kopiert jeden ungeraden Koeffizienten einmal nach links und einmal nach rechts; hier überlappen sich die Kopien nicht, weil nur gerade Exponenten hat und nur ungerade Exponenten.
Liest man binär von links nach rechts, bedeutet jede 0: Anzahl bleibt, jede 1: Anzahl verdoppelt sich. Also wird genau -mal verdoppelt.
Teil 3 — Beweisidee (Induktion mit einem „2er-Fenster“)
Wir beweisen die Aussage per Induktion über den größten Exponenten .
Schritt 1 — Spezialfall: ist eine Zweierpotenz
Sei . Dann gilt modulo 2:
Wenn nur Potenzen enthält (also ), dann:
Grund: und liegen in verschiedenen Exponentenbereichen und können sich nicht gegenseitig auslöschen.
Schritt 2 — Induktionsschritt: wähle ein Fenster
Wähle eine Zweierpotenz mit (z.B. die größte Zweierpotenz, die nicht größer als ist). Dann liegen alle Exponenten entweder unter oder in .
Fall A —
Setze . Dann ist und
Damit folgt:
Also reduziert sich alles auf , wieder mit dem Faktor 2 aus zwei nicht überlappenden Exponentenbereichen, und das ist die Induktionsannahme.
Fall B —
Splitte:
Dann:
Mit gilt:
Damit kann man direkt zählen:
Außerdem gilt : Betrachte einen Exponenten mit Koeffizienten in und in . Modulo 2 gilt . Ist ungerade, dann ist mindestens einer der beiden Koeffizienten in oder ungerade; daher deckt alle ungeraden Koeffizienten von ab. Damit:
Also insgesamt:
Die Schwierigkeit steckt hier nicht in einem Spezialtheorem, sondern in zwei gut erklärbaren Ideen:
- Modulo 2 denken (ungerade/gerade statt Zahlenwerte).
- Zweierpotenzen als Trennlinie: erzeugt eine saubere Zerlegung in zwei nicht überlappende Blöcke.
Alles andere sind Induktion und direkte Paritäts-Logik.
Spielplatz: Odd-Koeffizienten zählen
Gib Exponenten ein (aufsteigend). Der Rechner bestimmt und und prüft die Ungleichung.
Eingabeformat: ganze Zahlen zwischen 0 und 256, z.B. 1, 3, 4, 7. Duplikate und unsortierte Eingaben werden automatisch bereinigt.
Paritätstabellen & Beweisspur
| Summand | Binär | o(Qi) | Ungerade Grade r in Qi |
|---|---|---|---|
Q1 | 1 | 2 | 0, 1 |
Q3 | 11 | 4 | 0, 1, 2, 3 |
Q4 | 100 | 2 | 0, 4 |
Q7 | 111 | 8 | 0, 1, 2, 3, 4, 5, 6, 7 |
r=1: A-Exponenten 1, 3, B-Exponenten (reduziert) 0, 3. O3