Le saute-mouton de Conway
Vous vous souvenez sûrement du célèbre saute-mouton, jeu que je n'ai jamais vraiment compris. Est-ce que les moutons sont connus pour sauter sur eux-mêmes ? Ça saute même, un mouton ?
Après vérification, il semblerait que ce soient les bergers qui sautaient sur les moutons, mais ça reste incertain.
Bref, restons sur l'idée que les moutons sautent sur les moutons, et essayent d'avancer en groupe. Et disons qu'un mouton sauté sort du jeu. Ainsi chaque mouton peut sauter un nombre infini de fois, mais ne pourra être sauté qu'une fois avant de ne plus pouvoir agir.
Dans ce cadre, jusqu'où pensez-vous qu'un troupeau donné peut aller ? C'est la problématique que pose Conway dans son célèbre problème « Conway's Soldiers ». Les soldats sont ici nos moutons, qui vont avancer dans une grille à deux dimensions, similaire à un échiquier géant. Chacun des soldats peut aller à droite, à gauche, en haut ou en bas, seulement s'il a un soldat sur qui sauter.
Essayez par vous-mêmes avec ces quelques soldats :
Vous voyez rapidement que leurs mouvements seront limités, car au fur et à mesure qu'on les saute, les soldats disparaissent. Il est donc assez évident que la distance maximale que l'on pourrait atteindre est assez faible. Mais qu'en est-il si nous avions une infinité de soldats ? Pourrions-nous aller suffisamment loin ? Est-ce que cette gigantesque armée de soldats moutons pourrait s'organiser d'une telle manière qu'on puisse arriver à n'importe quelle distance ? Si oui, comment ? Si non, quelle distance maximale pourrions-nous parcourir, et comment montrer que c'est impossible de faire plus ?
Pour les organiser, mettons-les derrière notre ligne de départ. Nous compterons la distance parcourue comme la position verticale la plus éloignée de cette dernière.
Essayez par vous-mêmes avec cette quasi-infinité de soldats. Jusqu'où arrivez-vous ?
Arrivés là, vous avez peut-être une intuition qui vous fait penser à une réponse plutôt qu'à une autre. Donc avant de voir la résolution d'un tel problème, c'est l'heure de la conjecture. Que pensez-vous qu'il soit possible de faire ?
Jusqu'où le troupeau peut-il aller ?
Les jeux sont faits.
Si vous pensiez que les moutons allaient gambader aussi loin qu'ils le désiraient, la suite vous étonnera. À l'inverse, si vous aviez l'intuition que les moutons allaient rester confinés, comment l'auriez-vous prouvé ?
On se rend rapidement compte qu'il est trivial d'aller à 1, facile d'aller à 2, simple d'aller à 3, mais déjà beaucoup plus dur d'aller à 4. Qu'en serait-il de 5, 6 ou 7 ? Et qu'est-ce qui ferait qu'un chiffre apparaîtrait plus qu'un autre dans ce problème ?
Dans ce genre de problème, il est très commun d'essayer de chercher ce qu'on appelle un invariant. Une quantité qui, malgré toutes les opérations que l'on fait, ne variera pas. Par exemple, le nombre de soldats (en prenant un cas fini) n'est pas invariant, car chaque déplacement nous enlève un soldat. Cependant ici, on se rend compte que le nombre n'est pas le seul problème, mais aussi la position. Avoir beaucoup de soldats, c'est bien. Mais l'apparente infinité de soldats dont on dispose se situe de plus en plus loin de notre région de départ, ce qui coûtera un nombre de plus en plus important de soldats pour les acheminer jusqu'ici.
On trouve souvent dans les explications ou solutions de ce problème une formule tombant un peu du ciel, et qui, « comme par magie », fonctionne bien. Je vais essayer le plus possible dans la suite de vous expliquer l'intuition et l'émergence de cet invariant.
Tout d'abord, introduisons rapidement ce qu'est la distance de Manhattan. Vous êtes dans Manhattan, entre la 3rd Street et la 5th Avenue. Vous voulez aller un peu plus loin, à la 7th Street et la 6th Avenue. Évidemment, la distance « à vol d'oiseau » n'a ici pas vraiment d'intérêt, car vous savez que vous devez respecter le tracé des buildings qui quadrillent le quartier. Ainsi, vous devez faire 1 bloc à droite, et 4 blocs vers le haut.
On dira que la distance de Manhattan entre ces deux points est de 4 + 1 = 5, car c'est le nombre de « pas » que vous avez faits pour vous rendre du point A au point B.
Au vu de notre quadrillage, cette distance va être intéressante, car elle va représenter le nombre de pas effectifs qu'un soldat va devoir faire pour aller d'un point à un autre. Sans perte de généralité, prenons un soldat à la ligne de départ, et ce sera notre 0, notre référence. Tous les autres points commencent à une distance $d$ (comprise entre 0 et l'infini) de ce point. Ici, on pourra avoir une distance verticale négative, car le but est d'arriver le plus haut possible : notre centre est le point d'origine, et dans la direction verticale, on numérote vers le bas ($d$ diminue plus on monte).
Comme on l'a dit, ce n'est pas seulement le nombre, mais la position des soldats qui sera intéressante à analyser. Comment évolue-t-elle quand on les déplace ?
Si on devait avoir une quantité qui ne dépendait que de la position de notre soldat, qu'on appellerait $f(d)$, on voit qu'en avançant vers le haut, si on veut la conservation de cette quantité, on aurait (pour les pions qui sont sous la ligne de départ) :
Note de côté : quand on fait un coup de côté ou un coup en bas, cette relation ne tient pas. En toute généralité, on veut surtout que la somme ne puisse jamais augmenter : $\forall d \in \mathbb{N}^*,\ f(d-1) \leq f(d) + f(d+1)$.
Ce qui vous fait sûrement penser à (roulement de tambour) : notre ami Fibonacci !
La suite de Fibonacci, dont vous avez sûrement déjà entendu parler, se caractérise par :
Cette suite somme les deux derniers termes pour trouver le suivant, ainsi elle donne :
On comprend que la suite qui pourrait nous aider à trouver notre invariant est un petit peu différente, mais elles se ressemblent ! Plus formellement, ces suites tombent dans la catégorie plus générale des suites récurrentes linéaires d'ordre 2. Par chance, quand les coefficients sont constants, la formule générale est souvent de la forme $u_n = A r_1^n + B r_2^n$. Sans rentrer trop dans les détails, on comprend qu'on peut essayer quelque chose de la forme $\phi^n$ (vous me voyez arriver avec la formule tombée du ciel ?).
Ainsi notre relation nous donnerait :
Ou en simplifiant :
C'est donc un joli polynôme du second degré, dont il faut trouver la racine !
On trouve facilement que $\phi$ doit être égal à $\frac{-1 \pm \sqrt{5}}{2}$, et nous prendrons $\frac{\sqrt{5}-1}{2}$ pour que la valeur soit positive. En réalité, la valeur nous intéresse peu (pour l'instant). Ce qui nous intéresse, c'est le fait qu'avec ce $\phi$, la relation $\phi^{d+1} + \phi^{d} = \phi^{d-1}$ est toujours vraie.
Ainsi, si on associe à chacun de nos soldats cette valeur en fonction de la distance à laquelle il est de notre centre, on peut essayer de sommer la valeur totale de notre armée ! On s'attelle au calcul :
Or :
Et :
Ainsi :
Intéressant ! On voit le chiffre 5 arriver, et c'est central !
Car si un pion atteint la case 5 au-dessus de notre origine, il aura à lui tout seul la valeur $1/\phi^5$ !! Ainsi, il ne pourrait y avoir qu'un seul soldat, à cette case, et aucun autre, car sinon cela signifierait que notre invariant (la somme des poids de nos soldats, où qu'ils soient), qui n'était censé pouvoir que diminuer ou se conserver, aurait augmenté ! Comme c'est impossible par construction, il est impossible qu'un pion soit sur la ligne 5* !
* Du moins en un nombre fini de coups. Il est techniquement possible de construire une solution avec des « positions limites », mais cela sort du cadre du problème tel que posé.
Nous avons notre réponse ! Bien que très amusante, cette manière de se déplacer reste coûteuse et contraignante : on ne peut pas partir bien loin !
Si le lecteur est intéressé, il peut essayer d'arriver à la ligne 4, puis se demander combien de soldats, au minimum, il lui faudrait pour y arriver !