Le Taquin de Sam Loyd : la plus célèbre arnaque mathématique de l’histoire
Imaginez qu’on vous propose un défi apparemment simple : remettre en ordre deux pièces d’un puzzle coulissant, avec à la clé une récompense de 1 000 dollars, une somme considérable à la fin du XIXe siècle. Personne n’a jamais touché le prix. Non par manque de talent ou de persévérance, mais parce que la solution n’existait pas. Et l’homme qui a fait la réputation de ce défi, Sam Loyd, n’avait même pas inventé le puzzle. Bienvenue dans l’histoire du défi 14-15.
Sam Loyd, le prince des casse-tête
Samuel Loyd (1841-1911), né à Philadelphie, fut d’abord un compositeur de problèmes d’échecs : il en publiait dès l’adolescence et devint l’un des problémistes les plus connus de son temps. Il se tourna ensuite vers les casse-tête de toutes sortes (rébus, énigmes, puzzles géométriques et mathématiques) qu’il publiait dans la presse américaine. Il avait un vrai talent pour rendre les mathématiques amusantes, et un sens aigu du spectacle.
Ce sens du spectacle allait jusqu’à l’exagération. Loyd s’attribuait volontiers des casse-tête qu’il n’avait pas créés, et le taquin en est l’exemple le plus célèbre.
Le vrai inventeur : Noyes Palmer Chapman
Le puzzle à 15 pièces coulissantes a été conçu dans les années 1870 par Noyes Palmer Chapman, receveur des postes à Canastota, dans l’État de New York. Le jeu circule d’abord de main en main, puis devient une véritable mode aux États-Unis à la fin de 1879 et en 1880, avant de gagner l’Europe. Chapman demanda un brevet en 1880, qui lui fut refusé, son invention étant jugée trop proche d’un brevet antérieur de blocs à faire glisser.
En anglais, on l’appelait le 15 puzzle, le Gem Puzzle ou le Boss Puzzle. En France, il prit le nom de jeu de taquin, de « taquiner », qu’il a gardé. Notre article sur l’histoire du taquin retrace son parcours en détail.
Loyd, lui, n’apparaît pas dans cette naissance. Ce n’est que des années plus tard, à partir des années 1890, qu’il se présenta comme l’inventeur du puzzle, version reprise dans son recueil posthume, la Cyclopedia of Puzzles (1914). Les historiens des casse-tête ont depuis rendu la paternité à Chapman.
Le défi 14-15 : une configuration diabolique
Le défi qui a fait la légende de Loyd est d’une simplicité trompeuse : un taquin 4×4 où toutes les pièces sont dans l’ordre, la case vide en bas à droite comme dans la position résolue, sauf le 14 et le 15, inversés. Il suffit en apparence d’échanger deux pièces voisines, sans soulever aucune pièce du plateau, en utilisant uniquement les glissements autorisés. Loyd y attacha une récompense de 1 000 dollars.
La position avait tout pour accrocher : le but semblait à portée de main, et chaque échec donnait envie d’un nouvel essai. Mais aucune suite de glissements ne peut y arriver, et aucune prouesse n’y changera rien.
Pourquoi le défi est impossible : la parité des permutations
Le secret du défi 14-15 repose sur un concept mathématique élégant : la parité des permutations. Une permutation est un réarrangement d’éléments, et chaque permutation peut être décomposée en une série de transpositions, des échanges de deux éléments. Cette décomposition n’est pas unique, mais le nombre de transpositions est toujours pair ou toujours impair pour une permutation donnée. On dit qu’une permutation est « paire » ou « impaire ».
Dans le taquin, chaque glissement de pièce équivaut à une transposition entre la pièce déplacée et la case vide. Pour que la case vide revienne à sa position initiale (en bas à droite), elle doit avoir fait autant de pas vers la gauche que vers la droite, et autant vers le haut que vers le bas : un nombre pair de coups. La permutation obtenue est donc forcément paire.
Or, échanger uniquement le 14 et le 15 est une seule transposition : une permutation impaire. Il est donc mathématiquement impossible de passer de la position 14-15 à la position résolue par des glissements. La récompense ne risquait rien.
La preuve formelle : Johnson et Story
La démonstration rigoureuse fut publiée dès 1879, en pleine mode du puzzle, par les mathématiciens William Woolsey Johnson et William Edward Story dans l’American Journal of Mathematics. Johnson montra que la moitié des positions ne peuvent jamais être atteintes depuis la position résolue ; Story compléta en prouvant que toutes les autres peuvent l’être. Les positions du taquin se répartissent donc en deux classes de même taille, et le défi 14-15 appartient à la mauvaise.
Sur les 16! (environ 20 900 milliards) façons de disposer les 15 pièces et la case vide, exactement la moitié, soit 10 461 394 944 000 positions, sont atteignables depuis la position résolue, et autant ne le sont pas. C’est l’une des premières applications d’un résultat d’algèbre à un jeu populaire.
Loyd : génie ou escroc ?
Le défi était sans risque pour qui le proposait : quiconque connaissait le résultat de parité savait que la récompense ne serait jamais réclamée. Mais le vrai tour de passe-passe de Loyd est ailleurs. En se présentant pendant des décennies comme l’inventeur du taquin, il a réussi à faire oublier Chapman, au point que son nom reste aujourd’hui encore associé au puzzle dans bien des livres.
On ne peut pourtant pas lui retirer son talent de vulgarisateur. Le défi 14-15, tel qu’il l’a raconté, a fait découvrir à un large public une idée mathématique profonde : certaines choses ne sont pas difficiles, elles sont impossibles, et on peut le prouver.
Ce que le défi 14-15 nous enseigne
Au-delà de l’anecdote historique, le défi contient plusieurs leçons durables :
- L’importance de prouver avant d’essayer : des heures de tentatives n’apprennent rien, alors qu’un raisonnement de quelques lignes tranche la question.
- La notion d’invariant : la parité est une propriété qui ne change jamais, quels que soient les mouvements effectués. Ce concept est fondamental en mathématiques et en informatique.
- Distinguer le difficile de l’impossible : un problème très difficile demande plus d’efforts ; pour un problème impossible, aucune quantité d’efforts ne suffira jamais.
Le taquin est d’ailleurs resté un objet d’étude en informatique. Savoir si une position est soluble se décide en un instant en comptant les inversions. Trouver la solution la plus courte est une autre affaire : pour des grilles de taille quelconque, ce problème est NP-difficile, ce qui signifie qu’aucune méthode rapide n’est connue pour le résoudre en général.
Comment reconnaître un taquin insoluble
Grâce au travail de Johnson et Story, on dispose d’un critère simple. Il suffit de compter les inversions : les paires de pièces où la pièce de plus grand numéro précède celle de plus petit numéro quand on lit le plateau ligne par ligne, en ignorant la case vide.
Pour un taquin 4×4, une configuration est soluble si et seulement si la somme du nombre d’inversions et du numéro de la rangée de la case vide (en comptant depuis le bas, la dernière rangée étant la rangée 1) est impaire. Pour le défi 14-15 : une inversion, case vide sur la rangée 1, somme 2, paire : insoluble. Notre article sur les configurations insolubles du taquin détaille la méthode, avec un exemple pas à pas et la règle des grilles 3×3 et 5×5.
L’héritage d’une arnaque géniale
Près de 150 ans plus tard, le défi 14-15 reste l’un des exemples les plus cités pour illustrer la parité des permutations, et les mathématiques du taquin continuent d’intéresser chercheurs et amateurs. Sam Loyd reste un immense créateur de casse-tête, même si le taquin n’en fait pas partie.
La prochaine fois que vous jouerez à notre Taquin en ligne, souvenez-vous : si deux numéros refusent obstinément de se mettre en place sur un puzzle physique remonté à la main, ce n’est peut-être pas votre faute. Ce sont peut-être les mathématiques qui ont décidé que c’était impossible, et contre elles, même Sam Loyd ne pouvait rien.