2026 AIME I 详解 | LIVE by Po-Shen Loh

1.

Patrick 从学校沿一条笔直的路以恒定速度步行去公园。Patrick 出发一小时后，Tanya 从学校沿同一条笔直的路以恒定速度跑向公园，速度比 Patrick 步行快每小时 $2$ 英里。Tanya 出发一小时后，José 从学校沿同一条笔直的路以恒定速度骑车去公园，速度比 Tanya 跑步快每小时 $7$ 英里。三人同时到达公园。学校到公园的距离是 $\frac{m}{n}$ 英里，其中 $m$ 和 $n$ 为互质正整数。求 $m + n$ 。

Patrick started walking at a constant speed along a straight road from his school to the park. One hour after Patrick left, Tanya started running at a constant speed of $2$ miles per hour faster than Patrick walked, following the same straight road from the school to the park. One hour after Tanya left, José started bicycling at a constant speed of $7$ miles per hour faster than Tanya ran, following the same straight road from the school to the park. All three people arrived at the park at the same time. The distance from the school to the park is $\frac{m}{n}$ miles, where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

答案

知识点：路程、速度与时间方程组

难度评级：1840

小提示：

设 Patrick 的速度为 $v$ ，行程时间为 $T$ 小时；三人走过的距离相同

Let Patrick’s speed be $v$ and his travel time $T$ hours; all three cover the same distance

大提示：

在 $vT = (v+2)(T-1)$ 和 $vT = (v+9)(T-2)$ 中， $vT$ 项会相消，留下关于 $v$ 和 $T$ 的两个一次方程

In $vT = (v+2)(T-1)$ and $vT = (v+9)(T-2),$ the $vT$ terms cancel, leaving two linear equations in $v$ and $T$

解答：

设 Patrick 的速度为每小时 $v$ 英里，行程时间为 $T$ 小时。于是 Tanya 用 $T - 1$ 小时以速度 $v + 2$ 行进，José 用 $T - 2$ 小时以速度 $v + 9$ 行进（这比 Tanya 的速度多 $7$ ）。因为三人走过同一段距离， $\begin{aligned} vT &= (v+2)(T-1) \\ &= (v+9)(T-2) \end{aligned}\text{。}$

展开第一个等式得 $0 = 2T - v - 2$ ，所以 $v = 2T - 2$ 。展开第二个等式得 $0 = 9T - 2v - 18$ ，所以 $2v = 9T - 18$ 。代入可得 $4T - 4 = 9T - 18$ ，因此 $T = \frac{14}{5}$ ，且 $v = \frac{18}{5}$ 。

距离为 $vT = \frac{18}{5} \cdot \frac{14}{5} = \frac{252}{25}$ ，已经是最简分数，所以 $m + n = 252 + 25 = 277$ 。

Let $v$ be Patrick’s speed in miles per hour and $T$ his travel time in hours. Then Tanya travels for $T - 1$ hours at speed $v + 2,$ and José travels for $T - 2$ hours at speed $v + 9$ (which is $7$ more than Tanya’s speed). Since all three cover the same distance, $\begin{aligned} vT &= (v+2)(T-1) \\ &= (v+9)(T-2). \end{aligned}$

Expanding the first equality gives $0 = 2T - v - 2,$ so $v = 2T - 2.$ Expanding the second gives $0 = 9T - 2v - 18,$ so $2v = 9T - 18.$ Substituting, $4T - 4 = 9T - 18,$ hence $T = \frac{14}{5}$ and $v = \frac{18}{5}.$

The distance is $vT = \frac{18}{5} \cdot \frac{14}{5} = \frac{252}{25},$ which is in lowest terms, so $m + n = 252 + 25 = 277.$

2.

求 $10$ 进制表示中不含数字零、各位数字和为 $13$ 的正整数回文数的个数。例如， $42124$ 满足这些性质。回顾一下，回文数是从左到右读和从右到左读表示都相同的数。

Find the number of positive integer palindromes written in base $10,$ with no zero digits, and whose digits add up to $13.$ For example, $42124$ has these properties. Recall that a palindrome is a number whose representation reads the same from left to right as from right to left.

答案

知识点：回文数数字分拆与有序分拆奇偶性

难度评级：2110

小提示：

数字和 $13$ 为奇数，所以回文数有奇数位，且中间数字为奇数

A digit sum of $13$ is odd, so the palindrome has an odd number of digits and an odd middle digit

大提示：

若中间数字为 $m$ ，则它左侧的数字组成一个非零数字串，数字和为 $\frac{13-m}{2}$ ；计数组合

If the middle digit is $m,$ the digits to its left form a string of nonzero digits with sum $\frac{13-m}{2};$ count compositions

解答：

偶数位回文数的每个数字都会成镜像对出现，所以数字和为偶数。由于 $13$ 是奇数，回文数必须有奇数位；若 $m$ 是中间数字，则剩余数字和 $13 - m$ 平均分到两侧，所以 $m$ 为奇数。一位回文数需要 $m = 13$ ，这不可能。

这个回文数由中间数字 $m$ 和中心左侧的数字块决定：这是一个非空的非零数字串，数字和为 $s = \frac{13 - m}{2}$ 。当 $m = 1, 3, 5, 7, 9$ 时，分别有 $s = 6, 5, 4, 3, 2$ 。由于 $s \le 6$ ，这样的数字串中每个数字自动不超过 $9$ ，所以字符串个数就是 $s$ 的正整数拆分成有序部分的个数，即 $2^{s-1}$ （在 $s - 1$ 个单位间隙中，每个间隙选择断开或不断开）。

总数为 $\begin{aligned} &2^{5} + 2^{4} + 2^{3} + 2^{2} + 2^{1} \\ &= 32 + 16 + 8 + 4 + 2 \\ &= 62 \end{aligned}\text{。}$

A palindrome with an even number of digits has each digit appearing in a mirrored pair, so its digit sum is even. Since $13$ is odd, the palindrome has an odd number of digits, and if $m$ is the middle digit, the rest of the digit sum $13 - m$ is split evenly between the two halves, so $m$ is odd. A one-digit palindrome would need $m = 13,$ which is impossible.

The palindrome is determined by its middle digit $m$ and the block of digits to the left of center: a nonempty string of nonzero digits with sum $s = \frac{13 - m}{2}.$ For $m = 1, 3, 5, 7, 9$ we get $s = 6, 5, 4, 3, 2.$ Since $s \le 6,$ every digit of such a string is automatically at most $9,$ so the number of strings is the number of compositions of $s,$ which is $2^{s-1}$ (each of the $s - 1$ gaps between units is either a break or not).

The total is $\begin{aligned} &2^{5} + 2^{4} + 2^{3} + 2^{2} + 2^{1} \\ &= 32 + 16 + 8 + 4 + 2 \\ &= 62. \end{aligned}$

3.

一个半径为 $200$ 的半球放在一个半径为 $200$ 的水平圆盘上，且半球与圆盘同心。令 $\mathcal{T}$ 为圆盘中所有点 $P$ 组成的区域，使得一个半径为 $42$ 的球可以放在圆盘上并在点 $P$ 处接触圆盘，同时完全位于半球内部。 $\mathcal{T}$ 的面积除以圆盘面积为 $\frac{p}{q}$ ，其中 $p$ 和 $q$ 为互质正整数。求 $p + q$ 。

A hemisphere with radius $200$ sits on top of a horizontal circular disk with radius $200,$ and the hemisphere and disk have the same center. Let $\mathcal{T}$ be the region of points $P$ in the disk such that a sphere of radius $42$ can be placed on top of the disk at $P$ and lie completely inside the hemisphere. The area of $\mathcal{T}$ divided by the area of the disk is $\frac{p}{q},$ where $p$ and $q$ are relatively prime positive integers. Find $p + q.$

答案

知识点：球立体几何圆面积平方差

难度评级：2180

小提示：

小球半径为 $42$ ，其球心位于 $P$ 正上方；它正好能放入半球内，当且仅当球心到公共球心的距离不超过 $200 - 42$

The small sphere’s center sits $42$ directly above $P,$ and the sphere fits inside the hemisphere exactly when its center is within $200 - 42$ of the common center

大提示：

若 $d$ 是圆盘中心到 $P$ 的距离，则条件是 $d^2 + 42^2 \le 158^2$ ，而 $158^2 - 42^2$ 可用平方差分解

With $d$ the distance from the center of the disk to $P,$ the condition is $d^2 + 42^2 \le 158^2,$ and $158^2 - 42^2$ factors as a difference of squares

解答：

一个半径为 $42$ 、球心位于 $P$ 正上方 $42$ 处的球，会在 $P$ 处接触圆盘。它完全位于半径为 $200$ 的半球内，当且仅当球心到公共中心的距离不超过 $200 - 42 = 158$ 。记公共中心为 $O$ 。若 $d$ 是 $O$ 到 $P$ 的距离，则小球球心到中心的距离为 $\sqrt{d^2 + 42^2}$ ，也就是它到 $O$ 的距离，所以条件为 $d^2 + 42^2 \le 158^2$ 。

由平方差， $d^2 \le 158^2 - 42^2$ $= 116 \cdot 200$ $= 23200$ 。因此 $\mathcal{T}$ 是半径为 $\sqrt{23200}$ 的圆盘，面积比为 $\frac{23200}{200^2} = \frac{23200}{40000} = \frac{29}{50}\text{。}$ 所以 $p + q = 29 + 50 = 79$ 。

A sphere of radius $42$ resting on the disk at $P$ has its center $42$ directly above $P.$ It lies inside the hemisphere of radius $200$ exactly when its center is within $200 - 42 = 158$ of the common center $O.$ If $d$ is the distance from $O$ to $P,$ the center of the sphere is at distance $\sqrt{d^2 + 42^2}$ from $O,$ so the condition is $d^2 + 42^2 \le 158^2.$

By difference of squares, $d^2 \le 158^2 - 42^2$ $= 116 \cdot 200$ $= 23200.$ Thus $\mathcal{T}$ is a disk of radius $\sqrt{23200},$ and the ratio of areas is $\frac{23200}{200^2} = \frac{23200}{40000} = \frac{29}{50}.$ Therefore $p + q = 29 + 50 = 79.$

4.

求不超过 $100$ 的整数中，有多少个可以写成 $a + b + ab$ ，其中 $a$ 和 $b$ 是两个不同的正整数。

Find the number of integers less than or equal to $100$ that are equal to $a + b + ab$ for some choice of distinct positive integers $a$ and $b.$

答案

知识点：西蒙最爱的因式分解技巧补集计数质数

难度评级：2300

小提示：

两边加 $1$ ： $a + b + ab + 1 = (a+1)(b+1)$

Add $1$ to both sides: $a + b + ab + 1 = (a+1)(b+1)$

大提示：

因此 $n$ 可行当且仅当 $n + 1$ 是两个不同因数的乘积，且每个因数至少为 $2$ ；从 $2$ 到 $101$ 中去掉质数和质数的平方

So $n$ works exactly when $n + 1$ is a product of two distinct factors, each at least $2;$ remove the primes and the squares of primes from $2$ through $101$

解答：

因为 $a + b + ab = (a+1)(b+1) - 1$ ，整数 $n$ 可表示当且仅当 $n + 1 = xy$ ，其中 $x = a + 1$ 和 $y = b + 1$ 是不同整数且都至少为 $2$ 。所以我们统计 $n + 1$ 在集合 $\{2, 3, \ldots, 101\}$ 中且能如此分解的情形。

质数不能分解成两个都至少为 $2$ 的因数；质数平方 $p^2$ 只能这样分解为 $p \cdot p$ ，但这不允许。其余每个合数 $M$ 都可行：若 $p$ 是它的最小质因数，则 $M = p \cdot \frac{M}{p}$ ，且有 $\frac{M}{p} \gt p$ ，因为 $M \gt p^2$ 。在 $\{2, \ldots, 101\}$ 中有 $26$ 个质数，其中 $25$ 个小于 $100$ ，另一个是 $101$ ；另有 $4$ 个质数平方，即 $4$ 、 $9$ 、 $25$ 、 $49$ 。

个数为 $100 - 26 - 4 = 70$ 。

Since $a + b + ab = (a+1)(b+1) - 1,$ an integer $n$ is representable exactly when $n + 1 = xy$ for distinct integers $x = a + 1$ and $y = b + 1$ that are each at least $2.$ So we count integers $n + 1$ in $\{2, 3, \ldots, 101\}$ that admit such a factorization.

A prime has no factorization into two factors that are both at least $2,$ and the square of a prime $p^2$ factors that way only as $p \cdot p,$ which is not allowed. Every other composite $M$ works: if $p$ is its smallest prime factor, then $M = p \cdot \frac{M}{p}$ with $\frac{M}{p} \gt p$ since $M \gt p^2.$ In $\{2, \ldots, 101\}$ there are $26$ primes (the $25$ primes below $100,$ together with $101$ ) and $4$ prime squares ( $4,$ $9,$ $25,$ $49$ ).

The count is $100 - 26 - 4 = 70.$

5.

平面中有点 $A$ 和 $B$ ，且 $AB = 1$ 。将点 $A$ 在平面中逆时针旋转一个锐角 $\theta$ ，旋转中心为点 $B$ ，得到点 $A'$ 。然后将点 $B$ 在平面中顺时针旋转角 $\theta$ ，旋转中心为点 $A'$ ，得到点 $B'$ 。已知 $AB' = \frac{4}{3}$ 。 $\cos\theta$ 可写成 $\frac{m}{n}$ ，其中 $m$ 和 $n$ 为互质正整数。求 $m + n$ 。

A plane contains points $A$ and $B$ with $AB = 1.$ Point $A$ is rotated in the plane counterclockwise through an acute angle $\theta$ around point $B$ to point $A'.$ Then $B$ is rotated in the plane clockwise through angle $\theta$ around point $A'$ to point $B'.$ Suppose $AB' = \frac{4}{3}.$ The value of $\cos\theta$ can be written as $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

答案

知识点：复数变换三角学

难度评级：2400

小提示：

在复平面中令 $B = 0$ 、 $A = 1$ ；把 $z$ 绕 $P$ 逆时针旋转 $\varphi$ 得 $P + e^{i\varphi}(z - P)$

Put $B = 0$ and $A = 1$ in the complex plane; rotating $z$ about $P$ through $\varphi$ counterclockwise gives $P + e^{i\varphi}(z - P)$

大提示：

计算得 $B' = e^{i\theta} - 1$ ，所以 $AB'^2 = \left|e^{i\theta} - 2\right|^2 = 5 - 4\cos\theta$

Compute $B' = e^{i\theta} - 1,$ so $AB'^2 = \left|e^{i\theta} - 2\right|^2 = 5 - 4\cos\theta$

解答：

在复平面中令 $B = 0$ 、 $A = 1$ 。把 $z$ 绕 $P$ 逆时针旋转角 $\varphi$ 得 $P + e^{i\varphi}(z - P)$ 。因此 $A' = e^{i\theta}$ ，而把 $B$ 顺时针旋转 $\theta$ ，旋转中心为 $A'$ ，得到 $\begin{aligned} &B' = A' + e^{-i\theta}(0 - A') \\ &= e^{i\theta} - e^{-i\theta}e^{i\theta} \\ &= e^{i\theta} - 1 \end{aligned}\text{。}$

于是 $\begin{aligned} &AB'^2 = \left|e^{i\theta} - 2\right|^2 \\ &= (\cos\theta - 2)^2 + \sin^2\theta \\ &= 5 - 4\cos\theta \end{aligned}\text{。}$ 令它等于 $\left(\frac{4}{3}\right)^2 = \frac{16}{9}$ ，得到 $4\cos\theta = 5 - \frac{16}{9} = \frac{29}{9}$ ，所以 $\cos\theta = \frac{29}{36}$ （确为正数，与 $\theta$ 为锐角一致）。因此 $m + n = 29 + 36 = 65$ 。

Work in the complex plane with $B = 0$ and $A = 1.$ Rotating $z$ about $P$ through angle $\varphi$ counterclockwise gives $P + e^{i\varphi}(z - P).$ So $A' = e^{i\theta},$ and rotating $B$ clockwise through $\theta$ about $A'$ gives $\begin{aligned} &B' = A' + e^{-i\theta}(0 - A') \\ &= e^{i\theta} - e^{-i\theta}e^{i\theta} \\ &= e^{i\theta} - 1. \end{aligned}$

Then $\begin{aligned} &AB'^2 = \left|e^{i\theta} - 2\right|^2 \\ &= (\cos\theta - 2)^2 + \sin^2\theta \\ &= 5 - 4\cos\theta. \end{aligned}$ Setting this equal to $\left(\frac{4}{3}\right)^2 = \frac{16}{9}$ gives $4\cos\theta = 5 - \frac{16}{9} = \frac{29}{9},$ so $\cos\theta = \frac{29}{36}$ (indeed positive, consistent with $\theta$ acute). Thus $m + n = 29 + 36 = 65.$

6.

满足方程 $\sqrt[20]{x^{\log_{2026} x}} = 26x$ 的所有正实数 $x$ 的乘积是一个整数 $P$ 。求 $P$ 的正整数因数个数。

The product of all positive real numbers $x$ satisfying the equation $\sqrt[20]{x^{\log_{2026} x}} = 26x$ is an integer $P.$ Find the number of positive integer divisors of $P.$

答案

知识点：对数二次方程韦达定理因数个数

难度评级：2300

小提示：

令 $t = \log_{2026} x$ ，并对两边取 $\log_{2026}$ ，得到关于 $t$ 的二次方程

Set $t = \log_{2026} x$ and take $\log_{2026}$ of both sides to get a quadratic in $t$

大提示：

两个根满足 $t_1 + t_2 = 20$ ，所以解 $x$ 的乘积就是 $2026$ 的这个次方；分解 $2026$

The two roots satisfy $t_1 + t_2 = 20,$ so the product of the solutions $x$ is $2026$ raised to that power; factor $2026$

解答：

令 $t = \log_{2026} x$ 。对两边取 $\log_{2026}$ ，原方程也就是 $x^{\frac{\log_{2026} x}{20}} = 26x$ ，于是 $\frac{t^2}{20} = \log_{2026} 26 + t\text{，}$ 即 $t^2 - 20t - 20\log_{2026} 26 = 0\text{。}$ 判别式 $400 + 80\log_{2026} 26$ 为正，所以有两个实根 $t_1, t_2$ ，每个都给出一个有效正解 $x = 2026^{t}$ 。

由 Vieta 公式， $t_1 + t_2 = 20$ ，所以这些解的乘积为 $2026^{t_1} \cdot 2026^{t_2} = 2026^{20}$ 。由于 $2026 = 2 \cdot 1013$ ，且 $1013$ 为质数， $P = 2^{20} \cdot 1013^{20}$ 有 $21 \cdot 21 = 441$ 个正因数。

Let $t = \log_{2026} x.$ Taking $\log_{2026}$ of both sides of $x^{\frac{\log_{2026} x}{20}} = 26x$ gives $\frac{t^2}{20} = \log_{2026} 26 + t,$ that is $t^2 - 20t - 20\log_{2026} 26 = 0.$ The discriminant $400 + 80\log_{2026} 26$ is positive, so there are two real roots $t_1, t_2,$ each giving a valid positive solution $x = 2026^{t}.$

By Vieta’s formulas $t_1 + t_2 = 20,$ so the product of the solutions is $2026^{t_1} \cdot 2026^{t_2} = 2026^{20}.$ Since $2026 = 2 \cdot 1013$ and $1013$ is prime, $P = 2^{20} \cdot 1013^{20}$ has $21 \cdot 21 = 441$ positive divisors.

7.

求满射函数 $\pi$ 的个数，其中该函数从集合 $A = \{1, 2, 3, 4, 5, 6\}$ 映到 $A$ ，并且对每个 $a \in A$ 都有 $\pi(\pi(\pi(\pi(\pi(\pi(a)))))) = a\text{。}$

Find the number of functions $\pi$ mapping the set $A = \{1, 2, 3, 4, 5, 6\}$ onto $A$ such that for every $a \in A,$ $\pi(\pi(\pi(\pi(\pi(\pi(a)))))) = a.$

答案

知识点：排列补集计数分类讨论

难度评级：2510

小提示：

有限集合到自身的满射是一个排列，而条件表示它的六次方是恒等映射

An onto map from a finite set to itself is a permutation, and the condition says its sixth power is the identity

大提示：

等价地，每个循环长度都整除 $6$ ，所以从 $720$ 中减去含有 $4$ -循环或 $5$ -循环的排列

Equivalently every cycle length divides $6,$ so subtract from $720$ the permutations that contain a $4$ -cycle or a $5$ -cycle

解答：

有限集合到自身的满射一定是双射，所以 $\pi$ 是六个元素的排列，条件表示 $\pi^6$ 是恒等映射。一个排列满足 $\pi^6 = \mathrm{id}$ ，当且仅当其循环分解中每个循环长度都整除 $6$ 。在可能的长度 $1$ 到 $6$ 中，只有 $4$ 和 $5$ 不整除 $6$ 。

要排除含有 $4$ -循环或 $5$ -循环的排列，并从 $6! = 720$ 中减去这些排列。循环类型 $4+1+1$ 给出 $\frac{6!}{4 \cdot 2!} = 90$ ，类型 $4+2$ 给出 $\frac{6!}{4 \cdot 2} = 90$ ，类型 $5+1$ 给出 $\frac{6!}{5} = 144$ ，共排除 $90 + 90 + 144 = 324$ 个排列。

所求个数为 $720 - 324 = 396$ 。

A function from a finite set onto itself is a bijection, so $\pi$ is a permutation of six elements, and the condition says $\pi^6$ is the identity. A permutation satisfies $\pi^6 = \mathrm{id}$ exactly when every cycle in its cycle decomposition has length dividing $6.$ Among the possible lengths $1$ through $6,$ only $4$ and $5$ fail to divide $6.$

We subtract the permutations containing a $4$ -cycle or a $5$ -cycle from $6! = 720.$ Cycle type $4+1+1$ gives $\frac{6!}{4 \cdot 2!} = 90,$ type $4+2$ gives $\frac{6!}{4 \cdot 2} = 90,$ and type $5+1$ gives $\frac{6!}{5} = 144,$ for $90 + 90 + 144 = 324$ excluded permutations.

The count is $720 - 324 = 396.$

8.

令 $N$ 为 $17017^{17}$ 的正整数因数中余数是 $5$ （除以 $12$ 时）的因数个数。求 $N$ 除以 $1000$ 的余数。

Let $N$ be the number of positive integer divisors of $17017^{17}$ that leave a remainder of $5$ upon division by $12.$ Find the remainder when $N$ is divided by $1000.$

答案

知识点：模运算质因数分解奇偶性分类讨论

难度评级：2600

小提示：

分解 $17017 = 7 \cdot 11 \cdot 13 \cdot 17$ ，再模 $12$ 化简：这些质数变为 $7$ 、 $11$ 、 $1$ 、 $5$ ，且 $7^2 \equiv 11^2 \equiv 5^2 \equiv 1$

Factor $17017 = 7 \cdot 11 \cdot 13 \cdot 17$ and reduce mod $12:$ the primes become $7,$ $11,$ $1,$ $5,$ with $7^2 \equiv 11^2 \equiv 5^2 \equiv 1$

大提示：

只有 $7$ 、 $11$ 、 $17$ 的指数奇偶性有影响，而 $7 \cdot 11 \equiv 5 \pmod{12}$ ，所以恰有两种奇偶模式给出余数 $5$

Only the parities of the exponents of $7,$ $11,$ $17$ matter, and $7 \cdot 11 \equiv 5 \pmod{12},$ so exactly two parity patterns give remainder $5$

解答：

因为 $17017 = 7 \cdot 11 \cdot 13 \cdot 17$ ， $17017^{17}$ 的因数为 $7^a 11^b 13^c 17^d$ ，其中每个指数都在 $0$ 到 $17$ 之间。模 $12$ 时有 $13 \equiv 1$ ，且 $7^2 \equiv 11^2 \equiv 17^2 \equiv 1$ （因为 $17 \equiv 5$ ），所以一个因数的余数为 $7^{\alpha} \, 11^{\beta} \, 5^{\delta} \pmod{12}$ ，其中 $\alpha, \beta, \delta$ 是 $a, b, d$ 的奇偶性。

四个可能值 $1, 5, 7, 11$ 组成群 $\{1, 5, 7, 11\}$ ，运算为模 $12$ 乘法，其中 $7 \cdot 11 \equiv 5$ 。检查八种奇偶模式可知，余数为 $5$ 当且仅当 $(\alpha, \beta, \delta) = (0, 0, 1)$ 或 $(1, 1, 0)$ 。每个奇偶条件有 $9$ 种选择，而相应指数共有 $18$ 种可能； $c$ 可任意选择，有 $18$ 种。

因此 $N = 2 \cdot 9 \cdot 9 \cdot 9 \cdot 18 = 26244$ ，模 $1000$ 的余数为 $244$ 。

Since $17017 = 7 \cdot 11 \cdot 13 \cdot 17,$ the divisors of $17017^{17}$ are $7^a 11^b 13^c 17^d$ with each exponent between $0$ and $17.$ Modulo $12$ we have $13 \equiv 1,$ and $7^2 \equiv 11^2 \equiv 17^2 \equiv 1$ (as $17 \equiv 5$ ), so the residue of a divisor is $7^{\alpha} \, 11^{\beta} \, 5^{\delta} \pmod{12},$ where $\alpha, \beta, \delta$ are the parities of $a, b, d.$

The four possible values $1, 5, 7, 11$ multiply like the group $\{1, 5, 7, 11\}$ mod $12,$ in which $7 \cdot 11 \equiv 5.$ Checking the eight parity patterns, the residue is $5$ exactly when $(\alpha, \beta, \delta) = (0, 0, 1)$ or $(1, 1, 0).$ Each parity condition is satisfied by $9$ of the $18$ choices of that exponent, while $c$ is free with $18$ choices.

Therefore $N = 2 \cdot 9 \cdot 9 \cdot 9 \cdot 18 = 26244,$ and the remainder mod $1000$ is $244.$

9.

Joanne 有一个空白的公平六面骰子，以及六张贴纸，每张贴纸分别标有从 $1$ 到 $6$ 的一个不同整数。Joanne 掷骰子，然后把标有 $1$ 的贴纸贴在朝上的面上。她再掷一次骰子，把标有 $2$ 的贴纸贴在朝上的面上，并继续这个过程，按顺序贴完其余贴纸。如果骰子朝上的面已经有贴纸，则新贴纸盖在旧贴纸上。设 $p$ 为如下条件概率：在所有偶数编号贴纸最终都可见的条件下，过程结束时恰好有一个面仍为空白。若 $p$ 可写成 $\frac{m}{n}$ ，其中 $m$ 和 $n$ 为互质正整数，求 $m + n$ 。

Joanne has a blank fair six-sided die and six stickers each displaying a different integer from $1$ to $6.$ Joanne rolls the die and then places the sticker labeled $1$ on the top face of the die. She then rolls the die again, places the sticker labeled $2$ on the top face, and continues this process to place the rest of the stickers in order. If the die ever lands with a sticker already on its top face, the new sticker is placed to cover the old sticker. Let $p$ be the conditional probability that at the end of the process exactly one face has been left blank, given that all the even-numbered stickers are visible on faces of the die. Then $p$ can be written as $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

答案

知识点：条件概率独立事件分类讨论

难度评级：2840

小提示：

追踪六次掷出的朝上面 $f_1, \ldots, f_6$ ，它们独立且均匀；贴纸 $i$ 最终可见当且仅当面 $f_i$ 之后再也没有被掷到

Track the six rolled top faces $f_1, \ldots, f_6,$ independent and uniform; sticker $i$ stays visible exactly when face $f_i$ never comes up afterward

大提示：

恰好一个空白面意味着恰有一次重复 $f_i = f_j$ ；统计哪些配对 $i \lt j$ 能让贴纸 $2$ 、 $4$ 、 $6$ 保持可见

Exactly one blank face means exactly one repeat $f_i = f_j;$ count which pairs $i \lt j$ keep stickers $2,$ $4,$ $6$ visible

解答：

令 $f_1, \ldots, f_6$ 为每次掷出的朝上面，它们在六个面上独立均匀。贴纸 $i$ 被贴在面 $f_i$ 上，并最终可见当且仅当 $f_j \ne f_i$ 对所有 $j \gt i$ 都成立（贴纸 $6$ 总是可见）。所以条件事件为 $f_3, f_4, f_5, f_6 \ne f_2$ 且 $f_5, f_6 \ne f_4$ 。按 $f_1, f_2, f_3, f_4, f_5, f_6$ 的顺序计数，得到 $6 \cdot 6 \cdot 5 \cdot 5 \cdot 4 \cdot 4 = 14400$ 个序列，全集为 $6^6$ 个序列。

一个面为空白当且仅当它从未在 $f_1, \ldots, f_6$ 中出现，所以恰好一个空白面意味着序列恰好取到 $5$ 个不同值，即恰有一次重合 $f_i = f_j$ ，其中 $i \lt j$ ，其余值都不同。该重合不能违反条件：配对 $(2, j)$ 以及 $(4, 5)$ 、 $(4, 6)$ 被禁止，剩下 $9$ 个配对 $(1,2)$ 、 $(1,3)$ 、 $(1,4)$ 、 $(1,5)$ 、 $(1,6)$ 、 $(3,4)$ 、 $(3,5)$ 、 $(3,6)$ 、 $(5,6)$ 。对每个允许的配对，五个不同值可用 $6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 = 720$ 种方式分配；由于唯一重复值位于允许配对中，所有条件自动满足。因此有 $9 \cdot 720 = 6480$ 个序列。

所以 $p = \frac{6480}{14400} = \frac{9}{20}$ ，且 $m + n = 9 + 20 = 29$ 。

Let $f_1, \ldots, f_6$ be the top faces rolled, independent and uniform over the six faces. Sticker $i$ goes on face $f_i$ and ends up visible exactly when $f_j \ne f_i$ for all $j \gt i$ (sticker $6$ is always visible). So the conditioning event is $f_3, f_4, f_5, f_6 \ne f_2$ and $f_5, f_6 \ne f_4.$ Counting choices in the order $f_1, f_2, f_3, f_4, f_5, f_6$ gives $6 \cdot 6 \cdot 5 \cdot 5 \cdot 4 \cdot 4 = 14400$ sequences out of $6^6.$

A face is blank exactly when it never appears among $f_1, \ldots, f_6,$ so exactly one blank face means the sequence takes exactly $5$ distinct values, i.e. there is exactly one coincidence $f_i = f_j$ with $i \lt j$ and all other values distinct. The coincidence must not violate the conditioning: pairs $(2, j)$ and $(4, 5),$ $(4, 6)$ are forbidden, leaving the $9$ pairs $(1,2),$ $(1,3),$ $(1,4),$ $(1,5),$ $(1,6),$ $(3,4),$ $(3,5),$ $(3,6),$ $(5,6).$ For each allowed pair, the five distinct values can be assigned in $6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 = 720$ ways, and every constraint holds automatically because the only repeated value occupies an allowed pair. That gives $9 \cdot 720 = 6480$ sequences.

Therefore $p = \frac{6480}{14400} = \frac{9}{20},$ and $m + n = 9 + 20 = 29.$

10.

设 $\triangle ABC$ 的边长为 $AB = 13$ 、 $BC = 14$ 、 $CA = 15$ 。三角形 $\triangle A'B'C'$ 是将 $\triangle ABC$ 绕其外心旋转得到的，使得 $\overline{A'C'}$ 垂直于 $\overline{BC}$ ，且 $A'$ 和 $B$ 不在直线 $B'C'$ 的同侧。求最接近六边形 $AA'CC'BB'$ 面积的整数。

Let $\triangle ABC$ have side lengths $AB = 13,$ $BC = 14,$ and $CA = 15.$ Triangle $\triangle A'B'C'$ is obtained by rotating $\triangle ABC$ about its circumcenter so that $\overline{A'C'}$ is perpendicular to $\overline{BC},$ with $A'$ and $B$ not on the same side of line $B'C'.$ Find the integer closest to the area of hexagon $AA'CC'BB'.$

答案

知识点：坐标几何变换鞋带公式外接圆、外心与外接圆半径

难度评级：2920

小提示：

取 $B = (0,0)$ 、 $C = (14,0)$ 、 $A = (5,12)$ ；外心为 $\left(7, \frac{33}{8}\right)$ ，旋转会使六个顶点都留在外接圆上

Use $B = (0,0),$ $C = (14,0),$ $A = (5,12);$ the circumcenter is $\left(7, \frac{33}{8}\right),$ and the rotation keeps all six vertices on the circumcircle

大提示：

把方向 $(3,-4)$ ，也就是 $\overline{AC}$ 的方向，旋转到竖直方向；异侧条件选出 $\cos\varphi = \frac{4}{5}$ 、 $\sin\varphi = -\frac{3}{5}$ 。使用鞋带公式

Rotate direction $(3,-4)$ of $\overline{AC}$ to vertical; the side condition selects $\cos\varphi = \frac{4}{5},$ $\sin\varphi = -\frac{3}{5}.$ Use the shoelace formula

解答：

取 $B = (0,0)$ 、 $C = (14,0)$ 、 $A = (5,12)$ 。外心在 $x = 7$ 上，令它到 $B$ 和到 $A$ 的距离相等，得到 $O = \left(7, \frac{33}{8}\right)$ 。 $\overline{AC}$ 的方向为 $C - A = (9, -12)$ ，与 $(3, -4)$ 平行。旋转角 $\varphi$ 后使 $\overline{A'C'}$ 竖直，当且仅当它把 $(3,-4)$ 送到 $(0, \pm 5)$ ，所以 $(\cos\varphi, \sin\varphi) = \left(\frac{4}{5}, -\frac{3}{5}\right)$ 或 $\left(-\frac{4}{5}, \frac{3}{5}\right)$ 。用标量叉积检查有向直线 $B'C'$ 的两侧。对第一种旋转， $\begin{aligned} (C'-B') \times (A'-B') &= 168, \\ (C'-B') \times (B-B') &= -\frac{189}{4} \end{aligned}\text{；}$ 对第二种旋转，这两个量分别为 $168$ 和 $\frac{651}{4}$ 。因此 $A'$ 和 $B$ 只在 $\cos\varphi = \frac{4}{5}$ 、 $\sin\varphi = -\frac{3}{5}$ 时位于直线两侧。

用这个旋转， $P' = O + R(P - O)$ ，三个旋转后的顶点为 $A' = \left(\tfrac{81}{8}, \tfrac{93}{8}\right)\text{，}$ $B' = \left(-\tfrac{43}{40}, \tfrac{201}{40}\right)\text{，}$ $C' = \left(\tfrac{81}{8}, -\tfrac{27}{8}\right)\text{。}$ 例如， $A - O = \left(-2, \tfrac{63}{8}\right)$ 旋转为 $\left(\tfrac{25}{8}, \tfrac{15}{2}\right)$ ，得到 $A' = \left(\tfrac{81}{8}, \tfrac{93}{8}\right)$ 。

六边形 $A A' C C' B B'$ 以这些顶点为顺序时是简单六边形，所以对 $(5,12)$ 、 $\left(\tfrac{81}{8}, \tfrac{93}{8}\right)$ 、 $(14,0)$ 、 $\left(\tfrac{81}{8}, -\tfrac{27}{8}\right)$ 、 $(0,0)$ 、 $\left(-\tfrac{43}{40}, \tfrac{201}{40}\right)$ 使用鞋带公式，得到面积 $\frac{1557}{10} = 155.7$ 。最接近的整数为 $156$ 。

Place $B = (0,0),$ $C = (14,0),$ $A = (5,12).$ The circumcenter lies on $x = 7,$ and equating distances to $B$ and $A$ gives $O = \left(7, \frac{33}{8}\right).$ The direction of $\overline{AC}$ is $C - A = (9, -12),$ parallel to $(3, -4).$ A rotation through $\varphi$ makes $\overline{A'C'}$ vertical exactly when it sends $(3,-4)$ to $(0, \pm 5),$ so $(\cos\varphi, \sin\varphi) = \left(\frac{4}{5}, -\frac{3}{5}\right)$ or $\left(-\frac{4}{5}, \frac{3}{5}\right).$ Use the scalar cross product to test sides of the directed line $B'C'.$ For the first rotation, $\begin{aligned} (C'-B') \times (A'-B') &= 168, \\ (C'-B') \times (B-B') &= -\frac{189}{4}, \end{aligned}$ while for the second rotation these quantities are $168$ and $\frac{651}{4},$ respectively. Thus $A'$ and $B$ are on opposite sides only for $\cos\varphi = \frac{4}{5},$ $\sin\varphi = -\frac{3}{5}.$

With this rotation, $P' = O + R(P - O)$ gives $A' = \left(\tfrac{81}{8}, \tfrac{93}{8}\right),$ $B' = \left(-\tfrac{43}{40}, \tfrac{201}{40}\right),$ $C' = \left(\tfrac{81}{8}, -\tfrac{27}{8}\right).$ For example, $A - O = \left(-2, \tfrac{63}{8}\right)$ rotates to $\left(\tfrac{25}{8}, \tfrac{15}{2}\right),$ giving $A' = \left(\tfrac{81}{8}, \tfrac{93}{8}\right).$

The hexagon $A A' C C' B B'$ is simple with these vertices in order, so the shoelace formula on $(5,12),$ $\left(\tfrac{81}{8}, \tfrac{93}{8}\right),$ $(14,0),$ $\left(\tfrac{81}{8}, -\tfrac{27}{8}\right),$ $(0,0),$ $\left(-\tfrac{43}{40}, \tfrac{201}{40}\right)$ gives area $\frac{1557}{10} = 155.7.$ The closest integer is $156.$

11.

将整数 $1$ 到 $64$ 以某种顺序填入一个 $8 \times 8$ 方格中，每个格子填一个数。令 $a_{i,j}$ 为第 $i$ 行第 $j$ 列格子中的数，令 $M$ 为相邻格子之间差的绝对值之和，也就是说， $\begin{aligned} M = \sum_{i=1}^{8} \sum_{j=1}^{7} \big(&|a_{i,j+1} - a_{i,j}| \\ &{}+ |a_{j+1,i} - a_{j,i}|\big) \end{aligned}\text{。}$ 求 $M$ 的最大可能值除以 $1000$ 的余数。

The integers from $1$ to $64$ are placed in some order into an $8 \times 8$ grid of cells with one number in each cell. Let $a_{i,j}$ be the number placed in the cell in row $i$ and column $j,$ and let $M$ be the sum of the absolute differences between adjacent cells. That is, $\begin{aligned} M = \sum_{i=1}^{8} \sum_{j=1}^{7} \big(&|a_{i,j+1} - a_{i,j}| \\ &{}+ |a_{j+1,i} - a_{j,i}|\big). \end{aligned}$ Find the remainder when the maximum possible value of $M$ is divided by $1000.$

答案

知识点：最优化绝对值极端原理

难度评级：3160

小提示：

把每条边的贡献归到端点上： $M = \sum_v c_v a_v$ ，其中 $c_v$ 是小于 $a_v$ 的邻居数减去大于它的邻居数，所以 $|c_v| \le \deg(v)$

Attribute each edge to its endpoints: $M = \sum_v c_v a_v,$ where $c_v$ counts neighbors smaller than $a_v$ minus neighbors larger, so $|c_v| \le \deg(v)$

大提示：

因为 $\sum_v c_v = 0$ ，也有 $M \le \sum_v \deg(v)\,|a_v - 32.5|$ 。把较大的偏差配给度数为 $4$ 的格子，并检查棋盘式放置可达到这个上界。

Since $\sum_v c_v = 0,$ also $M \le \sum_v \deg(v)\,|a_v - 32.5|.$ Match the large deviations with the degree- $4$ cells, and check that a checkerboard placement attains the bound.

解答：

将方格看作图，其 $112$ 条边连接相邻格子。每条边都把较大端点的值正向贡献一次、较小端点的值负向贡献一次，所以 $M = \sum_v c_v a_v$ ，其中 $a_v$ 是格子 $v$ 中的数， $c_v$ 是 $v$ 的邻居中数值更小的个数减去数值更大的个数。于是 $|c_v| \le \deg(v)$ 。度数为 $4$ 的内部格子有 $36$ 个，度数为 $3$ 的边上非角格子有 $24$ 个，度数为 $2$ 的角格子有 $4$ 个，且 $\sum_v c_v = 0$ ，因为每条边贡献 $+1$ 和 $-1$ 。

由于 $\sum_v c_v = 0$ ， $\begin{aligned} M &= \sum_v c_v \left(a_v - \tfrac{65}{2}\right) \\ &\le \sum_v \deg(v)\left|a_v - \tfrac{65}{2}\right| \end{aligned}\text{。}$ 由重排不等式，上式在如下配对时最大：把 $36$ 个离 $\frac{65}{2}$ 最远的数（即 $1$ 至 $18$ 和 $47$ 至 $64$ ，偏差总和为 $828$ ）配给内部格子；把接下来的 $24$ 个数（ $19$ 至 $30$ 和 $35$ 至 $46$ ，总和为 $192$ ）配给边上格子；把 $31$ 至 $34$ （总和为 $4$ ）配给角。因此 $M \le 4 \cdot 828 + 3 \cdot 192 + 2 \cdot 4$ $= 3896$ 。

等号要求每个填入至多 $32$ 的格子都小于它的所有邻居，而每个填入至少 $33$ 的格子都大于它的所有邻居，棋盘式放置可以做到：把 $1$ 至 $32$ 放在黑格中（ $1$ 至 $18$ 放内部黑格、 $19$ 至 $30$ 放边上黑格、 $31$ 至 $32$ 放黑色角），把 $33$ 至 $64$ 放在白格中（ $33$ 至 $34$ 放角、 $35$ 至 $46$ 放边上、 $47$ 至 $64$ 放内部）。这样每对相邻格子都是白格大于黑格，所以 $M = 3896$ ，答案为 $3896 \bmod 1000 = 896$ 。

View the grid as a graph whose $112$ edges join adjacent cells. Each edge contributes its larger endpoint value positively and its smaller one negatively, so $M = \sum_v c_v a_v,$ where $a_v$ is the entry in cell $v$ and $c_v$ is the number of neighbors of $v$ with smaller entries minus the number with larger entries. Then $|c_v| \le \deg(v),$ which is $4$ for the $36$ interior cells, $3$ for the $24$ edge cells, and $2$ for the $4$ corners, and $\sum_v c_v = 0$ since each edge contributes $+1$ and $-1.$

Because $\sum_v c_v = 0,$ $\begin{aligned} M &= \sum_v c_v \left(a_v - \tfrac{65}{2}\right) \\ &\le \sum_v \deg(v)\left|a_v - \tfrac{65}{2}\right|. \end{aligned}$ By the rearrangement inequality this is maximized by pairing the $36$ values farthest from $\frac{65}{2}$ (namely $1$ – $18$ and $47$ – $64,$ whose deviations total $828$ ) with the interior cells, the next $24$ values ( $19$ – $30$ and $35$ – $46,$ totaling $192$ ) with the edge cells, and $31$ – $34$ (totaling $4$ ) with the corners. Hence $M \le 4 \cdot 828 + 3 \cdot 192 + 2 \cdot 4$ $= 3896.$

Equality requires every cell holding a value at most $32$ to be smaller than all its neighbors and every value at least $33$ to be larger, which a checkerboard achieves: put $1$ – $32$ on the black cells ( $1$ – $18$ on interior blacks, $19$ – $30$ on edge blacks, $31$ – $32$ on black corners) and $33$ – $64$ on the white cells ( $33$ – $34$ on corners, $35$ – $46$ on edges, $47$ – $64$ in the interior). Every neighbor pair then compares white over black, so $M = 3896,$ and the answer is $3896 \bmod 1000 = 896.$

12.

三角形 $\triangle ABC$ 位于平面 $\mathcal{P}$ 内，且 $AB = 6$ 、 $AC = 4$ 、 $\angle BAC = 90^\circ$ 。令 $D$ 为 $\triangle ABC$ 的重心关于 $\overline{BC}$ 反射后所得的点。四个球都位于 $\mathcal{P}$ 的同一侧，半径分别为 $1$ 、 $2$ 、 $3$ 和 $r$ ，并与 $\mathcal{P}$ 相切，切点分别为 $A$ 、 $B$ 、 $C$ 和 $D$ 。这四个球还都与第二个平面 $\mathcal{T}$ 相切，并全部位于 $\mathcal{T}$ 的同一侧。 $r$ 的值可写成 $\frac{m}{n}$ ，其中 $m$ 和 $n$ 为互质正整数。求 $m + n$ 。

Triangle $\triangle ABC$ lies in plane $\mathcal{P}$ with $AB = 6,$ $AC = 4,$ and $\angle BAC = 90^\circ.$ Let $D$ be the reflection across $\overline{BC}$ of the centroid of $\triangle ABC.$ Four spheres, all on the same side of $\mathcal{P},$ have radii $1,$ $2,$ $3,$ and $r$ and are tangent to $\mathcal{P}$ at points $A,$ $B,$ $C,$ and $D,$ respectively. The four spheres are also each tangent to a second plane $\mathcal{T}$ and are all on the same side of $\mathcal{T}.$ The value of $r$ can be written as $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

答案

知识点：球立体几何坐标几何变换

难度评级：3060

小提示：

每个球心位于其切点上方，高度等于半径；把第二个平面写成 $n \cdot x = c$ ，其中 $n$ 是单位向量，并表达两个相切条件

Each center lies at height equal to its radius above its tangency point; write the second plane as $n \cdot x = c$ with $n$ a unit vector and express both tangencies

大提示：

条件说明半径是切点在 $\mathcal{P}$ 中位置的仿射函数；取值依次为 $1, 2, 3$ 的点是 $A, B, C$ ，所以在 $D$ 处代入这个函数

The conditions say the radius is an affine function of the tangency point in $\mathcal{P};$ it takes values $1, 2, 3$ at $A, B, C,$ so evaluate that function at $D$

解答：

一个半径为 $\rho$ 、与 $\mathcal{P}$ 相切于 $P$ 的球，其球心为 $P + \rho k$ ，其中 $k$ 是 $\mathcal{P}$ 向上的单位法向量。把 $\mathcal{T}$ 写成 $\{x : n \cdot x = c\}$ ，其中单位法向量 $n = (n_1, n_2, h)$ ，所用坐标使 $\mathcal{P}$ 为 $xy$ -平面。所有球在同一侧相切意味着对每个球都有 $n \cdot (P + \rho k) - c = \rho$ ，也就是 $n_1 x_P + n_2 y_P - c = (1 - h)\rho$ 。这里 $h \ne 1$ ，否则左边会是常数而半径不同。因此 $\rho = g(P)$ ，其中仿射函数 $g(x,y) = \frac{n_1 x + n_2 y - c}{1 - h}$ 。

取 $A = (0,0)$ 、 $B = (6,0)$ 、 $C = (0,4)$ 。满足 $g(A) = 1$ 、 $g(B) = 2$ 、 $g(C) = 3$ 的仿射函数为 $g(x,y) = 1 + \frac{x}{6} + \frac{y}{2}$ 。重心为 $G = \left(2, \frac{4}{3}\right)$ ，直线 $BC$ 为 $2x + 3y = 12$ 。因为 $2 \cdot 2 + 3 \cdot \frac{4}{3} - 12 = -4$ ，反射得到 $\begin{aligned} D &= G + \frac{8}{13}\,(2, 3) \\ &= \left(\frac{42}{13},\ \frac{124}{39}\right) \end{aligned}\text{。}$

因此 $r = g(D)$ $= 1 + \frac{1}{6} \cdot \frac{42}{13}$ $+ \frac{1}{2} \cdot \frac{124}{39}$ $= 1 + \frac{21}{39} + \frac{62}{39}$ $= \frac{122}{39}$ 。（这样的平面确实存在：法向量条件 $(1-h)^2\left|\nabla g\right|^2 = 1 - h^2$ ，且 $\left|\nabla g\right|^2 = \frac{5}{18}$ ，给出 $h = -\frac{13}{23}$ 。）因为 $\gcd(122, 39) = 1$ ，答案为 $122 + 39 = 161$ 。

A sphere of radius $\rho$ tangent to $\mathcal{P}$ at $P$ has center $P + \rho k,$ where $k$ is the upward unit normal of $\mathcal{P}.$ Write $\mathcal{T}$ as $\{x : n \cdot x = c\}$ with unit normal $n = (n_1, n_2, h)$ in coordinates where $\mathcal{P}$ is the $xy$ -plane. Tangency with all spheres on the same side means $n \cdot (P + \rho k) - c = \rho$ for each sphere, that is $n_1 x_P + n_2 y_P - c = (1 - h)\rho.$ Here $h \ne 1,$ since otherwise the left side would be constant while the radii differ. So $\rho = g(P)$ for the affine function $g(x,y) = \frac{n_1 x + n_2 y - c}{1 - h}.$

Take $A = (0,0),$ $B = (6,0),$ $C = (0,4).$ The affine function with $g(A) = 1,$ $g(B) = 2,$ $g(C) = 3$ is $g(x,y) = 1 + \frac{x}{6} + \frac{y}{2}.$ The centroid is $G = \left(2, \frac{4}{3}\right),$ and line $BC$ is $2x + 3y = 12.$ Since $2 \cdot 2 + 3 \cdot \frac{4}{3} - 12 = -4,$ reflecting gives $\begin{aligned} D &= G + \frac{8}{13}\,(2, 3) \\ &= \left(\frac{42}{13},\ \frac{124}{39}\right). \end{aligned}$

Therefore $r = g(D)$ $= 1 + \frac{1}{6} \cdot \frac{42}{13}$ $+ \frac{1}{2} \cdot \frac{124}{39}$ $= 1 + \frac{21}{39} + \frac{62}{39}$ $= \frac{122}{39}.$ (Such a plane exists: the normal condition $(1-h)^2\left|\nabla g\right|^2 = 1 - h^2$ with $\left|\nabla g\right|^2 = \frac{5}{18}$ gives $h = -\frac{13}{23}.$ ) Since $\gcd(122, 39) = 1,$ the answer is $122 + 39 = 161.$

13.

对每个小于 $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.$

答案

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

难度评级：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.

14.

在一个等角五边形中，边长平方和等于 $308$ ，对角线长度平方和等于 $800$ 。该五边形周长的平方可表示为 $m\sqrt{n}$ ，其中 $m$ 和 $n$ 为正整数，且 $n$ 不被任何质数的平方整除。求 $m + n$ 。

In an equiangular pentagon, the sum of the squares of the side lengths equals $308,$ and the sum of the squares of the diagonal lengths equals $800.$ The square of the perimeter of the pentagon can be expressed as $m\sqrt{n},$ where $m$ and $n$ are positive integers and $n$ is not divisible by the square of any prime. Find $m + n.$

答案

知识点：等角多边形向量三角学代数变形

难度评级：3270

小提示：

把边写成向量 $s_k u_k$ ，其中 $u_k = (\cos 72k^\circ, \sin 72k^\circ)$ ，且总和为零；每条对角线是两个相邻边向量之和

Write the sides as vectors $s_k u_k$ with $u_k = (\cos 72k^\circ, \sin 72k^\circ)$ and vanishing sum; each diagonal is the sum of two consecutive side vectors

大提示：

对角线数据给出 $2\cos 72^\circ \sum s_k s_{k+1} = 184$ ，再展开 $\left|\sum s_k u_k\right|^2 = 0$ 可确定 $\sum s_k s_{k+2}$

The diagonal data gives $2\cos 72^\circ \sum s_k s_{k+1} = 184,$ and expanding $\left|\sum s_k u_k\right|^2 = 0$ then determines $\sum s_k s_{k+2}$

解答：

在等角五边形中，每条边的方向转过外角 $72^\circ$ ，所以边向量为 $s_k u_k$ ，其中 $k = 1, \ldots, 5$ ， $u_k = (\cos 72k^\circ, \sin 72k^\circ)$ ，且 $\sum_k s_k u_k = 0$ 。记 $Q = \sum s_k^2 = 308$ 、 $P_1 = \sum_{k} s_k s_{k+1}$ 、 $P_2 = \sum_k s_k s_{k+2}$ （下标循环）。每条对角线都是两个相邻边向量之和，所以其平方为 $s_{k+1}^2 + s_{k+2}^2 + 2 s_{k+1} s_{k+2} \cos 72^\circ$ ，把五条相加得 $800 = 2Q + 2\cos 72^\circ \, P_1\text{，}$ 所以 $\begin{aligned} &2\cos 72^\circ \, P_1 = 800 - 616 \\ &= 184 \end{aligned}\text{。}$

展开 $\left|\sum_k s_k u_k\right|^2 = 0$ ， $u_k$ 与 $u_{k+1}$ 的夹角为 $72^\circ$ ， $u_k$ 与 $u_{k+2}$ 的夹角为 $144^\circ$ ： $\begin{aligned} &0 = Q + 2\cos 72^\circ \, P_1 \\ &\quad {}+ 2\cos 144^\circ \, P_2 \\ &= 308 + 184 - 2\cos 36^\circ \, P_2 \end{aligned}\text{，}$ 所以 $2\cos 36^\circ \, P_2 = 492$ 。利用 $\cos 72^\circ = \frac{\sqrt{5} - 1}{4}$ 和 $\cos 36^\circ = \frac{\sqrt{5} + 1}{4}$ ，得到 $2P_1 = \frac{184}{\cos 72^\circ} = 184\left(\sqrt{5} + 1\right)$ ，且 $2P_2 = \frac{492}{\cos 36^\circ} = 492\left(\sqrt{5} - 1\right)$ 。

周长的平方为 $\begin{aligned} &\left(\sum s_k\right)^2 = Q + 2P_1 + 2P_2 \\ &= 308 + 184\sqrt{5} + 184 \\ &\quad {}+ 492\sqrt{5} - 492 \\ &= 676\sqrt{5} \end{aligned}\text{。}$ 因此 $m + n = 676 + 5 = 681$ 。

In an equiangular pentagon each side direction turns by the exterior angle $72^\circ,$ so the sides are the vectors $s_k u_k$ for $k = 1, \ldots, 5,$ where $u_k = (\cos 72k^\circ, \sin 72k^\circ)$ and $\sum_k s_k u_k = 0.$ Write $Q = \sum s_k^2 = 308,$ $P_1 = \sum_{k} s_k s_{k+1},$ and $P_2 = \sum_k s_k s_{k+2}$ (indices cyclic). Each diagonal is a sum of two consecutive side vectors, so its square is $s_{k+1}^2 + s_{k+2}^2 + 2 s_{k+1} s_{k+2} \cos 72^\circ,$ and summing all five gives $800 = 2Q + 2\cos 72^\circ \, P_1,$ so $\begin{aligned} &2\cos 72^\circ \, P_1 = 800 - 616 \\ &= 184. \end{aligned}$

Expanding $\left|\sum_k s_k u_k\right|^2 = 0,$ the angle between $u_k$ and $u_{k+1}$ is $72^\circ$ and between $u_k$ and $u_{k+2}$ is $144^\circ:$ $\begin{aligned} &0 = Q + 2\cos 72^\circ \, P_1 \\ &\quad {}+ 2\cos 144^\circ \, P_2 \\ &= 308 + 184 - 2\cos 36^\circ \, P_2, \end{aligned}$ so $2\cos 36^\circ \, P_2 = 492.$ Using $\cos 72^\circ = \frac{\sqrt{5} - 1}{4}$ and $\cos 36^\circ = \frac{\sqrt{5} + 1}{4},$ we get $2P_1 = \frac{184}{\cos 72^\circ} = 184\left(\sqrt{5} + 1\right)$ and $2P_2 = \frac{492}{\cos 36^\circ} = 492\left(\sqrt{5} - 1\right).$

The square of the perimeter is $\begin{aligned} &\left(\sum s_k\right)^2 = Q + 2P_1 + 2P_2 \\ &= 308 + 184\sqrt{5} + 184 \\ &\quad {}+ 492\sqrt{5} - 492 \\ &= 676\sqrt{5}. \end{aligned}$ Therefore $m + n = 676 + 5 = 681.$

15.

设 $a$ 、 $b$ 和 $n$ 为正整数，其中 $a$ 和 $b$ 都大于或等于 $2$ ，且小于或等于 $2n$ 。定义一个 $a \times b$ 的格子环：它位于一个 $2n \times 2n$ 的方格网中，由 $2a + 2b - 4$ 个围绕 $(a-2) \times (b-2)$ （可能为空）矩形的格子组成。例如，下图展示了一种把 $6 \times 6$ 方格网分成 $4$ 个格子环的方法。

求把一个 $10 \times 10$ 方格网分成 $5$ 个格子环的方法数，使得方格网中的每个格子都恰好属于一个格子环。

Let $a,$ $b,$ and $n$ be positive integers with both $a$ and $b$ greater than or equal to $2$ and less than or equal to $2n.$ Define an $a \times b$ cell loop in a $2n \times 2n$ grid of cells to be the $2a + 2b - 4$ cells that surround an $(a-2) \times (b-2)$ (possibly empty) rectangle of cells in the grid. For example, the following diagram shows a way to partition a $6 \times 6$ grid of cells into $4$ cell loops.

Find the number of ways to partition a $10 \times 10$ grid of cells into $5$ cell loops so that every cell of the grid belongs to exactly one cell loop.

答案

知识点：铺砖极端原理递推计数

难度评级：3700

小提示：

每个环的矩形内部必须恰好由其他环填满，而环的大小迫使 $\sum (a_i + b_i) = 60$ 。研究最外层环的矩形。

Every loop’s rectangle must have its inner rectangle exactly filled by other loops, and the loop sizes force $\sum (a_i + b_i) = 60.$ Study the rectangles of the outermost loops.

大提示：

面积与环数迫使最外层矩形成为整个正方形或平行的全长板条；板条宽度为偶数 $w$ ，每条恰好使用 $\frac{w}{2}$ 个环

Area and loop counts force the outermost rectangles to be the full square or parallel full-length slabs of even width $w,$ each using exactly $\frac{w}{2}$ loops

解答：

因为五个环覆盖了 $\sum \left(2(a_i + b_i) - 4\right) = 100$ 个格子，所以 $\sum (a_i + b_i) = 60$ 。每个环含偶数个格子，因此奇数乘奇数的矩形不能被环完全填满；并且填充一个最短偶数边为 $e$ 的矩形至少需要 $\frac{e}{2}$ 个环，因为剥去一个最外层环会使那条边正好缩短 $2$ ，而把矩形分成较小矩形只会把这些需求相加。现在考虑一个分割中的最外层环（也就是其矩形不位于任何其他环的矩形内部的环）：它们的矩形铺满 $10 \times 10$ 正方形。若最外层矩形 $R_i$ 的最短偶数边为 $e_i$ ，它使用 $n_i \ge \frac{e_i}{2}$ 个环，且最多覆盖 $10\,e_i$ 个格子。对这个铺法求和， $100 \le \sum 10\,e_i \le 20 \sum n_i = 100$ ，所以处处取等：每个 $R_i$ 都在一个方向上跨满长度 $10$ ，宽度为偶数 $e_i$ ，并且恰好由 $\frac{e_i}{2}$ 个环填充。两个不同方向的全长板条会相交，所以最外层矩形要么是整个正方形，要么是平行板条；同样的等号论证可在每个环的内部矩形中重复。

令 $s(w)$ 为填充一条全高、偶数宽度为 $w$ 的板条的方法数，其中使用 $\frac{w}{2}$ 个环，并要求板条自身的 $10 \times w$ 边界是一个最外层环。宽度 $2$ 的板条是一个单环： $s(2) = 1$ 。宽度 $4$ 的板条是一个 $10 \times 4$ 环围住一个 $8 \times 2$ 环： $s(4) = 1$ 。宽度 $6$ 的板条是一个 $10 \times 6$ 环，围住一个 $8 \times 4$ 区域，内部有两个环：要么嵌套（ $8 \times 4$ 围住 $6 \times 2$ ），要么是两条 $8 \times 2$ 板条，所以 $s(6) = 2$ 。宽度 $8$ 的板条围住一个 $8 \times 6$ 区域，内部有三个环：一个 $8 \times 6$ 环围住一个含两个环的 $6 \times 4$ 区域（如前有 $2$ 种）；或全高板条宽度为 $2 + 2 + 2$ （ $1$ 种）；或宽度为 $2 + 4$ 的两种顺序（ $2$ 种），所以 $s(8) = 5$ 。同样的递推计数整个正方形：一个 $10 \times 10$ 环围住一个含四个环的 $8 \times 8$ 区域，其中 $4 \times 4$ 、 $6 \times 6$ ，和 $8 \times 8$ 区域分别有 $3$ ，再有 $3 + 3 + 3 = 9$ ，再有 $9 + 9 + 9 = 27$ 种填法（每一步为单个嵌套环、竖直板条或水平板条）。

最后统计最外层结构。单个 $10 \times 10$ 矩形给出 $27$ 种分割。若为平行板条，其宽度构成 $10$ 的偶数部分有序拆分，且至少有两部分，并且方向（竖直或水平）使计数翻倍： $(2,2,2,2,2)$ 给出 $1$ ； $(4,2,2,2)$ 的 $4$ 种顺序给出 $4$ ； $(4,4,2)$ 的 $3$ 种顺序给出 $3$ ； $(6,2,2)$ 的 $3$ 种顺序给出 $3 \cdot 2 = 6$ ； $(6,4)$ 的 $2$ 种顺序给出 $2 \cdot 2 = 4$ ； $(8,2)$ 的 $2$ 种顺序给出 $2 \cdot 5 = 10$ ，每个方向共 $28$ 种。总数为 $27 + 2 \cdot 28 = 83$ 。

Since the five loops cover $\sum \left(2(a_i + b_i) - 4\right) = 100$ cells, $\sum (a_i + b_i) = 60.$ Every loop has an even number of cells, so no odd-by-odd rectangle can be exactly filled by loops; and filling a rectangle whose shortest even side is $e$ requires at least $\frac{e}{2}$ loops, since peeling off an outermost loop shrinks that side by exactly $2$ while splitting a rectangle into smaller ones only adds up such requirements. Now consider the outermost loops of a partition (those whose rectangles lie inside no other loop’s rectangle): their rectangles tile the $10 \times 10$ square. If outermost rectangle $R_i$ has shortest even side $e_i,$ it uses $n_i \ge \frac{e_i}{2}$ loops and covers at most $10\,e_i$ cells. Summing over the tiling, $100 \le \sum 10\,e_i \le 20 \sum n_i = 100,$ so equality holds throughout: each $R_i$ spans the full $10$ in one direction, has even width $e_i,$ and is filled with exactly $\frac{e_i}{2}$ loops. Two full-length slabs in different directions would overlap, so the outermost rectangles are the whole square or parallel slabs, and the same equality argument repeats inside every loop’s inner rectangle.

Let $s(w)$ be the number of ways to fill a full-height slab of even width $w$ with $\frac{w}{2}$ loops, subject to the slab’s own $10 \times w$ boundary being one outermost loop. (A split into smaller outermost slabs is counted later instead.) A width- $2$ slab is a single loop: $s(2) = 1.$ A width- $4$ slab is a $10 \times 4$ loop around an $8 \times 2$ loop: $s(4) = 1.$ A width- $6$ slab is a $10 \times 6$ loop around an $8 \times 4$ region holding two loops — either nested ( $8 \times 4$ around $6 \times 2$ ) or two $8 \times 2$ slabs — so $s(6) = 2.$ A width- $8$ slab surrounds an $8 \times 6$ region holding three loops: an $8 \times 6$ loop around a $6 \times 4$ region with two loops ( $2$ ways as before), or full-height strips of widths $2 + 2 + 2$ ( $1$ way), or widths $2 + 4$ in two orders ( $2$ ways), so $s(8) = 5.$ The same recursion counts the full square: a $10 \times 10$ loop around an $8 \times 8$ region with four loops, where the $4 \times 4,$ $6 \times 6,$ and $8 \times 8$ regions admit $3,$ then $3 + 3 + 3 = 9,$ then $9 + 9 + 9 = 27$ fillings (single nested loop, vertical strips, or horizontal strips at each stage).

Finally, tally the outermost structures. The single $10 \times 10$ rectangle gives $27$ partitions. For parallel slabs, the widths form a composition of $10$ into even parts with at least two parts, and orientations (vertical or horizontal) double the count: $(2,2,2,2,2)$ gives $1;$ $(4,2,2,2)$ in $4$ orders gives $4;$ $(4,4,2)$ in $3$ orders gives $3;$ $(6,2,2)$ in $3$ orders gives $3 \cdot 2 = 6;$ $(6,4)$ in $2$ orders gives $2 \cdot 2 = 4;$ and $(8,2)$ in $2$ orders gives $2 \cdot 5 = 10,$ for $28$ per orientation. The total is $27 + 2 \cdot 28 = 83.$