# Developing a strategy to win a game of picking elements from $S_n$

Given a integer $$n>1$$, Let $$S_n$$ be the group of permutations of the numbers $$1,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 $$S_n$$. It is forbidden to select an element that had been already selected. The game ends when the selected elements generate the whole group $$S_n$$. The player who made the last move loses. The first move is made by $$A$$. Which player has a winning strategy?

My attempt involves finding

What elements of $$S_n$$ can generate $$S_n$$?

I know that $$(123 \dots n)$$ and $$(12)$$ can generate $$S_n$$.

But we are supposed to look for all other such set of elements which can generate $$S_n$$.

How do I solve this?

• "all other" sets might be a bit ambitious. – Lord Shark the Unknown Dec 23 '18 at 4:56
• The probability that two random elements of $S_n$ generate $S_n$ approaches $1$ as $n \to \infty$. – Derek Holt Dec 23 '18 at 10:41
• Please ask one question at a time. – Shaun Dec 23 '18 at 16:11
• @shaun The actual question is "Second Question". I thought that the first question is necessary to solve the actual question. My attempt involves solving first question to solve second question – Rakesh Bhatt Dec 23 '18 at 17:04
• Okay. I suggest that you edit the question, then, to make that clear. It might be closed as too broad otherwise, since it's easy to overlook such detail. – Shaun Dec 23 '18 at 17:06

## 1 Answer

I guess for $$n=1$$, A must choose the identity, which generates $$S_n$$, so B wins.

For $$n=2$$ A wins by choosing the identity, and for $$n=3$$ A wins by choosing a $$3$$-cycle, such as $$(1,2,3)$$.

For $$n \ge 4$$, all maximal subgroups of $$S_n$$ have even order, and the subgroup generated by the elements chosen so far will eventually be maximal, so B wins.