Le Raisonnement par Récurrence

Lions and a Dead Zebra

Dans la savane, des lions sont affamés et sans pitié. Chacun mangera un autre lion s’il le peut, à condition que ceci peut se faire en toute sécurité. Tout à coup, un zèbre malade tombe à terre au milieu de la savane. Les lions vont-ils le manger ?

Ben, s’ils ont faim, oui. Non ?

A priori, oui. En effet. Mais imaginons que, lorsqu’un lion commence à manger, il devient vulnérable aux attaques des autres lions… Ah oui, aussi, même si, je te l’accorde, c’est pas super réaliste, on va supposer que les lions sont super intelligents ! Donc chaque lion sait que s’il s’attaque le zèbre, il risque de se faire bouffer par un autre lion… Le zèbre va-t-il se faire manger ?

Bah du coup, non. Les lions ne vont pas manger le zèbre…

Prends ton temps… Réfléchis-y…

Euh… Hummm. Je vois pas trop où tu veux en venir. Tu peux me donner un indice ?

OK, je vais t’expliquer les bases du raisonnement par récurrence… Ça devrait t’aider pour résoudre le problème des lions.

Une énigme de cadenas pour commencer…

Et donc, c’est quoi, un raisonnement par récurrence ?

Je vais commencer par une petite blague. Supposons qu’il faille 3 physiciens pour visser une ampoule, un pour tenir l’ampoule pendant que les deux autres font tourner l’univers, combien de mathématiciens faut-il pour visser la même ampoule ?

Humm…

Bah un seul. Le mathématicien embauche les 3 physiciens, et se ramène ainsi à un problème déjà résolu.

Haha… Les matheux aiment bien réduire leurs problèmes à des problèmes bien connus !

Oui ! Un peu comme les informaticiens, les matheux sont des gros fainéants. On déteste refaire la même chose deux fois. Du coup, si l’on peut se ramener à un problème dont on sait qu’il a été résolu, on considère qu’on a résolu le problème. Et du coup, on commence par les versions les plus simples du problèmes, et on essaie de ramener les versions plus compliquées à ces versions plus simples.

Tu peux donner un « vrai » exemple ?

Bien sûr ! Considérons le problème suivant du génialissime James Grime sur SingingBanana.

En gros, on a un cadenas codé par trois numéros entre 1 et 3. Tu peux seulement tourner les deux premiers en même temps, ou les deux derniers en même temps. En commençant par la position 3-3-3, comment en arriver à la position 2-2-1?

James Grime a présenté sa solution, mais je vais donner la mienne, parce que je la trouve plus jolie ! Haha James, j’ai fait mieux que toi et de toute façon tu ne parles pas français donc tu ne remarqueras jamais que je fais des blagues à tes dépends ! Plus sérieusement, ma preuve est plus pertinente pour cet article, puisqu’elle utilise le raisonnement par récurrence.

Comment ça marche ?

On va devoir être un peu malin. Je vais prétendre que, peu importe quel mouvement on fait, si l’on ajoute le premier numéro avec le troisième, et si l’on soustrait le deuxième, on obtient toujours un multiple de trois. Autrement dit, $gauche-milieu+droite$ est divisible par 3. C’est ce que je vais appeler la propriété d’invariance. Et bien, on peut la prouver par un raisonnement par récurrence!

Comment il faut faire?

À toi de deviner ! Allez, je t’ai quasiment déjà tout dit !

Ah oui ! Il faut commencer par les cas les plus simples… comme la combination 3-3-3, hein ?

Oui ! Pour cette combinaison, on a $gauche-milieu+droite=3-3+3=3$. C’est un multiple de 3 !

Trop facile ! Et, maintenant, il faut se ramener à ce cas, c’est ça ?

Oui !

Et on fait comment ?

Commençons par une remarque simple. Toute suite de mouvements que l’on peut faire est une suite finie de mouvement. Par ailleurs, la combinaison 3-3-3 correspond à une suite de 0 mouvement. C’est pour ça que c’est le cas « simple ». Alors, le cas juste un poil plus compliqué, c’est si l’on fait 1 mouvement. Puis 2 mouvements. Et bien, ce que l’on va montrer, c’est que peu importe le nombre $n$ de mouvements que l’on fait, on peut toujours se ramener à un cas plus simple avec moins de mouvements. Autrement dit, on va montrer que le fait que $gauche-milieu+droite$ soit divisible par 3 est héréditaire.

Euh… c’est quoi l’hérédité?

C’est un peu comme entre fille et mère. L’hérédité, c’est quelque chose qui, si elle affecte la mère (ou le nombre $n-1$), alors elle va forcément affecter la fille aussi (ou le nombre suivant $n$). Du coup, pour montrer que l’hérédité est vraie, on va supposer que l’on a prouvé la propriété d’invariance pour $n-1$ (ou que la mère est intelligente), et montrer que cela l’implique pour $n$ aussi (ou que la fille est intelligente aussi).

Lock - Recursion Property

Et donc, dans notre cas… ça donne quoi ?

D’abord, je suppose que toute combinaison obtenue après $n-1$ mouvements ou moins est telle que $gauche-milieu+droite$ est un multiple de 3. C’est ce que l’on va appeler l’hypothèse de récurrence.

Okay… Et ensuite ?

Ensuite, si l’on considère une combinaison obtenue après $n$ mouvements, alors elle vient forcément d’une combinaison obtenue après $n-1$ mouvement, à laquelle on a appliqué un autre mouvement. L’hypothèse de récurrence dit que la combinaison obtenue après $n-1$ mouvements vérifie la propriété d’invariance, à savoir $gauche-milieu+droite$ est un multiple de 3. Maintenant, si l’on fait le dernier mouvement, ou bien on ajoute 1 à $gauche$ et $milieu$ (avec peut-être quelque part une soustraction de 3 si l’un des nombres obtenus est 4), ou bien on ajoute 1 à $milieu$ et $droite$ (avec la même remarque). Dans les deux cas, au final, on a ajouté un multiple de 3 à la quantité $gauche-milieu+droite$. Et donc, il restera multiple de 3.

Et ça, ça prouve l’hérédité ?

Oui! L’hérédité dit que la propriété d’invariance pour $n$ mouvements peut se déduire de la propriété d’invariance pour $n-1$ mouvements. Mais alors, elle se déduit du cas $n-2$, donc du cas $n-3$, et ainsi de suite… jusqu’au cas…

où l’on n’a pas fait de mouvement !

Exactement ! La figure suivante illustre ce phénomène de cascade :

Induction

Et voilà qui montre que la propriété d’invariance est vérifiée peu importe le nombre de mouvements que l’on fait. Et donc, pour toute combinaison qui peut être atteinte ! On l’a prouvé par récurrence !

Le raisonnement par récurrence est intimement lié à la nature même des nombres naturels, lesquels sont définis par les axiomes de Peano (ou un autre système d’axiomes équivalents). Tu peux en savoir plus avec mon article sur the construction of numbers ou sur type theory!

Une autre image très à propos est celle des dominos. Si l’on s’assure que chaque domino fait tomber le suivant, et que le premier domino va tomber, tous les dominos finissent par tomber :

Selon cette métaphore, la preuve par récurrence consiste en deux étapes. Premièrement, on doit vérifier que le premier domino va tomber. Ça correspond à prouver le cas simple. Ensuite, on doit vérifier que les dominos sont bien alignés, de sorte que chaque domino va faire tomber le suivant. C’est l’hérédité.

Et donc, pour en revenir à l’énigme du cadenas…

Oui, pour en finir avec l’énigme de James Grime, on peut voir que la combinaison que l’on cherche à atteindre, 2-2-1, ne satisfait pas la propriété d’invariance. En effet, $2-2+1=1$, ce n’est pas divisible par 3! Et donc, c’est mort. Ce n’est pas atteignable. Le problème est donc impossible ! Héhé, James Grime, sacré mathématicien très joueur…

Voici d’autres énigmes : Quelles sont toutes les combinaisons atteignables ? En particulier, peut-on atteindre toutes les positions qui satisfont la propriété d’invariance ? Et pour les matheux : À quoi est isomorphe l’ensemble des combinaisons atteignables ? Pour cette dernière question, il faut faire un peu de théorie des groupes… Tu peux en savoir plus en lisant mes articles sur symmetries et sur space deformation and group representation.

Et maintenant que tu es calé en raisonnement par récurrence, revenons-en aux lions! Je vais donner la réponse… mais essaie de la trouver par toi-même avant de lire la suite !

Revenons-en aux lions

Lion Eating Zebra

Alors, t’as trouvé?

Euh… J’y réfléchis…

Si c’est le cas, ne continue pas de lire, et prends le temps de réfléchir !

Euh… Bon je ne trouve pas…

Pense à tout ce que l’on a dit jusque là. On a parlé de raisonnement par récurrence. Du coup…

Du coup il faut commencer par le cas simple. Qui correspond à 1 lion, j’imagine…

Oui! Que se passe-t-il s’il y a 1 lion?

Ben clairement, il va aller bouffer le zèbre, puisqu’il n’a pas à avoir peur des autres lions.

Oui. Que se passe-t-il s’il y a 2 lions?

Aucun n’y va, puisque chacun a peur de l’autre.

Super ! Continue comme ça ! Que se passe-t-il s’il y a 3 lions?

La même chose que pour 2 lions !

T’en es sûr ? Je vais reformuler ma question. Est-ce que le cas à 3 lions peut se réduire au cas à 2 lions ?

Euh… Oui ! J’ai trouvé ! Si un lion va manger le zèbre, alors il devient une sorte de zèbre lui-même !

Eating Lion Becomes sort of the Zebra

Bravo ! Voilà qui permet de ramener le cas à 3 lions au cas à 2 lions ! Rappelons que dans ce cas à 2 lions, aucun lion ne va manger le zèbre, et donc, quand il y a 3 lions, le lion qui va manger le zèbre peut le manger en toute sécurité !

Et du coup, chaque lion a intérêt à aller manger le zèbre dans le cas à 3 lions !

Exactement ! Et maintenant, que se passe-t-il dans le cas à 4 lions ?

Si un lion mange le zèbre, alors il devient le zèbre entouré de 3 lions… et donc va se faire bouffer. Donc, aucun lion ne va manger le zèbre… c’est ça ?

T’as tout compris ! Donc, si je récapitule, avec 1 lion, le zèbre se fait manger. Avec 2 lions, il ne se fait pas manger. Avec 3 lions, il se fait manger. Avec 4 lions, il ne se fait pas manger. Tu vois ce qu’il se passe ?

Je crois, oui. S’il y a un nombre pair de lions, le zèbre ne se fait pas manger. Et sinon, il se fait manger… c’est ça ?

Ben, il reste à prouver cette proposition. On a l’intuition, on peut donc passer à la preuve ! Et on va la faire par récurrence.

On a prouvé les cas simples. Donc j’imagine qu’il ne reste plus qu’à prouver l’hérédité…

Yep. Donc supposons que ta proposition est vraie pour $n-1$ lions (c’est notre hypothèse de récurrence), et prouvons-la pour $n$ lions. Bien sûr, on va distinguer deux cas, en fonction de si $n$ est pair ou impair.

Bien sûr ! Commençons par le cas où $n$ est pair !

OK. Si $n$ est pair et si un lion va bouffer le zèbre, alors il devient un zèbre entouré de $n-1$ lions. Mais si $n-1$ est impair, alors, d’après l’hypothèse de récurrence, notre lion qui est devenu zèbre va se faire bouffer. Donc, si $n$ est pair, un lion qui va bouffer le zèbre se fait bouffer. Du coup, le zèbre ne se fait pas bouffer !

OK, et si $n$ est impair…

Si un lion va bouffer le zèbre, il devient alors zèbre et est entouré de $n-1$ lions. Mais, comme $n-1$ est alors pair, il va être en sécurité. Du coup, quand $n$ est impair, les lions ont tout intérêt à aller bouffer le zèbre. Et voilà ! On a prouvé que le cas à $n$ lions se déduisait du cas à $n-1$ lions! L’hérédité a été prouvée.

Yoohoo! Et donc ça marche ! On l’a prouvé : un lion mange le zèbre si et seulement s’il y a un nombre impair de lions !

Félicitations ! Problème résolu. On peut donc passer à un problème plus dur…

Passons aux moines

Dans un monastère, 666 moines super intelligents se rassemblent une fois par jour pour la prière. Ils peuvent alors tous voir les uns les autres, mais la religion leur interdit toute communication, que ce soit orale, écrite ou gestuelle. Le monastère interdit aussi formellement les miroirs. Un matin, une malédiction frappe le monastère. Au moins un moine est touché. Les moines le savent. Les moines frappés par la malédictions ont un point rouge sur leurs fronts, mais ne savent pas qu’ils sont maudits. Dès qu’un moine s’en rend compte, pour le bien de la communauté, il doit se suicider au coucher du soleil. Pendant les 7 premiers jours, rien ne se passe. Mais le soir du 7ème jour, certains moines se suicident. Pourquoi ?

Pour éviter de spoiler la réponse, voici une photo d’Ayutthaya, en Thaïlande, que j’ai prise. La réponse au problème des moines est données en dessous.

Monks

Alors, problème résolu ?

Bon j’ai essayé la récurrence sur le nombre de moines, mais je n’y arrive pas…

Ce n’est pas avec le nombre de moines qu’il faut faire la récurrence…

J’ai aussi essayé avec le nombre de jours avant le premier suicide mais je n’y arrive pas…!

En fait, il faut faire la récurrence sur le nombre de moines maudits ! Pense au cas le plus simple avec un seul moine maudit.

Euh… j’ai trouvé ! Il ne voit personne de maudit, du coup, il sait que le maudit, c’est lui !

Exactement ! Du coup, il se suicide dès le premier soir. Passons maintenant au cas avec 2 moines maudits. Appelons-les Albert et Bob. Le premier jour, chacun voit un autre maudit. Donc aucun des deux ne commet de suicide. Mais le jour suivant, Albert et Bob découvrent que l’autre ne s’est pas suicidé. Et donc…

chacun sait que l’autre a vu au moins un moine maudit !

Monks on Second Day

Exact ! Albert comprend donc qu’il y a un moine maudit que Bob a vu. Mais Albert ne l’a pas vu, cet autre moine maudit. Il s’agit donc forcément de lui-même ! De façon similaire, Bob comprend que lui aussi est maudit. Et donc…

Le soir du 2ème jour, tous deux se suicident!

Parfaitement ! Et donc. S’il y a 1 moine maudit, il se suicide le premier soir. S’il y en a 2, ils se suicident le deuxième soir. Une proposition de généralisation ?

Ben j’imagine que s’il y a $n$ moines maudits, tous ce suicident le $n^{ième}$ soir… c’est ça ?

Tu sais ce qu’il te reste à faire…

Oui, je sais, il reste à prouver cette proposition. Et comme j’ai fait le cas simple, il ne reste plus qu’à prouver l’hérédité !

Oui. Et donc, supposons que ta proposition soit vraie pour $n-1$ moines, quid de $n$ moines ?

Ah j’ai compris ! S’il y a $n$ moines, chacun des $n$ moines croit qu’il y en a $n-1$. Or, d’après l’hypothèse de récurrence, ces $n-1$ moines devraient se suicider le $(n-1)^{ième}$ soir. Mais comme le $n^{ième}$ midi ils sont encore là, c’est qu’il y a un $n^{ième}$ moine !

Bravo! Et comme chaque moine maudit fait ce même raisonnement, tous se suicident le $n^{ième}$ soir. L’hérédité est prouvée!

Woohoo! Et donc dans ton exemple, il y avait 7 moines maudits!

Bingo.

Finissons par le crayon mystérieusement coloré

Pour finir cet article, je vais vous parler d’un raisonnement très perturbant. Je vais vous montrer par récurrence que tous les crayons sont de la même couleur !

Ben voyons !

Attends ! Écoute la preuve avant de céder à tes préjugés ! D’abord, le cas simple qui initialise la récurrence est évidemment le cas avec un seul crayon. Et, très clairement, s’il est le seul crayon, tous les crayons (c’est-à-dire lui et lui seul) ont sa couleurs.

OK, j’avoue que le cas simple est vrai…

Bien. Passons à l’hérédité. Supposons que j’ai $n$ crayons. J’en mets un de côté. Je n’ai donc plus que $n-1$ crayons. Je peux donc appliquer l’hypothèse de récurrence à ces $n-1$ crayons, qui sont donc tous de la même couleur. Maintenant, je remets un autre crayon de côté, et je reprends celui que j’avais laissé de côté au début. J’ai toujours $n-1$ crayons, et, en utilisant à nouveau l’hypothèse de récurrence, je sais que ces $n-1$ crayons ont la même couleur. Du coup, tous ont la même couleur ! J’ai prouvé l’hérédité !

Oula… je suis perdu…

Tout ceci est illustré dans l’image ci-dessous. Bon, bien sûr, il y a une erreur dans ma preuve par récurrence. Et bien, ton défi, jeune padawan, c’est de trouver l’erreur !

La réponse à ce défi est donnée en dessous de l’image suivante.

Pencils2

Alors ?

Arg… Je ne voix pas ce qui cloche…

En fait, tout marche parfaitement bien pour les grands nombres. En particulier, l’hérédité est vraie pour $n \geq 3$. Mais, parfois en mathématiques, comme pour la Poincaré conjecture, c’est dans les petits nombres que réside la difficulté… Tu vois ce que je veux dire ?

Euh… Oui ! J’ai trouvé ! L’hérédité est fausse pour $n=2$ !

Exactement ! Chaque sous-groupe de $n-1$ crayons a, par hypothèse de récurrence, toujours la même couleur. Mais, pour $n=2$, cette couleur n’est pas nécessairement la même, car les deux sous-groupes de $(n-1)=1$ crayon n’ont aucun crayon en commun ! Ainsi, tous les dominos sont bien alignés et prêts à tomber pour $n \geq 3$ et le premier domino tombe, mais le premier domino ne fait pas tomber le second ! Et du coup, aucun des dominos suivants ne tombe.

Dominoes won't Fall

Résumons

Le raisonnement par récurrence est l’une des plus importantes idées de la logique et des mathématiques. C’est une technique puissante, surtout en mathématiques constructives, et j’espère que je t’ai aidé à voir pourquoi. Elle repose sur deux fondamentaux : le cas simple (ou initialisation) et l’hérédité. Ce principe est aussi au coeur des algorithmes et structures récursifs que j’ai décrits dans mon article sur self-reference.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *