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

1.

设 $S$ 为整数有序对 $(a, b)$ 的个数，其中 $1 \le a \le 100$ 、 $b \ge 0$ ，并且多项式 $x^2 + ax + b$ 可以分解为两个（不一定不同的）整系数一次因式的乘积。求 $S$ 除以 $1000$ 的余数。

Let $S$ be the number of ordered pairs of integers $(a, b),$ with $1 \le a \le 100$ and $b \ge 0,$ such that the polynomial $x^2 + ax + b$ can be factored into the product of two (not necessarily distinct) linear factors with integer coefficients. Find the remainder when $S$ is divided by $1000.$

答案

知识点：二次方程完全平方数奇偶性

难度评级：2260

小提示：

这个二次式能在整数中分解，当且仅当判别式 $a^2 - 4b$ 是完全平方数

The quadratic factors over the integers exactly when the discriminant $a^2 - 4b$ is a perfect square

大提示：

对每个 $a$ 有效的 $b$ 来自 $4b = a^2 - c^2$ ，其中 $0 \le c \le a$ 且 $c \equiv a \pmod 2$ ；数出这样的 $c$ 并对 $a$ 求和

For each $a,$ the valid $b$ come from $4b = a^2 - c^2$ with $0 \le c \le a$ and $c \equiv a \pmod 2;$ count those $c$ and sum over $a$

解答：

该多项式分解为整系数一次因式，恰好等价于它的根是整数，也就是判别式 $a^2 - 4b$ 等于某个整数 $c \ge 0$ 的平方 $c^2$ 。给定 $a$ 时，这样的 $b \ge 0$ 存在，当且仅当 $4b = a^2 - c^2 = (a-c)(a+c)$ ，其中 $c$ 满足 $0 \le c \le a$ 且 $c \equiv a \pmod 2$ ，不同的 $c$ 给出不同的 $b = \frac{a^2 - c^2}{4}$ 。

当 $a$ 为奇数时，有效的 $c$ 是 $1, 3, \ldots, a$ ，共有 $\frac{a+1}{2}$ 个；当 $a$ 为偶数时，有效值是 $0, 2, \ldots, a$ ，共有 $\frac{a}{2} + 1$ 个。

对 $a = 1, \ldots, 100$ 求和：奇数 $a$ 贡献 $1 + 2 + \cdots + 50 = 1275$ ，偶数 $a$ 贡献 $2 + 3 + \cdots + 51 = 1325$ 。因此 $S = 2600$ ，余数为 $600$ 。

The polynomial factors into integer linear factors exactly when its roots are integers, that is, when the discriminant $a^2 - 4b$ equals $c^2$ for some integer $c \ge 0.$ Given $a,$ such a $b \ge 0$ exists exactly when $4b = a^2 - c^2 = (a-c)(a+c)$ for some $c$ with $0 \le c \le a$ and $c \equiv a \pmod 2,$ and distinct such $c$ give distinct values $b = \frac{a^2 - c^2}{4}.$

For odd $a$ the valid $c$ are $1, 3, \ldots, a,$ which is $\frac{a+1}{2}$ choices; for even $a$ they are $0, 2, \ldots, a,$ which is $\frac{a}{2} + 1$ choices.

Summing over $a = 1, \ldots, 100:$ the odd $a$ contribute $1 + 2 + \cdots + 50 = 1275,$ and the even $a$ contribute $2 + 3 + \cdots + 51 = 1325.$ Thus $S = 2600,$ and the remainder is $600.$

2.

数 $n$ 在 $14$ 进制中可写为 $\underline{a}\,\underline{b}\,\underline{c}$ ，在 $15$ 进制中可写为 $\underline{a}\,\underline{c}\,\underline{b}$ ，在 $6$ 进制中可写为 $\underline{a}\,\underline{c}\,\underline{a}\,\underline{c}$ ，其中 $a \gt 0$ 。求 $n$ 的 $10$ 进制表示。

The number $n$ can be written in base $14$ as $\underline{a}\,\underline{b}\,\underline{c},$ can be written in base $15$ as $\underline{a}\,\underline{c}\,\underline{b},$ and can be written in base $6$ as $\underline{a}\,\underline{c}\,\underline{a}\,\underline{c},$ where $a \gt 0.$ Find the base- $10$ representation of $n.$

答案

知识点：进制位值丢番图方程

难度评级：2180

小提示：

三种表示给出 $196a + 14b + c = 225a + 15c + b$ $= 222a + 37c$ 。

The three representations give $196a + 14b + c = 225a + 15c + b$ $= 222a + 37c$

大提示：

比较后两个式子得到 $b = 22c - 3a$ ；代入第一个式子会迫使 $a = 4c$ ，其中 $a$ 与 $c$ 是 $6$ 进制数字

Comparing the last two gives $b = 22c - 3a;$ substituting into the first forces $a = 4c,$ where $a$ and $c$ are base- $6$ digits

解答：

写出各位值，得 $n = 196a + 14b + c$ $= 225a + 15c + b$ $= 222a + 37c$ ，其中 $a$ 与 $c$ 是 $6$ 进制数字，满足 $1 \le a \le 5$ 、 $0 \le c \le 5$ ，并且 $0 \le b \le 13$ 。

令后两个表达式相等，得 $b = 22c - 3a$ 。把它代入 $196a + 14b + c = 225a + 15c + b$ （即 $13b = 29a + 14c$ ），得到 $13(22c - 3a) = 29a + 14c$ ，所以 $272c = 68a$ ，即 $a = 4c$ 。数字范围迫使 $c = 1$ 、 $a = 4$ ，于是 $b = 22 - 12 = 10$ ，这是 $14$ 进制与 $15$ 进制中的有效数字。

因此 $n = 222 \cdot 4 + 37 \cdot 1 = 925$ 。确实 $925 = 196 \cdot 4 + 14 \cdot 10 + 1$ 与 $14$ 进制表示相符。答案为 $925$ 。

Writing out the place values, $n = 196a + 14b + c$ $= 225a + 15c + b$ $= 222a + 37c,$ where $a$ and $c$ are base- $6$ digits with $1 \le a \le 5$ and $0 \le c \le 5,$ and $0 \le b \le 13.$

Equating the last two expressions gives $b = 22c - 3a.$ Substituting into $196a + 14b + c = 225a + 15c + b$ (which says $13b = 29a + 14c$ ) yields $13(22c - 3a) = 29a + 14c,$ so $272c = 68a,$ that is $a = 4c.$ The digit bounds force $c = 1,$ $a = 4,$ and then $b = 22 - 12 = 10,$ which is a valid digit in bases $14$ and $15.$

Therefore $n = 222 \cdot 4 + 37 \cdot 1 = 925.$ Indeed $925 = 196 \cdot 4 + 14 \cdot 10 + 1,$ confirming the base- $14$ form. The answer is $925.$

3.

Kathy 有 $5$ 张红卡和 $5$ 张绿卡。她洗混这 $10$ 张卡，并随机按顺序排出其中 $5$ 张。当且仅当所有排出的红卡相邻且所有排出的绿卡相邻时，她会满意。例如，卡片顺序 RRGGG、GGGGR 或 RRRRR 会让 Kathy 满意，但 RRRGR 不会。Kathy 满意的概率为 $\frac{m}{n}$ ，其中 $m$ 与 $n$ 是互质正整数。求 $m + n$ 。

Kathy has $5$ red cards and $5$ green cards. She shuffles the $10$ cards and lays out $5$ of the cards in a row in a random order. She will be happy if and only if all the red cards laid out are adjacent and all the green cards laid out are adjacent. For example, card orders RRGGG, GGGGR, or RRRRR will make Kathy happy, but RRRGR will not. The probability that Kathy will be happy is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

答案

知识点：基本概率有限制的排列分类讨论

难度评级：2400

小提示：

只需要考虑颜色模式：Kathy 满意恰好意味着排出的红卡形成一个连续块，排出的绿卡也形成一个连续块

Only the color pattern matters: Kathy is happy exactly when the laid-out reds form one block and the laid-out greens form one block

大提示：

含 $r$ 张红卡的模式在全部 $10 \cdot 9 \cdot 8 \cdot 7 \cdot 6$ 个等可能有序排列中出现 $\frac{5!}{(5-r)!} \cdot \frac{5!}{r!}$ 次

A pattern with $r$ reds occurs in $\frac{5!}{(5-r)!} \cdot \frac{5!}{r!}$ of the $10 \cdot 9 \cdot 8 \cdot 7 \cdot 6$ equally likely ordered layouts

解答：

从 $10$ 张不同卡中排出 $5$ 张，共有 $10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 = 30240$ 个等可能的有序排列。Kathy 满意恰好意味着颜色模式由一个红色块和一个绿色块组成：模式包括 RRRRR、GGGGG，以及 $r = 1, 2, 3, 4$ 时的八种混合模式 $\text{R}^r\text{G}^{5-r}$ 和 $\text{G}^{5-r}\text{R}^r$ 。

一个使用 $r$ 个红色位置和 $5 - r$ 个绿色位置的模式，可以用 $\frac{5!}{(5-r)!} \cdot \frac{5!}{r!}$ 种方式填入具体卡片。对 $r = 5, 4, 3, 2, 1, 0$ ，这些数分别为 $120$ 、 $600$ 、 $1200$ 、 $1200$ 、 $600$ 、 $120$ 。满意的排列数为 $\begin{aligned} &120 + 120 \\ &{}+ 2\,(600 + 1200 + 1200 + 600) \\ &{}= 7440 \end{aligned}\text{。}$

概率为 $\frac{7440}{30240} = \frac{31}{126}$ ，所以 $m + n = 31 + 126 = 157$ 。

There are $10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 = 30240$ equally likely ordered layouts of $5$ of the $10$ distinct cards. Kathy is happy exactly when the color pattern consists of one block of reds and one block of greens: the patterns are RRRRR, GGGGG, and the eight mixed patterns $\text{R}^r\text{G}^{5-r}$ and $\text{G}^{5-r}\text{R}^r$ for $r = 1, 2, 3, 4.$

A pattern using $r$ red and $5 - r$ green positions can be filled in $\frac{5!}{(5-r)!} \cdot \frac{5!}{r!}$ ways (ordered choices of which red cards and which green cards appear). For $r = 5, 4, 3, 2, 1, 0$ these counts are $120,$ $600,$ $1200,$ $1200,$ $600,$ $120.$ The happy layouts number $\begin{aligned} &120 + 120 \\ &{}+ 2\,(600 + 1200 + 1200 + 600) \\ &{}= 7440. \end{aligned}$

The probability is $\frac{7440}{30240} = \frac{31}{126},$ so $m + n = 31 + 126 = 157.$

4.

在 $\triangle ABC$ 中， $AB = AC = 10$ ，且 $BC = 12$ 。点 $D$ 严格位于 $\overline{AB}$ 上 $A$ 与 $B$ 之间，点 $E$ 严格位于 $\overline{AC}$ 上 $A$ 与 $C$ 之间，并且 $AD = DE = EC$ 。则 $AD$ 可写成 $\frac{p}{q}$ 的形式，其中 $p$ 与 $q$ 是互质正整数。求 $p + q$ 。

In $\triangle ABC,$ $AB = AC = 10$ and $BC = 12.$ Point $D$ lies strictly between $A$ and $B$ on $\overline{AB}$ and point $E$ lies strictly between $A$ and $C$ on $\overline{AC}$ so that $AD = DE = EC.$ Then $AD$ can be expressed in the form $\frac{p}{q},$ where $p$ and $q$ are relatively prime positive integers. Find $p + q.$

答案

知识点：余弦定理等腰三角形

难度评级：2410

小提示：

设 $AD = x$ ，所以 $AE = 10 - x$ ；先从三角形 $ABC$ 计算 $\cos A$

Let $AD = x,$ so $AE = 10 - x;$ compute $\cos A$ from triangle $ABC$

大提示：

在三角形 $ADE$ 中使用余弦定理，得到 $x^2 = x^2 + (10-x)^2$ $- 2x(10-x)\cos A$ ；约去一个 $10 - x$ 因子

The law of cosines in triangle $ADE$ gives $x^2 = x^2 + (10-x)^2$ $- 2x(10-x)\cos A;$ cancel a factor of $10 - x$

解答：

在 $\triangle ABC$ 中由余弦定理， $\begin{aligned} \cos A &= \frac{10^2 + 10^2 - 12^2}{2 \cdot 10 \cdot 10} \\ &= \frac{56}{200} = \frac{7}{25} \end{aligned}\text{。}$

设 $x = AD = DE = EC$ ，则 $AE = 10 - x$ 。在 $\triangle ADE$ 中用余弦定理： $\begin{aligned} &x^2 = x^2 + (10 - x)^2 \\ &\quad {}- 2x(10 - x)\cdot\frac{7}{25} \end{aligned}\text{，}$ 所以 $(10 - x)^2 = \frac{14}{25}\,x(10 - x)$ 。因为 $x \lt 10$ 可除以 $10 - x$ ，得 $10 - x = \frac{14x}{25}$ ，于是 $250 = 39x$ ， $x = \frac{250}{39}$ 。

由于 $\gcd(250, 39) = 1$ ，答案是 $250 + 39 = 289$ 。

By the law of cosines in $\triangle ABC,$ $\begin{aligned} \cos A &= \frac{10^2 + 10^2 - 12^2}{2 \cdot 10 \cdot 10} \\ &= \frac{56}{200} = \frac{7}{25}. \end{aligned}$

Let $x = AD = DE = EC,$ so $AE = 10 - x.$ The law of cosines in $\triangle ADE$ gives $\begin{aligned} &x^2 = x^2 + (10 - x)^2 \\ &\quad {}- 2x(10 - x)\cdot\frac{7}{25}, \end{aligned}$ so $(10 - x)^2 = \frac{14}{25}\,x(10 - x).$ Since $x \lt 10,$ we may divide by $10 - x$ to get $10 - x = \frac{14x}{25},$ hence $250 = 39x$ and $x = \frac{250}{39}.$

As $\gcd(250, 39) = 1,$ the answer is $250 + 39 = 289.$

5.

对每个满足 $\begin{aligned} &\log_2(2x + y) \\ &= \log_4(x^2 + xy + 7y^2) \end{aligned}$ 的实数有序对 $(x, y)$ ，都存在一个实数 $K$ ，使得 $\begin{aligned} &\log_3(3x + y) \\ &= \log_9(3x^2 + 4xy + Ky^2) \end{aligned}\text{。}$ 求所有可能的 $K$ 的乘积。

For each ordered pair of real numbers $(x, y)$ satisfying $\begin{aligned} &\log_2(2x + y) \\ &= \log_4(x^2 + xy + 7y^2), \end{aligned}$ there is a real number $K$ such that $\begin{aligned} &\log_3(3x + y) \\ &= \log_9(3x^2 + 4xy + Ky^2). \end{aligned}$ Find the product of all possible values of $K.$

答案

知识点：对数因式分解分类讨论

难度评级：2510

小提示：

因为 $\log_4 u = \log_2 \sqrt{u}$ ，第一个方程说明 $(2x + y)^2 = x^2 + xy + 7y^2$

Since $\log_4 u = \log_2 \sqrt{u},$ the first equation says $(2x + y)^2 = x^2 + xy + 7y^2$

大提示：

该条件可分解为 $(x - y)(x + 2y) = 0$ ；把每种情况代入第二个方程的平方形式以求 $K$

That condition factors as $(x - y)(x + 2y) = 0;$ substitute each case into the squared form of the second equation to find $K$

解答：

因为 $\log_4 u = \log_2 \sqrt{u}$ ，第一个方程等价于 $(2x + y)^2 = x^2 + xy + 7y^2$ ，并且 $2x + y \gt 0$ 。展开得 $3x^2 + 3xy - 6y^2 = 0$ ，分解为 $3(x - y)(x + 2y) = 0$ 。所以 $x = y$ 或 $x = -2y$ ，且 $(x, y) \ne (0, 0)$ 。

同理，第二个方程说明 $(3x + y)^2 = 3x^2 + 4xy + Ky^2$ ，也就是 $6x^2 + 2xy + y^2 = Ky^2$ 。若 $x = y$ （取 $x \gt 0$ 使两个对数都有定义），则 $K = 6 + 2 + 1 = 9$ 。若 $x = -2y$ （取 $y \lt 0$ ，使 $2x + y = -3y \gt 0$ 且 $3x + y = -5y \gt 0$ ），则 $24y^2 - 4y^2 + y^2 = Ky^2$ ，所以 $K = 21$ 。

两种情况都可以发生，所以所有可能值的乘积为 $9 \cdot 21 = 189$ 。

Because $\log_4 u = \log_2 \sqrt{u},$ the first equation is equivalent to $(2x + y)^2 = x^2 + xy + 7y^2$ together with $2x + y \gt 0.$ Expanding gives $3x^2 + 3xy - 6y^2 = 0,$ which factors as $3(x - y)(x + 2y) = 0.$ So $x = y$ or $x = -2y,$ with $(x, y) \ne (0, 0).$

Similarly the second equation says $(3x + y)^2 = 3x^2 + 4xy + Ky^2,$ that is $6x^2 + 2xy + y^2 = Ky^2.$ If $x = y$ (taking $x \gt 0$ so both logarithms are defined), then $K = 6 + 2 + 1 = 9.$ If $x = -2y$ (taking $y \lt 0,$ so $2x + y = -3y \gt 0$ and $3x + y = -5y \gt 0$ ), then $24y^2 - 4y^2 + y^2 = Ky^2,$ so $K = 21.$

Both cases occur, so the product of all possible values is $9 \cdot 21 = 189.$

6.

设 $N$ 为满足 $|z| = 1$ 且 $z^{6!} - z^{5!}$ 为实数的复数 $z$ 的个数。求 $N$ 除以 $1000$ 的余数。

Let $N$ be the number of complex numbers $z$ with the properties that $|z| = 1$ and $z^{6!} - z^{5!}$ is a real number. Find the remainder when $N$ is divided by $1000.$

答案

知识点：复数三角学分类讨论

难度评级：2720

小提示：

写成 $z = e^{i\theta}$ ；差为实数恰好等价于 $\sin 720\theta = \sin 120\theta$

Write $z = e^{i\theta};$ the difference is real exactly when $\sin 720\theta = \sin 120\theta$

大提示：

正弦相等意味着两角模 $2\pi$ 同余或互补；分别数出 $\theta \in [0, 2\pi)$ 的两类解，并检查两类不重合

Equal sines mean the angles are equal or supplementary modulo $2\pi;$ count $\theta \in [0, 2\pi)$ of each type and check the two families do not overlap

解答：

令 $z = e^{i\theta}$ ，其中 $\theta \in [0, 2\pi)$ 。那么 $z^{720} - z^{120}$ 为实数，当且仅当 $\sin 720\theta = \sin 120\theta$ ，这发生在两角模 $2\pi$ 同余或互补时：要么 $720\theta = 120\theta + 2\pi k$ ，得到 $\theta = \frac{\pi k}{300}$ ，要么 $720\theta = \pi - 120\theta + 2\pi k$ ，得到 $\theta = \frac{(2k+1)\pi}{840}$ 。

第一族在 $[0, 2\pi)$ 中有 $600$ 个值，第二族有 $840$ 个。它们不可能重合：若 $\frac{\pi k}{300} = \frac{(2j+1)\pi}{840}$ ，则 $14k = 5(2j + 1)$ ，等式左右一边为偶数、一边为奇数。

因此 $N = 600 + 840 = 1440$ ，余数为 $440$ 。

Write $z = e^{i\theta}$ with $\theta \in [0, 2\pi).$ Then $z^{720} - z^{120}$ is real exactly when $\sin 720\theta = \sin 120\theta,$ which happens when the angles are equal or supplementary modulo $2\pi:$ either $720\theta = 120\theta + 2\pi k,$ giving $\theta = \frac{\pi k}{300},$ or $720\theta = \pi - 120\theta + 2\pi k,$ giving $\theta = \frac{(2k+1)\pi}{840}.$

The first family has $600$ values in $[0, 2\pi)$ and the second has $840.$ They cannot coincide: $\frac{\pi k}{300} = \frac{(2j+1)\pi}{840}$ would give $14k = 5(2j + 1),$ equating an even number with an odd one.

Hence $N = 600 + 840 = 1440,$ and the remainder is $440.$

7.

一个直六棱柱的高为 $2$ 。底面是边长为 $1$ 的正六边形。任取 $12$ 个顶点中的 $3$ 个确定一个三角形。求这些三角形中等腰三角形（包括等边三角形）的个数。

A right hexagonal prism has height $2.$ The bases are regular hexagons with side length $1.$ Any $3$ of the $12$ vertices determine a triangle. Find the number of these triangles that are isosceles (including equilateral triangles).

答案

知识点：图形中的形状计数立体几何分类讨论

难度评级：2840

小提示：

先分别计算所有顶点都在同一个六边形上的三角形；每个六边形单独贡献 $8$ 个等腰三角形

Count triangles with all vertices on one hexagon separately from those using both; each hexagon alone contributes $8$ isosceles triangles

大提示：

若两个顶点在一个底面上，则另一底面上的顶点必须位于这一对点的垂直平分线上，或者某条侧向边 $\sqrt{d^2 + 4}$ 必须等于底面弦长 $2$

For two vertices on one base, the apex on the other base must lie above the perpendicular bisector of the pair, or a lateral side $\sqrt{d^2 + 4}$ must equal the base chord $2$

解答：

单位正六边形的弦长可能为 $1$ 、 $\sqrt{3}$ 、 $2$ 。一个六边形中 $\binom{6}{3} = 20$ 个三角形里， $6$ 个的边长为 $1, 1, \sqrt{3}$ ， $2$ 个是边长为 $\sqrt{3}$ 的等边三角形，其余 $12$ 个的边长为 $1, \sqrt{3}, 2$ ，是不等边三角形。所以每个底面贡献 $8$ 个等腰三角形，两个底面共 $16$ 个。

否则，两个顶点在一个底面上（有 $2$ 种底面选择），一个顶点在另一个底面上。上底面某顶点到下底面某顶点的距离为 $\sqrt{d^2 + 4} \ge 2$ ，其中 $d$ 是水平距离。若下底面这一对相邻（弦长 $1$ ）：正六边形边的垂直平分线不经过顶点，且没有侧向边能等于 $1$ ，所以没有等腰三角形。若这一对中间隔一个顶点（弦长 $\sqrt{3}$ 有 $6$ 对）：上底面位于中间顶点正上方和对顶点正上方的两个顶点到这对点等距，得到 $6 \cdot 2 = 12$ 个。若这一对是对径点（弦长 $2$ 有 $3$ 对）：没有顶点在垂直平分线上，但任一端点正上方的顶点给出侧向边 $\sqrt{0 + 4} = 2$ ，等于该弦长，得到 $3 \cdot 2 = 6$ 个。

总数为 $16 + 2\,(12 + 6) = 52$ 。

The chords of a unit regular hexagon have lengths $1,$ $\sqrt{3},$ and $2.$ Among the $\binom{6}{3} = 20$ triangles in one hexagon, $6$ have sides $1, 1, \sqrt{3}$ and $2$ are equilateral with side $\sqrt{3};$ the other $12,$ with sides $1, \sqrt{3}, 2,$ are scalene. So each base contributes $8$ isosceles triangles, for $16$ in all.

Otherwise two vertices lie on one base ( $2$ choices of that base) and one on the other. A vertex of the top base at horizontal distance $d$ from a bottom vertex is at distance $\sqrt{d^2 + 4} \ge 2$ from it. If the bottom pair is adjacent (chord $1$ ): the perpendicular bisector of a hexagon edge passes through no vertices, and no slant side can equal $1,$ so there are no isosceles triangles. If the pair has one vertex between them (chord $\sqrt{3},$ $6$ pairs): the top vertices above that middle vertex and above the opposite vertex are equidistant from the pair, giving $6 \cdot 2 = 12.$ If the pair is diametrically opposite (chord $2,$ $3$ pairs): no vertex lies above the perpendicular bisector, but the top vertex directly above either endpoint gives a slant side $\sqrt{0 + 4} = 2$ equal to the chord, giving $3 \cdot 2 = 6.$

The total is $16 + 2\,(12 + 6) = 52.$

8.

设 $ABCDEF$ 为等角六边形，且 $AB = 6$ 、 $BC = 8$ 、 $CD = 10$ 、 $DE = 12$ 。记能放入该六边形内的最大圆的直径为 $d$ 。求 $d^2$ 。

Let $ABCDEF$ be an equiangular hexagon such that $AB = 6,$ $BC = 8,$ $CD = 10,$ and $DE = 12.$ Denote by $d$ the diameter of the largest circle that fits inside the hexagon. Find $d^2.$

答案

知识点：等角多边形平行线最优化

难度评级：2920

小提示：

在等角六边形中， $AB + BC = DE + EF$ ，且 $FA + AB = CD + DE$ ；先求 $EF$ 和 $FA$

In an equiangular hexagon $AB + BC = DE + EF$ and $FA + AB = CD + DE;$ find $EF$ and $FA$

大提示：

对边平行，它们的距离为连接这两边的两条边长之和乘以 $\frac{\sqrt{3}}{2}$ ；三个条带中最窄的限制了圆

Opposite sides are parallel, at distance $\frac{\sqrt{3}}{2}$ times the sum of the two sides connecting them; the narrowest of the three strips limits the circle

解答：

所有内角都是 $120^\circ$ ，所以对边平行。在两条对边外接等边三角形可形成平行四边形，从而有 $AB + BC = DE + EF$ 以及 $FA + AB = CD + DE$ 。因此 $EF = 2$ ， $FA = 16$ 。

沿连接两条对边的两条边从一边走到对边，可知一对对边之间的距离为这两条连接边长度之和的 $\frac{\sqrt{3}}{2}$ 倍： $AB$ 与 $DE$ 之间的条带宽度为 $\frac{\sqrt{3}}{2}(BC + CD) = 9\sqrt{3}$ ； $BC$ 与 $EF$ 之间为 $\frac{\sqrt{3}}{2}(CD + DE) = 11\sqrt{3}$ ； $CD$ 与 $FA$ 之间为 $\frac{\sqrt{3}}{2}(DE + EF) = 7\sqrt{3}$ 。六边形内任意圆都必须位于最窄条带内，所以 $d \le 7\sqrt{3}$ 。

一个直径为 $7\sqrt{3}$ 、与直线 $CD$ 和 $FA$ 相切的圆，可以调整圆心使它也恰好与 $DE$ 接触，并且到直线 $EF$ 、 $BC$ 、 $AB$ 的距离分别为 $6\sqrt{3}$ 、 $5\sqrt{3}$ 和 $\frac{11\sqrt{3}}{2}$ ，都大于半径 $\frac{7\sqrt{3}}{2}$ ，所以它确实能放入六边形。故 $d = 7\sqrt{3}$ ， $d^2 = 147$ 。

All interior angles are $120^\circ,$ so opposite sides are parallel. Attaching equilateral triangles to two opposite sides produces a parallelogram, which forces $AB + BC = DE + EF$ and $FA + AB = CD + DE.$ Hence $EF = 2$ and $FA = 16.$

Walking from one side to the opposite side along the two connecting sides shows that the distance between a pair of opposite sides is $\frac{\sqrt{3}}{2}$ times the sum of those two connecting sides: the strips have widths $\frac{\sqrt{3}}{2}(BC + CD) = 9\sqrt{3}$ between $AB$ and $DE,$ $\frac{\sqrt{3}}{2}(CD + DE) = 11\sqrt{3}$ between $BC$ and $EF,$ and $\frac{\sqrt{3}}{2}(DE + EF) = 7\sqrt{3}$ between $CD$ and $FA.$ Any circle inside the hexagon fits in the narrowest strip, so $d \le 7\sqrt{3}.$

A circle of diameter $7\sqrt{3}$ tangent to lines $CD$ and $FA$ can be centered so that it also touches $DE$ exactly and has distances $6\sqrt{3},$ $5\sqrt{3},$ and $\frac{11\sqrt{3}}{2}$ from lines $EF,$ $BC,$ and $AB,$ all more than its radius $\frac{7\sqrt{3}}{2},$ so it fits inside the hexagon. Therefore $d = 7\sqrt{3}$ and $d^2 = 147.$

9.

求集合 $\{1, 2, 3, 4, \ldots, 20\}$ 中满足以下性质的四元素子集个数：子集中有两个不同元素的和为 $16$ ，并且有两个不同元素的和为 $24$ 。例如， $\{3, 5, 13, 19\}$ 和 $\{6, 10, 20, 18\}$ 是两个这样的子集。

Find the number of four-element subsets of $\{1, 2, 3, 4, \ldots, 20\}$ with the property that two distinct elements of the subset have a sum of $16,$ and two distinct elements of the subset have a sum of $24.$ For example, $\{3, 5, 13, 19\}$ and $\{6, 10, 20, 18\}$ are two such subsets.

答案

知识点：子集数对计数分类讨论

难度评级：2990

小提示：

和为 $16$ 的数对有 $7$ 个，和为 $24$ 的数对有 $8$ 个；按这两对是否能不相交来分类

There are $7$ pairs summing to $16$ and $8$ pairs summing to $24;$ split by whether the two pairs can be chosen disjoint

大提示：

若两对必须重叠，则某个元素 $a$ 使 $16 - a$ 与 $24 - a$ 都在子集中，再加一个自由的第四元素；减去有两个这种中心的子集

If the pairs must overlap, some element $a$ has both $16 - a$ and $24 - a$ in the subset plus a free fourth element; subtract the subsets that have two such centers

解答：

两个不同元素和为 $16$ 的数对为 $\{1,15\}, \{2,14\}, \ldots, \{7,9\}$ （七对），和为 $24$ 的数对为 $\{4,20\}, \{5,19\}, \ldots, \{11,13\}$ （八对）。先数同时含有一个 $16$ -数对和一个不相交的 $24$ -数对的子集。在 $7 \cdot 8 = 56$ 种配对组合中，共用某个元素 $x$ 的组合要求 $16 - x$ 、 $x$ 、 $24 - x$ 都有效；这发生在 $x \in \{4, \ldots, 15\}$ 中除 $8$ 和 $12$ 以外的 $10$ 个值上。没有四元素集合会来自两个不同的不相交组合（第二种分解会迫使一个 $16$ -数对与一个 $24$ -数对重合），所以此类给出 $56 - 10 = 46$ 个子集。

在其余子集中，每个 $16$ -数对都与每个 $24$ -数对相交，因此某个中心 $a$ 使 $b = 16 - a$ 与 $c = 24 - a$ 都在子集中。可能的中心有 $10$ 个（ $a \in \{4, \ldots, 15\}$ ，且 $a \ne 8, 12$ ），第四个元素可为其余 $17$ 个数中的任意一个，得到 $170$ 个中心-子集计数。恰有 $6$ 个子集有两个中心并被数了两次： $\{1,7,9,15\}$ 、 $\{2,6,10,14\}$ 、 $\{3,5,11,13\}$ 、 $\{5,11,13,19\}$ 、 $\{6,10,14,18\}$ 、 $\{7,9,15,17\}$ 。此类给出 $170 - 6 = 164$ 个子集，且其中没有包含不相交数对的子集。

总数为 $46 + 164 = 210$ 。

The pairs of distinct elements summing to $16$ are $\{1,15\}, \{2,14\}, \ldots, \{7,9\}$ (seven pairs), and those summing to $24$ are $\{4,20\}, \{5,19\}, \ldots, \{11,13\}$ (eight pairs). First count subsets containing a $16$ -pair and a $24$ -pair that are disjoint. Of the $7 \cdot 8 = 56$ combinations, the ones sharing an element $x$ require $16 - x,$ $x,$ and $24 - x$ all to be valid, which happens for the $10$ values $x \in \{4, \ldots, 15\}$ other than $8$ and $12.$ No four-element set arises from two different disjoint combinations (a second decomposition would force a $16$ -pair to coincide with a $24$ -pair), so this case gives $56 - 10 = 46$ subsets.

In the remaining subsets every $16$ -pair meets every $24$ -pair, so some center $a$ has both $b = 16 - a$ and $c = 24 - a$ in the subset. There are $10$ possible centers ( $a \in \{4, \ldots, 15\}$ with $a \ne 8, 12$ ), and the fourth element can be any of the $17$ remaining numbers, giving $170$ center–subset counts. Exactly $6$ subsets admit two centers and are counted twice: $\{1,7,9,15\},$ $\{2,6,10,14\},$ $\{3,5,11,13\},$ $\{5,11,13,19\},$ $\{6,10,14,18\},$ and $\{7,9,15,17\}.$ This case gives $170 - 6 = 164$ subsets, none of which contain disjoint pairs.

The total is $46 + 164 = 210.$

10.

下图所示的轮子由两个圆和五根辐条组成，每个辐条与圆的交点都有标签。一只虫子从点 $A$ 出发沿轮子行走。在过程的每一步中，虫子从一个有标签的点走到相邻的有标签点。沿内圆时，虫子只能逆时针行走；沿外圆时，虫子只能顺时针行走。例如，虫子可以沿路径 $AJABCHCHIJA$ 行走，这条路径有 $10$ 步。令 $n$ 为经过 $15$ 步、起点和终点均为 $A$ 的路径数。求 $n$ 除以 $1000$ 的余数。

The wheel shown below consists of two circles and five spokes, with a label at each point where a spoke meets a circle. A bug walks along the wheel, starting at point $A.$ At every step of the process, the bug walks from one labeled point to an adjacent labeled point. Along the inner circle the bug only walks in a counterclockwise direction, and along the outer circle the bug only walks in a clockwise direction. For example, the bug could travel along the path $AJABCHCHIJA,$ which has $10$ steps. Let $n$ be the number of paths with $15$ steps that begin and end at point $A.$ Find the remainder when $n$ is divided by $1000.$

答案

知识点：双射组合不变量

难度评级：3060

小提示：

每个点都恰有两种移动；若一步是逆时针或向内，称为 $X$ ，若是顺时针或向外，称为 $Y$ ，于是路径对应由字符 $XY$ 构成的字符串

Every point offers exactly two moves; call a move $X$ if it goes counterclockwise or inward and $Y$ if clockwise or outward, so paths correspond to $XY$ -strings

大提示：

虫子回到 $A$ 恰好当最后一步是 $X$ ，并且 $X$ 的个数比 $Y$ 的个数多 $5$ 的倍数

The bug is back at $A$ exactly when the last move is an $X$ and the number of $X$ s exceeds the number of $Y$ s by a multiple of $5$

解答：

从任一内圆点出发，虫子恰有两种移动：沿内圆逆时针，或沿辐条向外；从任一外圆点出发，也恰有两种移动：沿外圆顺时针，或沿辐条向内。若一步是逆时针或向内，称为 $X$ ；若是顺时针或向外，称为 $Y$ 。于是 $\{X, Y\}^{15}$ 中的每个字符串都唯一描述一条从 $A$ 出发的 $15$ 步路径。

一步到达内圆恰好当这一步是 $X$ ，所以路径终点在内圆上恰好当最后一步是 $X$ ；此时向内和向外的步数相等。以五分之一圈为单位测量角位置（逆时针为 $+1$ ，顺时针为 $-1$ ，辐条移动为 $0$ ），路径回到 $A$ 恰好当它终止在内圆且净转动是 $5$ 的倍数，也就是最后一步为 $X$ ，且 $\#X - \#Y \equiv 0 \pmod 5$ 。共有 $15$ 步时，这意味着 $X$ 的个数为 $5$ 、 $10$ ，或 $15$ 。

固定最后一步为 $X$ ，前 $14$ 步分别含 $4$ 、 $9$ ，或 $14$ 个 $X$ ，所以 $\begin{aligned} n &= \binom{14}{4} + \binom{14}{9} + \binom{14}{14} \\ &= 1001 + 2002 + 1 = 3004 \end{aligned}\text{，}$ 余数为 $4$ 。

From any inner point the bug has exactly two moves, counterclockwise along the inner circle or outward along a spoke; from any outer point it has exactly two, clockwise along the outer circle or inward along a spoke. Call a move $X$ if it is counterclockwise or inward and $Y$ if it is clockwise or outward. Then every string in $\{X, Y\}^{15}$ describes exactly one $15$ -step path from $A.$

A step arrives on the inner circle exactly when it is an $X,$ so the path ends on the inner circle exactly when its last move is an $X;$ in that case the numbers of inward and outward moves are equal. Measuring angular position in fifths of a turn (counterclockwise $+1,$ clockwise $-1,$ spokes $0$ ), the path returns to $A$ exactly when it ends on the inner circle and the net rotation is a multiple of $5,$ that is, when the last move is $X$ and $\#X - \#Y \equiv 0 \pmod 5.$ With $15$ moves this means the number of $X$ s is $5,$ $10,$ or $15.$

Fixing the last move as $X,$ the first $14$ moves contain $4,$ $9,$ or $14$ $X$ s, so $\begin{aligned} n &= \binom{14}{4} + \binom{14}{9} + \binom{14}{14} \\ &= 1001 + 2002 + 1 = 3004, \end{aligned}$ and the remainder is $4.$

11.

求最小正整数 $n$ ，使得 $3^n$ 写成 $143$ 进制时，其最右边两位 $143$ 进制数字为 $01$ 。

Find the least positive integer $n$ such that when $3^n$ is written in base $143,$ its two right-most digits in base $143$ are $01.$

答案

知识点：乘法阶模运算二项式定理最小公倍数

难度评级：2990

小提示：

条件等价于 $3^n \equiv 1 \pmod{143^2}$ ；分别模 $11^2$ 与 $13^2$ 处理，并注意 $3^5 = 243 = 2 \cdot 11^2 + 1$

The condition says $3^n \equiv 1 \pmod{143^2};$ work modulo $11^2$ and $13^2$ separately, noting $3^5 = 243 = 2 \cdot 11^2 + 1$

大提示：

由于 $3^3 = 1 + 2 \cdot 13$ ，二项式定理给出 $3^{3k} \equiv 1 + 26k \pmod{13^2}$ ；确定何时它为 $1$ ，再取最小公倍数

Since $3^3 = 1 + 2 \cdot 13,$ the binomial theorem gives $3^{3k} \equiv 1 + 26k \pmod{13^2};$ determine when this is $1,$ then take an lcm

解答：

最后两个 $143$ 进制数字为 $01$ ，恰好等价于 $3^n \equiv 1 \pmod{143^2}$ 。由于 $143^2 = 11^2 \cdot 13^2$ ，这又等价于 $3^n \equiv 1$ 在模 $11^2$ 与模 $13^2$ 下同时成立。

模 $121$ ： $3^5 = 243 = 2 \cdot 121 + 1 \equiv 1$ ，且由于 $5$ 是质数、 $3 \not\equiv 1$ ， $3$ 的阶恰为 $5$ 。模 $169$ ： $3$ 模 $13$ 的阶为 $3$ ，所以模 $169$ 的阶是 $3$ 的倍数。写 $3^3 = 27 = 1 + 26$ ，并注意 $26^2 = 4 \cdot 169 \equiv 0 \pmod{169}$ ，二项式定理给出 $3^{3k} = (1 + 26)^k$ $\equiv 1 + 26k \pmod{169}$ ，它等于 $1$ 当且仅当 $k$ 是 $13$ 的倍数。所以 $3$ 模 $169$ 的阶为 $39$ 。

因此 $n$ 必须是 $5$ 与 $39$ 的公倍数，最小为 $\operatorname{lcm}(5, 39) = 195$ 。

The last two base- $143$ digits are $01$ exactly when $3^n \equiv 1 \pmod{143^2},$ and since $143^2 = 11^2 \cdot 13^2,$ this holds exactly when $3^n \equiv 1$ modulo both $11^2$ and $13^2.$

Modulo $121:$ $3^5 = 243 = 2 \cdot 121 + 1 \equiv 1,$ and since $5$ is prime and $3 \not\equiv 1,$ the order of $3$ is exactly $5.$ Modulo $169:$ the order of $3$ modulo $13$ is $3,$ so the order modulo $169$ is a multiple of $3.$ Writing $3^3 = 27 = 1 + 26$ and noting $26^2 = 4 \cdot 169 \equiv 0 \pmod{169},$ the binomial theorem gives $3^{3k} = (1 + 26)^k$ $\equiv 1 + 26k \pmod{169},$ which is $1$ exactly when $k$ is a multiple of $13.$ So the order of $3$ modulo $169$ is $39.$

Therefore $n$ must be a common multiple of $5$ and $39,$ and the least is $\operatorname{lcm}(5, 39) = 195.$

12.

对集合 $U = \{1, 2, 3, \ldots, 18\}$ 的每个子集 $T$ ，令 $s(T)$ 为 $T$ 中元素之和，并规定 $s(\emptyset)$ 为 $0$ 。若从 $U$ 的所有子集中随机选取 $T$ ，则 $s(T)$ 能被 $3$ 整除的概率为 $\frac{m}{n}$ ，其中 $m$ 与 $n$ 是互质正整数。求 $m$ 。

For each subset $T$ of $U = \{1, 2, 3, \ldots, 18\},$ let $s(T)$ be the sum of the elements of $T,$ with $s(\emptyset)$ defined to be $0.$ If $T$ is chosen at random among all subsets of $U,$ the probability that $s(T)$ is divisible by $3$ is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m.$

答案

知识点：子集模运算组合范德蒙德卷积

难度评级：3060

小提示：

模 $3$ 的每个余数类在 $U$ 中都恰有六个元素，并且只有所选的 $\equiv 1$ 和 $\equiv 2$ 的元素个数重要

Each residue class modulo $3$ contains exactly six elements of $U,$ and only the numbers of chosen elements $\equiv 1$ and $\equiv 2$ matter

大提示：

若选了 $a$ 个 $\equiv 1$ 的元素与 $b$ 个 $\equiv 2$ 的元素，需要 $a \equiv b \pmod 3$ ；用范德蒙德恒等式计算 $\sum \binom{6}{a}\binom{6}{b}$

With $a$ chosen elements $\equiv 1$ and $b$ elements $\equiv 2,$ you need $a \equiv b \pmod 3;$ evaluate $\sum \binom{6}{a}\binom{6}{b}$ using Vandermonde’s identity

解答：

集合 $U$ 在模 $3$ 的每个余数类中各有六个元素。若 $T$ 包含 $a$ 个 $\equiv 1$ 的元素和 $b$ 个 $\equiv 2 \pmod 3$ 的元素，则 $s(T) \equiv a + 2b \equiv a - b \pmod 3$ ，所以 $s(T)$ 能被 $3$ 整除当且仅当 $a \equiv b \pmod 3$ ；六个 $3$ 的倍数可自由选择，对有利数与总数都贡献因子 $2^6$ 。

由范德蒙德恒等式，选择这些 $a$ 与 $b$ 时，满足 $a - b = 0$ 的选法数为 $\sum_a \binom{6}{a}^2 = \binom{12}{6} = 924$ ；满足 $a - b = \pm 3$ 的选法数为 $2\sum_a \binom{6}{a}\binom{6}{a - 3} = 2\binom{12}{9} = 440$ ；满足 $a - b = \pm 6$ 的选法数为 $2$ 。有利选法为 $924 + 440 + 2 = 1366$ ，总数为 $2^{12}$ 。

概率为 $\frac{1366}{4096} = \frac{683}{2048}$ ，由于 $683$ 是奇数，已经最简。因此 $m = 683$ 。

The set $U$ contains six elements in each residue class modulo $3.$ If $T$ contains $a$ elements $\equiv 1$ and $b$ elements $\equiv 2 \pmod 3,$ then $s(T) \equiv a + 2b \equiv a - b \pmod 3,$ so $s(T)$ is divisible by $3$ exactly when $a \equiv b \pmod 3;$ the six multiples of $3$ may be included freely, contributing a factor $2^6$ to both the favorable and total counts.

By Vandermonde’s identity, the number of ways to choose the $a$ s and $b$ s with $a - b = 0$ is $\sum_a \binom{6}{a}^2 = \binom{12}{6} = 924;$ with $a - b = \pm 3$ it is $2\sum_a \binom{6}{a}\binom{6}{a - 3} = 2\binom{12}{9} = 440;$ and with $a - b = \pm 6$ it is $2.$ The favorable choices number $924 + 440 + 2 = 1366$ out of $2^{12}.$

The probability is $\frac{1366}{4096} = \frac{683}{2048},$ which is in lowest terms since $683$ is odd. Thus $m = 683.$

13.

设 $\triangle ABC$ 的边长为 $AB = 30$ 、 $BC = 32$ 、 $AC = 34$ 。点 $X$ 位于 $\overline{BC}$ 的内部，点 $I_1$ 和 $I_2$ 分别为 $\triangle ABX$ 与 $\triangle ACX$ 的内心。当 $X$ 沿 $\overline{BC}$ 变化时，求 $\triangle AI_1I_2$ 的最小可能面积。

Let $\triangle ABC$ have side lengths $AB = 30,$ $BC = 32,$ and $AC = 34.$ Point $X$ lies in the interior of $\overline{BC},$ and points $I_1$ and $I_2$ are the incenters of $\triangle ABX$ and $\triangle ACX,$ respectively. Find the minimum possible area of $\triangle AI_1I_2$ as $X$ varies along $\overline{BC}.$

答案

知识点：内切圆、内心与内切圆半径正弦定理三角恒等式最优化

难度评级：3270

小提示：

对每个 $X$ 的位置，都有 $\angle I_1AI_2 = \frac{A}{2}$ ，所以只需最小化 $AI_1 \cdot AI_2$

$\angle I_1AI_2 = \frac{A}{2}$ for every position of $X,$ so it suffices to minimize $AI_1 \cdot AI_2$

大提示：

利用 $\angle AI_1B = 90^\circ + \frac{1}{2}\angle AXB$ 和正弦定理，面积与 $\frac{1}{\sin \angle AXB}$ 成正比；当 $\angle AXB = 90^\circ$ 时最小

Using $\angle AI_1B = 90^\circ + \frac{1}{2}\angle AXB$ and the law of sines, the area is proportional to $\frac{1}{\sin \angle AXB},$ minimized when $\angle AXB = 90^\circ$

解答：

由于 $AI_1$ 与 $AI_2$ 分别平分角 $BAX$ 与 $XAC$ ， $\angle I_1AI_2 = \frac{1}{2}\angle BAX$ $+ \frac{1}{2}\angle XAC = \frac{A}{2}$ 为常数。设 $\alpha = \angle AXB$ 。内心角公式给出 $\angle AI_1B = 90^\circ + \frac{\alpha}{2}$ ，所以在 $\triangle ABI_1$ 中由正弦定理得 $AI_1 = \frac{AB \sin\frac{B}{2}}{\cos\frac{\alpha}{2}}$ 。同理，由于 $\angle AXC = 180^\circ - \alpha$ ，有 $AI_2 = \frac{AC \sin\frac{C}{2}}{\sin\frac{\alpha}{2}}$ 。

因此 $\begin{aligned} &[\triangle AI_1I_2] = \frac{1}{2}\,AI_1 \cdot AI_2 \sin\frac{A}{2} \\ &= \frac{AB \cdot AC \sin\frac{A}{2}\sin\frac{B}{2}\sin\frac{C}{2}}{\sin\alpha} \end{aligned}\text{，}$ 这在 $\alpha = 90^\circ$ 时最小，也就是 $X$ 为从 $A$ 到对边的垂足时。

令 $a = 32$ 、 $b = 34$ 、 $c = 30$ ，半周长 $s = 48$ ，半角公式给出 $\sin\frac{A}{2}\sin\frac{B}{2}\sin\frac{C}{2}$ $= \frac{(s-a)(s-b)(s-c)}{abc}$ ，所以最小面积为 $\begin{aligned} &bc \cdot \frac{(s-a)(s-b)(s-c)}{abc} \\ &= \frac{16 \cdot 14 \cdot 18}{32} = 126 \end{aligned}\text{。}$

Since $AI_1$ and $AI_2$ bisect angles $BAX$ and $XAC,$ $\angle I_1AI_2 = \frac{1}{2}\angle BAX$ $+ \frac{1}{2}\angle XAC = \frac{A}{2},$ a constant. Let $\alpha = \angle AXB.$ The incenter angle formula gives $\angle AI_1B = 90^\circ + \frac{\alpha}{2},$ so the law of sines in $\triangle ABI_1$ yields $AI_1 = \frac{AB \sin\frac{B}{2}}{\cos\frac{\alpha}{2}},$ and similarly, since $\angle AXC = 180^\circ - \alpha,$ $AI_2 = \frac{AC \sin\frac{C}{2}}{\sin\frac{\alpha}{2}}.$

Therefore $\begin{aligned} &[\triangle AI_1I_2] = \frac{1}{2}\,AI_1 \cdot AI_2 \sin\frac{A}{2} \\ &= \frac{AB \cdot AC \sin\frac{A}{2}\sin\frac{B}{2}\sin\frac{C}{2}}{\sin\alpha}, \end{aligned}$ which is minimized when $\alpha = 90^\circ,$ that is, when $X$ is the foot of the altitude from $A.$

With $a = 32,$ $b = 34,$ $c = 30,$ and $s = 48,$ the half-angle formulas give $\sin\frac{A}{2}\sin\frac{B}{2}\sin\frac{C}{2}$ $= \frac{(s-a)(s-b)(s-c)}{abc},$ so the minimum area is $\begin{aligned} &bc \cdot \frac{(s-a)(s-b)(s-c)}{abc} \\ &= \frac{16 \cdot 14 \cdot 18}{32} = 126. \end{aligned}$

14.

设 $SP_1P_2P_3EP_4P_5$ 为一个七边形。一只青蛙从顶点 $S$ 开始跳跃。除 $E$ 外，从七边形的任意顶点，青蛙都可以跳到两个相邻顶点之一。当它到达顶点 $E$ 时，就停止并停在那里。求不超过 $12$ 次跳跃且最终到达 $E$ 的不同跳跃序列个数。

Let $SP_1P_2P_3EP_4P_5$ be a heptagon. A frog starts jumping at vertex $S.$ From any vertex of the heptagon except $E,$ the frog may jump to either of the two adjacent vertices. When it reaches vertex $E,$ the frog stops and stays there. Find the number of distinct sequences of jumps of no more than $12$ jumps that end at $E.$

答案

知识点：递推计数对称性

难度评级：3160

小提示：

把顶点分组为 $\{S, P_1\}$ 、 $\{P_2, P_5\}$ 、 $\{P_3, P_4\}$ ；每个顶点在相邻的每个类别中各有一个邻点，所以只需关心类别

Group the vertices as $\{S, P_1\},$ $\{P_2, P_5\},$ $\{P_3, P_4\};$ each vertex has exactly one neighbor in each adjacent class, so only the class matters

大提示：

若 $a_n, b_n, c_n$ 分别计数停在三类中的路径，则 $a_{n+1} = a_n + b_n$ 、 $b_{n+1} = a_n + c_n$ 、 $c_{n+1} = b_n$ ，并且恰有 $c_n$ 条路径在第 $n + 1$ 跳到达 $E$

If $a_n, b_n, c_n$ count paths ending in the three classes, then $a_{n+1} = a_n + b_n,$ $b_{n+1} = a_n + c_n,$ $c_{n+1} = b_n,$ and exactly $c_n$ paths reach $E$ on jump $n + 1$

解答：

把顶点分为 $\mathcal{A} = \{S, P_1\}$ 、 $\mathcal{B} = \{P_2, P_5\}$ 和 $\mathcal{C} = \{P_3, P_4\}$ 。 $\mathcal{A}$ 中每个顶点邻接一个 $\mathcal{A}$ 中的点和一个 $\mathcal{B}$ 中的点； $\mathcal{B}$ 中每个顶点邻接一个 $\mathcal{A}$ 中的点和一个 $\mathcal{C}$ 中的点； $\mathcal{C}$ 中每个顶点邻接一个 $\mathcal{B}$ 中的点和吸收顶点 $E$ 。因此若 $a_n$ 、 $b_n$ 、 $c_n$ 计数从 $S$ 出发、尚未到达 $E$ 且经过 $n$ 跳后停在各类中的路径数，则 $\begin{aligned} &a_{n+1} = a_n + b_n, \\ &b_{n+1} = a_n + c_n, \\ &c_{n+1} = b_n \end{aligned}\text{，}$ 并且恰有 $c_n$ 条路径会在第 $n + 1$ 跳首次到达 $E$ 。

从 $(a_0, b_0, c_0) = (1, 0, 0)$ 开始， $n = 0, 1, \ldots, 11$ 时的 $c_n$ 依次为 $0$ 、 $0$ 、 $1$ 、 $1$ 、 $3$ 、 $4$ 、 $9$ 、 $14$ 、 $28$ 、 $47$ 、 $89$ 、 $155$ 。

不超过 $12$ 跳且到达 $E$ 的序列数为 $c_0 + c_1 + \cdots + c_{11} = 351$ 。

Group the vertices into classes $\mathcal{A} = \{S, P_1\},$ $\mathcal{B} = \{P_2, P_5\},$ and $\mathcal{C} = \{P_3, P_4\}.$ Each vertex of $\mathcal{A}$ adjoins one vertex of $\mathcal{A}$ and one of $\mathcal{B};$ each vertex of $\mathcal{B}$ adjoins one of $\mathcal{A}$ and one of $\mathcal{C};$ and each vertex of $\mathcal{C}$ adjoins one of $\mathcal{B}$ and the absorbing vertex $E.$ Hence if $a_n,$ $b_n,$ $c_n$ count the $n$ -jump paths from $S$ that have not yet reached $E$ and end in each class, $\begin{aligned} &a_{n+1} = a_n + b_n, \\ &b_{n+1} = a_n + c_n, \\ &c_{n+1} = b_n, \end{aligned}$ and exactly $c_n$ paths reach $E$ for the first time on jump $n + 1.$

Starting from $(a_0, b_0, c_0) = (1, 0, 0),$ the values of $c_n$ for $n = 0, 1, \ldots, 11$ are $0,$ $0,$ $1,$ $1,$ $3,$ $4,$ $9,$ $14,$ $28,$ $47,$ $89,$ $155.$

The number of sequences of at most $12$ jumps ending at $E$ is $c_0 + c_1 + \cdots + c_{11} = 351.$

15.

David 找到四根长度不同的木棍，它们可用来组成三个不全等的凸圆内接四边形 $A$ 、 $B$ 、 $C$ ，每个都可内接于半径为 $1$ 的圆。令 $\varphi_A$ 表示四边形 $A$ 的对角线所成锐角的大小，并类似地定义 $\varphi_B$ 与 $\varphi_C$ 。已知 $\sin\varphi_A = \frac{2}{3}$ 、 $\sin\varphi_B = \frac{3}{5}$ 、 $\sin\varphi_C = \frac{6}{7}$ 。三个四边形的共同面积为 $K$ ，它可写成 $\frac{m}{n}$ 的形式，其中 $m$ 与 $n$ 是互质正整数。求 $m + n$ 。

David found four sticks of different lengths that can be used to form three non-congruent convex cyclic quadrilaterals, $A,$ $B,$ and $C,$ which can each be inscribed in a circle with radius $1.$ Let $\varphi_A$ denote the measure of the acute angle made by the diagonals of quadrilateral $A,$ and define $\varphi_B$ and $\varphi_C$ similarly. Suppose that $\sin\varphi_A = \frac{2}{3},$ $\sin\varphi_B = \frac{3}{5},$ and $\sin\varphi_C = \frac{6}{7}.$ All three quadrilaterals have the same area $K,$ which can be written in the form $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

答案

知识点：圆内接四边形弧三角学面积

难度评级：3500

小提示：

三个四边形都使用同样四条弦，所以它们的边在圆上截出的四段弧相同，只是循环顺序不同

All three quadrilaterals use the same four chords, so their sides cut the circle into the same four arcs, just in different cyclic orders

大提示：

在单位圆中，跨越两段弧的对角线长度等于把这两段弧的半和代入 $2\sin$ 后所得的值，而这个半和正是另外两个四边形之一的对角线夹角

In a unit circle a diagonal spanning two arcs has length $2\sin$ of their half-sum, and that half-sum is the diagonal angle of one of the other two quadrilaterals

解答：

四根木棍是单位圆的弦，分别截出固定弧 $\alpha$ 、 $\beta$ 、 $\gamma$ 、 $\delta$ ，且 $\alpha + \beta + \gamma + \delta = 360^\circ$ 。三个四边形对应三种不同的边的循环顺序：设 $A$ 的弧依次为 $\alpha, \beta, \gamma, \delta$ ；那么 $B$ （顺序 $\alpha, \gamma, \beta, \delta$ ）和 $C$ （顺序 $\alpha, \beta, \delta, \gamma$ ）是另外两种。圆内接四边形的对角线夹角等于任一对对边所截弧之和的一半，所以 $\sin\varphi_B = \sin\frac{\alpha + \beta}{2}$ ，且 $\sin\varphi_C = \sin\frac{\alpha + \delta}{2} = \sin\frac{\beta + \gamma}{2}$ 。

半径为 $1$ 的圆中，跨越弧 $\theta$ 的弦长为 $2\sin\frac{\theta}{2}$ 。四边形 $A$ 的两条对角线分别跨越弧 $\alpha + \beta$ 与 $\beta + \gamma$ ，所以长度为 $2\sin\varphi_B$ 和 $2\sin\varphi_C$ 。于是 $\begin{aligned} &K = \frac{1}{2}\,d_1 d_2 \sin\varphi_A \\ &= 2\sin\varphi_A \sin\varphi_B \sin\varphi_C \end{aligned}\text{，}$ 这是关于三个四边形对称的公式，因此三者面积相等。

所以 $K = 2 \cdot \frac{2}{3} \cdot \frac{3}{5} \cdot \frac{6}{7} = \frac{24}{35}$ ，于是 $m + n = 24 + 35 = 59$ 。

The four sticks are chords of the unit circle subtending fixed arcs $\alpha,$ $\beta,$ $\gamma,$ $\delta$ with $\alpha + \beta + \gamma + \delta = 360^\circ.$ The three quadrilaterals are the three distinct cyclic orders of the sides: say $A$ has arcs in order $\alpha, \beta, \gamma, \delta;$ then $B$ (order $\alpha, \gamma, \beta, \delta$ ) and $C$ (order $\alpha, \beta, \delta, \gamma$ ) are the other two. The angle between the diagonals of a cyclic quadrilateral is half the sum of the arcs subtended by either pair of opposite sides, so $\sin\varphi_B = \sin\frac{\alpha + \beta}{2}$ and $\sin\varphi_C = \sin\frac{\alpha + \delta}{2} = \sin\frac{\beta + \gamma}{2}.$

In a circle of radius $1,$ a chord spanning an arc $\theta$ has length $2\sin\frac{\theta}{2}.$ The diagonals of $A$ span the arcs $\alpha + \beta$ and $\beta + \gamma,$ so their lengths are $2\sin\varphi_B$ and $2\sin\varphi_C.$ Hence $\begin{aligned} &K = \frac{1}{2}\,d_1 d_2 \sin\varphi_A \\ &= 2\sin\varphi_A \sin\varphi_B \sin\varphi_C, \end{aligned}$ a formula symmetric in the three quadrilaterals, which is why all three areas are equal.

Therefore $K = 2 \cdot \frac{2}{3} \cdot \frac{3}{5} \cdot \frac{6}{7} = \frac{24}{35},$ and $m + n = 24 + 35 = 59.$