Maths Olympiad Prep

Library / AMC 10 B /14 of 14

AMC 10 B

Combinatorics Difficulty 5.8 AIME, harder Find the answer United States

A group of 16 people will be partitioned into 4 indistinguishable 4-person committees. Each committee will have one chairperson and one secretary. The number of different ways to make these assignments can be written as 3rM3^r M, where rr and MM are positive integers and MM is not divisible by 3. What is rr?

Pick one

Solution

The 16 people can be partitioned into the 4 committees, each of size 4, in
16!(4!)5 \frac{16!}{(4!)^5}
ways; four of the 4!4! factors come from permuting the members of the committees and one 4!4! factor comes from permuting the committees. Then there are 444^4 ways to choose the four chairpersons and 343^4 ways to choose the four secretaries. This gives a total of
16!⋅44⋅34(4!)5 \frac{16! \cdot 4^4 \cdot 3^4}{(4!)^5}
assignments. The numerator has 1 factor of 3 in each of 15, 12, 6, and 3; it has 2 factors of 3 in 9 and 4 factors in 343^4, a total of 10. The denominator has 5 factors of 3. Thus r=10−5=5r = 10 - 5 = 5.

OR

There are 16⋅1516 \cdot 15 ways to choose the chairperson and secretary of the first committee, 14⋅1314 \cdot 13 ways to choose the chairperson and secretary of the second committee, 12⋅1112 \cdot 11 ways to choose the chairperson and secretary of the third committee, and 10⋅910 \cdot 9 ways to choose the chairperson and secretary of the fourth committee. There are then 8⋅72=28\frac{8 \cdot 7}{2} = 28 ways to choose the remaining members of the first committee, 6⋅52=15\frac{6 \cdot 5}{2} = 15 ways to choose the remaining members of the second committee, 4⋅32=6\frac{4 \cdot 3}{2} = 6 ways to choose the remaining members of the third committee, and 2⋅12=1\frac{2 \cdot 1}{2} = 1 way to choose the remaining members of the fourth committee. There are 4!4! ways to account for the fact that the committees are indistinguishable. This gives a total of
16⋅15⋅14⋅13⋅12⋅11⋅10⋅9⋅28⋅15⋅6⋅14! \frac{16 \cdot 15 \cdot 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 28 \cdot 15 \cdot 6 \cdot 1}{4!}
assignments. There are 1+1+2+1+1=61 + 1 + 2 + 1 + 1 = 6 factors of 3 in the numerator and 1 factor of 3 in the denominator, so r=6−1=5r = 6 - 1 = 5.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.