Trouver Vs. Vérifier

EDIT: Attention, il y a une erreur dans cet article. Je n’ai pas fait attention à prendre des m_j 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 m_1,m_2, ..., m_k (non nécessairement distincts) tels que:

\displaystyle{ 1+\frac{2^k-1}{n}=(1+ \frac{1}{m_1})(1+ \frac{1}{m_2}) ... (1+ \frac{1}{m_k})}

La solution, version foutage de gueule

Soit k,n deux entiers naturels strictement positifs. Pour tout entier naturel j compris entre 1 et k, on pose m_j=\dfrac{n+2^{j-1}-1}{2^{j-1}}. On a donc:

\begin{array}{rcl}  \displaystyle{ \prod_{j=1}^{k} (1+ \frac{1}{m_j}) } &=& \displaystyle{ \prod_{j=1}^{k} (1+ \frac{2^{j-1}}{n+2^{j-1}-1}) } \\  & & \\  &=& \displaystyle{ \prod_{j=1}^{k} \frac{n+2^{j-1}-1 + 2^{j-1}}{n+2^{j-1}-1} }\\  &&\\  &=& \displaystyle{ \prod_{j=1}^{k} \frac{n+2^{j}-1}{n+2^{j-1}-1} } \\  \end{array}

Et là, on reconnaît un produit télescopique où les termes se simplifient successivement. Plus précisément,

\displaystyle{ \prod_{j=1}^{k} (1+ \frac{1}{m_j}) = \frac{n+2^{1}-1}{n+2^{0}-1} \times \frac{n+2^{2}-1}{n+2^{1}-1} \times ... \times \frac{n+2^{k}-1}{n+2^{k-1}-1} }

Ainsi, après simplifications, il reste:

\displaystyle{ \prod_{j=1}^{k} (1+ \frac{1}{m_j}) = \frac{n+2^{k}-1}{n+2^{0}-1} = \frac{n+2^{k}-1}{n} = 1 + \frac{2^{k}-1}{n} }

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 m_j 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 m_j=\dfrac{n+2^{j-1}-1}{2^{j-1}} ? « . 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 n=1,2,.... Je n’ai rien trouvé de bien concluant. Puis, je me suis dit, « serait-il possible de construire cette suite m_j 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 n. Pour tout k, on nous demande de montrer l’existence d’une suite (m_j)_{0 \leq j \leq k}. A priori, si je prend un k différent, toute la suite (m_j) 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 (m_j) correspondant à l’entier k+1 à partir de la suite (m_j) correspondant à l’entier k. Autrement dit, si on suppose que m_1, m_2, ..., m_k sont déjà construits et qu’ils vérifient \displaystyle{ 1+\frac{2^k-1}{n}=(1+ \frac{1}{m_1})(1+ \frac{1}{m_2}) ... (1+ \frac{1}{m_k})}, alors puis-je réutiliser ces k nombres pour former, à partir d’eux, une nouvelle suite à laquelle on ajouterait un terme supplémentaire m_{k+1} et qui vérifierait \displaystyle{ 1+\frac{2^{k+1}-1}{n}=(1+ \frac{1}{m_1})(1+ \frac{1}{m_2}) ... (1+ \frac{1}{m_{k+1}})}? Suivons donc cette idée.

■ Si k=1, alors \displaystyle{ 1+\frac{2^1-1}{n} } = 1 + \dfrac{1}{n} et donc on voit qu’on peut poser m_1 = n.

■ Si k=2, cherchons m_2 en supposant que m_1=n. Dans ces conditions, on doit avoir:

\displaystyle{ 1+\frac{2^2-1}{n} } = (1 + \dfrac{1}{m_1}) (1 + \dfrac{1}{m_2})

c’est-à-dire:

\displaystyle{ 1+\frac{3}{n} } = (1 + \dfrac{1}{n}) (1 + \dfrac{1}{m_2})

On résout cette petite équation, en multipliant chaque membre par n pour obtenir une expression plus sympatoche:

\displaystyle{ n + 3 = (n + 1) ( 1 + \frac{1}{m_2} )}

et donc on trouve

m_2 = \dfrac{n+1}{4}

Cela est intéressant, car on se rend compte, qu’à partir de m_1 déjà construit, on a pu trouver un m_2 qui réponde au problème. Reste plus qu’à passer au cas général.

■ Si k est un entier strictement positif, on suppose avoir m_1, m_2, ..., m_k des nombres tels que

\displaystyle{ 1+\frac{2^k-1}{n}=(1+ \frac{1}{m_1})(1+ \frac{1}{m_2}) ... (1+ \frac{1}{m_k})}

et on cherche un nombre m_{k+1} tel que

\displaystyle{ 1+\frac{2^{k+1}-1}{n}=(1+ \frac{1}{m_1})(1+ \frac{1}{m_2}) ... (1+ \frac{1}{m_k}) (1+ \frac{1}{m_{k+1}})}.

Remarquons immédiatement que la dernière égalité est équivalente à

\displaystyle{ 1+\frac{2^{k+1}-1}{n}= (1+ \frac{2^{k}-1}{n}) (1+ \frac{1}{m_{k+1}})}

On a juste utilisé notre hypothèse de récurrence ! A partir de là, le reste est simple. On multiplie cette égalité par n et on en déduit m_{k+1}:

\displaystyle{ n+2^{k+1}-1= (n+ 2^{k}-1) (1+ \frac{1}{m_{k+1}})}

Donc,

\displaystyle{ \frac{n+2^{k+1}-1}{n+ 2^{k}-1}= 1+ \frac{1}{m_{k+1}}}

Ainsi,

\displaystyle{ \frac{(n+2^{k+1}-1)-(n+2^k - 1)}{n+ 2^{k}-1}= \frac{1}{m_{k+1}}}

D’où,

\displaystyle{ \frac{2^{k+1}-2^k }{n+ 2^{k}-1}= \frac{1}{m_{k+1}}}

Puis,

\displaystyle{ \frac{2^{k}}{n+ 2^{k}-1}= \frac{1}{m_{k+1}}}

Et on trouve:

\displaystyle{m_{k+1} = \frac{n+ 2^{k}-1}{2^{k}}}

Ainsi, si les nombres m_j existent, alors nécessairement, m_j = \dfrac{n+2^{j-1}-1}{2^{j-1}}. 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
Cet article, publié dans Algèbre, est tagué , , . Ajoutez ce permalien à vos favoris.

2 commentaires pour Trouver Vs. Vérifier

  1. … 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!

    • blogdemaths dit :

      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…

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s