Des triangles rectangles presque isocèles… à la pelle !

En parcourant le sujet de mathématiques du baccalauréat Scientifique tombé le 21 Juin dernier en métropole et à la Réunion, je suis tombé sur un exercice particulièrement intéressant (non pas que les autres ne le soient pas…) et qui a éveillé m’a curiosité. Il s’agissait du dernier exercice du sujet reservé aux candidats qui ont choisi la spécialité mathématiques, et il portait sur des notions d’arithmétique.

Cliquez sur l’image pour voir le sujet.

Dans cet exercice on définissait un type de triangle assez particulier: les triangles rectangles presque isocèles (TRPI).  Un TRPI est un triangle rectangle dont tous les côtés ont des longueurs qui sont des nombres entiers, et tel que les deux côtés qui ne sont pas l’hypoténuse ont des longueurs qui diffèrent juste d’une unité (et qui sont donc presque égales, d’où l’appellation « presque isocèles »). Cet exercice faisait prouver aux candidats quelques propriétés d’un TRPI (par exemple que y est toujours un nombre impair) et il se terminait en donnant une suite de TRPI. La dernière question faisait d’ailleurs démontrer que le plus petit TRPI dont les longueurs sont toutes supérieures à 2017 est le TRPI qui a pour côtés 4059, 4060 et 5741.

Voilà le triangle qui a fait suer des milliers de candidats cette année ! J’en connais qui n’ont pas eu le bac juste à cause de lui…

La question que je me suis posée en finissant cet exercice était: « Peut-on déterminer tous les TRPI ? ». Cette question, je vous la pose aussi ! Je vous laisse réfléchir autant que vous le voulez, puis lisez la suite.

Une équation diophantienne

Afin de trouver tous les TRPI possibles et inimaginables (oh qu’il y en a !), commençons par déterminer une équation qui traduit le problème. D’après le théorème de Pythagore,  un triangle de côtés x, x+1 et y est un TRPI si, et seulement si

y^2 = (x+1)^2 + x^2 \iff y^2 =2x^2 + 2x +1

Cette équation n’est pas particulièrement émoustillante (personnellement, je n’ai pas la gigite en la regardant), essayons de la transformer en utilisant la fameuse forme canonique:

\begin{array}{rcl}  y^2 =2x^2 + 2x +1 & \iff& 2x^2 + 2x - y^2 = -1 \\[6pt]  & \iff & 2 \left[ x^2 + x \right] - y^2 = - 1 \\[6pt]  & \iff & 2\left[ (x + \frac{1}{2})^2 - \frac{1}{4} \right] - y^2 = -1 \\[6pt]  & \iff & 2(x + \frac{1}{2})^2 - 2y^2 = - \frac{1}{2} \\[6pt]  & \iff & 4(x + \frac{1}{2})^2 - 2y^2 = - 1 \\[6pt]  & \iff & \left[2(x + \frac{1}{2}) \right]^2 - 2y^2 = - 1 \\  \end{array}

La dernière équation est encore équivalente à \left(2x+1 \right)^2 - 2y^2 = - 1 . En posant X = 2x+1 et Y = y, l’équation devient

\boxed{X^2 - 2Y^2 = - 1}

Si ce type d’équation vous dit quelque chose, c’est normal car il s’agit d’une équation de Pell-Fermat ! Et s’il ne vous dit rien… voyons voir comment on résout cela !

Premières solutions

Avant de résoudre complètement notre équation de Pell-Fermat (j’annonce !), cherchons-en quelques solutions. On vérifie facilement que le couple X = 1 et Y = 1 est une solution car 1^2 - 2 \times 1 ^2 = -1. Comme nous avions fait les changements d’inconnues X= 2x +1 et Y = y, on a donc x = \frac{1}{2} (X - 1) et y=Y ce qui donne ici la solution x = \frac{1}{2} (1 -1) = 0 et y = 1.

Le triangle qui a pour côtés 0, 1 et 1 n’étant pas très intéressant, cherchons donc une autre solution moins débile. En tâtonnant (c’est-à-dire en testant les valeurs X= 1, 2, \cdots), on voit que X= 7 et Y=5 est un couple de solutions de l’équation X^2 - 2Y^2 = -1 car 7^2 - 2 \times 5^2 = 49 -50 =-1. En revenant à x et y, cela donne les valeurs

x= \frac{1}{2} (7 - 1) = 3 et y = 5

On peut alors vérifier que le triangle qui a pour côtés 3, 4 et 5 est bien un TRPI et c’est même le plus petit possible. Au passage, on retrouve ici la question 2 de la partie A du sujet de bac.

Le fameux triangle 3-4-5 est un TRPI. Désormais, vous ne le regarderez plus de la même façon. (Source de l’image)

Tout cela est bien joli mais trouver une autre solution à l’équation X^2 - 2Y^2 = -1 semble devenir difficile ensuite car, comme vous pouvez le vérifier, il n’y a aucune solution pour X allant de 8 à 40. Et pourtant, cette équation possède une infinité de solutions !

Une infinité de solutions

Avant de prouver qu’il existe une infinité de solutions (ce qui est une première étape avant de trouver toutes les solutions), voyons comment noter plus simplement les solutions. Nous avons vu précédemment que le couple X=7 et Y=5 est une solution de l’équation X^2 - 2Y^2 =-1. Nous dirons alors que 7 + 5\sqrt{2} est une solution de cette équation. De même, nous avons vu que 1+\sqrt{2} est une solution de notre équation, car ce nombre correspond au couple X=1 et Y=1.

Pourquoi utiliser une notation avec des racines carrées ? Tout simplement car cela va nous permettre de multiplier des solutions entre elles pour fabriquer d’autres solutions. Cela étant dit, cette notation est bien définie car à un couple (X,Y) ne correspond qu’un seul nombre X+Y\sqrt{2}. Autrement dit, X+Y\sqrt{2}=X'+Y'\sqrt{2} \iff X=X' \quad , \quad  Y=Y'  et, sans rentrer dans les détails, cela vient du fait que \sqrt{2} est irrationnel.

Sachant tout cela, nous allons voir comment à partir de solutions déjà connues on peut construire d’autre solutions. Un premier pas pour cela est la propriété suivante (dont une démonstration est donnée en annexe à la fin de l’article):

Si a + b \sqrt{2} est une solution de l’équation X^2 - 2Y^2 = n et si c + d\sqrt{2} est une solution de l’équation X^2 - 2Y^2 =m alors

(a + b \sqrt{2})(c + d \sqrt{2}) est une solution de l’équation X^2 - 2Y^2 = n \times m

Qu’on s’entende bien sur ce que cela signifie: en le développant, on peut voir que le nombre (a + b \sqrt{2})(c + d \sqrt{2}) s’écrit de manière unique sous la forme \alpha + \beta \sqrt{2} et donc dire que (a + b \sqrt{2})(c + d \sqrt{2}) est une solution de l’équation X^2 - 2Y^2 = n \times m signifie que \alpha^2 -2\beta ^2 = n \times m. Voilà donc où réside l’intérêt de noter les couples de solutions sous la forme X + Y \sqrt{2}.

Par exemple, on a vu que 1+ \sqrt{2} est 7 + 5 \sqrt{2} sont deux solutions de X^2 - 2Y^2 = - 1 donc cette propriété nous dit que (1+\sqrt{2})(7 + 5 \sqrt{2}) = 17 +12 \sqrt{2} est une solution de l’équation X^2 - 2Y^2 = (-1) \times (-1) = 1, ce dont on peut se convaincre assez aisément car

17^2 - 2 \times 12^2 = 289 - 2 \times 144 = 1

Cependant, ce qui nous intéresse ici n’est pas l’équation X^2 - 2Y^2 = 1 mais X^2 - 2Y^2 =-1. Qu’à cela ne tienne, en appliquant la propriété précédente deux fois de suite, on peut trouver par exemple que (1+\sqrt{2})(1+\sqrt{2})(7+5\sqrt{2} )= 41 + 29 \sqrt{2} est une solution de l’équation X^2 - 2 Y^2  = (-1) \times (-1) \times (-1) = -1. Là encore, je vous laisse vérifier que 41^2 - 2 \times 29^2 = -1. Ca paraît tellement magique de pouvoir construire autant que l’ont veut de solutions  à cette équation dont on n’arrivait même pas à trouver plus de deux solutions à la main !

Plus généralement, on peut démontrer par récurrence (voir en fin d’article) qu’il y a une infinité de solutions :

Pour tout entier naturel n, (1+\sqrt{2})^{2n+1} est une solution de l’équation X^2 - 2Y^2 = -1.

Par exemple, si on prend n=3 alors (1+\sqrt{2})^7 = 239 + 169 \sqrt{2} est bien une solution de notre équation. En fait, on pourrait même montrer que si n est un entier relatif (donc éventuellement négatif) alors (1+\sqrt{2})^{2n+1} est une solution de notre équation. Par exemple, si n=-1, on a (1+\sqrt{2})^{2n+1} = (1+ \sqrt{2})^{-1} mais

(1+ \sqrt{2})^{-1} = \dfrac{1}{1+ \sqrt{2}} = \dfrac{1- \sqrt{2}}{(1+\sqrt{2})(1-\sqrt{2})} = \dfrac{1-\sqrt{2}}{-1} = - 1 + \sqrt{2}

et cela nous donne la solution X= -1 et Y=1 ((-1)^2 - 2 \times 1^2 = -1). Youpi.

Réciproque

En début d’article, nous nous étions mis en tête de trouver toutes les solutions de cette équation. Je dois vous avouer qu’on pourrait en fait s’arrêter là car nous les avons déjà toutes trouvées… sauf que nous ne le savons pas encore. Du moins, nous ne l’avons pas encore démontré mais les solutions (1+\sqrt{2})^{2n+1} sont bien les seules possibles:

Toute solution de l’équation X^2 - 2Y^2 = - 1 est de la forme X+Y \sqrt{2} = (1+\sqrt{2})^{2n+1}.

Pour le démontrer, on considère une solution X+Y \sqrt{2} de l’équation X^2 - 2Y^2 = -1. Comme la suite (1+\sqrt{2})^{2n+1} est strictement croissante et tend vers +\infty, il existe un unique entier naturel n tel que

(1+\sqrt{2})^{2n+1} \leqslant X + Y \sqrt{2} < (1+\sqrt{2})^{2(n+1)+1}

ce qui est équivalent à  1 \leqslant (1+\sqrt{2})^{-(2n+1)} (X + Y \sqrt{2}) < (1+\sqrt{2})^{2}

c’est-à-dire: 1 \leqslant (1+\sqrt{2})^{-(2n+1)} (X + Y \sqrt{2}) < 3 +2 \sqrt{2}

Comme (1+\sqrt{2})^{-(2n+1)} =(1+\sqrt{2})^{2(-n-1)+1} est de la forme (1+\sqrt{2})^{2k+1} , alors, comme nous l’avons vu, c’est une solution de l’équation X^2 - 2Y^2 = -1 et on en déduit que (1+\sqrt{2})^{-(2n+1)} (X + Y \sqrt{2}) est une solution de l’équation X^2 - 2Y^2 = (-1) \times (-1) = 1.

D’autre part, 3 +2 \sqrt{2} est aussi une solution de X^2 - 2Y^2 = 1. C’est même la plus petite solution non triviale (c’est-à-dire avec X et Y tous deux non nuls) de cette équation comme on peut le vérifier facilement.

Nous sommes en train de voir que (1+\sqrt{2})^{-(2n+1)} (X + Y \sqrt{2}) est une solution de X^2 - 2Y^2 = 1 strictement plus petite que la plus petite solution non triviale 3 +2 \sqrt{2}. Cela implique donc que (1+\sqrt{2})^{-(2n+1)} (X + Y \sqrt{2}) ne peut être autre chose que la solution triviale 1+ 0\sqrt{2} de l’équation X^2 -2Y^2 = 1. Autrement dit,

(1+\sqrt{2})^{-(2n+1)} (X + Y \sqrt{2}) =1 \iff X + Y \sqrt{2} = (1+\sqrt{2})^{2n+1}

CQFD!

Retour sur les TRPI

Pour finir de décrire toutes les solutions de l’équation X^2 - 2Y^2 = -1, cherchons à déterminer les suites X_n et Y_n telles que pour tout entier n,

X_n + Y_n \sqrt{2} = (1+\sqrt{2})^{2n+1}

Tout d’abord,  X_0 + Y_0 \sqrt{2} = (1+\sqrt{2})^{2\times 0 +1} = 1+ \sqrt{2} entraine que X_0=1 et Y_0 = 1. D’autre part,

\begin{array}{rcl}  X_{n+1} + Y_{n+1} \sqrt{2} = (1+\sqrt{2})^{2(n+1)+1} & \iff & X_{n+1} + Y_{n+1} \sqrt{2} = (1+\sqrt{2})^{2n +1} \times (1+\sqrt{2})^2 \\[6pt]  & \iff & X_{n+1} + Y_{n+1} \sqrt{2} = (X_n + Y_n \sqrt{2}) (3+2\sqrt{2}) \\[6pt]  & \iff & X_{n+1} + Y_{n+1} \sqrt{2} = 3X_n + 4Y_n + (2X_n + 3Y_n) \sqrt{2}  \end{array}

Par identification, on obtient les égalités suivantes:

\begin{cases} X_{n+1} = 3X_n + 4Y_n  \\Y_{n+1} = 2X_n + 3Y_n \end{cases}

Pour faire le lien avec les TRPI, n’oublions pas qu’on avait les relations

X_n = 2x_n +1 \iff x_n = \frac{1}{2} (X_n - 1) et y_n = Y_n

et de cela on peut en déduire les relations de récurrence ci-dessous :

\boxed{\begin{cases} x_{n+1} =  3x_n  + 2y_n + 1 \\y_{n+1} = 4x_n  + 3y_n  +2 \end{cases} }

(je vous ai épargné les calculs… si vous êtes arrivés à ce stade de l’article, je suis déjà content !).

Sachant que x_0 = \frac{1}{2} (X_0 -1) = 0 et y_0 = Y_0 = 1 (on retrouve ici la solution débile que nous avions trouvée tout au début), on peut alors calculer par récurrence la liste de tous les TRPI (et constater que ça croît très vite !):

En fait, ces suites (x_n) et (y_n) sont exactement les suites données dans le sujet de bac sous forme matricielle et nous avons vu qu’elles permettent de trouver tous les TRPI, sans exception. Les élèves ne le savaient donc pas quand ils composaient, mais ils avaient sous les yeux toutes les solutions possibles de TRPI !

Note:

Vous trouverez les démonstrations des propriétés énoncées dans l’article dans ce document.

Publié dans Arithmétique | Tagué , , , , , , , | 3 commentaires

2017, année des cubes

Une nouvelle année commence, et avec elle son lot de surprises. Qu’est-ce qui nous attend pour 2017 ? C’est ce que nous allons essayer de voir, du moins du point de vue mathématique (car pour le reste, je n’ai toujours pas ouvert mon cabinet de voyance, mais j’y travaille).

Ça faisait longtemps  !

Tout d’abord, 2017 est un nombre premier, youpi ! Cela n’était pas arrivé depuis 2011, donc il était temps. La prochaine fois qu’une année sera un nombre premier, ce sera en 2027.

De plus, comme 2017 est un nombre premier de la forme 4k +1 (car 2017=  4 \times 504 +1), on sait, grâce à un théorème énoncé par Fermat, qu’il peut alors s’écrire comme une somme de deux carrés. Et en effet,

2017 = 9^2 + 44^2

Cela n’était pas arrivé depuis 2009 qu’une année puisse se décomposer en une somme de deux carrés et ce sera encore le cas en 2018 et 2020. L’année 2017 est la 622ème année depuis l’an I à pouvoir être décomposée en une somme de deux carrés. C’est pas mal, mais il y a mieux… beaucoup mieux !

Somme de trois cubes

Le nombre 2017 peut non seulement se décomposer en une somme de deux carrés, mais aussi en une somme de trois cubes (strictement positifs) ! Plus précisément,

2017 = 7^3 + 7^3 + 11^3

La dernière fois que cela était arrivé, c’était en 2001 (2001 = 1^3 + 10^3 + 10^3) et cela ne se reproduira plus avant 2027 (2027 = 3^3 + 10^3 +10^3… encore 2027 décidément ! Comptez sur moi pour vous ressortir le même article dans 10 ans…). Je vous sens tout de même encore un peu dubitatifs, donc essayons de comprendre pourquoi il est vraiment remarquable d’être une somme de trois cubes.

Le problème de Waring

Le problème qui consiste à savoir si un nombre peut s’écrire comme la somme de plusieurs cubes positifs date de 1770 et fait partie de ce qu’on appelle le problème de Waring. En 1909 et 1912, les dénommés Wieferich et Kempner ont démontré que tout entier naturel peut s’écrire comme la somme d’au plus neuf cubes. Dickson en 1939 ([1]) a réussi à améliorer ce résultat en démontrant que tous les nombres sauf 23 et 239 peuvent s’écrire comme la somme de huit cubes. En 1943, Linnik a même prouvé que tous les nombres assez grands (c’est-à-dire plus grands qu’un nombre donné) peuvent s’écrire comme la somme de sept cubes ([2]). On sait aussi depuis 1939 grâce à Davenport ([3]) que presque tous les nombres entiers naturels peuvent s’écrire comme une somme de quatre cubes (c’est-à-dire que la proportion de ceux qui ne peuvent pas l’être tend vers 0).

En ce qui concerne les nombres qui sont somme de trois cubes, la situation est vraiment différente. Voici ce que l’on peut affirmer tout de même:

  • il existe une infinité de nombres qui peuvent s’écrire comme la somme de trois cubes;
  • il existe une infinité de nombres qui ne peuvent pas s’écrire comme la somme de trois cubes.

Si vous n’êtes pas convaincu par ces deux affirmations (qui semblent contradictoires !), je vous propose de les démontrer.

1/ Il est facile de voir qu’il existe une infinité de nombres qui s’écrivent comme la somme de trois cubes car pour tout entier naturel non nul n, le nombre n^3 + 2 =  n^3 + 1^3  + 1^3 est une somme de trois cubes strictement positifs.

2/ Pour montrer qu’il existe une infinité de nombres qui ne peuvent pas s’écrire comme une somme de trois cubes, nous allons raisonner modulo 9. On commence par établir tous les restes possibles d’un nombre au cube quand on en fait la division par 9:

\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline \vphantom{\dfrac{X}{X}} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline \vphantom{\dfrac{X}{X}} n^3 & 0 & 1 & 8 & 0 & 1 & 8 & 0 & 1 & 8 \\ \hline \end{array}

Il n’y a donc que  trois possibilités: 0, 1 et 8. Maintenant, si on fait la somme de trois cubes x^3 + y^3 + z^3 modulo 9, voici les 27 possibilités:2017_annee_cubique_table_des_sommes_des_cubes_modulo_9Vous voyez que seuls les nombres 0, 1, 2, 3, 6, 7 et 8 apparaissent dans les colonnes de droite. Autrement dit, une somme de trois cubes ne peut jamais être congrue à 4 ou 5 modulo 9. Ainsi, tous les nombres de la forme 9k+4 ou 9k+5 ne s’écriront jamais comme une somme de trois cubes. Cela en fait donc bien une infinité ! Nous pouvons même affirmer qu’au plus \dfrac{7}{9} des nombres sont une somme de trois cubes. En fait, la proportion des nombres qui peuvent s’écrire comme une somme de trois cubes est bien plus petite que cela…

Beaucoup de sommes de trois cubes ?

Pour se rendre compte du nombre de nombres qui peuvent s’écrire comme une somme de trois cubes strictement positifs, nous allons en calculer la proportion. Par exemple, il y a eu 245 années (2017 y compris) depuis l’an I qui s’écrivent comme une somme de trois cubes strictement positifs, donc la proportion en 2017 est de \dfrac{245}{2017}\simeq 0,12.

Si on va plus loin dans le temps, en l’an 10 000, il y aura eu 1154 années « somme de trois cubes » ce qui donnera une proportion de 11,54%.  Si on va encore plus loin, jusqu’en l’an 50 000 (on a le temps de voir venir !), alors il y aura eu 5482 années qui s’écrivent comme une somme de trois cubes, ce qui fera un ratio de 10,96%.

A l’heure actuelle, on conjecture (mais on n’a toujours pas prouvé) que cette proportion totale de nombres qui peuvent s’écrire comme une somme de trois cubes strictement positifs est d’environ 0,0999425 ([4]). Autrement dit, il y aurait seulement environ 10% des nombres qui peuvent s’écrire comme une somme de trois cubes et 2017 en fait partie !

N’oublions pas que 2017 est premier

Que 2017 soit un nombre premier est assez remarquable; qu’il puisse s’écrire comme une somme de trois cubes est encore plus fort; mais qu’il soit les deux en même temps, c’est assez étonnant ! En fait, des années qui furent à la fois des nombres premiers et une somme de trois cubes, il n’y en a eu que 45 depuis l’an I et 2017 ne sera que la 46ème ! La question que je vous entends déjà poser est: « Est-ce qu’il y en aura encore beaucoup des années comme 2017 à l’avenir ? » et vous poseriez ainsi une belle question mathématique bien difficile.

Hardy et Littlewood avaient conjecturé ([5]) en 1923 qu’il existe une infinité de nombres premiers qui s’écrivent comme une somme de trois cubes.

2017_annee_cubique_conjecture_n_hardy-littlewood

Hardy et Littlewood énoncent leur conjecture.

Si cela a été conjecturé par Hardy et Littlewood, autant vous dire qu’il s’agit d’un problème très compliqué… et pourtant, cette conjecture a été validée en 2001 (soit 78 ans après) par Roger Heath-Brown ([6])  qui a démontré qu’il existe une infinité de nombres premiers de la forme x^3 + y^3 + y^3 (où x et y sont des entiers naturels non nuls).

La bonne nouvelle, c’est que je pourrai ressortir une infinité de fois ce même article ! A commencer par 2027.

Bonne année 2017 !

Références

Publié dans Arithmétique, Nombres | Tagué , , , , | 5 commentaires

Comment ne pas tracer un heptagone régulier ?

Sur ce blog, nous avons déjà vu comment tracer à la règle et au compas un pentagone régulier, un hexagone régulier ou même un décagone régulier. Je pense que vous savez aussi tracer un triangle équilatéral et un carré à la règle et au compas (ne m’obligez pas à faire un article là-dessus, je serais capable !)

En revanche, je n’ai jamais publié d’article expliquant comment tracer un heptagone (figure à 7 côtés) régulier à la règle et au compas, et pour cause, cela n’est pas possible ! Je vous entends déjà marmonner « Mais pourquoi diantre cela n’est-il donc pas possible ? » (j’aime imaginer que mes lecteurs sont des gens qui parlent comme des personnages de Molière). Ça tombe vraiment bien que vous vous posiez cette question car c’est justement ce que nous allons voir ici.

Un heptagone régulier qui n'a évidemment pas été construit à la règle et au compas (mais avec un ordinateur).

Un heptagone régulier qui n’a évidemment pas été construit à la règle et au compas.

Des racines et des cubes

Le fait qu’il n’est pas possible de tracer un heptagone régulier à la règle et au compas va venir d’un petit théorème que nous allons énoncer ci-dessous. Auparavant, rappelons que:

  • l’ensemble \mathbb{Q} désigne l’ensemble des nombres rationnels, c’est-à-dire les fractions \dfrac{a}{b} avec a et b deux entiers;
  • un polynôme est rationnel si ses coefficients sont des nombres rationnels, par exemple le polynôme \dfrac{2}{3}X^4 - \dfrac{1}{2}X^3 + 2X - 3;
  • une racine x d’un polynôme P est un nombre tel que P(x)=0.

Cela étant dit, voici le théorème qui va nous aider à démontrer qu’un heptagone n’est pas constructible à la règle et au compas:

Soit P un polynôme rationnel de degré 3 tel que P n’a pas de racine rationnelle. Alors toute racine de P n’est pas constructible à la règle et au compas.

Nous admettrons ce théorème mais, si cela vous intéresse (et que vous êtes assez costaud niveau théorie des corps…), vous pourrez en trouver une démonstration à la fin de cet article. Il nous reste à voir comment utiliser ce théorème dans le cas d’un heptagone…

Raisonnement par l’absurde

S’il était possible de construire un heptagone régulier à la règle et au compas, alors il serait possible de construire un angle de \dfrac{2 \pi}{7} radians (environ 51,4°) avec l’axe des abscisses. En traçant le cercle de centre l’origine et de rayon 1, on couperait un rayon de cet heptagone (point A sur la figure ci-dessous).comment_ne_pas_tracer_un_heptagone_construction_de_cos_2pi_7En particulier, en  traçant la perpendiculaire à l’axe des abscisses passant par A (ce que l’on sait faire à la règle et au compas) on obtiendrait un segment de longueur \cos\left( \dfrac{2 \pi}{7}\right). Comme on peut doubler une longueur avec un compas, on pourrait donc obtenir un segment de longueur 2\cos\left( \dfrac{2 \pi}{7}\right):comment_ne_pas_tracer_un_heptagone_construction_du_double_de_cos_2pi_7Bref, si on savait construire un heptagone régulier, on saurait construire le nombre 2\cos\left( \dfrac{2 \pi}{7}\right) à la règle et au compas. Et nous allons voir que cela n’est pas possible en vertu du théorème que nous avons donné ! Pour cela, nous allons montrer que 2\cos\left( \dfrac{2 \pi}{7}\right) est une racine d’un polynôme rationnel de degré 3 qui ne possède aucune racine dans \mathbb{Q}.

Sans aucun complexe (ou plutôt si)

Nous allons chercher un polynôme rationnel dont 2\cos\left( \dfrac{2 \pi}{7}\right) est une racine et vous allez voir que l’utilisation des nombres complexes va grandement nous simplifier la tâche…

Nous avons choisi de nous intéresser au nombre 2\cos\left( \dfrac{2 \pi}{7}\right) plutôt qu’à \cos\left( \dfrac{2 \pi}{7}\right) à cause de l’égalité

2\cos\left( \dfrac{2 \pi}{7}\right) = \text{e}^{i \frac{2\pi}{7}} + \text{e}^{-i \frac{2\pi}{7}}

qui elle-même vient du fait que \cos\left( \frac{2 \pi}{7}\right) est la partie réelle du nombre \text{e}^{i \frac{2\pi}{7}}.

Pour faciliter les notations, nous poserons \omega = \text{e}^{i \frac{2\pi}{7}}. Ainsi, 2\cos\left( \dfrac{2 \pi}{7}\right) = \omega + \overline{\omega} = \omega + \omega^{-1}  car \omega est un nombre complexe de module 1, donc \overline{\omega} = \frac{1}{\omega} = \omega^{-1}.

Cela étant dit, on sait que ce nombre complexe \omega est racine du polynôme X^7 - 1 car \left( \text{e}^{i \frac{2\pi}{7}} \right)^7 = \text{e}^{i \frac{2\pi}{7} \times 7} = 1. Comme ce polynôme peut se factoriser

X^7 - 1 = (X-1) (1+X+X^2 +X^3 +X^4 + X^5 +X^6)

et comme \omega \neq 1 alors on a la relation

1+\omega+\omega^2 +\omega^3 +\omega^4 + \omega^5 +\omega^6 = 0

En multipliant cette relation par \omega^{-3}, on obtient la relation symétrique suivante

\omega^{-3} + \omega^{-2} + \omega^{-1}  + 1 + \omega + \omega^2 + \omega^3=0

ce que l’on peut écrire plus élégamment sous la forme

\boxed{(\omega^3 + \omega^{-3}) + (\omega^2 + \omega^{-2}) + (\omega  + \omega^{-1}) + 1 = 0}

Cette relation est tellement jolie que je pourrais arrêter l’article ici et retourner élever mes chèvres dans le Larzac. Mais je n’ai ni chèvre, ni maison dans le Larzac, donc je crois que je vais tout de même poursuivre un peu.

"Bêêê"

« Bêêê »

N’oublions pas que nous sommes en train de chercher un polynôme rationnel de degré 3 qui annule 2\cos\left( \dfrac{2 \pi}{7}\right) = \omega + \omega^{-1}. Pour cela, on va calculer les puissances deuxième et troisième de ce nombre à l’aide de fameuses (mais utiles !) identités remarquables.

\begin{array}{ccl} (\omega + \omega^{-1})^3 & = & \omega^3 + 3 \omega^{2} \omega^{-1} + 3 \omega \omega^{-2} + \omega^{-3} \\ & = & \omega^3 + 3 \omega + 3 \omega^{-1} + \omega^{-3} \\ & = & (\omega^{3} + \omega^{-3}) + 3 (\omega + \omega^{-1})\end{array}

Nous en déduisons que (\omega + \omega^{-1})^3 - 2 (\omega + \omega^{-1}) = (\omega^3 + \omega^{-3}) + (\omega + \omega^{-1}). D’autre part,

\begin{array}{ccl} (\omega + \omega^{-1})^2 & = & \omega^2 + 2 \omega \omega^{-1} + \omega^{-2} \\ & = & \omega^2 + \omega^{-2} + 2 \\ & = & \omega^2 + \omega^{-2} + 1 + 1\end{array}

On voit donc qu’en combinant astucieusement ces relations, on fait apparaître la relation encadrée vue plus haut (celle qui m’avait presque poussé à tout plaquer pour élever des ovidés):

(\omega + \omega^{-1})^3 - 2 (\omega + \omega^{-1}) + (\omega + \omega^{-1})^2  = \underbrace{(\omega^3 + \omega^{-3}) + (\omega + \omega^{-1}) + (\omega^2 + \omega^{-2}) +1 }_{=0}+ 1

et on en déduit que

(\omega + \omega^{-1})^3 - 2 (\omega + \omega^{-1}) + (\omega + \omega^{-1})^2  =1

Ainsi, le nombre 2\cos\left( \dfrac{2 \pi}{7}\right) est solution de l’équation X^3 - 2X + X^2 = 1, c’est-à-dire que c’est une racine du polynôme rationnel de degré 3  P = X^3 +X^2-2X -1.

Étude des racines

Pour finir, nous allons montrer que ce polynôme, aussi gentil et sympathique soit-il (là n’est pas la question), n’a pas de racine rationnelle. Par l’absurde, si \frac{p}{q} (avec p  premier avec q) est une racine de P alors

\dfrac{p^3}{q^3} + \dfrac{p^2}{q^2}- 2 \dfrac{p}{q}-1=0

En multipliant par q^3, on a

p^3 +qp^2 - 2pq^2 - q^3 = 0

En passant -q^3 de l’autre côté et en factorisant par p dans le membre de gauche, on obtient finalement

p(p^2+qp-2q^2) = q^3

On voit donc que p doit diviser q^3. Comme p et q sont premiers entre eux, cela n’est possible que si p=1 ou p=-1. Un raisonnement similaire ( \dfrac{p^3}{q^3} + \dfrac{p^2}{q^2}- 2 \dfrac{p}{q}-1=0 \iff q(p^2 - 2pq - q^2) = -p^3) montre aussi que q ne peut valoir que 1 ou -1. Donc \frac{p}{q} vaut 1 ou -1.

Mais si on remplace X par 1 ou -1 dans l’expression X^3 +X^2-2X -1, on ne trouve pas 0. Ce polynôme ne possède donc aucune racine rationnelle.

Retour à l’heptagone

Si je résume, nous avons vu que si on pouvait construire un heptagone régulier à la règle et au compas, alors le nombre 2\cos\left( \dfrac{2 \pi}{7}\right) serait constructible. Or, nous avons vu que ce nombre est racine d’un polynôme rationnel du troisième degré qui ne possède pas de racine rationnelle. D’après notre théorème, ce nombre ne peut pas être constructible. Nous voilà donc face à une contradiction… Donc posez vos compas, inutile de vouloir construire un heptagone régulier, cela est impossible ! (non, vraiment, posez vos compas, ça peut être dangereux ces machins…)

Bonus: l’impossible trisection d’un angle

Ce qui est bien avec ce théorème, c’est qu’on peut s’en resservir pour montrer qu’il n’est pas possible de trisecter (couper en trois) un angle à la règle et au compas. En effet, si cela était possible, on pourrait par exemple trisecter l’angle \dfrac{\pi}{3} (60°) et donc obtenir un angle de \dfrac{\pi}{9} (20°). On pourrait donc construire le nombre 2\cos\left( \dfrac{\pi}{9}\right). Or, ce nombre est racine du polynôme

P =  X^3 - 3X -1

En effet, la formule \cos(3 \theta) = 4 \cos(\theta)^3 - 3 \cos(\theta) (comme quoi, elles servent les formules de trigo !) appliquée \theta = \frac{\pi}{9} donne

\dfrac{1}{2} = 4 \cos( \pi/9)^3 - 3 \cos(\pi/9) \iff 1 = 8 \cos( \pi/9)^3 - 3 \times 2 \cos(\pi/9)

c’est-à-dire

(2 \cos(\pi/9))^3 - 3 (2\cos(\pi/9)) - 1 = 0

Je vous laisse vérifier pour finir que le polynôme X^3 - 3X - 1 n’a pas de racine rationnelle, ce qui prouve que l’on ne peut pas construire 2\cos\left( \dfrac{\pi}{9}\right) et que la trisection de l’angle \frac{\pi}{3} est impossible !

Note:

Publié dans Algèbre, Géométrie | Tagué , , , , , , , , | Laisser un commentaire

Comment reconnaître deux nombres premiers jumeaux ?

Deux nombres premiers p et p+2 qui ne diffèrent que de 2 s’appellent une paire de nombres premiers jumeaux. Par exemple, les nombres 3 et 5 forment une paire de nombres premiers jumeaux. Le 14 Septembre 2016, le projet de calcul distribué PrimeGrid annonçait avoir découvert que les nombres

2 \, 996 \, 863 \, 034 \, 895 \times 2^{1 \, 290 \,  000} - 1 et 2 \, 996 \, 863 \, 034 \, 895 \times 2^{1 \, 290 \,  000} + 1

sont eux aussi des nombres premiers jumeaux. Ces nombres, au demeurant gigantesques (ils sont composés de 388 342 chiffres chacun !), sont la plus grande paire de nombres premiers jumeaux qu’on n’ait jamais trouvée !

Si l’on en croît l’annonce officielle de la découverte, on a vérifié que chacun de ces deux nombres est premier en leur appliquant à chacun le test de primalité LLR. Mais saviez-vous qu’il existe une formule très simple et qui tient en une ligne permettant de dire si deux nombres quelconques qui diffèrent de 2 sont des nombres premiers jumeaux ? Bon, c’est vrai que cette formule est peu efficace en pratique comme nous le verrons, mais elle a tout de même le mérite d’exister !

Un critère de gémellité

Voici donc le critère très simple permettant de dire si deux nombres n et n+2 forment une paire de nombres premiers jumeaux:

Soit n>1 un entier naturel. Les nombres n et n+2 sont deux nombres premiers jumeaux si, et seulement si,

4 \times [(n-1)! + 1] + n \equiv 0 \mod [n(n+2)]

Comme vous l’avez peut-être noté, ce critère se rapproche beaucoup du théorème de Wilson (qui dit que n est premier si, et seulement si, (n-1)!+1 \equiv 0 \mod [n]) et ce n’est pas un hasard !

Ce critère ne s'applique pas à Igor et Grichka. Impossible donc de savoir s'ils sont premiers, ni même jumeaux.

Ce critère ne s’applique pas à Igor et Grichka. Impossible donc de savoir s’ils sont premiers, ni même jumeaux.

Quelques exemples

Pour bien comprendre ce critère permettant de déterminer des nombres premiers jumeaux, prenons quelques exemples faciles:

Exemple 1: Si l’on prend n=3 alors n(n+2) = 3 \times 5 = 15. Il s’agit de regarder le nombre 4 \times [(3-1) ! +1] + 3 modulo 15 pour savoir si 3 et 5 forment bien une paire de nombres premiers jumeaux:

4  \times [(3-1) ! +1] + 3 = 4 \times ( 2! +1) + 3 = 4 \times (2+1) + 3 = 15 \equiv 0 \mod [15]

Voilà, nous venons de démontrer en un calcul que 3 et 5 sont bien des nombres premiers jumeaux !

• Exemple 2: Si l’on souhaite montrer que 8 et 10 ne sont pas des nombres premiers jumeaux, prenons n=8 et calculons modulo 8 \times 10 = 80:

4  \times [(8-1) ! +1] + 8 =  20172 \equiv 12 \mod [80]

Comme nous n’obtenons pas 0, c’est qu’il ne s’agissait pas d’une paire de nombres premiers jumeaux. En fait, ni 8, ni 10 n’est premier mais je voulais simplement illustrer le fait que ce critère marche vraiment avec tous les nombres !

• Exemple 3: Prenons l’exemple de 9 et 11, où seul 11 est premier. Puisque n=9, alors n(n+2) = 99 et :

4  \times [(9-1) ! +1] + 9 =  161293 \equiv 22 \neq 0 \mod [99]

et on retrouve bien le fait que 9 et 11 ne forment pas une paire de nombres premiers jumeaux.

Exemple 4: Pour finir, redémontrons que 11 et 13 sont bien des nombres premiers jumeaux en prenant n=11. On a

4  \times [(11-1) ! +1] + 11 = 4 \times ( 3628800 +1 ) + 11 = 14 \, 515 \, 215 

Comme 14 \, 515 \, 215 = 11 \times 13 \times 101 \, 505 (je vous invite à vérifier mes calculs par vous-même !), c’est qu’on a bien

4  \times [(11-1) ! +1] + 11 \equiv 0 \mod[11 \times 13]

Encore une fois, le critère marche !

Vous l’avez sans doute compris, cette formule permet de montrer en une fois que deux nombres qui diffèrent de 2 sont simultanément premiers.

La démonstration (1ère mi-temps)

La démonstration de ce critère va reposer sur le théorème de Wilson que nous avons mentionné plus haut. Puisque ce critère est une équivalence, il s’agit de montrer une implication et sa réciproque.

Le sens direct: Soit n>1 tel que n et n+2 sont deux nombres premiers. Il s’agit de montrer que

4 \times [(n-1)! + 1] + n \equiv 0 \mod [n(n+2)]

Comme n+2 est premier, d’après le théorème de Wilson, nous savons que

(n+1)! + 1 \equiv 0 \mod[n+2]

Or, n \equiv -2 \mod[n+2] et n+1 \equiv -1 \mod[n+2] donc n \times (n+1) \equiv (-1) \times (-2) = 2 \mod [n+2]. Ainsi,

(n+1)! + 1 = (n-1)! \times n \times (n+1) + 1 \equiv 2(n-1)! + 1\mod[n+2]

En reprenant alors l’égalité du théorème de Wilson, on a

2 (n-1)! +1 \equiv 0 \mod[n+2]

Si on quitte le (magnifique) langage des congruences un moment, cela signifie qu’il existe un entier k tel que

2(n-1) ! + 1 = k (n+2) \,\, \, \, (\star)

(gardez bien cette relation à l’esprit, nous allons nous en resservir !). Si on regarde cette égalité modulo n, cela donne

2 (n-1)! + 1 \equiv k ( 0 + 2) \mod[n]

Mais comme n est premier, alors (n-1)! \equiv -1 \mod[n] (toujours d’après le théorème de Wilson !) et donc

2 \times (-1) + 1 \equiv 2 k \mod[n]

Nous venons donc de montrer que -1 \equiv 2k \mod[n]. Autrement dit, il existe un entier q tel que 2k = -1 + qn. Si on reprend alors la relation (\star) et qu’on la multiplie par 2, on obtient

4(n-1)! + 2 = 2k (n+2)

En remplaçant à présent 2k par 1 + qn, on a alors

4(n-1)!  + 2 = (-1 + qn)(n+2)

et en distribuant (n+2) sur (-1 + qn), on en déduit que

4(n-1)! + 2 = -(n+2) + qn(n+2)

qui est encore équivalent à

4 \times [ (n-1)! + 1] + n = q n (n+2)

En revenant au langage des congruences, cela veut exactement dire que

\boxed{4 \times [ (n-1)! + 1] + n \equiv 0 \mod[n(n+2)]}.

Je vous laisse souffler un peu avant d’attaquer la suite. Profitez-en pour faire une petite pause pipi qui fait toujours du bien en milieu d’article.

La démonstration (2ème mi-temps)

Le sens réciproque: On suppose à présent que 4 \times [ (n-1)! + 1] + n \equiv 0 \mod[n(n+2)]. Autrement dit, il existe un entier k tel que

4 \times  (n-1)! + 4 + n = k n(n+2) \, \, \, (\star \star)

a) Commençons par montrer que cela implique que n (et donc n+2) est nécessairement impair. Par l’absurde, si on suppose que n est pair, alors n+2 est lui aussi pair. Nous avons ainsi deux nombres pairs consécutifs, donc il y en a un des deux qui est divisible par 4 (et l’autre non).

Si c’est n qui est divisible par 4 alors n=4q avec avec q <n. Ainsi, la relation (\star \star ) implique que

4 (n-1)! + 4 + 4q = k \times 4q \times (n+2)

En la simplifiant par 4, on a alors (n-1)! + 1 + q = k \times q \times (n+2) ce qui entraîne que q divise (n-1)! + 1 + q. Or, comme q divise q (comme d’habitude, chaque article a sa phrase débile, donc la voici pour celui-là) alors q divise (n-1)! +1. Mais, q divise aussi (n-1)! car q<n. On en déduit que q divise (n-1)! + 1 - (n-1)! = 1. Ainsi, q= 1 et donc n=4. Mais cela n’est pas possible car

4 \times ( (4-1) ! + 1) + 4 = 32 \neq 0 \mod [4 \times 6]

ce qui contredit notre hypothèse de départ. Tout cela montre donc que n n’est pas divisible par 4 et que c’est n+2 qui doit l’être. En d’autres termes, n+2 \equiv 0 \mod [4] et donc n \equiv 2 \mod[4]. Sachant cela, si on regarde la relation (\star \star) modulo 4, elle donne

0 \times (n-1)! + 0 + 2 \equiv k \times 2 \times 0 \mod[4]

c’est-à-dire 2 \equiv 0 \mod [4], ce qui est, bien entendu, fichtrement absurde (si je puis me permettre).

b) Maintenant que nous avons prouvé que n est nécessairement impair, reprenons notre hypothèse de départ: 4 \times [ (n-1)! + 1] + n \equiv 0 \mod[n(n+2)].  En particulier, elle implique que

4 \times [ (n-1)! + 1] + n \equiv 0 \mod[n+2]

car si un nombre est divisible par n(n+2), il est a fortiori divisible uniquement par n+2. Nous pouvons réécrire cela sous la forme

2 \times 2  (n-1)! + 4 + n \equiv 0 \mod[n+2]

Or, nous avions vu plus haut dans cette démonstration (voir le sens direct) que 2(n-1)! \equiv (n+1)! \mod[n+2]. Cela, plus le fait que 4+n \equiv 2 \mod [n+2], nous permet de dire que

2 (n+1)! + 2 \equiv 0 \mod [n+2]

et en factorisant, on a

2 [ (n+1)! + 1 ] \equiv 0 \mod [n+2]

C’est à présent que nous allons utiliser le fait que n+2 est impair: il est donc premier avec 2, ce qui veut dire que 2 admet un inverse modulo n+2. Bref, tout cela permet de simplifier par 2 et on obtient

(n+1)! + 1 \equiv 0 \mod [n+2]

D’après le théorème de Wilson, cette relation entraîne alors que n+2 est premier. Pour montrer que n est lui aussi premier, on suit un raisonnement analogue: de l’hypothèse de départ on tire que

4 \times [ (n-1)! + 1] + n \equiv 0 \mod[n]

comme n \equiv 0 \mod [n], cela est équivalent à

4 \times [ (n-1)! + 1]  \equiv 0 \mod[n]

Comme n est impair, il est premier avec 4 et donc on peut simplifier cette relation par 4, ce qui donne

(n-1)! + 1 \equiv 0 \mod [n]

et donc d’après le théorème de Wilson, n est premier. Les nombres n et n+2 sont bien des nombres premiers jumeaux ! CQFD.

Que donne ce critère en pratique ?

A l’instar du théorème de Wilson, en pratique, ce critère est inutilisable: à cause de la présence d’une factorielle dans la relation, le temps de calcul devient beaucoup trop long lorsque n devient très grand. Il faudrait une éternité (au sens propre) pour montrer que les gigantesques nombres découverts en Septembre dernier sont bien des premiers jumeaux en utilisant ce critère !

Malgré tout, on peut utiliser ce critère pour des nombres d’une taille raisonnable. Par exemple, ce test n’a mis « que » 14 secondes sur mon pauvre petit PC bien frêle pour montrer que 18 409 199 et 18 409 201 sont bien des nombres premiers jumeaux (à eux deux, ils forment la 100 000ème paire de nombres premiers jumeaux). Le programme utilisé se trouve ici.

Ce qui a pris 14 secondes pour mon ordi aurait sans doute pris des mois et des mois pour Euler... Vive les ordinateurs !

Ce qui a pris 14 secondes à mon ordi aurait sans doute pris des mois et des mois à Euler… Vive les ordinateurs !

3ème mi-temps: une généralisation

Le critère que nous avons donné peut se généraliser pour déterminer non plus des paires de nombres premiers jumeaux, mais des triplets de nombres premiers, c’est-à-dire trois nombres premiers de la forme n, n+2 et n+6 (on n’a pas mis n+4 car parmi l’un des trois nombres n, n+2 et n+4 l’un au moins est divisible par 3…). Plus précisément, on peut montrer que

Soit n>1 un entier naturel. Les nombres n, n+2 et n+6 sont trois nombres premiers si, et seulement si,

4320 \times ( 4 \times [(n-1)! + 1] + n ) + 361n(n+2) \equiv 0 \mod [n(n+2)(n+6)]

Par exemple, si on prend n=11:

4320 \times ( 4 \times [(11-1)! + 1] + 11 ) + 361 \times 11 \times ( 11 +2) = 62 \, 705 \, 780 \, 423

et comme 62 \, 705 \, 780 \, 423 = 11 \times 13 \times 17 \times 25 \, 794 \, 233 , cela veut dire que

4320 \times ( 4 \times [(11-1)! + 1] + 11 ) + 361 \times 11 \times 13 \equiv 0 \mod [11 \times 13 \times 17]

Nous avons bien redémontré que 11, 13 et 17 forment un triplet de nombres premiers !

Référence:

Congruences for Sets of Primes, P. A. Clement, The American Mathematical Monthly, Vol. 56, No. 1 (Jan., 1949), pp. 23-25

(Dans cet article, la démonstration de la réciproque du critère est vraiment torchée, pour ne pas dire laissée au lecteur en exercice… L’auteur donne aussi à la fin de son article un critère du même type pour que quatre nombres n, n+2, n+6 et n+8 soient tous premiers !)

Publié dans Arithmétique | Tagué , , , , , , | 2 commentaires

Le Roi des Catalans (2ème partie)

Dans la première partie de cet article, nous nous étions intéressés au problème suivant:

Si on place un Roi sur un échiquier de (n +1) \times (n +1) cases, et s’il ne peut se déplacer que vers la droite ou vers le haut à chaque étape, de combien de façons C_n peut-il aller de la case (0,0) à la case (n,n) sans jamais aller au-dessus de la diagonale principale ?

roi_des_catalans2_rappel_du_problemeNous avions déterminé une relation de récurrence suivie par la suite (C_n), à savoir:

\displaystyle C_{n+1} = \sum_{i=0}^n C_i C_{n-i}

Grâce à celle-ci, nous avions trouvé que, pour un échiquier standard (8 cases sur 8 cases), il y avait C_7 = 429 chemins possibles pour le Roi.

roi_des_catalans2_un_des_429_chemins

Un des 429 chemins possibles pour le Roi sur un échiquier standard.

Dans cette seconde partie, nous allons essayer de déterminer une formule explicite de la suite C_n. Rien de moins !

Rencontre du 3ème type

Plaçons-nous sur un échiquier à (n+1) \times (n+1) cases. Afin de trouver le nombre C_n de chemins du Roi qui ne dépassent jamais la diagonale principale, nous allons commencer par définir d’autres types de chemins qui, eux, seront plus simples à dénombrer. Plus précisément, voici les trois types de chemins que nous allons étudier:

■ Les chemins simples: ce sont les chemins allant de (0,0) à (n,n) sans contrainte particulière (si ce n’est qu’à chaque étape, le Roi ne se déplace que vers la droite ou vers le haut). Nous noterons S_n le nombre total de chemins simples.

Un exemple de chemin simple.

Exemple de chemin simple.

■ Les chemins légaux: ce sont les chemins allant de la case (0,0) à la case (n,n) qui ne dépassent jamais la diagonale principale. Comme nous l’avons dit, nous appelons C_n la nombre total de chemins légaux.

roi_des_catalans2_exemple_de__chemin_legal

Exemple de chemin légal.

■ Les chemins illégaux: ce sont les chemins allant de (0,0) à (n,n) qui dépassent au moins une fois la diagonale principale. Nous noterons I_n le nombre total de chemins illégaux.

Un exemple de chemin illégal. (Mais que fait la police ?)

Un exemple de chemin illégal. (Mais que fait la police ?)

Vous l’avez sans doute compris, notre problème de départ revient donc à déterminer le nombre de chemins légaux C_n. Comme tout chemin simple est soit un chemin légal, soit un chemin illégal, on en déduit la relation suivante:

S_n = C_n + I_n

Ainsi, pour déterminer le nombre C_n, il va nous falloir déterminer le nombre de chemins simples et le nombre de chemins illégaux.

Les chemins simples

Déterminer le nombre S_n de chemins simples va être quelque chose de plutôt… simple (cette blague est tellement drôle que je songe sérieusement à renommer ce blog en blaguedemaths). Lorsque le Roi effectue un chemin simple, il effectue au total exactement n déplacements vers la droite et n déplacement vers le haut. En fait, si on note D chaque fois que le Roi se déplace vers la droite et H chaque fois que le Roi se déplace vers le haut, on peut alors représenter un chemin simple par une suite de 2n lettres contenant n fois la lettre D et n fois la lettre H. Par exemple, sur un échiquier standard (c’est-à-dire pour n=7), voici un exemple de suite représentant un chemin simple du Roi:

D H D D D H H D H H D D H H

et voici le chemin que cette suite représente:roi_des_catalans2_exemple_de_chemin_simple_correspondant_a_une_suite_de_lettres

Si on revient à un échiquier quelconque, on peut dire que déterminer le nombre de chemins simples revient à déterminer le nombre de suites de 2n lettres contenant  n fois la lettre D et n fois la lettre H. Pour choisir une telle suite, on peut commencer par placer n lettres D parmi les 2n emplacements possibles de cette suite. Cela donne {2n \choose n} possibilités. Une fois toutes les lettres D placées, il n’y a guère plus le choix pour placer les H. Ainsi, nous voyons que le nombre de chemins simples vaut

\displaystyle S_n = {2n \choose n}

Les chemins illégaux

Déterminer le nombre de chemins illégaux va nous demander d’être beaucoup plus astucieux. L’idée va être la suivante: puisqu’on ne sait finalement bien dénombrer que des chemins simples, nous allons construire une bijection allant de l’ensemble des chemins illégaux vers l’ensemble des chemins simples d’un certain échiquier qui, lui, sera rectangulaire (et non pas carré !). Plus précisément, à tout chemin illégal, nous allons lui associer un chemin « symétrique » grâce à ce que j’appelle personnellement l’astuce du miroir.

Miroir, mon beau miroir…

Considérons un chemin illégal. Puisqu’il est illégal, il passera à un moment donné par au moins une case située dans la zone interdite et la première case illégale par laquelle il passera aura des coordonnées de la forme (k-1, k).roi_des_catalans2__chemin_illegal_avec_1ere_case_interdite

En fait, la première case de la zone interdite sur laquelle il passera est toujours située sur la petite diagonale allant de (0,1) à (n-1,n):roi_des_catalans2_petite_diagonale

Le « symétrique » de ce chemin illégal désignera le chemin obtenu de la façon suivante:

  • au départ, tant que le chemin illégal n’a pas encore été dans la zone interdite, le chemin illégal et son « symétrique » seront les mêmes;
  • à partir du moment où le chemin illégal entre dans la zone interdite (donc à partir de la case (k-1,k)), on effectue une symétrie axiale par rapport à la petite diagonale pour obtenir le deuxième morceau du chemin « symétrique » (d’où l’expression astuce du miroir).

Voici ci-dessous un exemple sans doute plus parlant que tout mon blabla; à gauche un chemin illégal et à droite son « symétrique »:roi_des_catalans2_chemin_illegal_et_son_symetrique

Comme vous le constatez, il faut tout de même agrandir l’échiquier d’une ligne sur le haut pour obtenir le chemin « symétrique ». Vous remarquez aussi que ce symétrique a toujours pour point de départ la case (0,0) et pour point d’arrivée la case (n-1, n+1) (qui est la case symétrique de la case d’arrivée (n,n) du chemin illégal).

Enfin, dernière remarque importante: quand vous prenez le « symétrique » d’un « symétrique », vous retombez sur votre chemin de départ !

Il ne nous reste plus qu’à montrer que cette opération est une bijection. Plus précisément, nous allons démontrer la proposition suivante:

A tout chemin illégal allant de (0,0) à (n,n) correspond un et un seul chemin simple allant de (0,0) à (n-1,n+1) par l’astuce du miroir.

La démonstration

Tout d’abord, le « symétrique » d’un chemin illégal est bien un chemin simple car lorsqu’on prend le symétrique d’un chemin illégal, chaque déplacement vers la droite sera transformé en un déplacement vers le haut et chaque déplacement vers le haut sera transformé en un déplacement vers la droite. De plus, nous avons déjà expliqué pourquoi les points de départ et d’arrivée du  symétrique sont (0,0) et (n-1,n+1).

Ensuite, nous allons montrer que tout chemin simple allant de (0,0) à (n-1,n+1) est le symétrique d’au moins un chemin illégal (autrement dit, on montre la surjectivité de notre opération de « symétrie »). Si on prend un chemin simple allant de (0,0) à (n-1,n+1), alors il traversera nécessairement la petite diagonale au moins une fois, disons en la case (k-1, k). Si, à partir de ce chemin simple, on prend le chemin obtenu de la  même façon que par la méthode de l’astuce du miroir décrite plus haut, alors le chemin obtenu est bien un chemin illégal (et il va de la case (0,0) à la case (n,n)) dont la première case interdite qu’il franchira est (k-1,k).

Enfin, montrons que chaque chemin simple allant de (0,0) à (n-1,n+1) ne peut pas être l’image de plus d’un chemin illégal (il s’agit donc de l’injectivité). Rappelez-vous que nous avions noté que quand on prend le « symétrique » du « symétrique », on retrouve le chemin de départ. Donc si deux chemins illégaux ont même « symétrique », en prenant le « symétrique » de ce « symétrique » on doit retrouver le chemin initial mais comme un chemin n’a qu’un seul « symétrique », c’est que les chemins de départ étaient identiques !

Nombres de chemins illégaux

 Nous pouvons enfin calculer le nombre I_n de chemins illégaux. Puisqu’il y autant de chemins illégaux que deux chemins simples allant de (0,0) à (n-1,n+1), il suffit de dénombrer ces derniers pour trouver le nombre de chemins illégaux. Or, un raisonnement similaire à ce qu’on a fait plus haut nous dit qu’un chemin simple allant de (0,0) à (n-1,n+1) est une suite de 2n lettres dont n-1 lettres D et n+1 lettres H. Ainsi,

\displaystyle I_n = {2n \choose n-1}

ou encore \displaystyle I_n = {2n \choose n+1}

Les chemins légaux

Le nombre de chemins légaux, c’est-à-dire la réponse à notre problème de départ, est alors facile à déterminer. Puisque

C_n = S_n - I_n

on en déduit que

\displaystyle C_n = {2n \choose n} - {2n \choose n+1}

Ainsi, on a

C_n = \dfrac{(2n)!}{(2n-n)! n!} - \dfrac{(2n)!}{(2n - (n+1)) ! (n+1)!}

donc

C_n = \dfrac{(2n)!}{n! n!} - \dfrac{(2n)!}{(n-1) ! (n+1)!}

En remarquant que (n-1)! (n+1)! = n! n! \times \dfrac{n+1}{n}, on en déduit que:

C_n = \dfrac{(2n)!}{n! n!} - \dfrac{n}{n+1} \times \dfrac{(2n)!}{n! n!}

c’est-à-dire:

\displaystyle C_n = {2n \choose n} - \frac{n}{n+1} {2n \choose n}

En factorisant, on obtient:

\displaystyle C_n = \left( 1 - \frac{n}{n+1} \right) {2n \choose n}

ce qui nous donne enfin la formule tant attendue pour les nombres de Catalan (que nous avons bien mérité d’obtenir après tant d’efforts !):

\boxed{ \displaystyle C_n = \frac{1}{n+1} {2n \choose n} }

Par exemple, pour un échiquier standard (n=7), on obtient

\displaystyle C_7 = \frac{1}{7+1} {14 \choose 7 } = \frac{1}{8}  \times 3432 = 429

ce qui était bien ce qu’on avait déjà trouvé !

Utilisation des nombres de Catalan

On ne retrouve pas les nombres de Catalan seulement sur un échiquier mais aussi dans une multitude de situations ! En fait, si on analyse ce qu’on a fait dans cet article, les nombres de Catalan permettront (entre autres) de dénombrer toute liste d’éléments composée de deux types d’éléments « A » et « B » telle que:

  • il y a autant de A que de B;
  • à chaque étape quand on parcourt la liste de la gauche vers la droite, il y a toujours plus (ou autant) de A que de B

Dans notre exemple, un chemin du Roi qui ne traverse pas la diagonale n’est rien d’autre qu’une suite de n déplacements vers la droite (D) et de n déplacements vers le haut (H) telle qu’à chaque étape, il y a toujours plus (ou autant) de D que de H (si à un moment il y a plus de H que de D, c’est qu’on est entré dans la zone interdite !).

Autre exemple: on voit que les nombres de Catalan permettent de dénombrer facilement le nombre de façons de disposer n paires de parenthèses car lorsqu’on place des parenthèses, il faut que:

  •   il y ait autant de parenthèses ouvrantes « ( » que fermante « ) »
  •   à chaque étape quand on lit une expression de la gauche vers la droite, il y a toujours plus ou autant de parenthèses ouvrantes « ( » que de parenthèses fermantes « ) ».

Ainsi, il y a C_n façons de disposer n paires de parenthèses.

roi_des_catalans2_les_14_facons_de_placer_4_paires_de_parentheses

Les C4 = 14 façons de placer 4 paires de parenthèses.

Un dernier exemple, pour la route…

Un autre exemple un peu moins trivial avec des parenthèses est le suivant: imaginons une opération qui n’est pas associative (par exemple le produit vectoriel). De combien de façons différentes peut-on interpréter le calcul du produit suivant ?

A \times B \times C \times D

Par exemple, une façon d’interpréter ce calcul est:

((A \times B) \times (C \times D))

ou bien:

(A \times (B \times (C \times D))

On peut remarquer que pour se donner une expression, il suffit de savoir où sont placées les parenthèses ouvrantes ainsi que les produits; le reste (les parenthèses fermantes et les variables) est alors entièrement déterminé. Par exemple, si je vous donne l’expression

(\times (( \times \times

alors on place les variables A, B et C à gauche des signes \times et la variable D à droite du dernier signe \times:

(A\times((B\times C \times D

Ensuite, il n’y a plus guère le choix pour placer les parenthèses fermantes de façon à ce que l’expression ait du sens:

(A\times((B\times C) \times D))

(en fait, on commence par fermer la parenthèse ouvrante la plus « intérieure » et on continue comme cela jusqu’à la parenthèse ouvrante la plus « extérieure »).

Tout cela pour dire que, pour se donner une expression valide, il suffit de se donner une suite de ( et de \times telle que:

  • il y a au total autant de parenthèses ouvrantes ( que de symboles \times
  • à chaque étape quand on lit l’expression de gauche à droite, il y a plus ou autant de parenthèses ouvrantes ( que de signes \times

D’après ce qu’on a dit plus haut, le nombre d’expressions de ce type possédant 3 parenthèses ouvrantes et 3 symboles \times est donné par le nombre de Catalan C_3 = 5. Voici toutes les possibilités:

  • ( \times ( \times ( \times
  • ( \times (( \times \times
  • ((\times \times ( \times
  • (( \times ( \times \times
  • ((( \times \times \times

et voici les 5 expressions possibles qu’elles donnent:

  • ( A\times ( B \times ( C \times D)))
  • ( A\times (( B\times C) \times D))
  • ((A\times B) \times ( C \times D))
  • (( A \times ( B\times C)) \times D)
  • ((( A \times B) \times C) \times D)

Bien entendu, on peut généraliser cela de la façon suivante:

Le nombre de façons de parenthéser l’expression x_1 \times x_2 \times \cdots \times x_n est C_{n-1}

Bref, on pourrait parler des nombres de Catalan encore pour longtemps car ils apparaissent souvent lorsqu’on fait du dénombrement ! J’espère juste que le Roi sur son échiquier ne m’en voudra pas trop de l’avoir mis entre parenthèses…

Notes:

Publié dans Dénombrement | Tagué , , , , , | 4 commentaires