Maths Olympiad Prep

Library / /32 of 43

Algebra Difficulty 8.1 Shortlist Find the answer

Given an integer n>1n>1, let SnS_{n} be the group of permutations of the numbers 1,2,,n1,2, \ldots, n. Two players, A and B, play the following game. Taking turns, they select elements (one element at a time) from the group SnS_{n}. It is forbidden to select an element that has already been selected. The game ends when the selected elements generate the whole group SnS_{n}. The player who made the last move loses the game. The first move is made by A. Which player has a winning strategy?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Player A can win for n=2n=2 (by selecting the identity) and for n=3n=3 (selecting a 3-cycle). We prove that B has a winning strategy for n4n \geq 4. Consider the moment when all permitted moves lose immediately, and let HH be the subgroup generated by the elements selected by the players. Choosing another element from HH would not lose immediately, so all elements of HH must have been selected. Since HH and any other element generate Sn,HS_{n}, H must be a maximal subgroup in SnS_{n}. If H|H| is even, then the next player is A, so B wins. Denote by nin_{i} the order of the subgroup generated by the first ii selected elements; then n1n2n3n_{1}\left|n_{2}\right| n_{3} \mid \ldots We show that B can achieve that n2n_{2} is even and n2<n!n_{2}<n!; then H|H| will be even and A will be forced to make the final - losing - move. Denote by gg the element chosen by A on his first move. If the order n1n_{1} of gg is even, then B may choose the identical permutation idid and he will have n2=n1n_{2}=n_{1} even and n2=n1<nn_{2}=n_{1}<n!. If n1n_{1} is odd, then gg is a product of disjoint odd cycles, so it is an even permutation. Then B can chose the permutation h=(1,2)(3,4)h=(1,2)(3,4) which is another even permutation. Since gg and hh are elements of the alternating group AnA_{n}, they cannot generate the whole SnS_{n}. Since the order of hh is 2, B achieves 2n22 \mid n_{2}. Remark. If n4n \geq 4, all subgrups of odd order are subgroups of AnA_{n} which has even order. Hence, all maximal subgroups have even order and B is never forced to lose.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.