uniolympiads Ελληνικά

IMC 2012, Day 1, Problem 3

Given an integer n>1n > 1, let SnS_n be the group of permutations of the numbers 1,2,…,n1, 2, \dots, 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?

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

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(Proposed by Fedor Petrov, St. Petersburg State University)

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 n≥4n\ge 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 SnS_n, HH 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 n1∣n2∣n3∣…n_1|n_2|n_3|\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<n!n_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 2∣n22|n_2.

Remark. If n≥4n\ge 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.

Transcribed from the official solutions, page 2. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?