Maths Olympiad Prep

Library / /17 of 18

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!4434(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=105=5r = 10 - 5 = 5.

OR

There are 161516 \cdot 15 ways to choose the chairperson and secretary of the first committee, 141314 \cdot 13 ways to choose the chairperson and secretary of the second committee, 121112 \cdot 11 ways to choose the chairperson and secretary of the third committee, and 10910 \cdot 9 ways to choose the chairperson and secretary of the fourth committee. There are then 872=28\frac{8 \cdot 7}{2} = 28 ways to choose the remaining members of the first committee, 652=15\frac{6 \cdot 5}{2} = 15 ways to choose the remaining members of the second committee, 432=6\frac{4 \cdot 3}{2} = 6 ways to choose the remaining members of the third committee, and 212=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
1615141312111092815614! \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=61=5r = 6 - 1 = 5.

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

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