Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2017-05-16 17:48:28

samuel.bradley.99
Member
Registered: 2016-03-16
Posts: 51

Seating arrangements

5 Chinese, 5 Russians and 5 Mexicans are sitting in a row in such a way that the Chinese cannot be seated in the first 5 seats, the Russians cannot be seated in the 5 middle seats and the Mexicans cannot be seated in the last 5 seats. In how many different ways can they sit?

Offline

#2 2017-05-26 18:39:49

thickhead
Member
Registered: 2016-04-16
Posts: 1,082

Re: Seating arrangements

I was away from the forum for quite some time.Was busy with Quora. The problem looks very complicated but it is quite simple. Suppose you choose 3 Russians and 2 Mexicans for the first 5 seats,no more choice is left as 2 remaining russians have to go to last 5 and remaining Mexicans have to go to middle 5. the Chinese are also split likewise. after this selection in each group people could be arranged in 5! different ways.

Last edited by thickhead (2017-06-07 18:53:24)


{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

Offline

#3 2017-06-12 20:37:46

thickhead
Member
Registered: 2016-04-16
Posts: 1,082

Re: Seating arrangements

What is cooking? No response from any body including Samuel!


{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

Offline

#4 2017-06-13 01:05:45

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,592

Re: Seating arrangements

Hi thickhead;

I've actually spent quite some hours on this, but I just don't have enough knowledge or understanding in this area to get anywhere with it. Having quit school after flunking 4th-year high school makes it well-nigh impossible for me to tackle something like this mathematically...which a problem of this size really needs.

Anyway, I ignored that and tried to solve it by reducing the OP's 5x3 group to the groups 2x3, 3x3 and 4x3, got each of the 3 groups' permutations, sifted out their incorrect seatings and obtained solutions for those groups (the 4x3 took a lot of effort!!). My plan was to play 'spot the pattern' with that info, but despite seeing lots of factorial content I just couldn't see a common factorial (or other) pattern in those groups that I could use to solve the 5x3 group.

I eventually decided that I'd spent far too much time taking the long route to nowhere, and gave up...and to make sure I didn't return to it (I find it hard to give up on something that I think I have a chance of solving, mind you!), I threw all of my work away.

Sorry, but your solution goes waaay over my head, and so I didn't comment. dizzy


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#5 2017-06-13 11:52:33

samuel.bradley.99
Member
Registered: 2016-03-16
Posts: 51

Re: Seating arrangements

Guys, I am getting 2252 ways...
This is probably wrong I guess...

Offline

#6 2017-06-13 16:27:13

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,592

Re: Seating arrangements

Hi Samuel;

I'd say, from the figures that are still embedded indelibly in my brain after spending so much time on your problem, that 2252 is a fair bit short of the mark.

Your puzzle, without any 'who can't sit where' constraints, has (3x5)! - ie, 1,307,674,368,000 - permutations of different seating arrangements.

Reducing the numbers in each group, I get:
     (3 groups of 2)! = 720 different arrangements, of which 640 are eliminated by the seating constraint, leaving 80 valid arrangements;
     (3 groups of 3)! = 362880 different arrangements, of which 350784 are eliminated by the seating constraint, leaving 12096 valid arrangements.

I got Mathematica to print the permutations, which I pasted into a text editor and did the eliminations there.

The next reduced group, that of 3 groups of 4 people, would give an even larger number of valid arrangements, and your 3 groups of 5 people puzzle would result in something much larger than the 3x4...which thickhead has probably found (not that I can confirm it).


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#7 2017-06-13 18:30:35

samuel.bradley.99
Member
Registered: 2016-03-16
Posts: 51

Re: Seating arrangements

Maybe I need to clarify that all Chinese, Russians and Mexicans are treated equally. Any Chinese can sit in any of their 5 seats etc.
Sorry for not having clarified this earlier; now that I saw your numbers I realised that you have this confusion.

Offline

#8 2017-06-13 23:33:19

thickhead
Member
Registered: 2016-04-16
Posts: 1,082

Re: Seating arrangements

I understand Samuel's point of view.The Chinese among themselves are indistinguishable. Similarly others.It is just like saying 5Cs,5Rs and 5Ms  are to be arranged in 15 slots with the given conditions. let us see in first 5 slots.
(1) 0 russian and 5 Mexicans can be seated in only 1 way. Now  seats 6 to 10 can accommodate 5 Chinese in 1 way and last 5 seats also 1 way. It is 1*1*1=1 way.
(2) 1 russian and 4 Mexicans can be seated in 5 different ways. so 5*5*5=125 ways.
(3)2 russian and 3 Mexicans can be seated in

  different ways. so totally 10*10*10=1000 ways. Continuuing this way we get 1+125+1000+1000+125+1=
ways.

Last edited by thickhead (2017-06-14 03:50:56)


{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

Offline

#9 2017-06-14 02:30:32

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,592

Re: Seating arrangements

Hi;

756756 permutations - 754504 constraints = 2252 different ways.


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#10 2017-06-14 03:23:19

samuel.bradley.99
Member
Registered: 2016-03-16
Posts: 51

Re: Seating arrangements

@Phrontister & thickhead, you are geniuses smile

Offline

#11 2017-06-14 12:06:42

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,592

Re: Seating arrangements

Thanks, Samuel, but thickhead's one, not me. I had to take the non-maths route.

I got Mathematica to work out the permutations and export them to a text file, and then copied the contents into Excel which counted the number of valid seating arrangements.

Mathematica could have done that last bit too, but I didn't know how. If bobbym was still here I'd've asked him, and he would've taught me how immediately!

Mathematica code: Export["seating.txt", Permutations[{c,c,c,c,c,r,r,r,r,r,m,m,m,m,m},{15}]]

Excel:
- Pasted the permutions list from the text file into A1, which Excel automatically populated into A1:A756756.
- Entered this formula into B1: =IF(AND(MID(A1,2,1)<>"c",MID(A1,5,1)<>"c",MID(A1,8,1)<>"c",MID(A1,11,1)<>"c",MID(A1,14,1)<>"c",MID(A1,17,1)<>"r",MID(A1,20,1)<>"r",MID(A1,23,1)<>"r",MID(A1,26,1)<>"r",MID(A1,29,1)<>"r",MID(A1,32,1)<>"m",MID(A1,35,1)<>"m",MID(A1,38,1)<>"m",MID(A1,41,1)<>"m",MID(A1,44,1)<>"m"),1,"")
- Double-clicked on the copy handle to automatically copy the formula down Column B alongside all the permutations in Column A.
- Entered this formula into C1: =SUM(B:B)

C1 output = 2252.

All quite quick, now that you clarified the problem, which shrank it to a manageable size for my method. smile

EDIT: This Mathematica code will give the answer 2252 (a post on mathematica.stackexchange gave me a clue):

Length[DeleteCases[Permutations[{c,c,c,c,c,r,r,r,r,r,m,m,m,m,m},{15}],{___,c,___,_,_,_,_,_,_,_,_,_,_}|{_,_,_,_,_,___,r,___,_,_,_,_,_}|{_,_,_,_,_,_,_,_,_,_,___,m,___}]]

It can be run online at Wolfram Programming Lab, if you don't have Mathematica. Just paste my code over the "2+2" code that appears in program 1 on the opening page, then press the orange/white 'Run input' arrow (or click somewhere in the code and press Shift+Enter).

Last edited by phrontister (2017-06-14 23:11:12)


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#12 2017-06-15 09:43:44

samuel.bradley.99
Member
Registered: 2016-03-16
Posts: 51

Re: Seating arrangements

Thanks also for sharing your work!

Offline

Board footer

Powered by FluxBB