Eddie rechnet: IMO 1985 Aufgabe B1

Gegeben sei eine Menge aus 1985 verschiedenen positiven ganzen Zahlen. Keine dieser Zahlen besitzt einen Primteiler größer als . Alle Primfaktoren liegen also in .

Zu zeigen ist: In gibt es vier verschiedene Zahlen , deren Produkt eine vierte Potenz ist:

Sei die Liste der erlaubten Primzahlen. Hier ist

Jede Zahl lässt sich eindeutig schreiben als

Dann gilt:

• ist ein Quadrat genau dann, wenn alle Exponenten gerade sind:
• ist eine vierte Potenz genau dann, wenn alle Exponenten durch teilbar sind:

Die Grundidee des Beweises ist daher zweistufig:

1. Zuerst sorgen wir dafür, dass Exponenten gerade werden (Quadrat).
2. Dann sorgen wir dafür, dass die Exponenten der Quadrat-Wurzeln wieder gerade sind.

Für jedes betrachten wir nur, welche Primzahlen mit ungeradem Exponenten vorkommen.

(A) Quadratfreier Kern

Man kann eindeutig zerlegen als

wobei quadratfrei ist. Dann enthält genau die Primzahlen, die in ungerade oft vorkommen.

(B) Paritätsvektor

Definiere

Dieser Vektor speichert: Exponent ungerade (=1) oder gerade (=0).

Wichtiger Merksatz:

Denn dann ist in jeder Exponent gerade. Es gibt insgesamt nur Paritätsklassen.

Wir zeigen die stärkere Behauptung:

Wichtig: Es ist weiterhin dieselbe Menge wie in der Aufgabenstellung; wir benutzen ab hier nur noch die schwächere Information, dass .

Angenommen, alle Zahlen in haben ihre Primteiler in . Gilt

dann gibt es paarweise verschieden und ein mit

Für unsere Aufgabe ist . Also:

Damit folgt das IMO-Ergebnis direkt aus der allgemeinen Behauptung.

Ab hier benutzen wir nur noch die Schranke ; die konkrete Zahl ist nur ein Spezialfall davon.

Schubfachprinzip: Verteilt man mehr Objekte als es Schubfächer gibt, dann enthält mindestens ein Schubfach mindestens zwei Objekte.

Stufe A — Wir bilden viele disjunkte Quadrat-Paare

Ordne jede Zahl nach ihrem Paritätsvektor . Sei die Anzahl der Zahlen in Klasse .

In jeder Klasse können wir paarweise zusammenfassen (1. mit 2., 3. mit 4., ...). Das ergibt in Klasse genau disjunkte Quadrat-Paare. Jedes so gebildete Paar hat ein Quadrat als Produkt, denn und damit ist ein Quadrat.

Insgesamt also:

Mit folgt:

Setzen wir ein, dann:

Da eine ganze Zahl ist, folgt daraus .

Ergebnis von Stufe A: Mindestens disjunkte Paare mit .

Stufe B — Aus zwei passenden Quadrat-Paaren wird eine vierte Potenz

Jedes Paar liefert ein Quadrat (mit , weil ein Quadrat ist). Für schreiben wir

Es gibt nur mögliche Wurzel-Paritäten, aber mindestens Paare. Also existieren zwei verschiedene Paare mit und .

Dann ist nach dem Merksatz aus Teil 3 das Produkt ein Quadrat, also , und damit:

Wichtig: Die Paare aus Stufe A sind disjunkt, also haben zwei verschiedene Paare keine gemeinsame Zahl. Damit sind automatisch vier verschiedene Elemente.

Damit ist die Behauptung bewiesen.

Betrachte

Für die ersten vier Zahlen gilt jeweils (mit gleichem quadratfreiem Kern ). Hier erhält man sogar:

Eddie:Mini-Eddie-Kommentar

Nettes Warm-up, oder? Das Beispiel zeigt die Idee zum Anfassen, aber der eigentliche IMO-Beweis läuft oben ganz sauber über die zwei Schubfach-Schritte - ohne Ratespiel und ohne Glückstreffer.