Developing a strategy to win a game of picking elements from $S_n$
$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?
group-theory discrete-mathematics combinatorial-game-theory
asked Dec 23 '18 at 4:40
Rakesh BhattRakesh Bhatt
967214
$endgroup$
add a comment |
$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?
group-theory discrete-mathematics combinatorial-game-theory
asked Dec 23 '18 at 4:40
Rakesh BhattRakesh Bhatt
967214
$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
add a comment |
$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?
group-theory discrete-mathematics combinatorial-game-theory
asked Dec 23 '18 at 4:40
Rakesh BhattRakesh Bhatt
967214
$endgroup$
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?
group-theory discrete-mathematics combinatorial-game-theory
group-theory discrete-mathematics combinatorial-game-theory
asked Dec 23 '18 at 4:40
Rakesh BhattRakesh Bhatt
967214
asked Dec 23 '18 at 4:40
Rakesh BhattRakesh Bhatt
967214
edited Dec 23 '18 at 17:09
Rakesh Bhatt
asked Dec 23 '18 at 4:40
Rakesh BhattRakesh Bhatt
967214
asked Dec 23 '18 at 4:40
Rakesh BhattRakesh Bhatt
967214
asked Dec 23 '18 at 4:40
Rakesh BhattRakesh Bhatt
967214
967214
$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
add a comment |
$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
$begingroup$
"all other" sets might be a bit ambitious.
$endgroup$
– Lord Shark the Unknown
Dec 23 '18 at 4:56
$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$
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$
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
$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
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
$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
add a comment |
1 Answer
1
active
oldest
votes
$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.
answered Dec 23 '18 at 17:26
Derek HoltDerek Holt
54.4k53574
$endgroup$
add a comment |
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3050061%2fdeveloping-a-strategy-to-win-a-game-of-picking-elements-from-s-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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.
answered Dec 23 '18 at 17:26
Derek HoltDerek Holt
54.4k53574
$endgroup$
add a comment |
$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.
answered Dec 23 '18 at 17:26
Derek HoltDerek Holt
54.4k53574
$endgroup$
add a comment |
$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.
answered Dec 23 '18 at 17:26
Derek HoltDerek Holt
54.4k53574
$endgroup$
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.
answered Dec 23 '18 at 17:26
Derek HoltDerek Holt
54.4k53574
edited Dec 23 '18 at 18:18
answered Dec 23 '18 at 17:26
Derek HoltDerek Holt
54.4k53574
answered Dec 23 '18 at 17:26
Derek HoltDerek Holt
54.4k53574
answered Dec 23 '18 at 17:26
Derek HoltDerek Holt
54.4k53574
54.4k53574
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3050061%2fdeveloping-a-strategy-to-win-a-game-of-picking-elements-from-s-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$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