AMC 10 Step by Step
Log inSign up

2024 AMC 10B Problem 22

P21-25~5 minPrint
Basic CountingPrimesApply an identity: SFFT, sum of squares, difference of cubes, VietaSet up the equation/formula and compute; no special trick needed

A group of 1616 people will be partitioned into 44 indistinguishable 44 -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 33 . What is rr ?

Log in to save your progress.
Show solution without answering

Key insight

Line up the 16 people, cut the line into four groups of 4, and divide out orders that do not matter. Then count the 3s on top and bottom.

Solution

We only need to know how many factors of 33 the count has, so write the count as a product of simple pieces instead of working out the number.

Step 1: a formula for the count.

1. Line up the 1616 people in a row. There are 16!16! ways.
2. Cut the row into four blocks of 44: people 11–44, 55–88, 99–1212, 1313–1616. In each block, the first person is chairperson, the second is secretary, and the last two are ordinary members.
3. Every lineup gives a valid set of committees, but many lineups give the same one:
- Swapping the two ordinary members in a block changes nothing. That is 22 lineups per block, so 2⋅2⋅2⋅2=242 \cdot 2 \cdot 2 \cdot 2 = 2^4 in all.
- The committees are indistinguishable, so reordering the four blocks changes nothing. That is 4!=244! = 24 lineups.
4. So each set of committees is counted 24⋅4!2^4 \cdot 4! times, and the number of ways is
16!24⋅4!.\frac{16!}{2^4 \cdot 4!}.

Step 2: count the factors of 33.

  1. On top, 16!=1⋅2⋅3⋯1616! = 1 \cdot 2 \cdot 3 \cdots 16. The multiples of 33 are 3,6,9,12,153, 6, 9, 12, 15: five of them, each giving one 33. The number 9=3⋅39 = 3 \cdot 3 gives one extra. So 16!16! has 66 factors of 33.
  2. On the bottom, 242^4 has no 33s, and 4!=24=3⋅84! = 24 = 3 \cdot 8 has one.
  3. So the count has 6−1=56 - 1 = 5 factors of 33, and r=5r = 5.

The answer is (A) 5\boxed{\textbf{(A)}\ 5}.

Why this works

"Line everyone up, then divide out the orders you do not care about" gives the count as a fraction of factorials and small numbers. That form is exactly what you want when the question asks how many times a prime divides the answer. To count the 33s in 16!16!, count the multiples of 33, then add one more for each multiple of 99.

Alternative approach

Build the committees directly. Choose 44 people for a first committee, then 44 of the remaining 1212, then 44 of the remaining 88, and the last 44 are forced. Divide by 4!4! because the committees have no order. This comes to 16!(4!)5\frac{16!}{(4!)^5}. Then choose a chair (44 ways) and a secretary (33 ways) in each committee: 12412^4 more. Count the 33s: 16!16! has 66, (4!)5(4!)^5 has 55, and 12412^4 has 44. So r=6−5+4=5r = 6 - 5 + 4 = 5.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Line the 1616 people up in a row (16!16! ways) and cut the row into four consecutive blocks of 44. In each block, call the first person the chairperson and the second the secretary; the last two are ordinary members.

This overcounts. Swapping the two ordinary members within a block changes nothing, a factor of 22 per block, so 242^4 overall. Reordering the four blocks changes nothing since committees are indistinguishable, a factor of 4!4!. Every assignment arises from exactly 24⋅4!2^4 \cdot 4! lineups, so the number of assignments is
16!24⋅4!.\frac{16!}{2^4 \cdot 4!}.

Now count factors of 33. In 16!16! the multiples of 33 contribute ⌊16/3⌋=5\lfloor 16/3 \rfloor = 5 and the multiple of 99 contributes one more, for 363^6. The denominator has 4!=24=3⋅84! = 24 = 3 \cdot 8, one factor of 33, and 242^4 has none. So
r=6−1=5.r = 6 - 1 = 5.

The answer is (A) 5\boxed{\textbf{(A)}\ 5}.

Review in the AoPS books

Similar problems

Problem © Mathematical Association of America (MAA), American Mathematics Competitions. Reproduced for non-commercial educational use. Solution and commentary are original to this site. Also appeared as 2024 12B #16.