wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> King Arthur
        
(Message started by: FiBsTeR on Sep 5^th, 2007, 6:43pm)

Title: King Arthur
Post by FiBsTeR on Sep 5^th, 2007, 6:43pm

Sorry if my English isn't gangster-ized (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1088326720)...

Anyway, this was a warm-up problem I had in my discrete math class today:

King Arthur and his twelve knights are to be seated around the Round Table, but they lost the seating arrangement chart. Two seating arrangements are the same iff each person is sitting next to the same two people in both arrangements.

a) How many different seating arrangements are there?

b) If King Arthur has a special seat to himself, how many different seating arrangements are there?

Title: Re: King Arthur
Post by Sameer on Sep 5^th, 2007, 7:23pm

1) [hide] Its a free circular permutation (n-1)!/2. In this case 12!/2 [/hide]

My permutation is little weak

2) [hide] I think if we fixed 1 seat, so it will be 11!/2. Not sure about it though!! [/hide]

Title: Re: King Arthur
Post by SMQ on Sep 6^th, 2007, 8:16am

Are mirrored arrangements considered the same? Each person is sitting next to the same people, but on opposite sides.

If not: 1) [hide]total permutations of seats divided by number of seats (because rotations around the table are the same) = 13!/13 = 12![/hide] 2) [hide]total number of permutations of knight's seats (rotations are no longer the same) = 12![/hide]. If mirrored arrangements are the same, divide each of the above by two to account for the symmetry. In either case [hide]there's no difference whether or not King Arthur's seat is fixed![/hide]

--SMQ

Title: Re: King Arthur
Post by rmsgrey on Sep 6^th, 2007, 9:37am

on 09/06/07 at 08:16:58, SMQ wrote:

In either case [hide]there's no difference whether or not King Arthur's seat is fixed![/hide]

Which is unsurprising if you think about it - [hide]when Arthur's seat isn't fixed, you can always rotate the table so he's in the same place without changing to a different seating arrangement.[/hide]

Title: Re: King Arthur
Post by FiBsTeR on Sep 6^th, 2007, 3:05pm

Your second part is correct, SMQ; mirrored arrangements are considered the same by the definition I gave in the problem.

If anyone has any problems seeing why the answer does not change when "restricting" the King's seat, notice that you can think of the second question (b) as lining up the knights after the King's seat; the problem thereby loses its "circular" properties.