Results 1 to 7 of 7

Math Help - tricky permutations problem

  1. #1
    Member
    Joined
    Dec 2008
    From
    Australia
    Posts
    161

    tricky permutations problem

    This is very tricky.

    8 people; A, B, C, D, E, F, G, and H sit around a table. How many ways can this be done if A must be directly opposite to B and C cannot sit next to D?

    I had 912. it must be wrong

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,390
    Thanks
    1476
    Awards
    1
    Quote Originally Posted by differentiate View Post
    8 people; A, B, C, D, E, F, G, and H sit around a table. How many ways can this be done if A must be directly opposite to B and C cannot sit next to D?
    Seat A at the table. That fixes where B must sit. It also leaves six chairs empty.
    There are four ways to seat C next to either A or B, leaving four ways to seat D.
    Sitting C next to neither A nor B can be done in two ways leaving three ways to seat D.
    So there are a total of twenty-two ways to seat C&D.
    Now seat the rest.
    So what is the answer?
    Last edited by Plato; March 30th 2010 at 07:24 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,547
    Thanks
    539
    Hello, differentiate!

    Eight people: \{ A, B, C, D, E, F, G, H\} sit around a table.
    How many ways can this be done if A must be directly opposite B
    and C cannot sit next to D?

    I had 912. It must be wrong. .
    How do you know?
    I will assume it is a circular table.

    A can sit anywhere; it doesn't matter.
    Then B's seat is already determined.

    So far, we have these 8 chairs with two of them occupied.
    Code:
              A
            /   \
          X       X
          |       |
          X       X
          |       |
          X       X
            \   /
              B


    Remove two of the chairs.
    Place stools between the remaining six chairs.
    Code:
              A
            o   o
          X       X
          o       o
          X       X
            o   o
              B

    Seat C in any of the 6 empty stools.
    Seat D is any of the 5 remaining stools.
    . . There are: . 6\cdot5 \,=\,30 ways.


    Then seat E,F,G,H in the four chairs.
    . . There are: . 4! \,=\,24 ways.


    Therefore, there are: . 30\cdot24 \:=\:720 ways.

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by differentiate View Post
    This is very tricky.

    8 people; A, B, C, D, E, F, G, and H sit around a table. How many ways can this be done if A must be directly opposite to B and C cannot sit next to D?

    I had 912. it must be wrong

    Thanks
    I'm getting a different answer from Soroban's, and since I don't understand his method with the stools, here is my approach.

    Fix A and B and number the other chairs according to the following diagram:
    Code:
                A
            1      6
         2            5
            3     4
               B
    (That's supposed by be a circle, although of course it isn't. You have to use your imagination.)

    If we disregard the restriction on C and D, there are 6! ways to place C-H.

    Let's see if we can count the number of arrangements in which C does sit next to D. We start by placing C. If C is in seat 1, 3, 4, or 6, there is only one place for D to sit and then 4! ways to place E-H. If C is in seat 2 or 5 then there are 2 places for D to sit and then 4! ways to place E-H. So all together there are 4 x 4! + 2 x 2 x 4! = 8 x 4! ways to arrange C-H with C sitting next to D.

    So the number of circular arrangements with A opposite B and C not sitting next to D is

    6! - 8 x 4! = 528.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Dec 2008
    From
    Australia
    Posts
    161
    to be honest, I don't know what the answer is
    I just want to know what you guys think.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,390
    Thanks
    1476
    Awards
    1
    Quote Originally Posted by differentiate View Post
    to be honest, I don't know what the answer is
    I just want to know what you guys think.
    I understand your confusion.
    My edited answer is correct. Both of the other replies have logical mistakes in them.
    Look at the attached diagram. Seating A&B “fixes the table”.
    If we seat C in any of 1,3,4,6 positions we can put D in any of four other positions.
    However, if we seat C in either 2 or 5 then there are only three ways to seat D.
    Therefore, once A&B are seated there are only 22 ways to seat C&D.
    There are four left to be seated. That can be done in 4! ways.
    Attached Thumbnails Attached Thumbnails tricky permutations problem-untitled.gif  
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by Plato View Post
    I understand your confusion.
    My edited answer is correct. Both of the other replies have logical mistakes in them.
    Look at the attached diagram. Seating A&B “fixes the table”.
    If we seat C in any of 1,3,4,6 positions we can put D in any of four other positions.
    However, if we seat C in either 2 or 5 then there are only three ways to seat D.
    Therefore, once A&B are seated there are only 22 ways to seat C&D.
    There are four left to be seated. That can be done in 4! ways.
    Ahem!

    Well, logical mistake or not, Plato and I seem to have arrived at the same number: 22 x 4! = 528.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Tricky (ln) problem
    Posted in the Algebra Forum
    Replies: 3
    Last Post: September 23rd 2011, 01:03 PM
  2. Tricky Problem
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 6th 2009, 05:59 PM
  3. Tricky ODE problem
    Posted in the Calculus Forum
    Replies: 2
    Last Post: September 22nd 2008, 02:17 AM
  4. Replies: 6
    Last Post: March 30th 2008, 10:39 AM
  5. tricky problem please HELP
    Posted in the Calculus Forum
    Replies: 3
    Last Post: November 27th 2006, 02:11 PM

Search Tags


/mathhelpforum @mathhelpforum