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

Solución:

Trabaje en el anillo $\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 $\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

Solución:

El Problema 13 en otros años