EDIT: Attention, il y a une erreur dans cet article. Je n’ai pas fait attention à prendre des qui soient entiers. Je laisse cependant l’article tel quel en attendant de le modifier… Ne m’en voulez pas trop ! Et bonne lecture.
Tous ceux qui ont pratiqué l’activité mathématique se sont au moins une fois aperçus qu’il existe une grande asymétrie entre trouver une solution à un problème et vérifier qu’une solution est bien une solution. La première option étant bien plus difficile que la seconde.
Nous allons illustrer ce principe dans cet article, à l’aide d’un des exercices posés lors des dernières Olympiades Internationales de Mathématiques, qui se sont tenues en Colombie au moins de Juillet dernier.
Le problème
Montrer que pour toute paire d’entiers strictement positifs, k et n, il existe k entiers
strictement positifs (non nécessairement distincts) tels que:
La solution, version foutage de gueule
Soit deux entiers naturels strictement positifs. Pour tout entier naturel
compris entre 1 et
, on pose
. On a donc:
Et là, on reconnaît un produit télescopique où les termes se simplifient successivement. Plus précisément,
Ainsi, après simplifications, il reste:
CQFD.
Cette démonstration est tout à fait correcte d’un point de vue mathématique, mais elle reste bien mystérieuse puisqu’on a parachuté des entiers de nulle part.
La recherche de la solution expliquée
Pour être honnête avec vous, je ne me suis pas levé un matin en me disant: « Tiens, et si on essayait les valeurs ? « . Comment apparaissent donc ces valeurs ?
Lorsque j’ai cherché la solution de ce problème, j’ai commencé par tâtonner, j’ai essayé de voir ce qu’il se passe pour . Je n’ai rien trouvé de bien concluant. Puis, je me suis dit, « serait-il possible de construire cette suite
par récurrence » ? C’est donc ce que j’ai tenté de faire, mais je dois dire auparavant que cela aurait pu ne pas fonctionner. Je vais essayer d’expliquer pourquoi.
On fixe un entier naturel . Pour tout
, on nous demande de montrer l’existence d’une suite
. A priori, si je prend un
différent, toute la suite
peut être différente; rien ne l’interdit en tout cas.
Cependant, j’ai essayé de voir ce qué se passerait si on pouvait construire la suite correspondant à l’entier
à partir de la suite
correspondant à l’entier
. Autrement dit, si on suppose que
sont déjà construits et qu’ils vérifient
, alors puis-je réutiliser ces
nombres pour former, à partir d’eux, une nouvelle suite à laquelle on ajouterait un terme supplémentaire
et qui vérifierait
? Suivons donc cette idée.
■ Si , alors
et donc on voit qu’on peut poser
.
■ Si , cherchons
en supposant que
. Dans ces conditions, on doit avoir:
c’est-à-dire:
On résout cette petite équation, en multipliant chaque membre par pour obtenir une expression plus sympatoche:
et donc on trouve
Cela est intéressant, car on se rend compte, qu’à partir de déjà construit, on a pu trouver un
qui réponde au problème. Reste plus qu’à passer au cas général.
■ Si est un entier strictement positif, on suppose avoir
des nombres tels que
et on cherche un nombre tel que
.
Remarquons immédiatement que la dernière égalité est équivalente à
On a juste utilisé notre hypothèse de récurrence ! A partir de là, le reste est simple. On multiplie cette égalité par et on en déduit
:
Donc,
Ainsi,
D’où,
Puis,
Et on trouve:
Ainsi, si les nombres existent, alors nécessairement,
. Voilà donc d’où ils sortent ! Rien de mystérieux comme vous le voyez. La solution donnée au départ se passait bien de ces explications, et mathématiquement, on s’en fout de savoir d’où ça sort du moment que ça marche. Mais en même temps, on ne peut pas se passer de cette phase de recherche car on a peu de chance de déviner cette solution au hasard…
Non(P=NP) ?
Comme je l’ai dit au début de cet article, ce petit problème permet d’illustrer empiriquement l’écart qu’il y a entre vérifier qu’une solution est bien une solution et trouver ladite solution. C’est un sujet qui est étudié de près en mathématiques: c’est ce qu’on appelle le problème « P=NP ».
Je vais être honnête avec vous et vous dire que je ne connais pas grand chose à ce problème, donc plutôt que de me lancer dans des explications hasardeuses, je vais laisser d’autres personnes vous en parler mieux que moi: rendez-vous sur cet article du site Interstices, écrit par le célèbre Jean-Paul Delahaye !
… et mathématiquement, on s’en fout de savoir d’où ça sort du moment que ça marche.
Pas d’accord! Je pense au contraire que la quête d’explication d’un phénomène, aussi subjectif cela soit il, est un moteur fondamental de la recherche en mathématique (et probablement en toute discipline). Aussi, même s’il est, provisoirement sans doute, entaché d’erreur, votre propos est très pertinent. D’ailleurs, le fait de se tromper est aussi un des catalyseurs de la recherche. Je n’ai pas encore complètement analysé votre argumentation et ne sais donc pas comment l’adapter – je ne saurai peut-être pas le faire du reste. Mais cela n’y change rien : la démarche est la bonne!
J’aimeJ’aime
Bonjour Pierre et merci de ces éclairages.
J’aurais dû préciser ce que j’entends par « mathématiquement »: il s’agit de la preuve mathématique. La preuve mathématique en tant que telle, n’a pas besoin de savoir d’où sortent les nombres qu’on posent, ni de comment on les a trouvé. Il suffit de vérifier qu’il marche. « Posons x=… Et vérifions que ça marche. Donc, il existe bien truc tel que… ».
Mais d’un point de vue de la recherche, évidemment que c’est important de savoir comment on trouve un objet. C’est l’idée que j’ai voulu illustrer dans cet article, à savoir que la recherche, même si elle n’apparaît pas au final dans la preuve, est aussi importante que le reste…
J’aimeJ’aime