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 题