Suppose 8 people are sitting in 8 chairs in a circle. They're playing musical chairs.

The music plays. They all get up and move.

The music ends. They all sit down.

How many ways can they sit such that nobody has the same person to their right as they did in the first orientation?

As usual for "round table" problems, the solution is invariant under rotation - i.e. the actual seat does not matter, only relative position.

I would appreciate any help on this problem. I have a feeling it would be easier to solve with inclusion-exclusion, but I can't quite define my sets correctly.

  • 1
    $\begingroup$ Arbitrarily choose a person and call them person $1$ (e.g. pick the youngest). Going counter-clockwise around the table from where person $1$ started, label the rest of the people $2,3,\dots,8$ according to where they initially sat. Let $A_1,A_2,A_3,\dots,A_8$ be the events where person $i$ still has person $i+1$ to his right, wrapping around so that $A_8$ is the event that person $8$ still has person $1$ to his right. $A_1\cup A_2\cup \dots \cup A_8$ is the "bad" outcome, we want the opposite, but we can count this one more easily than the opposite via inclusion-exclusion. $\endgroup$ – JMoravitz Nov 8 at 16:04
  • 1
    $\begingroup$ Now, consider $|A_1|, |A_1\cap A_2|$ and $|A_1\cap A_3|$ as examples. In $A_1$ you have $2$ following $1$, so briefly imagine they are siamese twins joined at the hip, so you are going to in effect arrange seven bodies around a circular table (despite the fact that they still count as eight people). Similarly, $|A_1\cap A_2|$ we can imagine that persons $1,2,$ and $3$ are all sharing the same body, like a three-headed ogre or siamese triplets, or however you need to justify this in your mind, so we have in effect six bodies to arrange. Similarly $|A_1\cap A_3|$ we have six bodies... $\endgroup$ – JMoravitz Nov 8 at 16:07

Your Answer

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

Browse other questions tagged or ask your own question.