Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

KingGeorge Group Title

Group Theory Challenge Problem! Let \(S_n\) be the group of permutations on \(\{1,2,...,n\}\), and let two players play a game. Taking turns, the two players select elements one at a time from \(S_n\). Players may only select elements that have not already been selected. The game ends when the set of selected elements generate \(S_n\). The player who made the last move loses. Who wins the game? [HINT: Think of this problem in terms of the largest possible set of elements you can have so that you don't generate the whole group.] [HINT 2: What are the orders of the maximal subgroups?]

  • one year ago
  • one year ago

  • This Question is Open
  1. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    This was a problem of the month offered by my undergraduate department where I was able to come up with the correct solution.

    • one year ago
  2. zzr0ck3r Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I post an easier group theory problem and only @KingGeorge looks, @KingGeorge posts one and you all are like flies....

    • one year ago
  3. zzr0ck3r Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    im playing:)

    • one year ago
  4. zepdrix Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    If \(\large n\) is even, the player to select first would win. If \(\large n\) is odd, the player to select first would lose. Do I have the right idea?? D: No it's probably more math'y than that...

    • one year ago
  5. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    Definitely more mathy than that. Although that was also one of my first ideas when given this question.

    • one year ago
  6. dan815 Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    the player who made the 2nd last move

    • one year ago
  7. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    Well, duh. But is that player the first or the second to have originally chosen?

    • one year ago
  8. swissgirl Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Ummm can they remove more than one element at a time?

    • one year ago
  9. dan815 Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    its the player that goes 2nd who wins

    • one year ago
  10. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    Only one at a time @swissgirl Show me a proof @dan815

    • one year ago
  11. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    Well, I'm off to bed. I'll leave you with the very vague hint, that while @zepdrix's idea is not the correct solution, you do need to keep even/odd in mind.

    • one year ago
  12. dan815 Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    |dw:1370241063380:dw|

    • one year ago
  13. dan815 Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    |dw:1370241133384:dw|

    • one year ago
  14. dan815 Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    sooo the first one loses!

    • one year ago
  15. dan815 Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    |dw:1370241271520:dw|

    • one year ago
  16. dan815 Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    so all even but +1 elements from s1=1 will give u an odd number of elements in total

    • one year ago
  17. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    I honestly have no idea what you're trying to do here.

    • one year ago
  18. dan815 Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    well i m just kinda guessing what set of permutations are xD does that mean for each permutation say for 3, there are 3! elements in there

    • one year ago
  19. dan815 Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    if it was like that in that case I said there are an even number of permutations in all but 1 element which is the 1! element so there will always be an odd number of elements in this set therefore the first one to Go, will always pick the first and last element

    • one year ago
  20. dan815 Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    it cant be that easy so.. i probably dont understand what a group of permutations mean xD

    • one year ago
  21. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    Hint: Think of this problem in terms of the largest possible set of elements you can have so that you don't generate the whole group.

    • one year ago
  22. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    Hint 2: What are the orders of the maximal subgroups?

    • one year ago
  23. alexandercpark Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Would the size of s_n be nCn?

    • one year ago
  24. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    The size of \(S_n\) is \(n!\).

    • one year ago
  25. alexandercpark Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    forgive my lack of talent in the equation editor :( because the size of s_n is n!, the ONLY time that the size of s_n is odd is when s_n is the emty set, or the set {1} any set beyond that would be even, because you have (integers) * 2. so, the winner depends on the origanl size of s_n, if n = 0 or 1, the first player to go will lose. if n > 1, the second player to go will lose.

    • one year ago
  26. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    There are some additional considerations you have to take in mind since this is a group. If you aren't familiar with some group theory, this problem is going to give you a tough time.

    • one year ago
  27. domu Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    The set of n-1 elements \[\left\{ (j,j+1) \left| \right| 1 \le j < n \right\}\] form a generating set. Thus, for n odd, the first player losses and for n even the second player losses. I believe this is correct but I still need to show that a set of n-2 elements does not generate the whole group. Thought? Counterexamples?

    • one year ago
  28. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    That is not correct. For example, if n=3, then I will choose \((123)\). Then, in order not to lose, second player must choose either \(e\) or \((132)\). I then choose the one second player didn't choose. Then whatever second player chooses next, he loses. So I win as first player.

    • one year ago
  29. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    Since this seems to have died, I'll be posting the solution here. For \(n=2,3\) player 1 wins. For any other \(n\ge1\), player 2 wins. It should be straightforward to see why this is the case for \(n=1,2,3\). Now suppose \(n\ge4\). First, I will prove that any maximal subgroup of \(S_n\) has even order. Note that any subgroup \(H\) of \(S_n\) that has odd order must have only elements of odd order as well. Let \(w\) be such an element. Then consider the unique cycle-decomposition of \(w\). Since \(|w|\) is odd, all the cycles must also have odd order. But if a cycle has odd order, then it must be contained in the alternating subgroup \(A_n\). Thus, \(w\in A_n\), and \(H\subsetneq A_n\). So \(H\) is not maximal. Thus, any maximal subgroup has even order. Now suppose \(2k\) elements have been chosen from \(S_n\) for some \(k\in\mathbb{Z}_{\ge0}\) so it is player 1's turn. We have two cases. Case 1: Player 1 chooses so that the game ends. Then player 2 wins. Case 2: Player 1 chooses so that the game does not end. Then \(2k+1\) elements have been chosen. But since every maximal subgroup has even order, this set of elements must be properly contained in some maximal subgroup. So there is at least one more element \(g\) in that subgroup that has not been chosen. Player 2 may choose \(g\), and thus does not end the game. We now have chosen \(2(k+1)\) elements. Since there are a finite number of elements, we are done by induction.

    • one year ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.