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.
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.