uniolympiads English

IMC 2012, Ημέρα 1, Θέμα 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?

Πρωτότυπο από το επίσημο 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?

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(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.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 2. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;