LE TAQUIN COMPLET

On peut considérer le jeu du taquin d'une autre manière; on suppose le taquin complètement couvert, et le joueur a la faculté d'enlever à son choix un cube quelconque, puis de jouer suivant la marche ordinaire et de replacer, à la fin de la partie, le cube enlevé sur la case vide. Il s'agit de choisir le cube à enlever de telle sorte que Ton puisse arriver à une position finale convenue.

Pour résoudre ce nouveau problème, on trace dans la position finale convenue un chemin, de manière à obtenir la suite naturelle des nombres; on trace le même chemin dans la position initiale, et l'on détermine le nombre des inversions de la permutation correspondante. Si la permutation est de première classe^ il faut

Le jeu du taquin. 219

enlever un cube d'écart pair, et, si la permutation est de seconde classe, il faut enlever un cube d'écart impair.

Il y a ainsi lieu de se demander si le problème est toujours possible ; en d'autres termes, existe-t-il des positions initiales pour lesquelles tous les cubes aient des écarts de même parité? Nous allons faire voir qu'il peut y avoir toujours possibilité ou toujours impossibilité pour tout cube choisi dans la permutation initiale. En effet, la position finale, disposée suivant l'ordre naturel, ne contient que des écarts nuls ; donc, si l'on exécute un nombre quelconque N d'échanges entre des cubes de même parité, tous les écarts resteront pairs, et il n'y aura aucun écart impair; par conséquent, si N est impair, la permutation considérée après les N échanges est de seconde classe; par suite, quel que soit le cube enlevé, la permutation reste de seconde classe et ne peut être ramenée à la position finale; il y a donc impossibilité pour un cube quelconque.

Dans le cas contraire, si N est pair, la permutation considérée après les N échanges est de première classe, comme la position finale; il y a donc possibilité pour un cube quelconque.

Lorsque le nombre total des cubes est pair, il existe une seconde série de positions initiales pour lesquelles il y a encore possibilité ou impossibilité complète. En effet, reprenons la permutation naturelle des n premiers nombres, échangeons chaque cube de numéro impair, avec le cube de numéro pair qui le suit; tous les écarts deviendront impairs; faisons ensuite un nombre quelconque d'échanges entre les cubes de même parité, nous obtiendrons alternativement des permutations de première et de seconde classe; les premières donnent l'impossibilité complète, et les dernières donnent la possibilité complète.

Huitième récréation. — Le jeu du taquin.

Lorsque le nombre total des cubes est impair, il existe toujours nécessairement un cube d'écart pair; alors les positions de la deuxième série comportent une seule exception, pour ce cube.

Remarque. — Les ingénieuses théories du Taquin continental et du Taquin complet sont dues, pour la plus grande partie, à M. Hermary,