Saut de Viète

En théorie des nombres, le saut de Viète (Vieta jumping en anglais) est une technique de démonstration. Elle est le plus souvent utilisée pour des problèmes dans lesquels une relation entre deux entiers positifs est donnée, avec une proposition à prouver au sujet de ses solutions.

Histoire

Le saut de Viète est une technique relativement récente dans la résolution de problèmes d'olympiades mathématiques, car le premier problème d'olympiade à l'utiliser dans une solution a été proposé en 1988 lors des Olympiades internationales de mathématiques et longtemps considéré comme le problème le plus difficile de l’histoire du concours[1]. Arthur Engel (en) a écrit ce qui suit à propos de la difficulté du problème : « Aucun des six membres du comité australien du problème n'a pu le résoudre. Deux des membres étaient George Szekeres et sa femme, tous deux célèbres pour résoudre des problèmes et en créer. Comme c'était un problème de théorie des nombres, il fut envoyé aux quatre théoriciens des nombres australiens les plus renommés. On leur avait demandé d'y travailler pendant six heures. Aucun d'eux ne put le résoudre dans le temps imparti. Le comité du problème le soumit au jury de l'OMI XXIX marqué d'un double astérisque, ce qui signifiait que le problème était peut-être trop difficile pour être posé. Après une longue discussion, le jury a finalement eu le courage de le choisir comme le dernier problème de la compétition. Onze étudiants donnèrent des solutions parfaites[1]. » Parmi les onze étudiants (sur près de 300) qui obtinrent le score maximum pour la résolution de ce problème, il y avait Ngô Bảo Châu, futur médaillé Fields, Ravi Vakil, professeur de mathématiques à Stanford, Zvezdelina Stankova, professeure au Mills College, et Nicușor Dan, mathématicien devenu politicien roumain[2]. En revanche, bien que Terence Tao eût obtenu une médaille d'or à cette olympiade, il avait échoué à ce seul problème[3].

Saut de Viète standard

Le concept de saut de Viète standard est un raisonnement par l'absurde, et plus précisément un raisonnement par descente infinie, qui se compose des trois étapes suivantes[4] :

  1. On suppose par l'absurde qu'il existe des solutions à la relation donnée qui ne satisfont pas l'énoncé que l'on veut prouver.
  2. On prend la solution (A, B) qui minimise une certaine fonction de A et B, généralement A + B. L'équation est ensuite réarrangée en une équation du second degré, dont l'une des racine est A, et les formules de Viète sont utilisées pour déterminer l'autre racine.
  3. On montre ensuite que l'autre racine donne une solution à la fois valide et plus petite, ce qui contredit la minimalité de la solution (A, B). Cette contradiction montre donc qu’il n’existe aucune solution ne satisfaisant pas l’énoncé.

On peut aussi interpréter ce raisonnement comme un moyen, à partir d’une solution, d’en construire une autre « plus petite », et de proche en proche une suite décroissante infinie d’entiers naturels, ce qui est absurde.

Exemple du problème #6 de l'OMI 1988: soit a et b des entiers strictement positifs tels que ab + 1 divise a2 + b2. Prouver que a2 + b2/ab + 1 est un carré parfait[5],[6].

  1. Soit k = a2 + b2/ab + 1. Nous supposons qu'il existe une ou plusieurs solutions à la condition donnée pour laquelle k n'est pas un carré parfait.
  2. Pour une valeur donnée de k, soit (A, B) une solution de cette équation qui minimise la valeur de A + B et sans perte de généralité AB. On peut réorganiser l'équation et remplacer A par une variable x pour obtenir x2 – (kB)x + (B2k) = 0. Une racine de cette équation est x1 = A. Par les relations de Viète, l'autre racine peut être exprimée des deux manières suivantes : x2 = kBA et x2 = B2k/A.
  3. La première expression de x2 montre que x2 est un entier, alors que l'autre expression implique que x2 ≠ 0 puisque k n'est pas un carré parfait. De x2B + 1 = x22 + B2/k > 0 on déduit que x2 est positif. Finalement, AB implique que x2 = B2k/A < A et, par conséquent, x2 + B < A + B, qui contredit la minimalité de (A, B).

Descente du saut de Viète

La méthode de descente du saut de Viète est utilisée lorsque nous souhaitons prouver une déclaration concernant une constante k ayant une relation avec a et b. Contrairement au saut de Viète standard, la descente n'est pas un raisonnement par l’absurde, et se compose des quatre étapes suivantes[7] :

  1. Le cas de l'égalité est prouvé pour que l'on puisse supposer que a > b.
  2. b et k sont supposés fixés et l'expression est réarrangée sous forme d'une équation du second degré, dont l'une des racines est a. L'autre racine, x2 est déterminée à l'aide des formules de Viète.
  3. Il est montré que pour tous (a, b) au-dessus d'un certain cas de base, 0 < x2 < b < a tel que x2 soit un entier. Ainsi, nous pouvons remplacer (a, b) avec (b, x2) et répéter ce processus jusqu'à ce que nous arrivions au cas de base.
  4. La déclaration est prouvée pour le cas de base, et comme k est resté constant à travers ce processus, cela suffit à prouver l'énoncé de départ.

Exemple

Soit a et b des entiers naturels tels que ab divise a2 + b2 + 1. Prouver que 3ab= a2 + b2 + 1[8].

  1. Si a = b, a2 doit diviser 2a2 + 1 donc a = b = 1 et 3(1)(1) = 12 + 12 + 1. Donc, sans perte de généralité, supposons que a > b.
  2. Soit k = a2 + b2 + 1/ab. En supposant b et k fixés, on peut réarranger l'expression et remplacer a par une variable x pour obtenir x2 − (kb)x + (b2 + 1) = 0. L'une des racines est a, donc l'autre peut s'écrire, par les formules de Viète : x2 = kba = b2 + 1/a.
  3. La première équation dit que x2 est un entier et la seconde qu'il est positif. Parce que a > b, x2 = b2 + 1/a < b sous réserve que b > 1.
  4. Le cas de base auquel nous arrivons est le cas où b = 1. Pour que cela satisfasse la condition donnée, a doit diviser a2 + 2, rendant a égal soit à 1 soit à 2. Le premier cas est éliminé parce que ab. Dans le second cas, k = a2 + b2 + 1/ab = 6/2 = 3. Puisque k est constant, cela suffit pour montrer que k sera toujours égal à 3.

Interprétation géométrique

Le saut de Viète peut être décrit en termes de points sur une hyperbole. Le processus de recherche de racines de plus en plus petites est utilisé pour trouver des points de l'hyperbole tout en restant dans le premier quadrant. La procédure est la suivante:

  1. À partir de la condition donnée, on obtient l'équation d'une famille d'hyperboles inchangées par l'échange de x et y tels qu'elles soient symétriques par rapport à la droite d'équation y = x.
  2. Prouver la proposition désirée pour les intersections des hyperboles et de la droite y = x.
  3. Supposons qu'il y a un point (x, y) sur une hyperbole et sans perte de généralité x < y. Ensuite, par les formules de Viète, il existe un point correspondant avec la même abscisse, situé sur l'autre branche de l'hyperbole, et par réflexion par rapport à y = x un nouveau point sur la branche d'origine de l'hyperbole est obtenu.
  4. Il est montré que ce processus produit des points de plus en plus bas sur la même branche et peut être répété jusqu'à ce que certaines conditions (par exemple x = 0) soit vérifiées. Enfin, en remplaçant cette condition dans l'équation de l'hyperbole, la conclusion souhaitée sera prouvée.

Exemple

Nous pouvons appliquer cette méthode au problème #6 de l'OMI 1988: Soit a et b des entiers naturels tels que ab + 1 divise a2 + b2. Prouver que a2 + b2/ab + 1 est un carré parfait.

  1. Soit a2 + b2/ab + 1 = q avec q fixé. Alors (a,b) représente un point du réseau situé sur l'hyperbole H d'équation x2 + y2qxyq = 0.
  2. Si x = y nous trouvons x = y = q = 1, qui est une solution triviale.
  3. Soit (x, y) un point du réseau situé sur l'hyperbole H ; supposons que x < y, c.-à-d. que le point est sur la branche supérieure. En appliquant les formules de Viète, (x, qxy) est un point situé sur la branche inférieure de H. Ainsi, par réflexion, (qxy, x) est un point du réseau sur la branche d'origine. Ce nouveau point a une ordonnée plus petite, et est donc en dessous du point d'origine. Puisque ce point est sur la branche supérieure, il est encore au-dessus de y = x.
  4. Ce processus peut être répété. À partir de l'équation de H, il n'est pas possible que ce processus se déplace dans le deuxième quadrant. Ainsi, ce processus doit se terminer en x = 0 et en substituant, nous avons q = y2 qui est un carré parfait.

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Vieta Jumping » (voir la liste des auteurs).
  1. (en) Arthur Engel, Problem Solving Strategies, Springer, , 403 p. (ISBN 978-0-387-98219-9, DOI 10.1007/b97682, lire en ligne), p. 127.
  2. (en) « Results of International Mathematical Olympiad 1988 », Imo-official.org (consulté le ).
  3. (en) La légende de la question six, sur Numberphile.
  4. (en) Yimin Ge, « The Method of Vieta Jumping », Mathematical Reflections, vol. 5, (lire en ligne).
  5. (en) « AoPS Forum – One of my favourites problems, yeah! », Artofproblemsolving.com (consulté le ).
  6. (en) K. S. Brown, « N = (x^2 + y^2)/(1+xy) is a Square », MathPages.com (consulté le ).
  7. (en) « AoPS Forum — Lemur Numbers », Artofproblemsolving.com (consulté le ).
  8. (en) « AoPS Forum – x*y | x^2+y^2+1 », Artofproblemsolving.com, (consulté le ).

Voir aussi

Articles connexes

Lien externe

Vieta Jumping sur Brilliant.org

  • Portail des mathématiques
  • Arithmétique et théorie des nombres
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.