2021 AMC 12A Spring 第 15 题

Question

合唱团指挥必须从他的

6

名男高音和

8

名男低音中选出一组歌手。唯一要求是男高音人数与男低音人数之差必须是

4

的倍数，并且这一组至少有一名歌手。设

N

为可选组数。

N

除以

100

的余数是多少？

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?

47

48

83

95

96

答案：D

知识点：单位根组合二项式定理

难度评级：2060

小提示：

用单位根筛法计数满足

t - b \equiv 0 \pmod 4

的配对

(t, b)

，其中

\omega = i

。

Count pairs

(t, b)

with

t - b \equiv 0 \pmod 4

using a roots of unity filter with

\omega = i

大提示：

计数为

\dfrac14\sum_{j=0}^{3}(1 + i^j)^6(1 + i^{-j})^8

；再减去

1

个空组

The count is

\dfrac14\sum_{j=0}^{3}(1 + i^j)^6(1 + i^{-j})^8;

then subtract

1

for the empty group

解答：

选

t

名男高音和

b

名男低音的权重为

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

。为了只保留

t - b \equiv 0 \pmod 4

，使用

\omega = i

的单位根筛法：

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

j = 0

项为

2^6\cdot 2^8 = 16384

。

j = 2

项含有因子

(1 + i^2)^6 = 0

。

j = 1

和

j = 3

项分别为

-128i

和

128i

，相互抵消。因此总和为

16384

，且

\dfrac{16384}{4} = 4096

。

这个计数包含空组，所以

N = 4096 - 1 = 4095

，因此

N \equiv 95 \pmod{100}

。

因此，正确答案是 D。

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.

2021 AMC 12A Spring 第 15 题

答案：D

难度评级：2060

小提示：

大提示：

解答：

其他年份的第 15 题