2024 AMC 10B Problem 22

Question

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

3^r M,

where

r

and

M

are positive integers and

M

is not divisible by

3.

What is

r?

5

6

7

8

9

Answer: A

Concepts:combinations Legendre’s Formula prime factorization

Difficulty rating: 2120

Small hint:

The number of ways is

\dfrac{16!}{(4!)^4 \cdot 4!} \cdot (4 \cdot 3)^4,

the partition count times chair/secretary choices per committee

Big hint:

Count factors of

3

in each piece using Legendre’s formula on

16!

and

4!

Solution:

Split

16

people into

4

indistinguishable groups of

4

in

\dfrac{16!}{(4!)^4 \, 4!}

ways, then each committee picks a chairperson and a secretary in

4 \cdot 3 = 12

ways, a factor of

12^4.

Now count factors of

3.

In

16!

there are

\lfloor \frac{16}{3} \rfloor + \lfloor \frac{16}{9} \rfloor = 6;

the denominator

(4!)^4 \, 4!

contributes

4 \cdot 1 + 1 = 5;

and

12^4