Question

Para cada entero no negativo

r

menor que

502,

defina

S_r = \sum_{m \ge 0} \binom{10{,}000}{502m + r},

donde

\binom{10{,}000}{n}

se define como

0

cuando

n \gt 10{,}000.

Es decir,

S_r

es la suma de todos los coeficientes binomiales de la forma

\binom{10{,}000}{k}

para los cuales

0 \le k \le 10{,}000

y

k - r

es múltiplo de

502.

Halle el número de enteros en la lista

S_0,

S_1,

S_2,

\ldots,

S_{501}

que son múltiplos del número primo

503.

For each nonnegative integer

r

less than

502

define

S_r = \sum_{m \ge 0} \binom{10{,}000}{502m + r},

where

\binom{10{,}000}{n}

is defined to be

0

when

n \gt 10{,}000.

That is,

S_r

is the sum of all the binomial coefficients of the form

\binom{10{,}000}{k}

for which

0 \le k \le 10{,}000

and

k - r

is a multiple of

502.

Find the number of integers in the list

S_0,

S_1,

S_2,

\ldots,

S_{501}

that are multiples of the prime number

503.

Respuesta

Respuesta: 39

Conceptos:teorema del binomio aritmética modular polinomio

Nivel de dificultad: 3370

Pista pequeña:

Trabaje con

(1+x)^{10000}

en

\mathbb{F}_{503}[x]

módulo

x^{502} - 1,

donde el coeficiente de

x^r

se convierte exactamente en

S_r

Work with

(1+x)^{10000}

in

\mathbb{F}_{503}[x]

modulo

x^{502} - 1,

where the coefficient of

x^r

becomes exactly

S_r

Pista grande:

Use

(1+x)^{503} \equiv 1 + x^{503} \equiv 1 + x

para colapsar

(1+x)^{10000}

a una potencia de grado menor que

502

Use

(1+x)^{503} \equiv 1 + x^{503} \equiv 1 + x

to collapse

(1+x)^{10000}

to a power of degree less than

502

Solución:

Trabaje en el anillo

\frac{\mathbb{F}_{503}[x]}{x^{502} - 1}.

Al reducir

(1 + x)^{10000} = \sum_k \binom{10000}{k} x^k

se reemplaza cada exponente

k

por

k \bmod 502,

así que

\begin{aligned} &(1+x)^{10000} \equiv \sum_{r=0}^{501} S_r \, x^r \\ &\pmod{503,\ x^{502} - 1}. \end{aligned}

Como

503

es primo,

(1+x)^{503} \equiv

1 + x^{503} \pmod{503},

y

x^{503} = x \cdot x^{502} \equiv x,

así que

(1+x)^{503} \equiv 1 + x

en este anillo. Escribiendo

10000 = 19 \cdot 503 + 443,

\begin{aligned} &(1+x)^{10000} \\ &= \left((1+x)^{503}\right)^{19} \\ &\quad {}\cdot (1+x)^{443} \\ &\equiv (1+x)^{19} \\ &\quad {}\cdot (1+x)^{443} \\ &= (1+x)^{462}. \end{aligned}

Como

462 \lt 502,

ningún exponente se pliega, así que

S_r \equiv \binom{462}{r} \pmod{503}

para

0 \le r \le 501,

donde

\binom{462}{r} = 0

para

r \gt 462.

Para

0 \le r \le 462

el coeficiente binomial

\binom{462}{r}

no es divisible por

503:

tanto

462

como

r

son dígitos únicos en base

503,

así que el teorema de Lucas da un valor no nulo (de hecho

\binom{462}{r} = \frac{462!}{r!\,(462-r)!}

no involucra ningún factor de

503

). Por lo tanto

S_r \equiv 0 \pmod{503}

exactamente para

r = 463, 464, \ldots, 501,

que son

501 - 463 + 1 = 39

valores.

Work in the ring

\frac{\mathbb{F}_{503}[x]}{x^{502} - 1}.

Reducing

(1 + x)^{10000} = \sum_k \binom{10000}{k} x^k

replaces each exponent

k

by

k \bmod 502,

so

\begin{aligned} &(1+x)^{10000} \equiv \sum_{r=0}^{501} S_r \, x^r \\ &\pmod{503,\ x^{502} - 1}. \end{aligned}

Since

503

is prime,

(1+x)^{503} \equiv

1 + x^{503} \pmod{503},

and

x^{503} = x \cdot x^{502} \equiv x,

so

(1+x)^{503} \equiv 1 + x

in this ring. Writing

10000 = 19 \cdot 503 + 443,

\begin{aligned} &(1+x)^{10000} \\ &= \left((1+x)^{503}\right)^{19} \\ &\quad {}\cdot (1+x)^{443} \\ &\equiv (1+x)^{19} \\ &\quad {}\cdot (1+x)^{443} \\ &= (1+x)^{462}. \end{aligned}

As

462 \lt 502,

no exponents fold, so

S_r \equiv \binom{462}{r} \pmod{503}

for

0 \le r \le 501,

where

\binom{462}{r} = 0

for

r \gt 462.

For

0 \le r \le 462

the binomial coefficient

\binom{462}{r}

is not divisible by

503:

both

462

and

r

are single digits in base

503,

so Lucas’ theorem gives a nonzero value (indeed

\binom{462}{r} = \frac{462!}{r!\,(462-r)!}

involves no factor of

503

). Hence

S_r \equiv 0 \pmod{503}

exactly for

r = 463, 464, \ldots, 501,

which is

501 - 463 + 1 = 39

values.

2026 AIME I Problema 13

Respuesta: 39

Nivel de dificultad: 3370

Pista pequeña:

Pista grande:

Solución:

El Problema 13 en otros años