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

[UNSOLVED] KingGeorge's Challenge of the Month/Annual 4th of July Problem! Suppose you have an 8-pointed star like in the picture below, and you want to color the edges of that star in either purple or green. How many ways are there to do this? Assume that two colorings are the same if the star can be rotated or reflected so that the two colorings look the same.

  • one year ago
  • one year ago

  • This Question is Closed
  1. KingGeorge
    Best Response
    You've already chosen the best response.
    Medals 4

    • one year ago
    1 Attachment
  2. Ishaan94
    Best Response
    You've already chosen the best response.
    Medals 0

    \[\binom{8}{2}\cdot \frac12\]?

    • one year ago
  3. KingGeorge
    Best Response
    You've already chosen the best response.
    Medals 4

    There's a lot more than that. Remember that there are 16 edges here, not 8.

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

    Ohh edges. Can I substitute 16 in place of 8?

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

    Nope. There's still a lot more than that. I'll be gone for a while now. If it still isn't solved when I get back, I might give a hint.

    • one year ago
  6. Ishaan94
    Best Response
    You've already chosen the best response.
    Medals 0

    Okay :|

    • one year ago
  7. nbouscal
    Best Response
    You've already chosen the best response.
    Medals 0

    Hrm... there are 8 rotational symmetries and 4 reflective symmetries. Ignoring symmetries, there are \(2^{16}\) patterns. Perhaps we simply divide the symmetries away, leaving us with \(2^{11}\)? Not sure, will have to think about it more.

    • one year ago
  8. asnaseer
    Best Response
    You've already chosen the best response.
    Medals 1

    another way of looking at it: Purple Edges Green Edges 16 0 15 1 14 2* 13 3* 12 4* 11 5* 10 6* 9 7* 8 8* where N* stands for how many ways we can select N unique edges - so 2* would be 8 in this case. Then multiply the whole lot by 2 as we can swap the Purple and Green edges.

    • one year ago
  9. KonradZuse
    Best Response
    You've already chosen the best response.
    Medals 0

    256.

    • one year ago
  10. KonradZuse
    Best Response
    You've already chosen the best response.
    Medals 0

    I win !!!

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

    It is not 256. @nbouscal's way is closest to my original method, although I would be very interested in seeing if @asnaseer's way also pans out. I will point out that the solution is an odd number, however odd that sounds (pun intended). In asnaseer's potential solution, after you multiply by 2, you are counting 8 purple/8 green twice, so you have to subtract it (I think that should work). Hint containing my method in white \(\LaTeX\) below: \[\color{white}{\text{I used Burnside's Lemma from Group Theory using the group } D_8.}\]\[\color{white}{D_8\text{ is also called }D_{16}\text{ sometimes.}}\]

    • one year ago
  12. mathslover
    Best Response
    You've already chosen the best response.
    Medals 0

    I used Burnside's Lemma from Group Theory using the group

    • one year ago
  13. mathslover
    Best Response
    You've already chosen the best response.
    Medals 0

    I used Burnside's Lemma from Group Theory using the group D8. D8 is also called D16 sometimes.

    • one year ago
  14. Ishaan94
    Best Response
    You've already chosen the best response.
    Medals 0

    What's Burnside's Lemma?

    • one year ago
  15. mathslover
    Best Response
    You've already chosen the best response.
    Medals 0

    I also dont know about that : )

    • one year ago
  16. experimentX
    Best Response
    You've already chosen the best response.
    Medals 0

    Purple Edges Green Edges Ways 16 0 1 15 1 1 14 2* 7 or 8 13 3* 12 4* 11 5* 10 6* 9 7* 8 8* looks like this will take a month.

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

    Unless you're familiar with group theory, I would encourage ignoring Burnside's Lemma, and trying to find another way.

    • one year ago
  18. Ishaan94
    Best Response
    You've already chosen the best response.
    Medals 0

    How would you arrange 2 things in a circle at 16 places, repetition allowed

    • one year ago
  19. KingGeorge
    Best Response
    You've already chosen the best response.
    Medals 4

    What do you mean with repetition allowed? Can you place two things at the same place? That would give you \(16^2\).

    • one year ago
  20. Ishaan94
    Best Response
    You've already chosen the best response.
    Medals 0

    I meant repetition of the things, you can use them more than once. I am sorry :/

    • one year ago
  21. Ishaan94
    Best Response
    You've already chosen the best response.
    Medals 0

    Ignore me. I will try to come up with concrete solution and only then reply

    • one year ago
  22. Ishaan94
    Best Response
    You've already chosen the best response.
    Medals 0

    But I would like to know about the symmetries nbouscal mentioned. @nbouscal

    • one year ago
  23. KingGeorge
    Best Response
    You've already chosen the best response.
    Medals 4

    That is basically what Burnside's Lemma does for you. It's a little bit more complicated, but basically you look at the colorings that are fixed by certain symmetries, multiply by some things, add a bunch of these terms, and then divide by the amount of symmetries. Of which there are 16.

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

    Don't get discouraged by Burnside's Lemma. It's a(n) (advanced) technique that trivializes the problem to one or two lines. I would love to see another way to do this problem.

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

    @mukushla you might like to do this :-)

    • 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.