Ein schwieriges Problem auf der IMO
Von: trunx
Datum: So. 08. Dezember 2019 08:36:17
Thema: Mathematik
\(\usepackage{setspace}\)
|
Auf der Wikipediaseite "Internationale Mathematik-Olympiade" werden die zwei schwersten Probleme genannt, die je auf einer IMO gestellt worden sind. Beide Aufgaben konnten nur von 11 Schülern gelöst werden, einmal (1986) bei insgesamt 210, das zweite Mal (1988) bei insgesamt 268 Teilnehmern.
Während für die erste dieser Aufgaben auch eine Lösung verlinkt wurde, habe ich für die zweite Aufgabe keine Lösung im Internet gefunden (aber auch nicht wirklich intensiv danach gesucht). Da es zudem hieß, dass weder die Mitglieder des Aufgabenausschusses noch von ihnen beauftragte Mathematiker des entsprechenden Fachgebietes (Zahlentheorie) die Aufgabe in 6h lösen konnten, war bei mir das Interesse geweckt.
Die Aufgabe lautete (siehe hier):
Let \(a\) and \(b\) positive integers such that \(ab+1\) divides \(a^2 +b^2\). Show that
\[\frac{a^2 +b^2}{ab+1}\]
is the square of an integer.
(dt. lt. wikipedia: Sind \(a\) und \(b\) natürliche Zahlen, sodass \[c=\frac{a^2 +b^2}{ab+1}\] ebenfalls eine natürliche Zahl ist, ist c sogar eine Quadratzahl.)
Ich habe deutlich mehr als 6h für die Lösung gebraucht, aber es hat Spass gemacht. Daher, wer es selbst probieren will, macht jetzt besser den PC aus und rechnet!
Nachtrag: Die nachgelieferte Zuendeführung des angekündigten Beweises findet sich im nächsten Abschnitt in blauer Schrift.
Beweis
Die entscheidende Beweisidee ist folgende: Wäre obiges c als Lösung eine nicht näher spezifizierte Zahl q, dann gibt es natürlich für a und b jeweils q-adische Darstellungen. Diese seien
\[a=\sum \limits_{i=0}^{n} a_i q^i\]
\[b=\sum \limits_{j=0}^{m} b_j q^j\]
Wir setzen nun in \(c\cdot (ab+1)=q\cdot (ab+1)=a^2 +b^2\) diese beiden Darstellungen ein und machen einen Koeffizientenvergleich zwischen den so entstehenden Polynomen in q.
Man erhält
\((1+a_0 b_0 )q +(a_0 b_1 +a_1 b_0 )q^2 +(a_0 b_2 +a_1 b_1 +a_2 b_0)q^3 + ... =a_0^2 +b_0^2 +2(a_0 a_1 +b_0 b_1 )q+(2a_0 a_2 +a_1^2 +2b_0 b_2 +b_1^2 )q^2 +...\)
Daraus erhält man zunächst \(a_0^2 +b_0^2 =0\) und damit \(a_0 =b_0 =0\). Aber schon die Koeffizienten von q können nicht gleich werden, d.h. um die gesamte Gleichung doch noch erfüllen zu können, müsste \(q=0\) gesetzt werden, es wäre also a = b = c = 0; c kann also nicht einfach irgendeine natürliche Zahl sein.
Lt. Aufgabenstellung ist sie das auch nicht, wir setzen also \(c=q^2\) an, die q-adischen Darstellungen von \(a\) und \(b\) bleiben.
Diese eingesetzt in nunmehr \(q^2 (ab+1)=a^2 +b^2\) ergibt:
\((1+a_0 b_0 )q^2 +(a_0 b_1 +a_1 b_0 )q^3 +(a_0 b_2 +a_1 b_1 +a_2 b_0)q^4 + ... =a_0^2 +b_0^2 +2(a_0 a_1 +b_0 b_1 )q+(2a_0 a_2 +a_1^2 +2b_0 b_2 +b_1^2 )q^2 +...\)
und im Koeffizientenvergleich zunächst ebenfalls \(a_0^2 +b_0^2 =0\) und damit \(a_0 =b_0 =0\). Aber schon für die nächsten Koeffizienten gilt \(a_1^2 +b_1^2 =1\), also insbesondere (o.B.d.A. wegen der Symmetrie zwischen und a und b) \(a_1^2=1\) und \(b_1=0\).
Das aber bedeutet bereits, es könnte Lösungspaare (a,b) geben für die die in der Aufgabenstellung behauptete Eigenschaft zutrifft.
Um den Beweis abzuschließen, müssen wir noch prüfen, dass es für \(c=q^l\) mit \(l>2\) keine Lösungen gibt. Wir setzen also
\((1+a_0 b_0 )q^l +(a_0 b_1 +a_1 b_0 )q^{l+1} +(a_0 b_2 +a_1 b_1 +a_2 b_0)q^{l+2} + ... =a_0^2 +b_0^2 +2(a_0 a_1 +b_0 b_1 )q+(2a_0 a_2 +a_1^2 +2b_0 b_2 +b_1^2 )q^2 +...\)
Hier erhält man, wie man leicht sieht, in Folge stets \(a_k^2 +b_k^2 =0\) und damit \(a_k =b_k =0\) für alle \(k\ge 0\), sprich auch hier erhält man lediglich die trivialen Lösungen a = b = c = 0.
Wir können also letztlich sagen, dass, wenn c überhaupt eine natürliche Zahl ist, diese eine Quadratzahl sein muss.
q.e.d.
Sei (a,b) ein nichttriviales Lösungspaar der Gleichung (1) \(\frac{a^2+b^2}{ab+1}=c\) (also \(c>1\)). Dann lässt sich aus diesem Paar eine Folge \(g(c)=\{g_i, i\in \IZ\}\) ganzer Zahlen erzeugen, für die gilt \(\frac{g_i^2+g_{i+1}^2}{g_i g_{i+1} +1}=c\) (2) mit stets demselben c.
Beweis: Sei o.B.d.A. \(a>b\), dann lässt sich ein \(a'>a\) aus \(\frac{a'^2+a^2}{a'a+1}=c\) wie folgt berechnen. Umgestellt ergibt sich die quadratische Gleichung \(a'^2-aca'+a^2-1=0\) für a'. Setzen wir für \(c=\frac{a^2+b^2}{ab+1}\) ein, lässt sich diese quadratische Gleichung elementar lösen mit den Ergebnissen \(a'=b\) (für uns ungeeignet, weil \(a'>a\) sein soll) und \(a'=\frac{a^3-b}{ab+1}\). Dieser Wert ist tatsächlich größer als a und er ist ganzzahlig, wie man nach einer kurzen Umrechnung feststellen kann. Dazu wird im Zähler \(ab^2-ab^2\) "addiert", was \(a'=ac-b\) ergibt.
Analog lässt sich ein \(b'a' bzw. b''
Setzen wir nun in \(\frac{g_i^2+g_{i+1}^2}{g_i g_{i+1} +1}\) für \(g_{i+1}=cg_i-g_{i-1}\) ein, erhalten wir zunächst
\(\frac{c^2g_i^2-2cg_ig_{i-1}+g_i^2+g_{i-1}^2}{cg_i^2-g_ig_{i-1}+1}\)
Nach Einsetzen von \(c(g_ig_{i-1}+1)\) für \(g_i^2+g_{i-1}^2\) im Zähler (quasi als Induktionsschritt) ergibt sich dann c.
\(\square\)
An sich benötigen wir von der Folge g(c) nur die nichtnegativen Glieder. Das hat dann auch den Vorteil, dass sich für lineare Rekursionen bei Kenntnis der Anfangswerte (hier \(g_0\) und \(g_1\)) stets \(g_i\) allgemein angeben lässt (siehe z.B. hier).
Deshalb berechnen wir jetzt insbesondere \(g_0\), also den kleinsten nichtnegativen Wert (die \( g_i\) für alle \(i<0\) sind negativ, entsprechend sind die \( g_i\) für alle \(i\ge0\) nichtnegativ). Dies erschliesst sich erstaunlich leicht durch folgende Überlegung: es ist \( g_0=0\). Wäre dies nämlich nicht der Fall, dann gäbe es mit \(g_0\) und \(g_{-1}\) zwei Nachbarn für die die obige Gleichung (2) entgegen ihrer Konstruktion nicht gelten würde. Negative und positive Werte von g(c) liegen also symmetrisch bzgl. der Null.
Für \(g_1\) setzen wir nun einfach und vor allem in aller Allgemeinheit q. Die nichtnegativen Werte von g(c) ergeben sich damit als die bereits unten in den Kommentaren von mir angegebenen \( f_k(q)\). Weitere Lösungen gibt es nicht.
Und insbesondere ist mit \(\frac{g_1^2+g_0^2}{g_1g_0+1}=q^2=c\) nun auch gezeigt, dass c stets eine Quadratzahl ist.
q.e.d.
Bonus
Mit dem Beweis haben wir aber noch mehr gewonnen, nämlich eine Möglichkeit zur Konstruktion von a und b. Damit können wir dann auch zeigen, ob c überhaupt eine natürliche Zahl sein kann (ausser für die trivialen Fälle).
Dabei ist folgendes zu berücksichtigen:
1. n und m müssen endlich sein, d.h. sie müssen terminiert werden. Dabei gehen wir so vor, dass wir peu á peu für a das Laufindexende n auf 1, dann auf 2, 3 usw. setzen, sprich es werden dadurch jeweils alle anderen \(a_i =0\) für \(i>n\). Daraus ermitteln wir, wenn möglich, das zugehörige b.
2. Natürlich ist die q-adische Darstellung eindeutig und die Koeffizienten sind die möglichen Reste der Division durch q, also die Ziffern 0, 1, 2, ..., q-1; es wäre also bspw. \((q-1)\cdot q^2\) eine solche Zahl. Da q aber unbekannt ist, könnte dies als \(-q^2 +q^3\) erscheinen, sprich wir lassen auch negative ganzzahlige Koeffizienten zu. Sollte es Lösungen mit negativen ganzen Zahlen geben, dann sind diese leicht in korrekter q-adischer Darstellung angebbar. Daher sind insbesondere zwei Fälle zu beachten nämlich \(a_1=1\) und \(a_1=-1\), in beiden Fällen ist \(b_1=0\).
Für \(n=1\) und \(a_1=1\) (also \(a_i=0\) für \(i>1\)) finden wir folgende Gleichungen für die jeweiligen Koeffizienten:
\(q^3 : a_0 b_1 +a_1 b_0 =0=2(a_0 a_3 +a_1 a_2 +b_0 b_3 +b_1 b_2 )\), was erfüllt ist.
\(q^4 : a_0 b_2 +a_1 b_1 +a_2 b_0 =0=2a_0 a_4 +2a_1 a_3 +a_2^2 +2b_0 b_4 +2b_1 b_3 +b_2^2\), was \(b_2=0\) ergibt.
\(q^5\) : erfüllt sich aus dem bisherigen zu 0, ergibt also nichts Neues.
\(q^6\) : ergibt \(b_3 = b_3^2\), also \(b_3=1\).
Alle anderen \(b_i=0\) für i > 3.
D.h. unsere erste Lösung lautet \(a=q\) und \(b=q^3\) für beliebige q (bspw. a=2 und b=8 wäre das erste nichttriviale Beispiel und ergibt 4).
Ganz analog erhält man \(a=-q+q^5\) und wiederum \(b=q^3\), hier wäre a=30, b=8 das erste Beispiel.
Schluss
Wir haben nun gezeigt, dass es Lösungen für c in den natürlichen Zahlen gibt. Insbesondere konnten wir zwei Lösungsfamilien finden. Ob es noch mehr Lösungsfamilien gibt, überlasse ich dem Leser.
Viel Freude
trunx (Jens Koch)
|
|