1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ "all other" sets might be a bit ambitious. $\endgroup$ – Lord Shark the Unknown Dec 23 '18 at 4:56
  • $\begingroup$ The probability that two random elements of $S_n$ generate $S_n$ approaches $1$ as $n \to \infty$. $\endgroup$ – Derek Holt Dec 23 '18 at 10:41
  • $\begingroup$ Please ask one question at a time. $\endgroup$ – Shaun Dec 23 '18 at 16:11
  • $\begingroup$ @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 $\endgroup$ – Rakesh Bhatt Dec 23 '18 at 17:04
  • 1
    $\begingroup$ 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. $\endgroup$ – Shaun Dec 23 '18 at 17:06
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.