Six grenouilles numérotées sur une bande de sept cases, une seule case libre. Il faut renverser leur ordre. Ce n’est pas difficile — et ce n’est pas la vraie question.
L’énoncé, publié à Londres en 1917
Traduit intégralement. Lisez-le jusqu’au bout : la dernière moitié ne ressemble à aucun énoncé de casse-tête.
Les six grenouilles savantes de l’illustration sont dressées à renverser leur ordre, de sorte que leurs numéros se lisent 6, 5, 4, 3, 2, 1, la case vide restant à la place qu’elle occupe. Elles peuvent sauter sur la case voisine (si elle est libre) ou franchir une grenouille pour se poser sur la case d’après (si elle est libre), tout comme on se déplace au jeu de dames, et cela en avant comme en arrière, à leur gré. Saurez-vous montrer comment elles accomplissent leur tour en aussi peu de coups que possible ? C’est assez facile ; aussi, quand vous y serez parvenu, ajoutez une septième grenouille à droite et recommencez. Ajoutez ensuite d’autres grenouilles, jusqu’à ce que vous soyez capable de donner la solution la plus courte pour un nombre quelconque. Car cela se fait toujours, avec cette unique case libre, quel que soit le nombre de grenouilles.
Henry Ernest Dudeney, Amusements in Mathematics, 1917
Ce qu’on lit aujourd’hui
L’énoncé contient son propre prolongement, et c’est très rare. Un casse-tête pose une question et s’arrête. Celui-ci dit : faites-le à six, puis à sept, puis continuez « jusqu’à ce que vous soyez capable de donner la solution la plus courte pour un nombre quelconque ». Dudeney ne demande pas une réponse, il demande une règle — c’est-à-dire qu’il demande à son lecteur du Strand Magazine de faire de la recherche. Et dans sa solution, il en donne une. Sur 430 problèmes, on compte sur les doigts d’une main ceux qui vont jusque-là.
Pour le reste, tout est affaire de mise en scène. Trois problèmes du livre mettent en scène des grenouilles — une petite troupe récurrente, comme un numéro de music-hall — et le mécanisme emprunté est celui du jeu de dames, que tout lecteur de 1917 pratiquait. Un objet mathématique nu n’intéresse personne ; habillé en grenouilles savantes sur une planche de sept cases, il fait vendre un magazine. C’est tout le métier du chroniqueur, et il n’a pas pris une ride.
Ce que le problème demande vraiment
Relisez les règles, elles sont plus étroites qu’on ne croit. Une grenouille glisse d’une case, ou en franchit une seule — jamais deux. Elle va dans les deux sens. Et surtout : la case vide doit se retrouver là où elle était. Cette dernière condition passe inaperçue à la première lecture, et c’est elle qui rend le compte final ce qu’il est.
Trouver une solution ne suffit pas. Une suite de k coups prouve qu’on peut y arriver en k coups au plus. Rien de plus. Pour affirmer que c’est le minimum, il faut un argument qui interdise de faire mieux — et il en existe un, tout simple : comptez le chemin. Chaque grenouille doit rejoindre la place symétrique de la sienne, ce qui représente une distance totale connue d’avance ; or une glissade ne déplace une grenouille que d’une case, un saut de deux. De là sort une borne. C’est ainsi qu’on démontre un minimum, et non en essayant très fort.
Puis il faut monter l’escalier. Une solution, c’est la première marche. La plus courte solution, la deuxième. La règle valable pour n grenouilles, la troisième — et c’est celle que Dudeney vous demande explicitement de gravir. Peu de gens font les trois.
Ce que ce problème fait travailler
La méthode, ici, est un réflexe de chercheur qu’on n’enseigne presque jamais : quand le cas qu’on vous donne résiste, faites-en un plus petit. Deux grenouilles, puis trois, puis quatre. Notez les nombres obtenus, alignez-les, regardez-les. La suite qui apparaît en dit plus long que six heures d’acharnement sur le cas à six. Descendre avant de monter, c’est presque toute la méthode.
Ensuite, la mécanique du taquin : une seule case libre, et tout le mouvement du plateau qui doit passer par elle. C’est la même contrainte que dans le cavalier taquin, et la même famille que le jeu de saute-mouton, dont le blog a déjà montré qu’il menait tout droit à l’algorithmique — et dont le site propose une version jouable, tirée de Jeux & Stratégie (1980).
Enfin, c’est un excellent problème de classe : sept cases dessinées à la craie, six jetons numérotés, et l’on cherche à plusieurs. Personne n’a besoin de savoir ce qu’est une permutation pour s’y mettre — et tout le monde en fait, sans le savoir, dès le troisième coup.
À vous
- en combien de coups renversez-vous les six grenouilles ?
- et êtes-vous sûr que c’est le minimum ?
- la question de Dudeney : quelle est la règle, pour n grenouilles ?
En commentaire. Un conseil : commencez à deux, ce n’est pas de la paresse, c’est de la méthode. J’y mettrai mes réponses dans quelques jours, avec le programme qui les confirme jusqu’à neuf grenouilles.
Dans la même série. Rétro Math’s reprend les 430 problèmes d’Amusements in Mathematics (1917) : l’énoncé traduit tel quel, ce qu’on en sait aujourd’hui, et la solution en commentaire. Les autres épisodes en ligne : CHINESE MONEY, CHANGING PLACES, THE STOP-WATCH, MRS. PERKINS’S QUILT, WATER, GAS, AND ELECTRICITY, THE INDUSTRIOUS BOOKWORM, SIR EDWYN DE TUDOR, THE NINE COUNTERS, A CENSUS PUZZLE, THE BARREL PUZZLE, A TRICK WITH DICE, CROSSING THE RIVER AXE, THE MILKMAID PUZZLE, THE TROUBLESOME EIGHT, THE FOUR POSTAGE STAMPS, A CHAIN PUZZLE, THE ROUND TABLE, THE CAB NUMBERS.
Problème n° 214 d’Amusements in Mathematics, de Henry Ernest Dudeney (Londres, 1917). Texte et gravure sont dans le domaine public : Dudeney est mort en 1930. Le livre est intégralement disponible sur Project Gutenberg, et l’énoncé original se lit ici.
Les réponses, comme promis — avec la règle générale, que Dudeney publiait là pour la première fois.
1. Vingt et un coups. Désignons chaque coup par le numéro de la grenouille qui bouge — elle n’a jamais le choix, puisqu’il n’y a qu’une case libre. La suite de Dudeney est :
2, 4, 6, 5, 3, 1, trois fois de suite, puis2, 4, 6. Soit3 × 6 + 3 = 21coups : quinze sauts et six glissades. Rejouée case par case, elle laisse bien les grenouilles dans l’ordre 6, 5, 4, 3, 2, 1 et la case vide à sa place, à gauche.2. Oui, c’est le minimum — et l’argument du chemin n’y suffit pas. Je vous avais suggéré de compter le chemin : les six grenouilles ont dix-huit cases à parcourir en tout, un saut en couvre deux, donc il faut au moins neuf coups. C’est une borne, mais elle est loin du compte, parce que les grenouilles reculent autant qu’elles avancent. Le bon argument est ailleurs : comptez les couples. Pour renverser l’ordre, chaque grenouille doit passer de l’autre côté de chacune des autres ; or une glissade ne fait croiser personne, et un saut fait croiser exactement deux grenouilles. Six grenouilles forment quinze couples : il faut donc au moins quinze sauts, et il n’y en a pas un de trop dans la solution. Restent les glissades, qui servent à ramener la case vide là où il faut : le programme, qui explore toutes les positions, confirme qu’on ne peut pas descendre sous six.
3. La règle, pour n grenouilles. Il y en a deux, selon la parité :
si
nest pair :(n² + n) / 2coups, dontnglissades ;si
nest impair :(n² + 3n) / 2 − 4coups, dont2n − 4glissades ;et dans les deux cas
(n² − n) / 2sauts — le nombre de couples, justement.Ce qui donne, de deux à neuf grenouilles : 3, 5, 10, 16, 21, 31, 36, 50. Le programme les retrouve tous les huit par un parcours exhaustif, et le résultat est le même que la case vide soit à gauche ou à droite.
La recette, pour un nombre pair. Écrivez les numéros pairs en montant, puis les impairs en descendant ; répétez cette série
n/2fois ; terminez par les pairs en montant, une seule fois. Pour quatorze grenouilles, cela fait(2, 4, 6, 8, 10, 12, 14, 13, 11, 9, 7, 5, 3, 1)sept fois, puis2, 4, 6, 8, 10, 12, 14: cent cinq coups. Le cas impair suit le même principe avec une fin plus tortueuse — pour sept grenouilles, trente et un coups.Le détail qui saute aux yeux dans la liste. Les nombres ne montent pas régulièrement : de six à sept grenouilles, dix coups de plus ; de sept à huit, cinq seulement. Une grenouille de plus coûte cher quand elle rend le nombre impair, et presque rien quand elle le rend pair. C’est exactement ce qu’on voit en alignant les petits cas, et c’est pour cela qu’il fallait commencer à deux.
Dudeney termine sa solution par une phrase qu’on ne lit pas souvent dans un recueil de casse-tête : « Cette solution générale complète est publiée ici pour la première fois. » Il avait demandé une règle à ses lecteurs ; il a eu l’honnêteté de donner la sienne.