0
$\begingroup$

$4$ people are invited to a dinner party and they are sitting on a round table. Each person is sitting on a chair there are exactly $4$ chairs. So each person has exactly two neighboring chairs, one on the left and the other on the right.

The host decides to shuffle the sitting arrangements. A person will be happy with the new arrangement if he can sit on his initial chair or any of his initial neighboring chairs.

We have to find the number of different arrangements such that at least $2$ people are happy.

Two arrangements are considered different if there is at least $1$ person sitting on a different chair in the arrangements.

Can this problem be solved with inclusion-exclusion principle? If so can anyone give me intuitive explanation of the solution process.

$\endgroup$
  • $\begingroup$ There are only $4! = 24$ seating arrangements. So, if you don't want to use P.I.E. then you could simply look at all of them and see how many of them have at least $2$ happy people. $\endgroup$ – JimmyK4542 Dec 16 '14 at 6:19
0
$\begingroup$

To begin with, count the number of arrangements with exactly two happy and two unhappy people. Since we restrict ourselves to a party of $4$, which allows only one move for making any unhappy person (directly across the table).

Pick any two of the four people to be "unhappy". The claim is that this forces the "happy" seating for the other two people. For example, if the two "unhappy" people are across from each other, then they have switched chairs. The other two people are forced to remain in their original seats (if they are to be "happy").

That leaves the case where the "unhappy" pair were sitting next to each other. In this case, the two "happy" people must move to the nearest chair opened by the movement of the "unhappy" pair. (So long as they do not move directly across the table from their original position, they will be happy.)

Thus the count of allowed seating arrangements for exactly two happy people is $\binom{4}{2} = 6$.

There are nine arrangements in which all four people are happy. One of these is the original seating (so it's unclear from the Question's wording if this is considered a "shuffle"). Two more are rotations of the entire seating to the left, resp. to the right. Two are seating swaps between two pairs of adjacent sitters (leaving all four people "happy"). Four more are obtained by swapping one adjacent pair (chosen in four ways) and leaving the other two in their original seats.

There is one arrangement in which all four people are unhappy, for which see the discussion at the previous Answer on similar rearrangements.

That leaves the cases for three happy people and one unhappy person (or by exclusion from all $4!=24$ arrangements, cases for one happy person and three unhappy people) for the interested Reader to work out. (Spoiler added.)

If there were three unhappy people, they must all move across the table of four. This forces the fourth person to move across the table as well, since no other spot is open! Hence the number of one happy/three unhappy cases is zero. The final answer can be given as the count of all permutations minus the number of no happy or exactly one happy person, so $4! - 1 - 0 = 23$, a fairly clear use of counting by exclusion. Otherwise the count could be completed by noting, for eight cases of one unhappy/three happy people: there are four ways to chose the unhappy person (who moves across the table) and two ways to move the person previously there to a happy place (left or right), with happy placement of the remaining two people being forced (one stays where they are, one takes the original chair of the unhappy person). Thus at least two happy people occurs in $6+8+9=23$ permutations.

$\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.