Le taquin permet d'illustrer ce qu'on appelle la théorie des invariants. Cela permet de tester les dispositions pour savoir si elles sont « légales » ou non. Introduisons d'abord deux notations. Supposons que le taquin que nous utilisons soit le plus classique, c'est-à-dire quinze morceaux bougeant dans un carré 4x4. Supposons qu'au lieu de représenter un dessin, chaque morceau contient un des nombres de 1 à 15. Nous appelerons position A la position du puzzle dans laquelle les cases se retrouvent ordonnées dans le sens de la lecture : la première ligne contient de gauche à droite 1-2-3-4, la deuxième 5-6-7-8, etc... et la case libre se retrouve tout en bas à droite. A présent, ayant la position A, imaginons que nous ayons interverti les carrés 12 et 15 (qui sont les deux plus proches du carré vide) : nous appelerons le résultat position B.
A présent considérons deux positions quelconques du taquin. Nous dirons que les deux positions sont « autant légales » lorsqu'il est possible de passer de la première à la seconde en n'utilisant que des coups légaux, c'est-à-dire ici en n'effectuant que des déplacements d'une case vers l'emplacement libre. Autrement dit, on s'interdit par exemple de déboîter les pièces du jeu avec une cuillère, comme tant de gens l'ont fait avec leur Rubik's cube ! La relation « être autant légales » entre les positions est ce que les mathématiciens appelent une relation d'équivalence. Cela signifie qu'elle est « réflexive » (toute position est autant légale qu'elle même, en considérant que ne rien faire est un coup légal), qu'elle est aussi « symétrique » (si une position a est autant légale que b, on peut passer de a à b par des mouvements légaux, mais alors les mouvements inverses permettent de passer de b à a, ce dont on déduit que b est autant légale que a), et enfin qu'elle est « transitive » : si a est autant légale que b et si b est autant légale que c, alors il existe une suite de mouvements pour passer de a à b et une autre pour passer de b à c et alors en les faisant suivre, on peut passer de a à c, et a est donc autant légale que c. Pour mieux comprendre, l'égalité entre deux nombres est aussi une relation d'équivalence : tout nombre est égal à lui-même (réflexivité), si a = b alors b = a (symétrie) et si a = b et b = c alors a = c (transitivité).
Les relations d'équivalence servent en mathématiques à classer les éléments d'un ensemble : on définit des « classes » d'objets équivalents. Par exemple dans notre cas, la classe de A est l'ensemble des positions qui sont autant légales que A. La classe de B est l'ensemble des positions qui sont autant légales que B. Bien sûr, si a est dans la classe de b, alors b est aussi dans la classe de a (par symétrie). Et il se peut que la classe de A et la classe de B coïncident. En revanche, on peut montrer (et c'est bien là l'intérêt des relations d'équivalence et des classes) que les classes forment une « partition » des positions du taquin : cela signifie que chaque position possible appartient à une des classes, mais une seule. C'est exactement comme quand vous recouvrez le sol de votre salle de bains avec des carreaux qui ne se chevauchent pas : chaque petit millimètre carré de votre sol est recouvert par un carreau, mais toujours par un seul carreau en même temps. Dès lors, nos considérations précédentes prennent tout leur sens : il existe une classe de positions qui sont toutes légales (il s'agit de la classe qui contient la position du puzzle quand vous l'avez sorti du tiroir), et toutes les autres sont illégales : vous ne parviendrez jamais à les trouver par des mouvements normaux. Autrement dit, il devient mathématiquement possible de déterminer si un problème de taquin est résoluble ou impossible : il « suffit » pour cela de déterminer le nombre de classes différentes, et de trouver un critère qui étant donné n'importe quelle position nous permettrait directement de savoir dans quelle classe elle se trouve. Nous allons donc à présent répondre partiellement à ce problème.

Première remarque : si vous avez bien compris ma méthode de résolution (ici), j'ai en fait démontré par un algorithme qu'à partir d'absolument n'importe quelle position, il est toujours possible d'amener légalement à leurs places les carrés 1,2,3,4,5,6,7,8 (deux premières lignes), 9, 10, 13 et 14 (deux premières colonnes). Il reste alors les carrés 11, 12 et 15 qui se baladent dans les quatre cases du coin bas-droit. Ils peuvent être dans plusieurs dispositions (pour chacune, je donne les carrés dans le sens de la lecture, et X donne l'emplacement vide). Par exemple 11/12/15/X, auquel cas on est en position A, 12/X/11/15, auquel cas en déplaçant le 12 puis le 11 puis le 15 on revient en A, 11/15/12/X qui est la position B, ou 15/X/11/12 où en déplaçant 15, 11 puis 12 on obtient B, etc... Je vous laisse vérifier qu'il y a en fait en tout 24 positions possibles pour ces quatre carrés et qu'à chaque fois on peut revenir à A ou B.
Ce que je viens de démontrer s'exprime donc ici : toute position est autant légale que A ou que B. En bref, il y a donc au plus deux classes pour le taquin : celle de A et celle de B. A ce stade, il reste deux possibilités : soit A est autant légale que B (dans ce cas, toutes les positions du taquin sont autant légales), soit A et B ne sont pas autant légales et on obtient deux classes distinctes. Je stoppe la démonstration ici, car elle utilise des maths de niveau supérieur (notamment la théorie des déterminants), mais je vous donne l'idée globale. Ayant une position du taquin, on peut lister les numéros des cases dans l'ordre de lecture (en oubliant le carré vide). On compte alors le nombre de paires de nombres pour lesquelles le plus petit nombre arrive après le plus grand dans la liste (par exemple pour une liste réduite 1/2/4/3/5, il y a une seule paire inversée : 4 et 3 ; pour 1/2/4/5/3, il y a deux paires inversées : 3 et 4 ainsi que 3 et 5). Ayant ce nombre, on associe à la position du taquin un nombre appelé signature : 1 si le nombre précédent était pair, -1 s'il était impair. Par exemple la signature de 1/2/4/3/5 est -1 tandis que la signature de 1/2/4/5/3 est 1.
Vous pouvez vérifier à la main que la signature de A vaut 1 et que la signature de B vaut -1. C'est alors qu'intervient le plus gros (et le plus délicat) du raisonnement : on montre que lorsque deux positions sont autant légales, alors elles ont la même signature. On en déduit que toutes les positions de la classe de A ont une signature de 1, et toutes les positions de la classe de B ont une signature de -1. Pour cette raison, la signature est ici ce qu'on appelle un « invariant de classe ». Nous avons à présent entièrement répondu au problème :
   - nous savons, comme la signature d'une position ne peut valoir en même temps 1 et -1, qu'il y a bel et bien pour le taquin deux classes distinctes, celle de A et celle de B. Si on considère que A est la position à laquelle le joueur est censé arriver, il y a donc certaines positions de départ qui permettent de résoudre le puzzle, mais aussi certaines positions de départ (celles qui correspondent à B) qui, quoi que vous fassiez de légal, ne vous permettront jamais de retrouver la position A (si vous avez une telle position au départ, le constructeur du jeu a fait une erreur, ou le précédent propriétaire du jeu a utilisé une cuillère).
   - nous disposons de plus d'une méthode déterministe pour différencier les positions : après avoir sorti votre jeu du tiroir, calculez sa signature comme indiqué précédemment ; si vous trouvez 1, le jeu est normal sinon il est impossible.
Voilà donc en gros comment Lloyd a pu être absolument certain que le problème pour lequel il proposait mille dollars ne le ruinerait jamais (Voir l'histoire du jeu). A présent, si vous reprenez mes explications, vous constaterez que tout le raisonnement peut se généraliser à n'importe quel jeu ou casse-tête : la définition d'une relation d'équivalence, la construction des classes, la découverte d'un invariant de classe et de la manière de le calculer. Au final dans cette méthode, la véritable difficulté (et elle peut vraiment être grande, par exemple pour le Rubik's Cube) est de trouver l'invariant et de montrer qu'il est bien invariant pour les classes !

Retour à la méthode de résolution
Retour à l'histoire du jeu