wu :: forums « wu :: forums - Seating Couples » Welcome, Guest. Please Login or Register. Jan 23rd, 2022, 5:23am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: towr, Eigenray, Grimbal, ThudnBlunder, SMQ, Icarus, william wu)    Seating Couples « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Seating Couples  (Read 12368 times)
william wu

Gender:
Posts: 1291
 Seating Couples   « on: May 27th, 2003, 6:28pm » Quote Modify

N married couples are to be a seated at a round table. Two arrangements are considered identical if one is a rotation of the other. In how many different arrangments can n married couples be seated such that there is always one man between two women, and none of the men is ever next to his own wife?

Source: Edouard Lucas (1842-1891). Came up with the closed-form formula for Fibonacci numbers and the Tower of Hanoi puzzle. Died of a freak accident at a banquet, when a plate fell and a shard flew into his cheek.
 IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
hyperdex
Newbie

Gender:
Posts: 2
 Re: Seating Couples   « Reply #1 on: May 28th, 2003, 12:55pm » Quote Modify

Here's a partial solution...

First, we will count the total number of arrangements that satisfy the alternating condition with no man seated next to his wife.  Dividing this result by 2N will produce the desired answer.

We will use the principle of inclusion-exclusion.  Given K<=N, how many arrangements are there so that a fixed set of K husbands are seated next to their wives?

Designate one chair to be the "head" and let's first solve the K=0 case.  The head will contain either a male or a female, and once this decision has been made there are (N!)^2 possible arrangements.  This means that in total there are 2(N!)^2 arrangements for K=0.

Suppose K>0 and fix a set of K husbands.  As before, we decide in advance whether the head seat has a man or a woman.   Consider a round table where we will have K love seats that will seat a husband and his wife and 2N-2K normal seats.  In total, we have 2N-K seats and we must choose K of them to be love seats.  This can be done in C(2N-K, K) ways.  Once we have chosen the love seats we can arrange the K husband/wife combos in exactly K! ways.  Once they are fixed, we can arrange the remaining husbands and wives in (N-K)!^2 ways.  This means that the total number of arrangements where the K husbands sit next to their wives is 2*C(2N-K,K)*K!*(N-K)!^2.  Call this number F(N, K).

The principle of inclusion/exclusion implies that the total number of arrangements where no husband is seated next to his wife is exactly

\sum_{K=0}^{N} (-1)^k * C(N, K) * F(N, K)

Using the formula for F(N, K), this can be "simplified" to

2(N!) \sum_{K=0}^{N} (-1)^k  *  C(2N-K, K)  * (N-K)!

and our desired answer would be this divided by 2N which is

(N-1)! \sum_{K=0}^{N} (-1)^k *  C(2N-K, K) * (N-K)!

Unfortunately, I do not know if there is a closed form for this.
 « Last Edit: May 28th, 2003, 12:57pm by hyperdex » IP Logged
Nigel_Parsons
Junior Member

Gender:
Posts: 63
 Re: Seating Couples   « Reply #2 on: Apr 30th, 2004, 5:21pm » Quote Modify

“A simple equation is a thing of beauty!”

Finding this in the ‘Unsolved – Hard’ puzzles, I started from basics.
::
For N couples (N>2: N=2 is impossible of solution)

Position first man, (Mr A) at a set point at the table. This avoids any duplication due to rotation, as we are looking at all seating plans relative to Mr A.

Set a woman (Mrs B) in the seat to his immediate left. This must not be Mrs A, so can be any one of (N-1) women.
At the next seat, place Mr C. As he is neither Mr A, nor the husband of Mrs B, he can be any one of (N-2) men.
By similar logic, the next woman can be chosen from (N-2), and the next man from (N-3)
This continues until all the seats are filled. The last two people to be seated are the Nth man, and the Nth woman. So for these there is no choice.

It will be seen that the number of solutions for women is (N-1)*(N-2)*(N-3).....*1
It will be seen that the number of solutions for men is (N-2)*(N-3).....*1
This gives (N-1)! * (N-2)! Possibilities.

However, the seating plan will fail if Mrs A is the last woman to be seated. As we deliberately avoided seating her to the left of her partner, the chance of her being the last to be seated is 1 in (N-1).
This reduces the possibilities to ((N-1)! * (N-2)!)/(N-1) = (N-2)! * (N-2)! = ((N-2)!)^2

Although rotations have been avoided, the mirror images have been included (where Mrs B sits to right of Mr A) and these would give everyone the same two partners only on opposite sides. Depending on how the question is phrased, the required answer may be (((N-2)!)^2)/2

The seating plan will also fail if the last man to be seated is the partner of either of the remaining ladies.
This is a chance of N/2. So the final solution would be ((((N-2)!)^2)/2)/(N/2) = (((N-2)!)^2)/N
::

I’m not totally happy with my final paragraph, but I believe I’ve ‘broken the back’ of this question

 « Last Edit: Apr 30th, 2004, 5:23pm by Nigel_Parsons » IP Logged
ThudnBlunder
wu::riddles Moderator
Uberpuzzler

The dewdrop slides into the shining Sea

Gender:
Posts: 4489
 Re: Seating Couples   « Reply #3 on: May 1st, 2004, 12:11pm » Quote Modify

Quote:
 So the final solution would be ((((N-2)!)^2)/2)/(N/2) = (((N-2)!)^2)/N

Putting N = 3 gives 1/3 ways.
 IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
rmsgrey
Uberpuzzler

Gender:
Posts: 2844
 Re: Seating Couples   « Reply #4 on: May 1st, 2004, 2:59pm » Quote Modify

on Apr 30th, 2004, 5:21pm, Nigel_Parsons wrote:
 By similar logic, the next woman can be chosen from (N-2), and the next man from (N-3)

At this stage you have (using capitals to denote men; lower-case women) AbC. The next woman could be any of n-2, including a, in which case, with AbCa, the next man is one of n-2 rather than the n-3 for AbCd.

In general, the number of possibilities for the next person increases by one when the previous person's spouse is already seated.
 IP Logged
ivancho
Newbie

Gender:
Posts: 3
 Re: Seating Couples   « Reply #5 on: Oct 12th, 2004, 5:59pm » Quote Modify

I think Hyperdex' formula is slightly off - due to somehow counting mirror images in, or something like that. What I get is:
[smiley=sum.gif](-1)k * Ck2N-k * (N-k)! * 2N / (2N -k)
and you can multiply that by (N-1)!, if you want.

Let's say man number 1 always sits at the head chair, since we can rotate the table. In fact, let's have men 2, 3, 4... sit clockwise from him, leaving chairs between them for the wives. This will remove the above (N-1)! from the formula - if you want to count all other possible seatings of the men, just permute them, together with the wives, and you'll get that factor.

Now, rook polynomials are effectively inclusion-exclusion, but they generally represent the things to count in a better light.  The numbers of the wives to the left of each man describe a permutation [smiley=pi.gif] of (1,2,..N), such that [smiley=pi.gif](i) is never equal to i or i-1. In terms of a rook configuration ( ie, N rooks on a NxN board, no 2 hitting each other ), it needs to be a configuration that avoids the main diagonal, upper second diagonal and a bottom left square. The main rook theorem tells us that the number of those configurations is   r0 * N! - r1 * (N-1)! + r2 * (N-2)! -..., where rk is the number of ways to place k rooks on the avoided area so that no 2 hit each other. But on our forbidden area, the only way 2 rooks can threaten each other is if they are neighbours ( if you count the bottom left cell as neighbour of top left and bottom right). So rk is equal to the number of ways we can choose k out of 2N marbles on a ring so that no 2 are neighbours. That number is Ck2N-k * 2N / (2N - k)  - I suppose here it's the same thing as Hyperdex's solution, where we can't have the left side of a love seat be a neighbour of another  left side.. I think the easiest way to derive the number itself is to count something slightly different - ie, k red and 1 blue marbles, so that no 2 red are adjacent - counting those placing red ones first gives (2N-k)* rk, counting them via placing the blue one first gives 2N * Ck2N-k. And that's that..

I think this is the most closed form we can get. Apparently it's possible to get a recurrence relation, but I haven't bothered with that..
 « Last Edit: Oct 12th, 2004, 6:25pm by ivancho » IP Logged
nakli
Junior Member

Gender:
Posts: 62
 Re: Seating Couples   « Reply #6 on: Jul 19th, 2012, 6:33am » Quote Modify

http://en.wikipedia.org/wiki/M%C3%A9nage_problem
 IP Logged

I was born naked on a bed with a lady.
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »