N couples sitting at a table...

Post Reply New Topic

Hi,
can anyone here solve this problem?

N married couples are sitting at a round table with exactly 2N chairs. How many ways are there to seat them such that no couple is sitting together and that no two men or two women are sitting next to each other?

Yes. I can solve this problem.

ruveyn

Seriously now.

I got

2*(N)!(N -1)!

given that there were 2*N people, N men, N women.

The factor 2 comes from applying a mirror reflection to an arrangement.

Please check this out.

ruveyn

I am going to reformulate the problem because I think it is easily misunderstood:

There are N married couples to be seated around a table.
The table is round. This means seating arrangements which can be reached by rotating the table are considered identical.
There are two conditions to be fulfilled:
1) No husband and wife are sitting right next to each other.
2) No man is sitting right next to another man and no woman next to another woman.

How many solutions are there to the above conditions?

I didn't solve it myself yet. I think the best way is by using the inclusion-exclusion principle. It can't be too hard, I'm probably going to figure this out tomorrow. Now it is getting late here so I'm going to bed.


Ruveyn, your solution doesn't appear to be correct. For N=2 there should be no solutions but your formula yields 4.

This is a wild guess.

1/3*[(N)(N!)/2]

If N = 5, there are 20 ways to seat the couples.

If N = 4, there are 16 ways to seat the couples.

If N = 3, there are 3 ways to seat the couples.

Would you like proof?

I'm still calculating (I have dyscaculia ) but my boyfriend said:





I'm -off course trying to prove him wrong XD i'll post later what my conclutions are

If N=3, there are only 2 distinct ways to seat them. This is easily seen by first choosing an arrangement for the men (there are two in this case, or more generally (N-1)!) and then simply exhausting arrangements for putting their wives between them (there is only one valid arrangement for each choice of male seating). Let each couple be A-A', B-B', C-C'.
ABC and ACB are the valid permutations of the three if we only care about who's sitting next to whom. ABC implies A' must be between BC, B' must be between CA, and C' must be between AB. Hence the unique corresponding arrangement is AC'BA'CB'. We can likewise find the unique arrangement for ACB.

And ruveyn's is unfortunately also wrong because it can easily be shown that the answer is less than N!(N-1)!: First choose an arrangement for the men at the table; there are (N-1)!. Then ignore the wife part and find the number of ways you can put women between them; this is equivalent to placing N women in N distinct seats, giving N!. Hence, the answer must be less than N!(N-1)!.

And finally, Dianitapilla's boyfriend's argument is invalid, although I'm not sure if his conclusion is wrong.

This simply doesn't follow at all. Suppose my seating proceeded thus:
A-BA'--------
I claim that B' has N-2 = 4 places he can sit.
A F' B A' C B' D C' E D' F E'
A E' B A' C F' D B' E C' F D'
A D' B A' C E' D F' E B' F C'
A C' B A' C E' D F' E D' F B'
(Check for mistakes, but even if this is wrong I bet the point is true still).

So,

I'll think about it some more.

This cannot be done with only two couples. So, for N>2 I see,

[(N)(N-1)!] / 3

Edit:
You know, I have quit trying to help someone with their homework, knowing that I will purposefully give wrong answers.

I realize that N(N-1)! = N!