2021 AMC 12A Problem 15

Problem 15 of 25IntermediateAlgebra Combinatorics

A choir director must select a group of singers from among his

6

tenors and

8

basses. The only requirements are that the difference between the number of tenors and basses must be a multiple of

4,

and the group must have at least one singer. Let

N

be the number of groups that can be selected. What is the remainder when

N

is divided by

100?

Show solution

Solution

Choosing

t

tenors and

b

basses is weighted by

\binom{6}{t}\binom{8}{b}.

To keep only

t - b \equiv 0 \pmod 4,

apply a roots of unity filter with

\omega = i:

\begin{aligned} &N + 1 \\ &= \frac14\sum_{j=0}^{3}(1 + i^{j})^6\,(1 + i^{-j})^8. \end{aligned}

The

j = 0

term is

2^6\cdot 2^8 = 16384.

The

j = 2

term has factor

(1 + i^2)^6 = 0.

The

j = 1

and

j = 3

terms are

-128i

and

128i,

which cancel. So the sum is

16384,

and

\dfrac{16384}{4} = 4096.

This count includes the empty group, so

N = 4096 - 1 = 4095,

and

N \equiv 95 \pmod{100}.

Thus, the correct answer is D.

Tagged: roots of unity · combinations · binomial theorem