Le défi de Sam Loyd : 1000 dollars pour un puzzle impossible
En 1880, les États-Unis sont pris d’une fièvre étrange. Dans les trains, les bureaux et les salons, des millions d’Américains s’acharnent sur un petit puzzle à glissière de 15 pièces. Un homme prétend offrir 1 000 dollars - une fortune à l’époque - à quiconque résoudra une configuration particulière. Cet homme, c’est Sam Loyd, le plus célèbre créateur de puzzles de son siècle. Et son défi est une arnaque géniale, car la solution n’existe tout simplement pas.
Sam Loyd : le roi des casse-tête
Samuel Loyd, né en 1841 à Philadelphie, était un personnage hors norme. Joueur d’échecs prodige dès l’adolescence, il s’est rapidement tourné vers la création de puzzles mathématiques et logiques. Ses colonnes de casse-tête, publiées dans les journaux américains, étaient lues par des millions de personnes. Il avait un talent unique pour transformer des problèmes mathématiques abstraits en défis populaires accessibles à tous.
Mais Loyd était aussi un formidable bonimenteur. Il s’attribuait volontiers l’invention de puzzles qu’il n’avait pas créés, et le taquin en est l’exemple le plus flagrant. Si l’on en croit les historiens, le puzzle à glissière existait avant lui - probablement inventé par Noyes Palmer Chapman vers 1874. Mais c’est Loyd qui l’a rendu célèbre, et c’est son nom qui reste associé à la grande histoire du taquin.
Le puzzle 14-15 : une configuration diabolique
Le taquin classique comporte 15 pièces numérotées de 1 à 15, disposées dans une grille 4×4 avec une case vide. L’objectif est de remettre les pièces dans l’ordre, de 1 à 15, en les faisant glisser dans l’espace libre. La plupart des configurations de départ sont résolubles avec suffisamment de patience et de méthode.
Le défi de Sam Loyd était spécifique : il présentait un taquin où toutes les pièces étaient dans l’ordre, sauf les pièces 14 et 15 qui étaient inversées. La case vide se trouvait en bas à droite, exactement comme dans la position résolue. Il fallait simplement échanger les positions de ces deux pièces pour atteindre la configuration parfaite. Cela semblait dérisoire. Des millions de personnes ont essayé. Personne n’a jamais réussi.
La folie du taquin en 1880
L’ampleur du phénomène est difficile à imaginer aujourd’hui. Les journaux de l’époque rapportent que des employés étaient surpris à jouer pendant les heures de travail. Des entreprises interdisaient le puzzle dans leurs locaux. Le New York Times publiait régulièrement des articles sur cette « manie du taquin » qui paralysait le pays. On raconte même que des parlementaires français s’y adonnaient en pleine séance - la fièvre avait traversé l’Atlantique.
L’offre de 1 000 dollars était un coup de génie marketing. À une époque où le salaire moyen annuel américain tournait autour de 400 dollars, cette somme représentait près de trois ans de revenus. Loyd savait parfaitement que personne ne pourrait jamais réclamer la récompense. Son offre n’était pas un pari : c’était une publicité gratuite et inusable.
Pourquoi c’est mathématiquement impossible
La clé de l’impossibilité du puzzle 14-15 repose sur un concept mathématique élégant : la parité des permutations. Pour comprendre, il faut d’abord saisir ce qu’est une permutation. Quand les 15 pièces sont disposées dans un certain ordre, cet arrangement constitue une permutation de la séquence (1, 2, 3, …, 15).
Chaque permutation peut être décomposée en une série de transpositions - des échanges de deux éléments. Par exemple, pour passer de (1, 3, 2) à (1, 2, 3), il suffit d’une transposition (échanger 2 et 3). Le point crucial est le suivant : une permutation nécessite toujours un nombre pair ou toujours un nombre impair de transpositions. On parle de permutation paire ou impaire. Cette propriété est invariante - elle ne change jamais, quelle que soit la façon dont on décompose la permutation.
La preuve de parité
Dans le taquin, chaque mouvement consiste à glisser une pièce dans la case vide. Ce mouvement équivaut à une transposition entre la pièce déplacée et la case vide. Mais il y a une subtilité : la case vide doit revenir à sa position d’origine pour que le puzzle soit résolu (en bas à droite). Or, pour que la case vide fasse un aller-retour complet, elle doit effectuer un nombre pair de mouvements.
Cela signifie que le nombre total de transpositions est pair. Autrement dit, seules les permutations paires des 15 pièces sont atteignables depuis la position résolue. Et voici le coup de grâce : l’échange des pièces 14 et 15 (toutes les autres restant en place) est une permutation impaire - c’est une seule transposition. Il est donc mathématiquement impossible d’atteindre cette configuration par des mouvements légaux du taquin. Comme l’explore notre article sur les configurations insolubles du taquin, exactement la moitié de toutes les configurations possibles sont inaccessibles.
Cette preuve, formalisée par les mathématiciens William Edward Story et William Woolsey Johnson dès 1879, est l’une des plus élégantes applications de la théorie des groupes à un problème concret. Elle montre que les 16 !/2 = 10 461 394 944 000 configurations accessibles ne représentent que la moitié de toutes les dispositions possibles des pièces.
Un génie du buzz avant l’heure
Ce qui rend l’histoire de Sam Loyd si remarquable, c’est sa modernité. Plus d’un siècle avant les réseaux sociaux, il avait compris les mécanismes de la viralité. Le défi 14-15 réunissait tous les ingrédients : un problème en apparence simple (il suffit d’échanger deux pièces !), une récompense alléchante, et l’impossibilité secrète de la solution qui garantissait que le défi ne s’épuiserait jamais.
Loyd a également exploité un biais cognitif puissant : le biais d’optimisme. Chaque joueur était convaincu qu’il était sur le point de trouver la solution. Les pièces 14 et 15 semblaient si proches de leur position finale que le cerveau refusait d’accepter l’impossibilité. « Encore un essai », se disait-on. Et encore un autre. Et encore un autre.
L’héritage mathématique
Au-delà de l’anecdote, le défi de Sam Loyd a eu un impact durable sur les mathématiques du taquin. Il a stimulé les recherches sur la théorie des groupes de permutations et a inspiré des générations de mathématiciens à s’intéresser aux puzzles combinatoires. Le concept de parité qui rend le puzzle 14-15 impossible se retrouve dans d’innombrables problèmes modernes, de la cryptographie à la théorie du codage.
Le taquin est devenu un problème classique en informatique théorique. La question « une configuration donnée est-elle résoluble ? » peut être tranchée en un instant grâce à un algorithme simple de comptage d’inversions. Mais la question « quel est le nombre minimal de coups pour la résoudre ? » est un problème NP-difficile pour les grilles de taille arbitraire - l’un des problèmes les plus ardus de l’informatique.
Une leçon intemporelle
L’histoire du défi de Sam Loyd nous enseigne plusieurs choses. D’abord, que l’apparente simplicité d’un problème peut dissimuler une impossibilité profonde. Ensuite, que les mathématiques sont le seul outil capable de trancher définitivement entre le difficile et l’impossible. Des millions de personnes auraient pu s’acharner éternellement sur le puzzle 14-15 ; il a fallu un théorème pour prouver que leur quête était vaine.
Enfin, cette histoire montre que les puzzles ne sont jamais de simples divertissements. Derrière chaque taquin que vous résolvez se cachent des structures mathématiques profondes - des groupes, des permutations, des invariants - qui régissent silencieusement ce qui est possible et ce qui ne l’est pas. Et peut-être que c’est cela, le véritable héritage de Sam Loyd : avoir montré à des millions de personnes, sans qu’elles le sachent, la beauté implacable des mathématiques.