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

1.

Zou 和 Chou 正在练习 $100$ 米短跑，彼此比赛 $6$ 场。Zou 赢了第一场；之后，如果某人赢了上一场，那么他赢下一场的概率是 $\frac{2}{3}$ ，但如果他输了上一场，那么他赢下一场的概率只有 $\frac{1}{3}$ 。Zou 恰好赢 $5$ 场（共 $6$ 场）的概率为 $\frac{m}{n}$ ，其中 $m$ 与 $n$ 是互质正整数。求 $m + n$ 。

Zou and Chou are practicing their $100$ -meter sprints by running $6$ races against each other. Zou wins the first race, and after that, the probability that one of them wins a race is $\frac{2}{3}$ if they won the previous race but only $\frac{1}{3}$ if they lost the previous race. The probability that Zou will win exactly $5$ of the $6$ races is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

答案

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

难度评级：2050

小提示：

Zou 必须在第 $2$ 到第 $6$ 场中恰好输一场。把输在第 $6$ 场的情况与更早输的情况分开处理

Zou must lose exactly one of races $2$ through $6.$ Treat a loss in race $6$ separately from an earlier loss.

大提示：

若较早输一场，会产生两次概率为 $\frac{1}{3}$ 的切换（进入输局和回到赢局）；若最后一场输，只产生一次切换

An earlier loss creates two probability- $\frac{1}{3}$ switches (into and out of the loss); a final-race loss creates just one

解答：

Zou 赢了第 $1$ 场，所以恰好赢 $5$ 场（共 $6$ 场），等价于他在第 $2$ 到第 $6$ 场中恰好输一场。第一场之后，每一场以概率 $\frac{2}{3}$ 重复上一场结果，以概率 $\frac{1}{3}$ 改变上一场结果。

如果输的是第 $6$ 场，那么五次转移是四次重复后接一次切换： $\left(\frac{2}{3}\right)^4 \cdot \frac{1}{3} = \frac{16}{243}$ 。如果输的是第 $i$ 场，其中 $2 \le i \le 5$ ，则有一次切换进入输局、一次切换回到赢局，另有三次重复： $\left(\frac{2}{3}\right)^3 \left(\frac{1}{3}\right)^2 = \frac{8}{243}$ 。这样的 $4$ 个位置共贡献 $\frac{32}{243}$ 。

总概率为 $\frac{16}{243} + \frac{32}{243} = \frac{48}{243} = \frac{16}{81}\text{，}$ 所以 $m + n = 16 + 81 = 97$ 。

Zou wins race $1,$ so winning exactly $5$ of the $6$ races means he loses exactly one of races $2$ through $6.$ Each race after the first repeats the previous outcome with probability $\frac{2}{3}$ and switches with probability $\frac{1}{3}.$

If the loss is race $6,$ the five transitions are four repeats followed by one switch: $\left(\frac{2}{3}\right)^4 \cdot \frac{1}{3} = \frac{16}{243}.$ If the loss is race $i$ for some $2 \le i \le 5,$ there is a switch into the loss and a switch back to winning, plus three repeats: $\left(\frac{2}{3}\right)^3 \left(\frac{1}{3}\right)^2 = \frac{8}{243}$ for each of the $4$ positions, contributing $\frac{32}{243}.$

The total is $\frac{16}{243} + \frac{32}{243} = \frac{48}{243} = \frac{16}{81},$ so $m + n = 16 + 81 = 97.$

2.

在下图中， $ABCD$ 是一个边长 $AB = 3$ 、 $BC = 11$ 的矩形， $AECF$ 是一个边长 $AF = 7$ 、 $FC = 9$ 的矩形，如图所示。两个矩形内部公共阴影区域的面积为 $\frac{m}{n}$ ，其中 $m$ 与 $n$ 是互质正整数。求 $m + n$ 。

In the diagram below, $ABCD$ is a rectangle with side lengths $AB = 3$ and $BC = 11,$ and $AECF$ is a rectangle with side lengths $AF = 7$ and $FC = 9,$ as shown. The area of the shaded region common to the interiors of both rectangles is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

答案

知识点：坐标几何矩形平行四边形

难度评级：2350

小提示：

令 $B$ 为原点，则 $A = (0, 3)$ 、 $C = (11, 0)$ 。注意 $7^2 + 9^2 = AC^2$ ，再确定 $F$ ：它满足 $AF = 7$ 和 $CF = 9$

Place $B$ at the origin so $A = (0, 3)$ and $C = (11, 0).$ Note $7^2 + 9^2 = AC^2,$ then locate $F$ from $AF = 7$ and $CF = 9.$

大提示：

重叠部分是水平直线 $y = 0$ 、 $y = 3$ 与两条平行直线 $AE$ 、 $FC$ 围成的平行四边形

The overlap is a parallelogram between the horizontal lines $y = 0,$ $y = 3$ and the parallel lines $AE,$ $FC$

解答：

令 $B = (0, 0)$ 、 $C = (11, 0)$ 、 $A = (0, 3)$ 、 $D = (11, 3)$ 。由 $AF = 7$ 与 $CF = 9$ 解得（这与 $AC^2 = 11^2 + 3^2 = 130$ $= 7^2 + 9^2$ 一致） $F = \left(\frac{28}{5}, \frac{36}{5}\right)$ ，由于矩形 $AECF$ 的对角线互相平分， $E = A + C - F = \left(\frac{27}{5}, -\frac{21}{5}\right)$ 。

边 $AE$ 与 $FC$ 的方向为 $(3, -4)$ ，分别位于直线 $4x + 3y = 9$ 与 $4x + 3y = 44$ 上；边 $AF$ 与 $EC$ 分别位于直线 $3x - 4y = -12$ 与 $3x - 4y = 33$ 上。矩形 $ABCD$ 中每个点都满足 $-12 \le 3x - 4y \le 33$ ，所以公共区域就是带状区域 $0 \le y \le 3$ 中夹在直线 $4x + 3y = 9$ 与 $4x + 3y = 44$ 之间的部分：一个顶点为 $A = (0, 3)$ 、 $\left(\frac{9}{4}, 0\right)$ 、 $C = (11, 0)$ 和 $\left(\frac{35}{4}, 3\right)$ 的平行四边形。

它的水平边长为 $11 - \frac{9}{4} = \frac{35}{4}$ ，两条水平边之间的高为 $3$ ，所以面积为 $\frac{35}{4} \cdot 3 = \frac{105}{4}$ ，从而 $m + n = 105 + 4 = 109$ 。

Place $B = (0, 0),$ $C = (11, 0),$ $A = (0, 3),$ $D = (11, 3).$ Solving $AF = 7$ and $CF = 9$ (consistent since $AC^2 = 11^2 + 3^2 = 130$ $= 7^2 + 9^2$ ) gives $F = \left(\frac{28}{5}, \frac{36}{5}\right),$ and since the diagonals of rectangle $AECF$ bisect each other, $E = A + C - F = \left(\frac{27}{5}, -\frac{21}{5}\right).$

Sides $AE$ and $FC$ have direction $(3, -4),$ lying on the lines $4x + 3y = 9$ and $4x + 3y = 44;$ sides $AF$ and $EC$ lie on $3x - 4y = -12$ and $3x - 4y = 33.$ Every point of $ABCD$ satisfies $-12 \le 3x - 4y \le 33,$ so the common region is just the part of the strip $0 \le y \le 3$ between the lines $4x + 3y = 9$ and $4x + 3y = 44:$ a parallelogram with vertices $A = (0, 3),$ $\left(\frac{9}{4}, 0\right),$ $C = (11, 0),$ and $\left(\frac{35}{4}, 3\right).$

Its horizontal sides have length $11 - \frac{9}{4} = \frac{35}{4}$ and the height between them is $3,$ so the area is $\frac{35}{4} \cdot 3 = \frac{105}{4},$ and $m + n = 105 + 4 = 109.$

3.

求小于 $1000$ 且可以表示为两个 $2$ 的整数次幂之差的正整数个数。

Find the number of positive integers less than $1000$ that can be expressed as the difference of two integral powers of $2.$

答案

知识点：2的幂因式分解分类讨论

难度评级：2110

小提示：

每个这样的差都可写成 $2^b(2^c - 1)$ ，其中 $c \ge 1$ ，并且它的奇数部分 $2^c - 1$ 会确定 $c$

Every such difference is $2^b(2^c - 1)$ with $c \ge 1,$ and its odd part $2^c - 1$ identifies $c$

大提示：

不同的数对 $(b, c)$ 给出不同的值，所以对每个 $c$ 分别统计小于 $1000$ 的值。注意： $63 \cdot 16 = 1008$ 会打破前面的模式。

Distinct pairs $(b, c)$ give distinct values, so count values below $1000$ for each $c$ separately. Beware: $63 \cdot 16 = 1008$ breaks the pattern.

解答：

两个 $2$ 的幂之差为 $2^a - 2^b = 2^b(2^c - 1)$ ，其中 $c = a - b \ge 1$ 。因为 $2^c - 1$ 是奇数，所以该数的奇数部分确定 $c$ ，而 $2$ 的幂次部分确定 $b$ ，因此不同的数对 $(b, c)$ 会给出不同整数。只需统计满足 $2^b(2^c - 1) \lt 1000$ 的数对。

对 $c = 1, 2, \ldots, 9$ ，因子 $2^c - 1$ 分别为 $1, 3, 7, 15, 31, 63, 127, 255, 511$ ，允许的 $b$ 的个数分别为 $10, 9, 8, 7, 6, 4, 3, 2, 1$ （ $63$ 的计数降为 $4$ ，因为 $63 \cdot 16 = 1008 \gt 1000$ ，而 $31 \cdot 32 = 992$ 仍然符合）。

总数为 $10 + 9 + 8 + 7 + 6$ $+ 4 + 3 + 2 + 1 = 50$ 。

A difference of powers of $2$ is $2^a - 2^b = 2^b(2^c - 1)$ where $c = a - b \ge 1.$ Since $2^c - 1$ is odd, the odd part of the number determines $c$ and the power of $2$ determines $b,$ so distinct pairs $(b, c)$ yield distinct integers. It suffices to count pairs with $2^b(2^c - 1) \lt 1000.$

For $c = 1, 2, \ldots, 9$ the factor $2^c - 1$ is $1, 3, 7, 15, 31, 63, 127, 255, 511,$ and the number of allowed values of $b$ is $10, 9, 8, 7, 6, 4, 3, 2, 1$ respectively (the count for $63$ drops to $4$ because $63 \cdot 16 = 1008 \gt 1000,$ while $31 \cdot 32 = 992$ still fits).

The total is $10 + 9 + 8 + 7 + 6$ $+ 4 + 3 + 2 + 1 = 50.$

4.

求将 $66$ 枚相同硬币分成三个非空堆的方法数，使得第一堆的硬币数少于第二堆，第二堆的硬币数少于第三堆。

Find the number of ways $66$ identical coins can be separated into three nonempty piles so that there are fewer coins in the first pile than in the second pile and fewer coins in the second pile than in the third pile.

答案

知识点：分拆与有序分拆隔板法对称性

难度评级：2180

小提示：

先数所有和为 $66$ 的正整数有序三元组：共有 $\binom{65}{2}$ 个

First count all ordered triples of positive integers summing to $66:$ there are $\binom{65}{2}$

大提示：

去掉有相等数值的三元组（三个全相等，或恰有两个相等），再除以 $3! = 6$

Discard triples with a repeated value (all three equal, or exactly two equal), then divide by $3! = 6$

解答：

正整数有序三元组 $(a, b, c)$ 满足 $a + b + c = 66$ 的个数为 $\binom{65}{2} = 2080$ 。其中三项全相等的恰有一个，即 $(22, 22, 22)$ 。恰有两个数值相等的三元组来自 $2a + c = 66$ 且 $c \ne a$ ：这里 $a$ 可取 $1$ 到 $32$ ，但不能取 $22$ ，得到 $31$ 个多重集合，每个可排列成 $3$ 个有序三元组，所以共有 $93$ 个。

因此有三个互不相同数值的有序三元组为 $2080 - 1 - 93 = 1986$ 个，而每个无序选择 $a \lt b \lt c$ 被计数 $6$ 次。有效分法数为 $\frac{1986}{6} = 331$ 。

The ordered triples $(a, b, c)$ of positive integers with $a + b + c = 66$ number $\binom{65}{2} = 2080.$ Exactly one of them has all three values equal, namely $(22, 22, 22).$ Triples with exactly two values equal come from $2a + c = 66$ with $c \ne a:$ here $a$ can be $1$ through $32$ except $22,$ giving $31$ multisets, each arrangeable in $3$ ways, so $93$ ordered triples.

Hence $2080 - 1 - 93 = 1986$ ordered triples have three distinct values, and each unordered choice $a \lt b \lt c$ is counted $6$ times. The number of valid separations is $\frac{1986}{6} = 331.$

5.

如果一个三项严格递增的整数等差数列的三项平方和等于中项与公差平方的乘积，就称它为特殊数列。求所有特殊数列第三项的和。

Call a three-term strictly increasing arithmetic sequence of integers special if the sum of the squares of the three terms equals the product of the middle term and the square of the common difference. Find the sum of the third terms of all special sequences.

答案

知识点：等差数列丢番图方程整除性

难度评级：2390

小提示：

将三项写成 $a - d$ 、 $a$ 、 $a + d$ ；条件化为 $3a^2 + 2d^2 = ad^2$

Write the terms as $a - d,$ $a,$ $a + d;$ the condition becomes $3a^2 + 2d^2 = ad^2$

大提示：

所以 $d^2 = \frac{3a^2}{a - 2}$ 。令 $t = a - 2$ 可看出 $t$ 必须整除 $12$ ，然后检验六个值。

So $d^2 = \frac{3a^2}{a - 2}.$ Substitute $t = a - 2$ to see that $t$ must divide $12,$ and test the six values.

解答：

将三项写成 $a - d$ 、 $a$ 、 $a + d$ ，其中整数 $d \ge 1$ 。条件为 $\begin{aligned} &(a-d)^2 + a^2 \\ &\quad {}+ (a+d)^2 = ad^2 \\ &\quad\Longleftrightarrow\quad 3a^2 + 2d^2 = ad^2 \end{aligned}\text{，}$ 所以 $d^2(a - 2) = 3a^2$ ，即 $d^2 = \frac{3a^2}{a - 2}$ 。为了使 $d^2$ 为正，需要 $a \gt 2$ 。事实上，若 $a = 0$ ，则 $d = 0$ ，不严格递增；若非零整数 $a \lt 2$ ，右边为负；而 $a = 2$ 不满足原方程。

令 $t = a - 2 \ge 1$ ，得到 $d^2 = \frac{3(t+2)^2}{t} = 3t + 12 + \frac{12}{t}\text{，}$ 所以 $t$ 整除 $12$ 。检验 $t = 1, 2, 3, 4, 6, 12$ ，得到 $d^2 = 27, 24, 25, 27, 32, 49$ ：只有 $t = 3$ 与 $t = 12$ 给出完全平方数。

它们分别给出 $(a, d) = (5, 5)$ ，数列为 $0, 5, 10$ ，以及 $(a, d) = (14, 7)$ ，数列为 $7, 14, 21$ 。第三项之和为 $10 + 21 = 31$ 。

Write the terms as $a - d,$ $a,$ $a + d$ with integer $d \ge 1.$ The condition is $\begin{aligned} &(a-d)^2 + a^2 \\ &\quad {}+ (a+d)^2 = ad^2 \\ &\quad\Longleftrightarrow\quad 3a^2 + 2d^2 = ad^2, \end{aligned}$ so $d^2(a - 2) = 3a^2$ and $d^2 = \frac{3a^2}{a - 2}.$ For $d^2$ to be positive we need $a \gt 2.$ Indeed, $a = 0$ forces $d = 0,$ while for any nonzero integer $a \lt 2$ the right side is negative; $a = 2$ makes the original equation impossible.

Substituting $t = a - 2 \ge 1$ gives $d^2 = \frac{3(t+2)^2}{t} = 3t + 12 + \frac{12}{t},$ so $t$ divides $12.$ Testing $t = 1, 2, 3, 4, 6, 12$ gives $d^2 = 27, 24, 25, 27, 32, 49:$ only $t = 3$ and $t = 12$ yield perfect squares.

These give $(a, d) = (5, 5)$ with sequence $0, 5, 10,$ and $(a, d) = (14, 7)$ with sequence $7, 14, 21.$ The sum of the third terms is $10 + 21 = 31.$

6.

线段 $\overline{AB}$ 、 $\overline{AC}$ ，和 $\overline{AD}$ 是一个立方体的三条棱， $\overline{AG}$ 是穿过立方体中心的一条体对角线。点 $P$ 满足 $BP = 60\sqrt{10}$ 、 $CP = 60\sqrt{5}$ 、 $DP = 120\sqrt{2}$ ，且 $GP = 36\sqrt{7}$ 。求 $AP$ 。

Segments $\overline{AB},$ $\overline{AC},$ and $\overline{AD}$ are edges of a cube and $\overline{AG}$ is a diagonal through the center of the cube. Point $P$ satisfies $BP = 60\sqrt{10},$ $CP = 60\sqrt{5},$ $DP = 120\sqrt{2},$ and $GP = 36\sqrt{7}.$ Find $AP.$

答案

知识点：立体几何坐标几何距离公式

难度评级：2450

小提示：

令 $A$ 为原点，立方体三条棱沿坐标轴，边长为 $s$ ；把每个距离平方展开为 $AP^2$ 、 $s$ ，和点 $P$ 坐标的式子

Put $A$ at the origin with the cube’s edges along the axes and side length $s;$ expand each squared distance in terms of $AP^2,$ $s,$ and the coordinates of $P$

大提示：

组合 $BP^2 + CP^2 + DP^2 - GP^2$ 会化简为 $2\,AP^2$ ：所有含 $s$ 的项都抵消

The combination $BP^2 + CP^2 + DP^2 - GP^2$ collapses to $2\,AP^2:$ all terms involving $s$ cancel

解答：

令 $A$ 为原点， $B = (s, 0, 0)$ 、 $C = (0, s, 0)$ 、 $D = (0, 0, s)$ 、 $G = (s, s, s)$ ，并设 $P = (x, y, z)$ 。展开得 $\begin{aligned} BP^2 &= AP^2 - 2sx + s^2, \\ CP^2 &= AP^2 - 2sy + s^2, \\ DP^2 &= AP^2 - 2sz + s^2 \end{aligned}\text{，}$ 而 $GP^2 = AP^2 - 2s(x + y + z)$ $+ 3s^2$ 。因此 $\begin{aligned} &BP^2 + CP^2 \\ &\quad {}+ DP^2 - GP^2 \\ &= 2\,AP^2 \end{aligned}\text{，}$ 其中所有含 $s$ 或点 $P$ 坐标的项都相消。

已知长度给出 $BP^2 = 36000$ 、 $CP^2 = 18000$ 、 $DP^2 = 28800$ ，以及 $GP^2 = 9072$ ，所以 $\begin{aligned} 2\,AP^2 &= 36000 + 18000 \\ &\quad {}+ 28800 - 9072 \\ &= 73728 \end{aligned}\text{，}$ 从而 $AP^2 = 36864$ ， $AP = 192$ 。

Let $A$ be the origin with $B = (s, 0, 0),$ $C = (0, s, 0),$ $D = (0, 0, s),$ $G = (s, s, s),$ and $P = (x, y, z).$ Expanding, $\begin{aligned} BP^2 &= AP^2 - 2sx + s^2, \\ CP^2 &= AP^2 - 2sy + s^2, \\ DP^2 &= AP^2 - 2sz + s^2, \end{aligned}$ while $GP^2 = AP^2 - 2s(x + y + z)$ $+ 3s^2.$ Therefore $\begin{aligned} &BP^2 + CP^2 \\ &\quad {}+ DP^2 - GP^2 \\ &= 2\,AP^2, \end{aligned}$ with every term involving $s$ or the coordinates of $P$ cancelling.

The given lengths yield $BP^2 = 36000,$ $CP^2 = 18000,$ $DP^2 = 28800,$ and $GP^2 = 9072,$ so $\begin{aligned} 2\,AP^2 &= 36000 + 18000 \\ &\quad {}+ 28800 - 9072 \\ &= 73728, \end{aligned}$ giving $AP^2 = 36864$ and $AP = 192.$

7.

求正整数数对 $(m, n)$ 的个数，其中 $1 \le m \lt n \le 30$ ，且存在实数 $x$ 满足 $\sin(mx) + \sin(nx) = 2\text{。}$

Find the number of pairs $(m, n)$ of positive integers with $1 \le m \lt n \le 30$ such that there exists a real number $x$ satisfying $\sin(mx) + \sin(nx) = 2.$

答案

知识点：三角学丢番图方程最大公约数分类讨论

难度评级：2920

小提示：

两个正弦值都必须等于 $1$ ，所以 $mx = \frac{\pi}{2} + 2\pi a$ 且 $nx = \frac{\pi}{2} + 2\pi b$ ，其中 $a, b$ 为整数

Both sines must equal $1,$ so $mx = \frac{\pi}{2} + 2\pi a$ and $nx = \frac{\pi}{2} + 2\pi b$ for integers $a, b$

大提示：

消去 $x$ 得 $4(na - mb) = m - n$ ，它有整数解当且仅当 $4\gcd(m, n)$ 整除 $n - m$

Eliminating $x$ gives $4(na - mb) = m - n,$ which is solvable exactly when $4\gcd(m, n)$ divides $n - m$

解答：

因为每个正弦值至多为 $1$ ，所以必须有 $\sin(mx) = \sin(nx) = 1$ ，即 $mx = \frac{\pi}{2} + 2\pi a$ 与 $nx = \frac{\pi}{2} + 2\pi b$ ，其中 $a, b$ 为整数。消去 $x$ 得 $n(4a + 1) = m(4b + 1)$ ，也就是 $4(na - mb) = m - n$ 。当 $a$ 和 $b$ 取遍整数时， $na - mb$ 恰好取遍 $g = \gcd(m, n)$ 的倍数，所以存在解当且仅当 $4g$ 整除 $n - m$ 。等价地，写 $m = gm'$ 、 $n = gn'$ ，当且仅当 $m' \equiv n' \pmod 4$ （这也迫使 $m'$ 和 $n'$ 都为奇数）。

对每个 $g$ ，统计满足 $m' \lt n' \le \lfloor \frac{30}{g} \rfloor$ 的互质奇数对，且二者模 $4$ 同余。若 $g = 1$ ：在 $1, 3, \ldots, 29$ 中，有八个数 $\equiv 1$ ，七个数 $\equiv 3 \pmod 4$ ，给出 $\binom{8}{2} + \binom{7}{2} = 49$ 对，其中 $\{3,15\}$ 、 $\{3,27\}$ 、 $\{9,21\}$ 、 $\{15,27\}$ 、 $\{5,25\}$ 这五对不互质，剩下 $44$ 对。若 $g = 2$ （奇数不超过 $15$ ）： $\binom{4}{2} + \binom{4}{2} = 12$ ，减去 $\{3,15\}$ 得 $11$ 。若 $g = 3$ （不超过 $10$ ）：数对 $\{1,5\}, \{1,9\}, \{5,9\}, \{3,7\}$ 给出 $4$ 。若 $g = 4$ （不超过 $7$ ）： $\{1,5\}$ 与 $\{3,7\}$ 给出 $2$ 。若 $g = 5$ 和 $g = 6$ ：都只有 $\{1,5\}$ ，各给出 $1$ 。若 $g \ge 7$ ，就需要两个不同的奇数不超过 $\lfloor \frac{30}{g} \rfloor \le 4$ 且模 $4$ 同余，这是不可能的。

总数为 $44 + 11 + 4 + 2 + 1 + 1 = 63$ 。

Since each sine is at most $1,$ we need $\sin(mx) = \sin(nx) = 1,$ i.e. $mx = \frac{\pi}{2} + 2\pi a$ and $nx = \frac{\pi}{2} + 2\pi b$ for integers $a, b.$ Eliminating $x$ gives $n(4a + 1) = m(4b + 1),$ that is, $4(na - mb) = m - n.$ As $a$ and $b$ range over the integers, $na - mb$ takes exactly the multiples of $g = \gcd(m, n),$ so a solution exists if and only if $4g$ divides $n - m$ — equivalently, writing $m = gm'$ and $n = gn',$ if and only if $m' \equiv n' \pmod 4$ (which forces both $m'$ and $n'$ odd).

For each $g$ we count coprime pairs $m' \lt n' \le \lfloor \frac{30}{g} \rfloor$ of odd numbers in the same class mod $4.$ For $g = 1:$ among $1, 3, \ldots, 29$ there are eight numbers $\equiv 1$ and seven $\equiv 3 \pmod 4,$ giving $\binom{8}{2} + \binom{7}{2} = 49$ pairs, of which the five pairs $\{3,15\},$ $\{3,27\},$ $\{9,21\},$ $\{15,27\},$ $\{5,25\}$ are not coprime, leaving $44.$ For $g = 2$ (odd numbers up to $15$ ): $\binom{4}{2} + \binom{4}{2} = 12$ minus the pair $\{3,15\}$ gives $11.$ For $g = 3$ (up to $10$ ): the pairs $\{1,5\}, \{1,9\}, \{5,9\}, \{3,7\}$ give $4.$ For $g = 4$ (up to $7$ ): $\{1,5\}$ and $\{3,7\}$ give $2.$ For $g = 5$ and $g = 6:$ only $\{1,5\},$ giving $1$ each. For $g \ge 7$ we would need two distinct odd numbers up to $\lfloor \frac{30}{g} \rfloor \le 4$ in the same class mod $4,$ which is impossible.

The total is $44 + 11 + 4 + 2 + 1 + 1 = 63.$

8.

答案

知识点：绝对值函数分类讨论

难度评级：2560

小提示：

令 $f(x) = \left|20|x| - x^2\right|$ 。方程分解为 $f(x) = c + 21$ 与 $f(x) = c - 21$ 。

Let $f(x) = \left|20|x| - x^2\right|.$ The equation splits into $f(x) = c + 21$ and $f(x) = c - 21.$

大提示：

画出 $f$ 的图像：每个严格介于 $0$ 与 $100$ 之间的高度恰好被取到 $6$ 次，所以两个高度都必须落在这个范围内

Graph $f:$ every height strictly between $0$ and $100$ is hit exactly $6$ times, so both levels must land in that range

解答：

设 $f(x) = \left|20|x| - x^2\right|$ ，这是偶函数；原方程表示 $f(x) = c + 21$ 或 $f(x) = c - 21$ 。当 $x \ge 0$ 时， $f$ 从 $0$ 增至 $100$ ，这发生在 $[0, 10]$ 上；然后降回 $0$ ，这发生在 $x = 20$ 处，之后无界增大。因此当 $k$ 满足 $0 \lt k \lt 100$ 时，方程 $f(x) = k$ 有 $3$ 个正解，故总共有 $6$ 个解；当 $k = 100$ 时有 $4$ 个解；当 $k \gt 100$ 时有 $2$ 个解；当 $k = 0$ 时有 $3$ 个解，即 $0$ 与 $\pm 20$ 。

两个高度 $c + 21$ 与 $c - 21$ 不同，所以要达到 $12$ 个解，唯一方式是 $6 + 6$ ： $c - 21$ 与 $c + 21$ 都必须严格介于 $0$ 与 $100$ 之间。这意味着 $c \ge 22$ 且 $c \le 78$ ，而每个这样的整数都可行，共有 $78 - 22 + 1 = 57$ 个。

Set $f(x) = \left|20|x| - x^2\right|,$ an even function; the equation says $f(x) = c + 21$ or $f(x) = c - 21.$ For $x \ge 0,$ the graph of $f$ rises from $0$ to $100$ on $[0, 10],$ falls back to $0$ at $x = 20,$ then increases without bound. So for $k$ with $0 \lt k \lt 100,$ the equation $f(x) = k$ has $3$ positive solutions, hence $6$ solutions in all; for $k = 100$ it has $4;$ for $k \gt 100$ it has $2;$ and for $k = 0$ it has $3$ (namely $0$ and $\pm 20$ ).

The two levels $c + 21$ and $c - 21$ are distinct, so the only way to reach $12$ solutions is $6 + 6:$ both $c - 21$ and $c + 21$ must lie strictly between $0$ and $100.$ This means $c \ge 22$ and $c \le 78,$ and every such integer works: there are $78 - 22 + 1 = 57$ values.

9.

设 $ABCD$ 是等腰梯形，满足 $AD = BC$ 且 $AB \lt CD$ 。已知从 $A$ 到直线 $BC$ 、 $CD$ ，和 $BD$ 的距离分别为 $15$ 、 $18$ ，和 $10$ ，设 $K$ 为 $ABCD$ 的面积。求 $\sqrt{2} \cdot K$ 。

Let $ABCD$ be an isosceles trapezoid with $AD = BC$ and $AB \lt CD.$ Suppose that the distances from $A$ to the lines $BC,$ $CD,$ and $BD$ are $15,$ $18,$ and $10,$ respectively. Let $K$ be the area of $ABCD.$ Find $\sqrt{2} \cdot K.$

答案

知识点：梯形坐标几何距离公式

难度评级：2990

小提示：

高为 $18$ ，对应于到 $CD$ 的距离，所以设 $D = (0, 0)$ 、 $C = (c, 0)$ 、 $A = (a, 18)$ 、 $B = (c - a, 18)$

The distance $18$ to $CD$ is the height, so set $D = (0, 0),$ $C = (c, 0),$ $A = (a, 18),$ $B = (c - a, 18)$

大提示：

到 $BC$ 与 $BD$ 的距离公式中，分子都为 $18 \cdot AB$ ；比较二者可得 $a = \frac{2}{5} AB$ ，再解出 $AB$

The distances to $BC$ and $BD$ both have numerator $18 \cdot AB$ in the point-line formula; comparing them gives $a = \frac{2}{5} AB,$ then solve for $AB$

解答：

因为 $AB \parallel CD$ ，高为 $18$ ，也就是从 $A$ 到 $CD$ 的距离。令 $D = (0, 0)$ 、 $C = (c, 0)$ 、 $A = (a, 18)$ 、 $B = (c - a, 18)$ ，并设 $u = AB = c - 2a \gt 0$ 。点到直线的距离公式给出 $\begin{aligned} \frac{18u}{\sqrt{324 + a^2}} &= 15, \\ \small \frac{18u}{\sqrt{324 + (u + a)^2}} \\ &= 10\text{。} \end{aligned}$ 所以 $324 + a^2 = \left(\frac{6u}{5}\right)^2$ ，且 $324 + (u + a)^2 = \left(\frac{9u}{5}\right)^2$ 。

两式相减，得 $u(u + 2a) = \frac{81 - 36}{25}u^2 = \frac{9}{5}u^2$ ，因此 $u + 2a = \frac{9}{5}u$ ，即 $a = \frac{2}{5}u$ 。代回可得 $324 = \frac{36u^2}{25} - \frac{4u^2}{25} = \frac{32u^2}{25}$ ，所以 $u^2 = \frac{2025}{8}$ ， $u = \frac{45\sqrt{2}}{4}$ 。

因此 $CD = c = u + 2a = \frac{9}{5}u$ $= \frac{81\sqrt{2}}{4}$ ，并且 $\begin{aligned} K &= \frac{AB + CD}{2} \cdot 18 \\ &= 9\left(\frac{45\sqrt{2}}{4} + \frac{81\sqrt{2}}{4}\right) \\ &= \frac{567\sqrt{2}}{2} \end{aligned}\text{，}$ 所以 $\sqrt{2} \cdot K = 567$ 。

Since $AB \parallel CD,$ the distance $18$ from $A$ to $CD$ is the height. Put $D = (0, 0),$ $C = (c, 0),$ $A = (a, 18),$ $B = (c - a, 18),$ and let $u = AB = c - 2a \gt 0.$ The point-to-line distance formulas give $\begin{aligned} \frac{18u}{\sqrt{324 + a^2}} &= 15, \\ \small \frac{18u}{\sqrt{324 + (u + a)^2}} \\ &= 10. \end{aligned}$ so $324 + a^2 = \left(\frac{6u}{5}\right)^2$ and $324 + (u + a)^2 = \left(\frac{9u}{5}\right)^2.$

Subtracting, $u(u + 2a) = \frac{81 - 36}{25}u^2 = \frac{9}{5}u^2,$ hence $u + 2a = \frac{9}{5}u$ and $a = \frac{2}{5}u.$ Substituting back, $324 = \frac{36u^2}{25} - \frac{4u^2}{25} = \frac{32u^2}{25},$ so $u^2 = \frac{2025}{8}$ and $u = \frac{45\sqrt{2}}{4}.$

Then $CD = c = u + 2a = \frac{9}{5}u$ $= \frac{81\sqrt{2}}{4},$ and $\begin{aligned} K &= \frac{AB + CD}{2} \cdot 18 \\ &= 9\left(\frac{45\sqrt{2}}{4} + \frac{81\sqrt{2}}{4}\right) \\ &= \frac{567\sqrt{2}}{2}, \end{aligned}$ so $\sqrt{2} \cdot K = 567.$

10.

考虑正有理数列 $(a_k)_{k \ge 1}$ ，其中 $a_1 = \frac{2020}{2021}$ ，且对 $k \ge 1$ ，若 $a_k = \frac{m}{n}$ ，其中 $m$ 与 $n$ 为互质正整数，则 $a_{k+1} = \frac{m + 18}{n + 19}\text{。}$ 求所有正整数 $j$ 的和，使得有理数 $a_j$ 可写成 $\frac{t}{t+1}$ 的形式，其中 $t$ 为正整数。

Consider the sequence $(a_k)_{k \ge 1}$ of positive rational numbers defined by $a_1 = \frac{2020}{2021}$ and for $k \ge 1,$ if $a_k = \frac{m}{n}$ for relatively prime positive integers $m$ and $n,$ then $a_{k+1} = \frac{m + 18}{n + 19}.$ Determine the sum of all positive integers $j$ such that the rational number $a_j$ can be written in the form $\frac{t}{t+1}$ for some positive integer $t.$

答案

知识点：最大公约数递推不变量

难度评级：2990

小提示：

形式 $\frac{t}{t+1}$ 表示最简分数中分母减分子等于 $1$ 。追踪这个差在每一步如何变化

The form $\frac{t}{t+1}$ means denominator minus numerator equals $1$ in lowest terms. Track how that difference evolves step by step.

大提示：

量 $19m - 18n$ 在加上 $18$ 和 $19$ 时不变，约分时会除以被约掉的因子；它一开始是 $2002 = 2 \cdot 7 \cdot 11 \cdot 13$

The quantity $19m - 18n$ is unchanged by adding $18$ and $19,$ and is divided by any factor you cancel; it starts at $2002 = 2 \cdot 7 \cdot 11 \cdot 13$

解答：

将 $a_k = \frac{m}{n}$ 写成最简形式，并令 $d = n - m$ ，于是 $a_j$ 具有 $\frac{t}{t+1}$ 的形式，当且仅当 $d = 1$ 。一步操作把 $(m, n)$ 变为 $(m + 18,\, n + 19)$ ，再约去 $g = \gcd(m + 18, n + 19)$ 。两个事实控制全过程。第一， $I = 19m - 18n$ 满足 $19(m + 18) - 18(n + 19) = I$ ，所以 $I$ 在平移时不变，在约分时被 $g$ 除。第二，由于 $I = 19(m + 18) - 18(n + 19)$ $= (m + 18) - 18(d + 1)$ ，一个数同时整除 $m + 18$ 与 $n + 19$ ，当且仅当它同时整除 $d + 1$ 与 $I$ 。因此 $g = \gcd(d + 1,\, I)$ ，约分后的新差为 $\frac{d + 1}{g}$ 。

初始时 $I = 19 \cdot 2020 - 18 \cdot 2021 = 2002$ $= 2 \cdot 7 \cdot 11 \cdot 13$ ，且 $d = 1$ ，所以 $j = 1$ 可行。下一步 $d + 1 = 2$ 、 $g = 2$ ： $a_2 = \frac{2038}{2040} = \frac{1019}{1020}$ ，所以 $j = 2$ 可行，且 $I = 1001 = 7 \cdot 11 \cdot 13$ 。从这里开始， $d$ 依次增长为 $1, 2, 3, \ldots$ ，直到 $d + 1$ 与 $I$ 有公因子：当 $d + 1 = 7$ 时，得到 $a_8 = \frac{161}{162}$ （约去 $7$ ，此时 $I = 143$ ）；然后当 $d + 1 = 11$ 时， $a_{18} = \frac{31}{32}$ （约去 $11$ ，此时 $I = 13$ ）；再当 $d + 1 = 13$ 时， $a_{30} = \frac{19}{20}$ （约去 $13$ ，此时 $I = 1$ ）。每次约分都使用 $g = d + 1$ ，所以 $d$ 回到 $1$ 的时刻为 $j = 8$ 、 $18$ 、 $30$ 。

一旦 $I = 1$ ，之后不会再约分，所以 $d$ 会一直增加，再也不会等于 $1$ 。有效下标为 $j = 1, 2, 8, 18, 30$ ，其和为 $1 + 2 + 8 + 18 + 30 = 59$ 。

Write $a_k = \frac{m}{n}$ in lowest terms and let $d = n - m,$ so $a_j$ has the form $\frac{t}{t+1}$ exactly when $d = 1.$ One step sends $(m, n)$ to $(m + 18,\, n + 19)$ and then cancels $g = \gcd(m + 18, n + 19).$ Two facts control everything. First, $I = 19m - 18n$ satisfies $19(m + 18) - 18(n + 19) = I,$ so $I$ is unchanged by the shift and divided by $g$ upon cancellation. Second, since $I = 19(m + 18) - 18(n + 19)$ $= (m + 18) - 18(d + 1),$ a number divides both $m + 18$ and $n + 19$ exactly when it divides both $d + 1$ and $I;$ hence $g = \gcd(d + 1,\, I),$ and after cancelling, the new difference is $\frac{d + 1}{g}.$

Initially $I = 19 \cdot 2020 - 18 \cdot 2021 = 2002$ $= 2 \cdot 7 \cdot 11 \cdot 13$ and $d = 1,$ so $j = 1$ works. The next step has $d + 1 = 2,$ $g = 2:$ $a_2 = \frac{2038}{2040} = \frac{1019}{1020},$ so $j = 2$ works and $I = 1001 = 7 \cdot 11 \cdot 13.$ From there $d$ climbs $1, 2, 3, \ldots$ until $d + 1$ shares a factor with $I:$ at $d + 1 = 7$ we get $a_8 = \frac{161}{162}$ (cancel $7,$ now $I = 143$ ); then at $d + 1 = 11,$ $a_{18} = \frac{31}{32}$ (cancel $11,$ now $I = 13$ ); then at $d + 1 = 13,$ $a_{30} = \frac{19}{20}$ (cancel $13,$ now $I = 1$ ). Each cancellation used $g = d + 1,$ so $d$ returned to $1$ at $j = 8,$ $18,$ and $30.$

Once $I = 1,$ no further cancellation is possible, so $d$ increases forever and never equals $1$ again. The valid indices are $j = 1, 2, 8, 18, 30,$ with sum $1 + 2 + 8 + 18 + 30 = 59.$

11.

设 $ABCD$ 是一个圆内接四边形，满足 $AB = 4$ 、 $BC = 5$ 、 $CD = 6$ 、 $DA = 7$ 。设 $A_1$ 与 $C_1$ 分别为从 $A$ 与 $C$ 向直线 $BD$ 所作垂线的垂足， $B_1$ 与 $D_1$ 分别为从 $B$ 与 $D$ 向直线 $AC$ 所作垂线的垂足。 $A_1B_1C_1D_1$ 的周长为 $\frac{m}{n}$ ，其中 $m$ 与 $n$ 是互质正整数。求 $m + n$ 。

Let $ABCD$ be a cyclic quadrilateral with $AB = 4,$ $BC = 5,$ $CD = 6,$ and $DA = 7.$ Let $A_1$ and $C_1$ be the feet of the perpendiculars from $A$ and $C,$ respectively, to line $BD,$ and let $B_1$ and $D_1$ be the feet of the perpendiculars from $B$ and $D,$ respectively, to line $AC.$ The perimeter of $A_1B_1C_1D_1$ is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

答案

知识点：圆内接四边形托勒密定理婆罗摩笈多公式相似

难度评级：3060

小提示：

设 $P$ 为两条对角线的交点， $\theta$ 为它们之间的夹角；每个垂足满足 $PA_1 = PA\cos\theta$ ，所以 $A_1B_1C_1D_1$ 与 $ABCD$ 相似，相似比为 $\cos\theta$

With $P$ the diagonals’ intersection and $\theta$ the angle between them, each foot satisfies $PA_1 = PA\cos\theta,$ so $A_1B_1C_1D_1$ is similar to $ABCD$ with ratio $\cos\theta$

大提示：

求 $\sin\theta$ ：利用面积 $= \frac{1}{2} d_1 d_2 \sin\theta$ ，其中 $d_1 d_2$ 由托勒密定理求得，面积由婆罗摩笈多公式求得

Get $\sin\theta$ from area $= \frac{1}{2} d_1 d_2 \sin\theta,$ using Ptolemy for $d_1 d_2$ and Brahmagupta for the area

解答：

设 $P = AC \cap BD$ ，并令 $\theta$ 为两条对角线之间的锐角。因为 $A$ 位于直线 $AC$ 上，其垂足 $A_1$ 落在 $BD$ 上并满足 $PA_1 = PA\cos\theta$ ；在 $BD$ 的两条射线中，它位于与射线 $PA$ 成锐角的一条；其他三个垂足同理。所以， $A_1B_1C_1D_1$ 是 $ABCD$ 在以下变换下的像：将从 $P$ 出发的每条射线旋转 $\theta$ 到另一条对角线方向，并按 $\cos\theta$ 缩放。在 $P$ 处的对应三角形相似，相似比为 $\cos\theta$ ，因而 $A_1B_1C_1D_1$ 的每条边都是 $\cos\theta$ 倍的 $ABCD$ 对应边。故其周长为 $(4 + 5 + 6 + 7)\cos\theta = 22\cos\theta$ 。

由托勒密定理， $AC \cdot BD = 4 \cdot 6 + 5 \cdot 7 = 59$ 。由婆罗摩笈多公式，取 $s = 11$ ，面积为 $\sqrt{7 \cdot 6 \cdot 5 \cdot 4} = 2\sqrt{210}$ 。另一方面，面积也等于 $\frac{1}{2} \, AC \cdot BD \sin\theta$ ，所以 $\sin\theta = \frac{4\sqrt{210}}{59}$ ，从而 $\begin{aligned} \cos^2\theta &= 1 - \frac{3360}{3481} = \frac{121}{3481}, \\ \cos\theta &= \frac{11}{59} \end{aligned}\text{。}$

周长为 $22 \cdot \frac{11}{59} = \frac{242}{59}$ ，且已经是最简分数，所以 $m + n = 242 + 59 = 301$ 。

Let $P = AC \cap BD$ and let $\theta$ be the acute angle between the diagonals. Since $A$ lies on line $AC,$ its foot $A_1$ on $BD$ satisfies $PA_1 = PA\cos\theta,$ landing on the ray of $BD$ making the acute angle with ray $PA;$ the same holds for all four feet. So $A_1B_1C_1D_1$ is the image of $ABCD$ under the map that rotates each ray from $P$ onto the other diagonal (through angle $\theta$ ) and scales by $\cos\theta:$ corresponding triangles at $P$ are similar with ratio $\cos\theta,$ and every side of $A_1B_1C_1D_1$ is $\cos\theta$ times the corresponding side of $ABCD.$ Hence the perimeter is $(4 + 5 + 6 + 7)\cos\theta = 22\cos\theta.$

By Ptolemy, $AC \cdot BD = 4 \cdot 6 + 5 \cdot 7 = 59.$ By Brahmagupta with $s = 11,$ the area is $\sqrt{7 \cdot 6 \cdot 5 \cdot 4} = 2\sqrt{210}.$ Since the area also equals $\frac{1}{2} \, AC \cdot BD \sin\theta,$ we get $\sin\theta = \frac{4\sqrt{210}}{59},$ so $\begin{aligned} \cos^2\theta &= 1 - \frac{3360}{3481} = \frac{121}{3481}, \\ \cos\theta &= \frac{11}{59}. \end{aligned}$

The perimeter is $22 \cdot \frac{11}{59} = \frac{242}{59},$ which is in lowest terms, so $m + n = 242 + 59 = 301.$

12.

设 $A_1A_2A_3 \ldots A_{12}$ 是一个 $12$ 边形。三只青蛙起初分别在 $A_4$ 、 $A_8$ 和 $A_{12}$ 上。每分钟结束时，三只青蛙同时各自跳到当前顶点相邻的两个顶点之一，两个选择等可能且彼此独立。只要有两只青蛙同时到达同一个顶点，三只青蛙就都停止跳跃。青蛙停止跳跃前的期望分钟数为 $\frac{m}{n}$ ，其中 $m$ 与 $n$ 是互质正整数。求 $m + n$ 。

Let $A_1A_2A_3 \ldots A_{12}$ be a dodecagon ( $12$ -gon). Three frogs initially sit at $A_4,$ $A_8,$ and $A_{12}.$ At the end of each minute, simultaneously, each of the three frogs jumps to one of the two vertices adjacent to its current position, chosen randomly and independently with both choices being equally likely. All three frogs stop jumping as soon as two frogs arrive at the same vertex at the same time. The expected number of minutes until the frogs stop jumping is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

答案

知识点：期望值随机游走递推概率

难度评级：3160

小提示：

追踪圆周上三只青蛙之间的三个弧长间隔，初始为 $4, 4, 4$ ；每分钟每个间隔会变化 $-2$ 、 $0$ ，或 $2$ ，当某个间隔变为 $0$ 时停止

Track the three arc gaps between the frogs around the circle, starting at $4, 4, 4;$ each minute every gap changes by $-2,$ $0,$ or $2,$ and the frogs stop when a gap reaches $0$

大提示：

停止前只会出现间隔多重集合 $\{4,4,4\}$ 、 $\{2,4,6\}$ 、 $\{2,2,8\}$ 。对每个状态列出 $8$ 种等可能跳法，并解三个线性方程。

Only gap multisets $\{4,4,4\},$ $\{2,4,6\},$ $\{2,2,8\}$ occur before stopping. List the $8$ equally likely jump combinations from each and solve three linear equations.

解答：

追踪圆周上相邻青蛙之间的三个间隔；它们从 $(4, 4, 4)$ 开始，且总和始终为 $12$ 。若三只青蛙的跳跃方向为 $X_1, X_2, X_3 \in \{\pm 1\}$ ，则三个间隔分别改变 $X_2 - X_1$ 、 $X_3 - X_2$ 、 $X_1 - X_3$ ，所以每个间隔保持偶数，并且过程恰在某个间隔变为 $0$ 时停止。枚举 $8$ 种等可能的符号选择：从 $\{4,4,4\}$ 出发，以概率 $\frac{2}{8}$ 留在原状态，转到 $\{2,4,6\}$ 的概率为 $\frac{6}{8}$ 。从 $\{2,4,6\}$ 出发，以概率 $\frac{4}{8}$ 留在原状态，转到 $\{4,4,4\}$ 或 $\{2,2,8\}$ 的概率各为 $\frac{1}{8}$ ，并以概率 $\frac{2}{8}$ 停止。从 $\{2,2,8\}$ 出发，以概率 $\frac{2}{8}$ 留在原状态，转到 $\{2,4,6\}$ 的概率为 $\frac{2}{8}$ ，并以概率 $\frac{4}{8}$ 停止。

设 $E_1, E_2, E_3$ 分别为从 $\{4,4,4\}$ 、 $\{2,4,6\}$ 、 $\{2,2,8\}$ 出发的剩余期望时间。则 $\begin{aligned} E_1 &= 1 + \tfrac{1}{4}E_1 + \tfrac{3}{4}E_2, \\ E_2 &= 1 + \tfrac{1}{2}E_2 + \tfrac{1}{8}E_1 \\ &\quad {}+ \tfrac{1}{8}E_3, \\ E_3 &= 1 + \tfrac{1}{4}E_3 + \tfrac{1}{4}E_2 \end{aligned}\text{。}$ 第三式给出 $E_3 = \frac{4}{3} + \frac{E_2}{3}$ ；代入第二式得 $E_2 = 4$ ，于是 $E_3 = \frac{8}{3}$ ，且 $E_1 = \frac{4}{3} + E_2 = \frac{16}{3}$ 。

期望分钟数为 $\frac{16}{3}$ ，所以 $m + n = 16 + 3 = 19$ 。

Track the three gaps between consecutive frogs around the circle; they start at $(4, 4, 4)$ and always sum to $12.$ If the frogs jump by $X_1, X_2, X_3 \in \{\pm 1\},$ the gaps change by $X_2 - X_1,$ $X_3 - X_2,$ $X_1 - X_3,$ so each gap stays even and the process stops exactly when some gap becomes $0.$ Enumerating the $8$ equally likely sign choices: from $\{4,4,4\},$ the state stays with probability $\frac{2}{8}$ and moves to $\{2,4,6\}$ with probability $\frac{6}{8}.$ From $\{2,4,6\}:$ stay with probability $\frac{4}{8},$ move to $\{4,4,4\}$ or $\{2,2,8\}$ with probability $\frac{1}{8}$ each, and stop with probability $\frac{2}{8}.$ From $\{2,2,8\}:$ stay with probability $\frac{2}{8},$ move to $\{2,4,6\}$ with probability $\frac{2}{8},$ and stop with probability $\frac{4}{8}.$

Let $E_1, E_2, E_3$ be the expected remaining times from $\{4,4,4\},$ $\{2,4,6\},$ $\{2,2,8\}.$ Then $\begin{aligned} E_1 &= 1 + \tfrac{1}{4}E_1 + \tfrac{3}{4}E_2, \\ E_2 &= 1 + \tfrac{1}{2}E_2 + \tfrac{1}{8}E_1 \\ &\quad {}+ \tfrac{1}{8}E_3, \\ E_3 &= 1 + \tfrac{1}{4}E_3 + \tfrac{1}{4}E_2. \end{aligned}$ The third gives $E_3 = \frac{4}{3} + \frac{E_2}{3};$ substituting into the second yields $E_2 = 4,$ then $E_3 = \frac{8}{3}$ and $E_1 = \frac{4}{3} + E_2 = \frac{16}{3}.$

The expected number of minutes is $\frac{16}{3},$ so $m + n = 16 + 3 = 19.$

13.

圆 $\omega_1$ 与 $\omega_2$ 的半径分别为 $961$ 和 $625$ ，且相交于不同的两点 $A$ 与 $B$ 。第三个圆 $\omega$ 与 $\omega_1$ 和 $\omega_2$ 都外切。设直线 $AB$ 与 $\omega$ 相交于两点 $P$ 和 $Q$ ，且小弧 $\widehat{PQ}$ 的度数为 $120^\circ$ 。求 $\omega_1$ 与 $\omega_2$ 的圆心之间的距离。

Circles $\omega_1$ and $\omega_2$ with radii $961$ and $625,$ respectively, intersect at distinct points $A$ and $B.$ A third circle $\omega$ is externally tangent to both $\omega_1$ and $\omega_2.$ Suppose line $AB$ intersects $\omega$ at two points $P$ and $Q$ such that the measure of minor arc $\widehat{PQ}$ is $120^\circ.$ Find the distance between the centers of $\omega_1$ and $\omega_2.$

答案

知识点：根轴圆幂相切圆弦

难度评级：3270

小提示：

直线 $AB$ 是 $\omega_1$ 与 $\omega_2$ 的根轴，而 $120^\circ$ 的弧说明 $\omega$ 的圆心到这条直线的距离等于它半径的一半

Line $AB$ is the radical axis of $\omega_1$ and $\omega_2,$ and the $120^\circ$ arc puts the center of $\omega$ at distance half its radius from that line

大提示：

由相切可知 $\omega$ 的圆心关于 $\omega_i$ 的幂为 $r^2 + 2r r_i$ ；两个幂的差等于 $2 \cdot O_1O_2 \cdot \frac{r}{2}$

By tangency the power of $\omega$ ’s center with respect to $\omega_i$ is $r^2 + 2r r_i;$ the difference of the two powers equals $2 \cdot O_1O_2 \cdot \frac{r}{2}$

解答：

设 $O$ 与 $r$ 为 $\omega$ 的圆心和半径， $O_1, O_2$ 为另外两个圆心。外切给出 $OO_1 = r + 961$ ，所以 $O$ 关于 $\omega_1$ 的幂为 $OO_1^2 - 961^2 = r^2 + 2 \cdot 961r$ ；同理，关于 $\omega_2$ 的幂为 $r^2 + 2 \cdot 625r$ 。两者之差为 $2r(961 - 625) = 672r$ 。

对任意点 $X$ ，差 $\mathrm{pow}_{\omega_1}(X) - \mathrm{pow}_{\omega_2}(X)$ $= (XO_1^2 - XO_2^2)$ $- (961^2 - 625^2)$ 是关于 $X$ 的线性函数，且在根轴直线 $AB$ 上为零；它沿垂直于 $AB$ 的方向变化率为 $2 \cdot O_1O_2$ 。因此这个差等于 $2 \cdot O_1O_2 \cdot \operatorname{dist}(O, AB)$ 。另一方面，弦 $PQ$ 所在的圆为 $\omega$ ，它对应 $120^\circ$ 的圆心角，所以 $\operatorname{dist}(O, AB) = r\cos 60^\circ = \frac{r}{2}$ 。

因此 $672r = 2 \cdot O_1O_2 \cdot \frac{r}{2} = O_1O_2 \cdot r$ ，两圆心距离为 $672$ 。

Let $O$ and $r$ be the center and radius of $\omega,$ and $O_1, O_2$ the other centers. External tangency gives $OO_1 = r + 961,$ so the power of $O$ with respect to $\omega_1$ is $OO_1^2 - 961^2 = r^2 + 2 \cdot 961r;$ similarly its power with respect to $\omega_2$ is $r^2 + 2 \cdot 625r.$ The difference is $2r(961 - 625) = 672r.$

For any point $X,$ the difference $\mathrm{pow}_{\omega_1}(X) - \mathrm{pow}_{\omega_2}(X)$ $= (XO_1^2 - XO_2^2)$ $- (961^2 - 625^2)$ is a linear function of $X$ that vanishes on the radical axis, which is line $AB;$ its rate of change perpendicular to $AB$ is $2 \cdot O_1O_2.$ So the difference equals $2 \cdot O_1O_2 \cdot \operatorname{dist}(O, AB).$ Meanwhile the chord $PQ$ of $\omega$ subtends a $120^\circ$ central angle, so $\operatorname{dist}(O, AB) = r\cos 60^\circ = \frac{r}{2}.$

Therefore $672r = 2 \cdot O_1O_2 \cdot \frac{r}{2} = O_1O_2 \cdot r,$ and the distance between the centers is $672.$

14.

对任意正整数 $a$ ， $\sigma(a)$ 表示 $a$ 的所有正整数因数之和。设 $n$ 是使 $\sigma(a^n) - 1$ 能被 $2021$ 整除的最小正整数，其中该条件须对所有正整数 $a$ 成立。求 $n$ 的质因数分解中所有质因数的和。

For any positive integer $a,$ $\sigma(a)$ denotes the sum of the positive integer divisors of $a.$ Let $n$ be the least positive integer such that $\sigma(a^n) - 1$ is divisible by $2021$ for all positive integers $a.$ Find the sum of the prime factors in the prime factorization of $n.$

答案

知识点：因数之和乘法阶最小公倍数模运算

难度评级：3270

小提示：

分解 $2021 = 43 \cdot 47$ 。由于 $\sigma$ 是乘法函数，只需保证 $p + p^2 + \cdots + p^{en} \equiv 0$ 在模 $43$ 和模 $47$ 下都成立，其中 $p$ 是任意质数， $e$ 是任意正整数

Factor $2021 = 43 \cdot 47.$ Since $\sigma$ is multiplicative, it suffices to force $p + p^2 + \cdots + p^{en} \equiv 0$ modulo $43$ and $47$ for every prime $p$ and every positive integer $e$

大提示：

满足 $p \equiv 1 \pmod q$ 的质数会迫使 $q$ 整除 $n$ ，而模 $q$ 的原根质数会迫使 $q - 1$ 整除 $n$ ；取最小公倍数

Primes $p \equiv 1 \pmod q$ force $q$ to divide $n,$ while primes that are primitive roots mod $q$ force $q - 1$ to divide $n;$ take the least common multiple

解答：

注意 $2021 = 43 \cdot 47$ 。若 $a = \prod p_i^{e_i}$ ，则 $\sigma(a^n) = \prod \sigma(p_i^{e_i n})$ ，所以只需（且取 $a$ 为质数可知也必须）有 $\sigma(p^N) \equiv 1$ ，即 $p + p^2 + \cdots + p^N \equiv 0$ $\pmod{43 \cdot 47}$ ，其中 $p$ 是任意质数， $N$ 是 $n$ 的任意倍数。

固定 $q \in \{43, 47\}$ 。若 $q$ 整除 $p$ ，则和为 $0$ 。若 $p \equiv 1 \pmod q$ ，则该和 $\equiv N$ ，所以选择这样的质数（由狄利克雷定理）会迫使 $q$ 整除 $n$ 。否则，和为 $p \cdot \frac{p^N - 1}{p - 1}$ ，其中 $p - 1$ 可逆，所以需要 $p^N \equiv 1 \pmod q$ ；选择 $p$ 为模 $q$ 的一个原根质数会迫使 $q - 1$ 整除 $n$ 。反过来，如果 $q(q-1)$ 整除 $n$ ，那么对每个 $N$ ，只要它是 $n$ 的倍数，并且对每个质数 $p$ ，该和在上述三种情形中都模 $q$ 为零。因此最小的 $n$ 为 $\begin{aligned} n &= \operatorname{lcm}(43 \cdot 42,\ 47 \cdot 46) \\ &= 2 \cdot 3 \cdot 7 \cdot 23 \cdot 43 \cdot 47 \end{aligned}\text{。}$

质因数之和为 $2 + 3 + 7 + 23 + 43 + 47 = 125$ 。

Note $2021 = 43 \cdot 47.$ If $a = \prod p_i^{e_i},$ then $\sigma(a^n) = \prod \sigma(p_i^{e_i n}),$ so it suffices (and is necessary, taking $a$ prime) that $\sigma(p^N) \equiv 1,$ i.e. $p + p^2 + \cdots + p^N \equiv 0$ $\pmod{43 \cdot 47},$ for every prime $p$ and every multiple $N$ of $n.$

Fix $q \in \{43, 47\}.$ If $q$ divides $p$ the sum is $0.$ If $p \equiv 1 \pmod q$ the sum is $\equiv N,$ so choosing such a prime (Dirichlet) forces $q$ to divide $n.$ Otherwise the sum is $p \cdot \frac{p^N - 1}{p - 1}$ with $p - 1$ invertible, so we need $p^N \equiv 1 \pmod q;$ choosing $p$ to be a primitive root mod $q$ forces $q - 1$ to divide $n.$ Conversely, if $q(q-1)$ divides $n$ then for every multiple $N$ of $n$ and every prime $p,$ the sum vanishes mod $q$ in all three cases. Hence the least $n$ is $\begin{aligned} n &= \operatorname{lcm}(43 \cdot 42,\ 47 \cdot 46) \\ &= 2 \cdot 3 \cdot 7 \cdot 23 \cdot 43 \cdot 47. \end{aligned}$

The sum of the prime factors is $2 + 3 + 7 + 23 + 43 + 47 = 125.$

15.

设 $S$ 为所有正整数 $k$ 的集合，使得两条抛物线 $y = x^2 - k$ 和 $x = 2(y - 20)^2 - k$ 相交于四个不同的点，并且这四点位于一个半径至多为 $21$ 的圆上。求 $S$ 的最小元素与 $S$ 的最大元素之和。

Let $S$ be the set of positive integers $k$ such that the two parabolas $y = x^2 - k$ and $x = 2(y - 20)^2 - k$ intersect in four distinct points, and these four points lie on a circle with radius at most $21.$ Find the sum of the least element of $S$ and the greatest element of $S.$

答案

知识点：抛物线圆多项式极限情形界定

难度评级：3370

小提示：

任何经过全部四个交点的二次曲线都可由两个给定方程组合得到；选择权重使 $x^2$ 与 $y^2$ 的系数相等

Any conic through all four intersection points is a combination of the two given equations; choose the weights that make the $x^2$ and $y^2$ coefficients equal

大提示：

得到的圆的半径平方随 $k$ 线性增长，这给出 $k$ 的上界；对于较小的 $k$ ，检查关于 $x$ 的四次方程只有两个实根

The resulting circle’s squared radius grows linearly in $k,$ which caps $k$ above; for small $k,$ check that the quartic in $x$ has only two real roots

解答：

将方程 $x^2 - y - k = 0$ 加上 $\frac{1}{2}$ 倍的 $2(y - 20)^2 - x - k = 0$ ，得到一条经过所有交点、且 $x^2$ 与 $y^2$ 系数相等的二次曲线： $\begin{aligned} &x^2 + y^2 - \tfrac{1}{2}x - 41y \\ &\quad {}+ 400 - \tfrac{3k}{2} = 0 \end{aligned}\text{。}$ 这是圆心为 $\left(\frac{1}{4}, \frac{41}{2}\right)$ 的圆，其半径平方为 $\frac{1}{16} + \frac{1681}{4} - 400 + \frac{3k}{2}$ $= \frac{325}{16} + \frac{3k}{2}$ 。所以只要存在四个不同交点，它们就共圆；并且半径至多 $21$ 当且仅当 $\frac{325}{16} + \frac{3k}{2} \le 441$ ，也就是对整数而言 $k \le 280$ 。

将 $y = x^2 - k$ 代入第二条抛物线，得到四次方程 $f(x) = 2(x^2 - c)^2 - x - k = 0$ ，其中 $c = k + 20$ 。当 $1 \le k \le 4$ 时：若 $x \le -k$ ，则 $f(x) = 2(x^2 - c)^2$ $+ (-x - k) \gt 0$ ；若 $-k \lt x \le 0$ ，则 $x^2 \lt 16$ 且 $c \ge 21$ ，所以 $f(x) \gt 2 \cdot 25 - k \gt 0$ 。因此在 $x \le 0$ 时没有交点。又因为 $f'(x) = 8x^3 - 8cx - 1$ 恰有一个正根， $f$ 至多有两个正根；由 $f(0) \gt 0$ 、 $f(\sqrt{c}) \lt 0$ 可知恰有两个正根。所以 $k \le 4$ 不符合。

当 $k \ge 5$ 时，有 $k^2 \ge k + 20$ ，因此 $f\left(-\sqrt{c}\right) = \sqrt{c} - k \le 0$ 。在 $(-\infty, -\sqrt{c}]$ 上， $f'(x) = 8x(x^2-c)-1 \lt 0$ ，所以其中恰有一个根；该根在 $-\sqrt{c}$ 处（当 $k=5$ 时）。当 $k=5$ 时，端点处导数为负，故其右侧的 $f$ 立即变为负；当 $k \gt 5$ 时，端点处的函数值已经为负。由于 $f(0) = 2c^2-k \gt 0$ ，区间 $(-\sqrt{c},0)$ 中有第二个根。最后， $f\left(\sqrt{c}\right) = -\sqrt{c}-k \lt 0$ 且 $f(+\infty)=+\infty$ ，所以 $(0,\sqrt{c})$ 与 $(\sqrt{c},\infty)$ 中各有一个根。这四个根互不相同，而四次方程不可能还有其他根。

因此 $S = \{5, 6, \ldots, 280\}$ ，答案为 $5 + 280 = 285$ 。

Adding the equation $x^2 - y - k = 0$ to $\frac{1}{2}$ times $2(y - 20)^2 - x - k = 0$ gives a conic through all intersection points with equal $x^2$ and $y^2$ coefficients: $\begin{aligned} &x^2 + y^2 - \tfrac{1}{2}x - 41y \\ &\quad {}+ 400 - \tfrac{3k}{2} = 0, \end{aligned}$ a circle centered at $\left(\frac{1}{4}, \frac{41}{2}\right)$ with squared radius $\frac{1}{16} + \frac{1681}{4} - 400 + \frac{3k}{2}$ $= \frac{325}{16} + \frac{3k}{2}.$ So whenever four distinct intersection points exist, they are concyclic, and the radius is at most $21$ exactly when $\frac{325}{16} + \frac{3k}{2} \le 441,$ i.e. $k \le 280$ for integers.

Substituting $y = x^2 - k$ into the second parabola gives the quartic $f(x) = 2(x^2 - c)^2 - x - k = 0$ where $c = k + 20.$ For $1 \le k \le 4:$ if $x \le -k$ then $f(x) = 2(x^2 - c)^2$ $+ (-x - k) \gt 0,$ and if $-k \lt x \le 0$ then $x^2 \lt 16$ while $c \ge 21,$ so $f(x) \gt 2 \cdot 25 - k \gt 0;$ thus there are no intersections with $x \le 0,$ and since $f'(x) = 8x^3 - 8cx - 1$ has exactly one positive root, $f$ has at most (and, by $f(0) \gt 0,$ $f(\sqrt{c}) \lt 0,$ exactly) two positive roots. So $k \le 4$ fails.

For $k \ge 5,$ we have $k^2 \ge k + 20,$ so $f\left(-\sqrt{c}\right) = \sqrt{c} - k \le 0.$ On $(-\infty, -\sqrt{c}],$ we have $f'(x) = 8x(x^2-c)-1 \lt 0,$ so there is exactly one root there (at $-\sqrt{c}$ when $k=5$ ). If $k=5,$ the negative derivative at that endpoint makes $f$ negative immediately to its right; if $k \gt 5,$ it is already negative at the endpoint. Since $f(0) = 2c^2-k \gt 0,$ there is a second root in $(-\sqrt{c},0).$ Finally, $f\left(\sqrt{c}\right) = -\sqrt{c}-k \lt 0$ and $f(+\infty)=+\infty,$ so there is one root in each of $(0,\sqrt{c})$ and $(\sqrt{c},\infty).$ These four roots are distinct, and a quartic has no others.

Hence $S = \{5, 6, \ldots, 280\},$ and the answer is $5 + 280 = 285.$