IMC 2012 · Day 1 · P3

Player A can win for $n = 2$ (by selecting the identity) and for $n = 3$ (selecting a 3-cycle).

We prove that B has a winning strategy for $n \ge 4$. Consider the moment when all permitted moves lose immediately, and let $H$ be the subgroup generated by the elements selected by the players. Choosing another element from $H$ would not lose immediately, so all elements of $H$ must have been selected. Since $H$ and any other element generate $S_n$, $H$ must be a maximal subgroup in $S_n$.

If $|H|$ is even, then the next player is A, so B wins. Denote by $n_i$ the order of the subgroup generated by the first $i$ selected elements; then $n_1 \mid n_2 \mid n_3 \mid \dots$. We show that B can achieve that $n_2$ is even and $n_2 < n!$; then $|H|$ will be even and A will be forced to make the final – losing – move.

Denote by $g$ the element chosen by A on his first move. If the order $n_1$ of $g$ is even, then B may choose the identical permutation $id$ and he will have $n_2 = n_1$ even and $n_2 = n_1 < n!$.

If $n_1$ is odd, then $g$ is a product of disjoint odd cycles, so it is an even permutation. Then B can chose the permutation $h = (1,2)(3,4)$ which is another even permutation. Since $g$ and $h$ are elements of the alternating group $A_n$, they cannot generate the whole $S_n$. Since the order of $h$ is 2, B achieves $2 \mid n_2$.

Remark. If $n \ge 4$, all subgrups of odd order are subgroups of $A_n$ which has even order. Hence, all maximal subgroups have even order and B is never forced to lose.