Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Let ur mind work

  1. Jan 9, 2005 #1

    abc

    User Avatar

    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
     
  2. jcsd
  3. Jan 9, 2005 #2

    T@P

    User Avatar

    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 dont 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
     
  4. Jan 9, 2005 #3
    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.
     
    Last edited: Jan 9, 2005
  5. Jan 9, 2005 #4
    Hmmm.... i dunno if its right.

    Select if you want to see: "115200"

    :frown:

    If each person represented a vertex of a regular 12-gon, could you solve it with err.. hmm.
     
  6. Jan 9, 2005 #5

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  7. Jan 10, 2005 #6
    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.
     
  8. Jan 10, 2005 #7
    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).
     
  9. Jan 10, 2005 #8

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It's 1 arrangement (not 12). We are not told that the seats are numbered, so must assume they are identical.
     
  10. Jan 10, 2005 #9
    Just 1 possibility. Remember it is a circular table.
     
  11. Jan 10, 2005 #10

    Galileo

    User Avatar
    Science Advisor
    Homework Helper

    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...
     
    Last edited: Jan 10, 2005
  12. Jan 10, 2005 #11
    Ok I thought it was 1, but your number of 500,000 got me questioning that. Now back to the problem.
     
  13. Jan 12, 2005 #12
    And it is! 12,771,840 :smile:
     
  14. Jan 12, 2005 #13
    i got 12!-4*6!
    if it is true - i'll explain the solution...
     
  15. Jan 12, 2005 #14
    Unfortunately it's false: it can't be more than 11!
     
  16. Jan 12, 2005 #15
    :redface: whoops! so i misunderstood something...
     
  17. Jan 18, 2005 #16
    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
     
    Last edited: Jan 18, 2005
  18. Jan 18, 2005 #17
    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 :smile:
     
  19. Jan 18, 2005 #18
    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.
     
  20. Jan 19, 2005 #19
    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.
     
  21. Jan 20, 2005 #20
    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?
     
  22. Jan 21, 2005 #21
    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
     
  23. Jan 21, 2005 #22
    You're right, I see the problem with my approach.
     
  24. Jan 22, 2005 #23
    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?
     
  25. Jan 22, 2005 #24
    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.
     
    Last edited: Jan 22, 2005
  26. Jan 22, 2005 #25
    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.
    Code (Text):
     Number of people        Solutions
            4               2       (1)
            6              32      (16)
            8            1488     (744)
           10          112512   (56256)
           12        12771840 (6385920)
    Code (Text):
    // 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;
    }
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook