LES IMPOSSIBILITÉS DE POSITION

Dans chacune des positions initiale et finale, on suppose un cube portant le numéro !{éro dans la case vide; on trace dans la position finale un chemin quelconque passant par toutes les cases,

Le jeu du taquin. 207

et une seule fois par chacune d'elles, en admettant même que ce chemin procède par bonds quelconques ; on trace le même chemin dans la position initiale; on considère les deux permutations formées par la succession des numéros des cubes dans ces deux chemins; de plus, on suppose que les cases du taquin sont alternativement noires et blanches, comme celles de l'échiquier. Gela fait;, on a la proposition suivante :

Théorème V. — Si les cases vides sont de même couleur, il est impossible de passer d'une position initiale à une position finale de classe différente; si les cases vides sont de couleurs différentes, il est impossible de passer d'une position initiale à une position finale de même classe.

En effet, la règle du jeu revient à échanger le cube fictif zéro à chaque coup, avec un autre occupant une case de couleur différente; donc, dans le premier cas, on ne pourra passer d'une position à l'autre que par un nombre pair d'échanges, c'està-dire sans changer la classe delà permutation; dans le second cas, on ne pourra passer d'une position à l'autre que par un nombre impair d'échanges, c'est-à-dire en changeant la classe de la permutation. Ce théorème s'apphqueà un jeu plus général, dans lequel on échangerait le cube fictif ^éro avec un cube placé sur une case de couleur différente.

On peut évidemment supprimer le nombre 0 dans les deux suites, s'il donne lieu dans l'une et l'autre à des écarts de même parité. Dans la pratique, on tracera le chemin de manière que, dans la position finale, il donne la suite naturelle des nombres; on joue ensuite quelques coups sur la position initiale, de manière à amener la case vide à la place correspondante de la position

^^^ Huitième récréation.

finale; alors on peut se dispenser de tenir compte du léro dans les permutations. En effet, il est fcicile de voir que si, dans deux permutations, des termes plus grands ou plus petits que les autres occupent les mêmes rangs, on peut les supprimer sans changer la parité de la différence des nombres de leurs inversions.

Par la considération de Téchiquier, on peut étendre la règle du jeu, en admettant que l'on puisse enlever un numéro d'une case de couleur opposée à la cass vide, pour le placer ensuite sur celle-ci. La théorie reste la même.