Mathematical Sciences Seminar - Puzzle Groups
When:
—
Venue:
Birkbeck Main Building, Malet Street
No booking required
The ‘15 puzzle’ is a sliding puzzle that consists of a frame of square tiles in random order with one tile missing (the ‘hole’), and where the aim is to obtain an ordered arrangement through an appropriate sequence of moves. Since the distance between tiles is the taxicab metric, a sequence of moves which leaves the hole in a fixed position induces an even permutation on the tiles. Thus the group of all such sequences (where composition is given by concatenation) is isomorphic to the alternating group A15.
Various generalisations of the 15-puzzle have already been studied. For example, Wilson (1974) considers an analogue for finite connected and non-separable graphs. More recently, Conway introduced a version of the puzzle which is played with counters on 12 of the 13 points in the finite projective plane P3. The 13th point h (called the hole) may be interchanged with a counter on any other point p, provided the two counters on the unique line containing h and p are also interchanged. It turns out that the group of move sequences which fix the hole is isomorphic to the Mathieu group M12.
In this talk, we extend Conway’s game to arbitrary simple 2-(n,4,λ) designs with the property that two lines intersect in at most two points. The group of move sequences which fix the hole is called the puzzle group for the design.
Results include a complete classification of puzzle groups when λ < 3 and a determination of designs with trivial puzzle group. We also prove that there exist infinitely many puzzle groups which are primitive but not alternating or symmetric groups and that the same statement fails if one fixes λ and allows n to vary.
Contact name:
Department of Economics, Mathematics and Statistics