2021 AMC 12A Spring Problema 15

Question

Un director de coro debe seleccionar un grupo de cantantes de entre sus

6

tenores y

8

bajos. Los únicos requisitos son que la diferencia entre el número de tenores y bajos debe ser un múltiplo de

4,

y que el grupo debe tener al menos un cantante. Sea

N

el número de grupos que se pueden seleccionar. ¿Cuál es el residuo cuando

N

se divide entre

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

Respuesta: D

Conceptos:raíces de la unidad combinaciones teorema del binomio

Nivel de dificultad: 2060

Pista pequeña:

Cuenta los pares

(t, b)

con

t - b \equiv 0 \pmod 4

usando un filtro de raíces de la unidad con

\omega = i

.

Count pairs

(t, b)

with

t - b \equiv 0 \pmod 4

using a roots of unity filter with

\omega = i

Pista grande:

El conteo es

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

luego resta

1

por el grupo vacío.

The count is

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

then subtract

1

for the empty group

Solución:

Elegir

t

tenores y

b

bajos tiene peso

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

Para conservar solo

t - b \equiv 0 \pmod 4,

aplica un filtro de raíces de la unidad con

\omega = i:

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

El término

j = 0

es

2^6\cdot 2^8 = 16384.

El término

j = 2

tiene el factor

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

Los términos

j = 1

y

j = 3

son

-128i

y

128i,

que se cancelan. Así que la suma es

16384,

y

\dfrac{16384}{4} = 4096.

Este conteo incluye el grupo vacío, así que

N = 4096 - 1 = 4095,

y

N \equiv 95 \pmod{100}.

Por lo tanto, la respuesta correcta es 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.