Vieta jumping

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Das Vieta jumping ist eine Beweistechnik aus der Zahlentheorie. Es wird meist für Probleme verwendet, in welchen ein Quotient zweier positiver ganzer Zahlen gegeben ist, gemeinsam mit einer zu beweisenden Aussage über dessen Lösungen. Es gibt mehrere Varianten des Vieta jumping, die alle auf dem Prinzip des unendlichen Abstiegs durch das wiederholte Ermitteln neuer Lösungen mit Hilfe des Satzes von Vieta aufbauen.

Bekanntheit erlangte die Beweismethode dadurch, dass mit ihr die sechste Aufgabe der Internationalen Mathematik-Olympiade 1988 lösbar ist, die als die schwerste Aufgabe des Wettbewerbs galt:[1][2]

Es seien und positive ganze Zahlen, sodass durch teilbar ist. Zeige, dass eine Quadratzahl ist.[3]

Arthur Engel schrieb folgendes über den Schwierigkeitsgrad der Aufgabe:

„Nobody of the six members of the Australian problem committee could solve it. Two of the members were husband and wife George and Esther Szekeres, both famous problem solvers and problem creators. Since it was a number theoretic problem it was sent to the four most renowned Australian number theorists. They were asked to work on it for six hours. None of them could solve it in this time. The problem committee submitted it to the jury of the XXIX IMO marked with a double asterisk, which meant a superhard problem, possibly too hard to pose. After a long discussion, the jury finally had the courage to choose it as the last problem of the competition. Eleven students gave perfect solutions.“

Arthur Engel

„Keiner der sechs Mitglieder des australischen Aufgabenausschusses konnte sie lösen. Zwei der Mitglieder waren das Ehepaar George und Esther Skekeres, beide bekannte Aufgabenlöser und -ersteller. Da es sich um ein Problem aus der Zahlentheorie handelte, wurde es an die vier renommiertesten australischen Mathematiker in diesem Teilgebiet weitergegeben. Sie sollten an der Aufgabe sechs Stunden lang arbeiten. Keiner von ihnen konnte das Problem in dieser Zeit lösen. Der Aufgabenausschuss legte es den Juroren der 29. IMO vor, gekennzeichnet mit einem doppelten Sternchen, was den enormen Schwierigkeitsgrad der Aufgabe kennzeichnen sollte. Nach einer langen Diskussion hatten die Juroren den Mut, das Problem als das letzte des Wettbewerbs auszuwählen. Elf Teilnehmer legten perfekte Lösungen vor.“

Arthur Engel

Unter den Teilnehmer, die die maximale Punktzahl für das Lösen der Aufgabe erhielten, waren unter anderem Ngô Bảo Châu, Ravi Vakil, Zvezdelina Stankova und Nicușor Dan.[4] Emanouil Atanassov aus Bulgarien löste die Aufgabe unter Nutzung des Vieta Jumping in einer besonders eleganten Weise und erhielt hierfür einen Sonderpreis.[5]

Standard Vieta jumping

[Bearbeiten | Quelltext bearbeiten]

Das Prinzip des Standard Vieta jumping ist ein Beweis durch Widerspruch und besteht aus den folgenden drei Schritten:[6]

  1. Annahme, dass eine Lösung existiert, die die gegebenen Voraussetzungen verletzt.
  2. Auswahl der kleinsten dieser Lösungen nach einer bestimmten Definition der Minimalität.
  3. Beweis, dass dadurch eine neue, kleinere Lösung entsteht und damit ein Widerspruch.
Beispiel

Wir betrachten die oben beschriebene sechste Aufgabe der IMO 1988:[7]

  1. Sei eine natürliche Zahl, die keine Quadratzahl ist. Wir nehmen an, dass es zwei positive ganze Zahlen und mit gibt.
  2. Seien und die in der Summe kleinstmöglichen positiven ganze Zahlen, sodass die Bedingung erfüllt ist. O.B.d.A. sei .
  3. Sei fest und . Durch Umformung erhalten wir . Eine Lösung ist offensichtlich . Durch den Satz von Vieta gilt ferner für die zweite Lösung und .
  4. Der erste Ausdruck impliziert, dass ganzzahlig ist, der zweite, dass , da nach Voraussetzung keine Quadratzahl ist. Über folgt weiter, dass positiv-ganzzahlig ist. Ferner gilt wegen auch und damit was der Minimalität von widerspricht.

Konstant absteigendes Vieta jumping

[Bearbeiten | Quelltext bearbeiten]

Die Methode des konstant absteigenden Vieta jumping wird benutzt, um eine Aussage bezüglich einer Konstanten , die etwas mit dem Verhältnis von und zu tun hat, zu beweisen. Anders als beim standard Vieta jumping, handelt es sich beim konstant absteigenden Vieta jumping nicht um einen Beweis durch Widerspruch. Es besteht aus vier Schritten:[8]

  1. Beweis des Gleichheitsfalls, sodass o. B. d. A. angenommen werden kann.
  2. Es werden und fixiert sowie der zu zeigende zu einer quadratischen Gleichung umgeformt, die als Lösung besitzt. Die andere Lösung ist über den Satz von Vieta bestimmt.
  3. Es wird gezeigt, dass für alle oberhalb eines bestimmten Basisfalls gilt und dass eine ganze Zahl ist. Es kann also durch ersetzt werden und dieser Vorgang wiederholt werden, bis der Basisfall erreicht ist.
  4. Die Aussage wird für den Basisfall bewiesen, und da über den Beweisprozess hinweg konstant geblieben ist, ist dies hinreichend dafür, dass die Aussage für alle geordneten Zahlenpaare gilt.
Beispiel

Seien und positive ganze Zahlen, sodass durch teilbar ist. Zeige, dass gilt.

  1. Wenn muss durch teilbar sein und damit , d. h. . O.B.d.A. können wir also annehmen.
  2. Sei . Durch Umformung und Substituierung erhalten wir . Hierzu ist eine Lösung . Damit gilt nach Vieta für die zweite Lösung .
  3. Die erste Darstellung zeigt, dass ganzzahlig ist, die zweite, dass positiv ist. Ferner ist wegen auch , für alle .
  4. Der Basisfall ist . Damit die Bedingung erfüllt ist, muss also durch teilbar sein, weshalb entweder oder sein muss. Da der erste Fall zu Beginn bereits ausgeschlossen wurde, erhalten wir . Und während des Beweises konstant war, ist dies hinreichend um zu zeigen, dass immer gilt.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Arthur Engel: Problem Solving Strategies (= Problem Books in Mathematics). Springer, 1998, ISBN 978-0-387-98219-9, S. 127, doi:10.1007/b97682 (google.com).
  2. The Return of the Legend of Question Six. In: Numberphile. via YouTube, 16. August 2016;.
  3. International Mathematical Olympiad. In: www.imo-official.org. Abgerufen am 29. September 2020.
  4. Results of International Mathematical Olympiad 1988. Imo-official.org, abgerufen am 3. März 2013.
  5. https://www.imo-official.org/participant_r.aspx?id=1586
  6. Yimin Ge: The Method of Vieta Jumping. In: Mathematical Reflections. 5. Jahrgang, 2007 (georgmohr.dk [PDF]).
  7. Kevin S. Brown: N = (x^2 + y^2)/(1+xy) is a Square. MathPages.com, abgerufen am 26. September 2016.
  8. AoPS Forum – Lemur Numbers. Artofproblemsolving.com, abgerufen am 3. März 2013.