Quinze prisonniers, seize cellules, une porte entre chacune. Le gouverneur promet la liberté s’ils parviennent à se ranger en carré magique. C’est un taquin — et le récit qu’en fait Dudeney est exact jusqu’au dernier détail, y compris le prisonnier boiteux.
L’énoncé, publié à Londres en 1917
Traduit intégralement. Regardez la gravure avant de lire : le prisonnier n° 6, bras écartés, est en train de crier les coups.
À moins de cinquante milles de Cadix se dressait au Moyen Âge un château dont toute trace a disparu depuis des siècles. Entre autres particularités, ce château renfermait un cachot des plus désagréables, divisé en seize cellules communiquant toutes entre elles, comme le montre l’illustration. Or le gouverneur était un joyeux drille, et fort amateur de casse-tête. Il descendit un jour au cachot et dit aux prisonniers : « Par ma foi ! vous serez tous libérés si vous résolvez ce problème. Vous devez vous disposer dans les seize cellules de manière que les nombres inscrits sur vos dos forment un carré magique, où chaque colonne, chaque rangée et chacune des deux diagonales donnent la même somme. Rappelez-vous seulement ceci : en aucun cas deux d’entre vous ne devront se trouver ensemble dans la même cellule. » L’un des prisonniers, après avoir travaillé au problème deux ou trois jours avec un morceau de craie, se fit fort d’obtenir sa liberté et celle de ses compagnons s’ils voulaient bien suivre ses instructions et passer de cellule en cellule dans l’ordre où il appellerait leurs numéros. Il y réussit et, chose plus remarquable encore, il semble d’après le récit de sa méthode consigné dans l’ancien manuscrit posé devant moi qu’il y parvint en un minimum de coups. On demande au lecteur de montrer quels furent ces coups.
Henry Ernest Dudeney, Amusements in Mathematics, 1917
Ce qu’on lit aujourd’hui
J’ai rejoué sa solution, et le récit est vrai jusqu’au bout. Dudeney donne la suite des coups, puis raconte : le prisonnier astucieux était le n° 6, celui qui lève les bras sur la gravure ; lui et le n° 10 ont fait le plus gros du travail, changeant de cellule cinq fois chacun ; et le n° 12, l’homme à la jambe torse, était boiteux, « et n’eut donc heureusement qu’à passer dans la cellule voisine quand son tour vint ». Tout est exact, et l’exactitude va jusqu’au choix des mots. Les coups sont légaux, le carré final est magique, les nos 6 et 10 se déplacent cinq fois chacun, et le boiteux se déplace exactement une fois. Dudeney écrit que les prisonniers 4, 8, 13 et 14 « sont laissés dans leurs cellules d’origine » : c’est vrai de la position finale, et il se garde bien de dire qu’ils n’ont pas bougé — le n° 14 sort de chez lui au deuxième coup et y revient au dix-septième. Trois hommes seulement ne bougent jamais. La mise en scène n’est pas un décor : c’est une description.
Et il retire discrètement sa promesse. L’énoncé affirme que le prisonnier y parvint « en un minimum de coups ». Le corrigé, lui, dit seulement que cette position « peut être atteinte en aussi peu que trente-sept coups », et concède qu’il faut « une étude et une expérience considérables » pour s’y retrouver. Entre la question et la réponse, « le minimum » est devenu « aussi peu que ». Personne, à ma connaissance, n’a démontré depuis que trente-sept soit optimal — et la borne la plus simple, celle des distances à parcourir, n’exige que vingt et un coups. Il reste donc de la place.
Ce que le problème demande vraiment
C’est un taquin, et vous en avez tenu un dans les mains. Quinze pièces numérotées, une case vide, et l’on ne peut faire glisser qu’une pièce voisine de ce trou. La seule différence avec le jouet de votre enfance, c’est le but : au lieu de remettre les nombres dans l’ordre, il faut les disposer en carré magique.
La cellule vide compte pour zéro. Sans quoi « carré magique » n’aurait pas de sens avec quinze nombres dans seize cases. La somme commune est alors imposée : les nombres de 0 à 15 totalisent 120, qu’il faut répartir en quatre rangées — vous avez le total de chaque ligne sans avoir rien cherché. C’est le genre de calcul qu’il faut faire avant de déplacer le premier prisonnier.
Et toutes les dispositions ne sont pas atteignables — Dudeney le sait et l’écrit : « beaucoup d’entre elles, nous le savons, ne peuvent absolument pas être atteintes ». C’est la vieille histoire du taquin : la moitié exactement des arrangements est hors d’atteinte, quel que soit le nombre de coups, et aucun acharnement n’y changera rien. Le prisonnier ne cherche donc pas un carré magique : il cherche un carré magique de la bonne moitié, et ce n’est pas la même quête.
Ce que ce problème fait travailler
Le raisonnement à rebours, que Dudeney recommande en toutes lettres : « il faut d’abord attraper son carré, puis remonter jusqu’à la position de départ ». Chercher depuis le but plutôt que depuis le début est un réflexe qui sert partout — dans un labyrinthe, dans une démonstration, dans une partie d’échecs — et qu’on n’enseigne presque jamais.
Ensuite les invariants, sous leur forme la plus célèbre : la parité du taquin, qui interdit la moitié des positions et qui a fait la fortune de bien des farceurs au XIXe siècle. Savoir qu’une chose est impossible avant d’avoir essayé, c’est ce que cette série raconte depuis le début, et c’est ici à portée de collège.
Et enfin une question d’optimisation honnête : trouver une solution est à la portée de tout le monde avec de la patience — Dudeney note que beaucoup de lecteurs y mettront « de soixante à cent coups ». En trouver une courte est autrement difficile ; prouver qu’on ne peut pas faire mieux l’est encore davantage, et personne ne l’a fait.
À vous
- trouvez une suite de coups qui range les prisonniers en carré magique. Comptez-les honnêtement.
- Dudeney y arrive en trente-sept. Faites-vous mieux ?
- et la vraie question, ouverte : trente-sept est-il vraiment le minimum ?
Un taquin de brocante ou seize petits papiers suffisent. En commentaire — et si quelqu’un descend à moins de trente-sept, ce sera une première depuis 1917.
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, THE SIX FROGS, 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, THE POTATO PUZZLE, THE ECCENTRIC CHEESEMONGER, THE CLUB CLOCK, THE TWELVE MINCE-PIES, THE ARTILLERYMEN’S DILEMMA, PAPA’S PUZZLE.
Problème n° 403 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.