Solve the Puzzle: 6 Men & Their Wives Seating Arrangement

[abc]

6 men with their wives ( total of 12 ) in how many ways can they sit in a circular table but no man sits beside his wife ?
needs smart people
cheers
abc

 

[T@P]

just a hint in case you are totally lost, a good approach would be to find the numebr of ways 12 people can sit around a table, and then subtract the numebr of times a man and his wife are nxt to each other.
then when a man and his wife ( 1 pair) sit together, every combination where tey don't move is bad. subtract the nume ways 10 people can sit around a table. then when two pairs of husband wives are together, so 8 people around a table etc. doing it out, you should come at the right answer. unfortunately, i never really came across any 1 step ways of doing these kinds of problems, but if you know one i would *very* interested in knowing it

 

[Bartholomew]

It's more complicated than that because when you subtract those arrangements with one particular pair (say man 1 and wife 1) together, you are also subtracting some arrangements with man 2 and wife 2 together, and you only want to count each arrangement once. I think, although I have not really thought about it, that you could do it the way I ended up doing the first of "Two Combinatorial Problems" in the set theory, logic, probability and statistics forum.

 

[gazzo]

Hmmm... i don't know if its right.

Select if you want to see: "115200"



If each person represented a vertex of a regular 12-gon, could you solve it with err.. hmm.

 

[Gokul43201]

I think not. I believe the number will be larger than 500,000. Nearly all the ways of seating the six men together, and their wives, together on the other side, will produce a successful arrangement. This can be done in (6!)^2 ways, which is bigger than 500,000.

 

[Moses]

Well, a good tactic you may use is to make pair 1 man set next to par 2 women, and on the opposite side of the circle the opp will happen [pair 1 women, will sti next to pair 1 man].

after words let the men set on one side [count the !]. then the women on the other side , then do it as 3 men, 1 women, and so one. After words, instead of using the paris 1-2 as "walls" use 1 & 3 and so on, so the number is soo mad large. Well, i am sure with factorials you can make the calulating less paining, but still a pain.

 

[mattmns]

Question: If 6 men sit next to each other, and 6 women sit next to each other (at the same time) Is this counted as 1 possibility, or 12? Meaning that you would move each man and woman one seat, for example, left (11 times).

 

[Gokul43201]

It's 1 arrangement (not 12). We are not told that the seats are numbered, so must assume they are identical.

 

[Rogerio]

Question: If 6 men sit next to each other, and 6 women sit next to each other (at the same time) Is this counted as 1 possibility, or 12?

Just 1 possibility. Remember it is a circular table.

 

[Galileo]

Just 1 possibility. Remember it is a circular table.

But the men and women ARE numbered right? So permuting (or is it permutating?) the men will give a different arrangement and permut(at)ing the women will as well.
So there are (6!)^2 ways of arranging the table such that 6 men are sitting next to each other.

EDIT: Nevermind, I don't think there was any confusion...

 

[mattmns]

It's 1 arrangement (not 12). We are not told that the seats are numbered, so must assume they are identical.

Ok I thought it was 1, but your number of 500,000 got me questioning that. Now back to the problem.

 

[Rogerio]

I believe the number will be larger than 500,000.

And it is! 12,771,840

 

[hemmul]

6 men with their wives ( total of 12 ) in how many ways can they sit in a circular table but no man sits beside his wife ?
needs smart people
cheers
abc

i got 12!-4*6!
if it is true - i'll explain the solution...

 

[Rogerio]

i got 12!-4*6!
if it is true - i'll explain the solution...

Unfortunately it's false: it can't be more than 11!

 

[hemmul]

Unfortunately it's false: it can't be more than 11!

whoops! so i misunderstood something...

 

[b0mb0nika]

look at the problem the other way around :
how many ways can the 6 men ( and women ) sit at the round table such that every men sits besides his wife :
there are 5! x 2^6 possible way to arrange the 6 pairs ( look at the pair - man + woman as 1 object, there are 5! ways you can arrange them around a round table, multiply it by 2^6 b/c for each pair it doesn't matter if the man or the woman is on the left/ right side)

now we know that 12 people can be arranged in 11! ways around a round table
so there are

11! -5! x 2^6
ways to arrange the people such that no man sits beside his wife

i believe that is the answer
Diana

 

[Rogerio]

...so there are
11! -5! x 2
ways to arrange the people such that no man sits beside his wife

i believe that is the answer
Diana

Well Diana, if "no man sits beside his wife", then "only one man beside his wife" is not allowed.
However, this arrangement doesn't belong to your exceptions set.
So, your answer is not the correct one.

BTW, I think it is 12,771,840

 

[b0mb0nika]

yes rogerio , ur right.. there's something wrong with my solution :)
i didn't subtract the possibilities that 1, 2, 3, 4 or 5 couple could be seated together

i did get the same answer as you after doing it like that

D.

 

[Bartholomew]

i did get the same answer as you after doing it like that

I don't believe you. There is much involved in subtracting the possibilities that 1, 2, 3, 4, or 5 couples could be seated together and a lot of room for error. Let's see your work.

 

[Bartholomew]

12,771,840

Well, I thought about this for a while trying to find a simpler way to do it than adding and subtracting as in the other problem I mentioned earlier in this thread, but finally I just decided to slog through.

The number of ways to arrange them around the table, considering each position distinct, is 12!. The number to exclude is:

12*10!*2*C(6,1) - 12*9*8!*2^2*C(6,2) + 12*9*7*6!*2^3*C(6,3) - 12*9*7*5*4!*2^4*C(6,4) + 12*9*7*5*3*2!*2^5*C(6,5) - 12*9*7*5*3*2^6*C(6,6)

For example, the second term, 12*9*8!*2^2*C(6,2), was obtained by first placing a pair (12 ways to place the first pair), then placing a second pair (9 ways to place the second pair once the first is down), then multiplying by 8! for the leftover positions, then multiplying by 2^2 to account for the two possible orders each pair can be in, then multiplying by C(6,2) to account for every possible pair of pairs. You add and subtract the terms as I did to account for overcount or undercount at each step; for example, the first term counts every arrangement containing 2 pairs twice (once when the pair "in question" in the first step occupies the first pair in the arrangement and the other pair is part of the 10!, and once when the pair in question occupies the second pair in the arrangement and the other pair is part of the 10!), so each must be subtracted back once in the second term.

This (the whole sequence of terms) comes out to 330,220,800. Subtracting this from 12! gets you 148,780,800. Divide by 12 (because rotations of a position only count once and we were counting them 12 times) and you get 12,398,400. This is slightly less than your answer, Rogerio. I recalculated it and came out with the same answer. Any idea why there is a difference? What method did you use?

 

[b0mb0nika]

let's say we have n couples, 2n chairs and k of the couples want to sit together
then there are 2n-k people to be placed around the table. One of them
can occupy one fixed position ( whichever it might be ) so there
are (2n-k-1)! ways to arrange the rest. But the order of the wives
and men doesn't matter ( in a couple) so we get another 2^k arrangements.
so there are 2^k*(2n-k-1)! ways to arrange k couples from n around a circular table.
For each set of such k, there are C(n,k) such pairs.
so i used the formula C(n,k)*2^k*(2n-k-1)!, with the same alternating
signs as u did.
substract that from 11! the total number you can arrange 12 people
around a cicular table (for n=6, and 1<=k<=6)
and that's what you get :

11! -C(6,1)*2*10! + C(6,2)*4*9! - C(6,3)*8*8! + C(6,4)*16*7! - C(6,5)*32*6! + C(6,6)*64*5! = 12,771,840

 

[Bartholomew]

You're right, I see the problem with my approach.

 

[ceptimus]

I wrote a program that simply counts up the ways.

I figured that if it's a round table, then to avoid counting each solution as twelve solutions (where everyone just moves to the chair to their left, one place) I would fix the position of one man. So M1 always sits in the 12 o' clock position.

Then I place his wife, W1 and she can sit in 9 places without sitting next to him.

Next M2 is placed, and there are always 10 places he can sit (as my program places the men first, the number of places a man can sit is always just the number of remaining chairs).

Then W2 is placed and so on.

Eventually we either reach a position where it is impossible to place a wife without sitting her next to her husband, in which case the program just backtracks to the previously placed man, etc., or we reach a solution, and add one to the count. When a solution is found, the program backtracks to find the next solution. It uses a recursive algorithm.

The program finishes when the first wife has been tried in each of the 9 available places. If we don't wish to count mirror image solutions as separate ones, then the first wife has only to be tried in 5 places (directly opposite her husband, or closer to his left than his right).

So, do you want me to post the answer (and the code?) or shall I wait a while longer yet?

 

[Bartholomew]

Ceptimus, so you believe rogerio's and bombonika's answer is wrong? I don't see anything wrong with it. Sure, post your code.

We did consider mirror image solutions to be separate, but I think all you need to do to consider them the same is divide by 2. If you take a position, start with an arbitrary person and go clockwise, transcribing the people onto a second circle counterclockwise, you get a representative mirror-image arrangement. If you do it again to the mirror-image arrangement you get the original arrangement. So each arrangement is paired with exactly one mirror image arrangement, and the mirror image arrangement is paired back; so just divide by 2 and get 6385920.

 

[ceptimus]

My answer agrees with Rogerio's and b0mb0nika's. However, I added some extra lines of code to avoid counting mirror image solutions separately, and when these are active, the answer is, of course, exactly half theirs.

 Number of people        Solutions
        4               2       (1)
        6              32      (16)
        8            1488     (744)
       10          112512   (56256)
       12        12771840 (6385920)

// round_table.c
// solves the puzzle: how many ways can 6 couples sit around a round table without any man sitting next to his wife?
// ceptimus: 2005-01-22

#include "stdio.h"

// the size of the table (number of chairs, and number of people)
#define PLACES 12

int chair[PLACES]; // 0 indicates that a chair is empty, or 1 to PLACES says which person is occupying it

unsigned long solutions; // counts the number of solutions found

void seat(int person) // sit [person] somewhere (if possible) and move onto next person
{
    int position;
    int places;

    if (person == 2)
        places = 1 + PLACES / 2; // only try the first wife on one side, or opposite her husband
    else
        places = PLACES; // try all the other people in each available place

    if ((chair[PLACES / 2] == 2) && (person == 3)) // if the first wife is seated opposite her husband
        places = PLACES / 2; // only try the second husband on one side of the table

    // above lines just eliminate mirror image solutions. To count such solutions, remove // from following line
    // places = PLACES;

    for (position = 1; position < places; position++)
    {
        if (!chair[position]) // if the chair is empty
        {
            if (person % 2) // if person is an odd number (i.e. a man)
                chair[position] = person; // seat him
            
            else // a woman
                if
                (
                    (chair[(position - 1) % PLACES] != (person - 1)) && // her husband isn't in the chair to the left
                    (chair[(position + 1) % PLACES] != (person - 1))    // or in the position to the right
                )
                    chair[position] = person; // seat her

            if (chair[position]) // if the person has been seated
            {
                if (person == PLACES) // if all the people have been seated
                    solutions++; // we've found and extra solution
                else
                    seat(person + 1); // try to seat the next person

                chair[position] = 0; // make the person stand up again, so we can search for further solutions
            }
        }
    }
}


int main(int argc, char* argv[])
{
    int i;

    for (i = 0; i < PLACES; i++)
        chair[i] = 0; // all chairs are empty

    solutions = 0L; // no solutions found yet

    chair[0] = 1; // sit the first man in the first chair

    seat(2); // sit his wife somewhere (and then try to seat all the remaining people)

    printf("%lu solutions found for seating %u people\n", solutions, PLACES);

    return 0;
}