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 l'on 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-ildes 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,