Séminaire des Doctorants et Doctorantes

Jeu de taquin

by Uran Meha

435 (ENS)




The Jeu de taquin, also known as the 15-puzzle, is a puzzle introduced by Sam Loyd in the 1870s. The objective of the puzzle is to obtain the numbers 1 to 15 in the correct ordering, by performing moves which ’slide’ a neighboring number into the empty space. Considering the starting position as a permutation in S 16 , including the empty space as the 16th element, we show that the puzzle is solvable if and only if the corresponding permutation restricts (in some sense) to an even permutation in the alternating group A 15. We also present a graph theoretic generalization of the 15-puzzle. Finally we show how the idea behind the ’sliding moves’ in the 15-puzzle gives rise to an equivalence relation in the set of skew-symmetric standard Young tableaux. These are objects that play an important role in algebraic combinatorics, and especially find use in the representation theory of Lie algebras and algebraic groups.