Le taquin

Des pièces numérotées à remettre en ordre en les faisant glisser, sur un plateau de 2 à 5 lignes et colonnes. Une position sur deux est sans solution : la signature d'une permutation l'explique.

Le plateau a de $2$ à $5$ lignes et de $2$ à $5$ colonnes. On fait glisser vers la case vide une pièce voisine, à la souris, au doigt ou avec les flèches du clavier, pour retrouver la position rangée, case vide en bas à droite. Un bouton mélange par des coups permis, un autre échange les pièces $1$ et $2$. Jusqu'à neuf cases, la page indique le nombre minimal de coups restants et peut en jouer un.

Ce que cela signifie : une position est une permutation des cases, la case vide comptant pour une pièce. Un coup est une transposition, qui change la signature en son opposée, et il change de $1$ la distance $d$ de la case vide au coin en bas à droite. Le produit de la signature par $(-1)^d$ est donc invariant ; il vaut $+1$ dans la position rangée. Échanger deux pièces le fait passer à $-1$ : la position obtenue ne peut pas être rangée. Réciproquement, dès qu'il y a au moins deux lignes et deux colonnes, toute position de produit $+1$ peut l'être : exactement la moitié des positions sont solubles, soit $181\,440$ sur $362\,880$ pour le jeu de $3$ sur $3$, ce que la page vérifie par un parcours complet ; le cas général est admis.

Le piège le plus courant est de juger une position à l'œil : celle qui ne diffère de la position rangée que par deux pièces échangées paraît presque résolue, et elle n'a aucune solution.