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

2 commentaires pour Trouver Vs. Vérifier

Pierre Lecomte dit :

29 septembre 2013 à 0 h 22 min

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

Réponse
- blogdemaths dit :
  
  2 octobre 2013 à 19 h 16 min
  
  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…
  
  Réponse

Laisser un commentaire Annuler la réponse.

Entrez votre commentaire...

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

E-mail (adresse strictement confidentielle)

Nom

Site web

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

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

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

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

Annuler

Connexion à %s