Question

对每个小于 $502$ 的非负整数 $r$ ，定义 $S_r = \sum_{m \ge 0} \binom{10{,}000}{502m + r}\text{，}$ 其中当 $n \gt 10{,}000$ 时，规定 $\binom{10{,}000}{n}$ 为 $0$ 。也就是说， $S_r$ 是所有形如 $\binom{10{,}000}{k}$ 的二项式系数之和，其中 $0 \le k \le 10{,}000$ ，且 $k - r$ 是 $502$ 的倍数。

求列表 $S_0$ 、 $S_1$ 、 $S_2$ 、 $\ldots$ 、 $S_{501}$ 中有多少个整数是质数 $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.$

答案

答案：39

知识点：二项式定理模运算多项式

难度评级：3370

小提示：

处理 $(1+x)^{10000}$ ，所在环为 $\mathbb{F}_{503}[x]$ ，并模 $x^{502} - 1$ 化简；此时 $x^r$ 的系数正好变成 $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$

大提示：

利用 $(1+x)^{503} \equiv 1 + x^{503} \equiv 1 + x$ ，把 $(1+x)^{10000}$ 化简为一个次数小于 $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$

解答：

在环 $\frac{\mathbb{F}_{503}[x]}{x^{502} - 1}$ 中工作。把 $(1 + x)^{10000} = \sum_k \binom{10000}{k} x^k$ 化简时，每个指数 $k$ 都替换为 $k \bmod 502$ ，所以 $\begin{aligned} &(1+x)^{10000} \equiv \sum_{r=0}^{501} S_r \, x^r \\ &\pmod{503,\ x^{502} - 1} \end{aligned}\text{。}$

因为 $503$ 是质数， $(1+x)^{503} \equiv$ $1 + x^{503} \pmod{503}$ ，且 $x^{503} = x \cdot x^{502} \equiv x$ ，所以在这个环中 $(1+x)^{503} \equiv 1 + x$ 。写成 $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}\text{。}$ 由于 $462 \lt 502$ ，没有指数折回，所以 $S_r \equiv \binom{462}{r} \pmod{503}$ 对 $0 \le r \le 501$ 都成立，其中 $\binom{462}{r} = 0$ 当 $r \gt 462$ 。

对 $0 \le r \le 462$ ，二项式系数 $\binom{462}{r}$ 不能被 $503$ 整除： $462$ 和 $r$ 在 $503$ 进制中都是一位数，所以 Lucas 定理给出非零值（也可以说 $\binom{462}{r} = \frac{462!}{r!\,(462-r)!}$ 不含因子 $503$ ）。因此 $S_r \equiv 0 \pmod{503}$ 当且仅当 $r = 463, 464, \ldots, 501$ ，共有 $501 - 463 + 1 = 39$ 个值。

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 第 13 题

答案：39

难度评级：3370

小提示：

大提示：

解答：

其他年份的第 13 题