Trouver Vs. Vérifier

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 !

Publicités