The Fiberglass Menagerie

My daughter has started a zoo on our refrigerator door. She has 20 animals, and wants to put them in cages, with an equal number of animals in each cage. (She's not concerned about some animals eating others; she assures me they're all vegetarians.) Which arrangement will afford her the greatest number of possible groupings of the animals?

Assume that the cages themselves are indistinguishable. So the same grouping of animals placed in different cages would not be considered a different grouping.

Two cages, 10 animals per cage Ten cages, 2 animals per cage Four cages, 5 animals per cage Five cages, 4 animals per cage

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Matt Enlow
Mar 24, 2014

The number of ways that n objects can be split into k groups of n k \frac{n}{k} objects each is

n ! ( ( n k ) ! ) k k ! . \frac{n!}{\left(\left(\frac{n}{k}\right)!\right)^k k!}.

So the question boils down to which of the following is greatest:

20 ! ( 10 ! ) 2 2 ! , 20 ! ( 5 ! ) 4 4 ! , 20 ! ( 4 ! ) 5 5 ! , 20 ! ( 2 ! ) 10 10 ! . \frac{20!}{\left(10!\right)^2 2!}, \quad \frac{20!}{\left(5!\right)^4 4!}, \quad \frac{20!}{\left(4!\right)^5 5!}, \quad \frac{20!}{\left(2!\right)^{10} 10!}.

Equivalently, we just need to determine which of

( 10 ! ) 2 2 ! , ( 5 ! ) 4 4 ! , ( 4 ! ) 5 5 ! , ( 2 ! ) 10 10 ! \left(10!\right)^2 2!, \quad \left(5!\right)^4 4!, \quad \left(4!\right)^5 5!, \quad \left(2!\right)^{10} 10!

is the least. So to do this, we'll compare them in pairs, then compare the lesser of each pair. Since

( 4 ! ) 5 5 ! ( 5 ! ) 4 4 ! = 4 ! 4 ! 4 ! 4 ! 4 ! 5 ! 5 ! 5 ! 5 ! 5 ! 4 ! = 4 ! 5 3 = 24 125 , \frac{(4!)^5 5!}{(5!)^4 4!}=\frac{4!4!4!4!4!5!}{5!5!5!5!4!}=\frac{4!}{5^3}=\frac{24}{125},

this tells us that ( 4 ! ) 5 5 ! < ( 5 ! ) 4 4 ! (4!)^5 5!<(5!)^4 4! . And since

( 2 ! ) 10 10 ! ( 10 ! ) 2 2 ! = 2 9 10 ! = 2 2 2 2 2 2 2 2 2 10 9 8 7 6 5 4 3 2 , \frac{(2!)^{10} 10!}{(10!)^2 2!}=\frac{2^9}{10!}=\frac{2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2}{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2},

it's clear that ( 2 ! ) 10 10 ! < ( 10 ! ) 2 2 ! (2!)^{10} 10!<(10!)^2 2! . Now for the finals!

( 4 ! ) 5 5 ! ( 2 ! ) 10 10 ! = 4 5 3 5 2 5 1 5 5 ! 2 5 2 5 10 ! = 2 5 3 5 5 ! 10 ! = 6 6 6 6 6 10 9 8 7 6 , \frac{(4!)^5 5!}{(2!)^{10} 10!}=\frac{4^5 3^5 2^5 1^5 5!}{2^5 2^5 10!}=\frac{2^5 3^5 5!}{10!}=\frac{6 \cdot 6 \cdot 6 \cdot 6 \cdot 6}{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6},

so ( 4 ! ) 5 5 ! (4!)^5 5! is the least, which means that 20 ! ( 4 ! ) 5 5 ! \frac{20!}{(4!)^5 5!} is the greatest. So the answer is Five cages, 4 animals per cage \boxed{\text{Five cages, 4 animals per cage}} .

Reading with understanding. I thought that it was meant to have the biggest ammount of animals per cage. -_-

Pola Forest - 7 years, 2 months ago

Log in to reply

me too!

robin tod - 7 years, 2 months ago

Matt, how did you arrive at ( ( n k ) ! ) k ( (\frac{n}{k})! ) ^ k ?

Neeraj T - 7 years, 2 months ago

Log in to reply

I think it might be easiest to use specific values, rather than n and k . Then you might see how it would generalize.

Suppose we want to count the number of ways to divide 20 animals into five cages, with four animals in each cage. We have the 20 animals in front of us. How many ways can we choose four animals for our first cage? ( 20 4 ) {20 \choose 4} . Then, to make our second cage, we choose 4 animals from the 16 remaining, and there are ( 16 4 ) {16 \choose 4} ways to do that. Then there are 12 animals remaining from which to make the third cage... and so on. So at first the answer appears to be

( 20 4 ) ( 16 4 ) ( 12 4 ) ( 8 4 ) ( 4 4 ) . {20 \choose 4}{16 \choose 4}{12 \choose 4}{8 \choose 4}{4 \choose 4}.

I'll simplify this expression first, then explain why it's not complete. The above expression simplifies to

20 ! 16 ! 4 ! 16 ! 12 ! 4 ! 12 ! 8 ! 4 ! 8 ! 4 ! 4 ! 4 ! 0 ! 4 ! , \frac{20!}{16!4!}\frac{16!}{12!4!}\frac{12!}{8!4!}\frac{8!}{4!4!}\frac{4!}{0!4!},

which you can see reduces to 20 ! ( 4 ! ) 5 \frac{20!}{(4!)^5} .

But we have over-counted! We're assuming the cages are identical, so our taking into account the order in which we made each cage resulted in our counting each distinct grouping 5 ! = 120 5!=120 times (the number of ways you could order the five cages). So we then need to divide our result by 5 ! 5! :

20 ! ( 4 ! ) 5 5 ! \frac{20!}{(4!)^5 5!}

So to answer your original question, the ( ( n k ) ! ) k ((\frac{n}{k})!)^k in this example is the ( 4 ! ) 5 (4!)^5 . I hope this helped!

Matt Enlow - 7 years, 2 months ago

what does ! sign mean dude ?

Rishabh Tripathi - 7 years, 2 months ago

Log in to reply

For any positive integer n ,

n ! : = n ( n 1 ) ( n 2 ) ( n 3 ) 3 2 1. n!:=n(n-1)(n-2)(n-3)\ldots 3 \cdot 2 \cdot 1.

Matt Enlow - 7 years, 2 months ago

that is factorial

Lexter Natividad - 7 years, 2 months ago

yay ! i solved it :)

Shreya Shankar - 7 years, 2 months ago

dont we need to arrange groups in cages by multiplying with k!

Yash Bhadauria - 7 years, 2 months ago

guess

math dude - 7 years, 2 months ago

Nice one! I have a same problem about this, but for k = 2.

My problem will become easy for now. *sobs

Can Cinderella avoid dancing with her stepfamily?

Samuraiwarm Tsunayoshi - 7 years, 2 months ago

very good answer sir matt enlow

waqas khan - 7 years, 2 months ago

(y)

Prince Sean - 7 years, 1 month ago

Well...I assumed the cages to be different as nothing about it was mentioned about it...through that you get the answer to be 2 animals in 10 cages ...is that right??

Tanya Gupta - 7 years, 2 months ago

Log in to reply

Yes, if the cages are distinguishable from each other, then the correct answer would be 10 cages, 2 animals per cage. (I added a clarification to the problem--Thank you!)

Matt Enlow - 7 years, 2 months ago

Log in to reply

You r welcome...thanx for clearing it up anyway!!

Tanya Gupta - 7 years, 2 months ago

Yea.. I did that too.. I attempted 2 animals, 10 cages. :/ but I understand the mistake now.

Mythreyi Ramesh - 7 years, 2 months ago

Log in to reply

It happens :D

Tanya Gupta - 7 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...