2023 AIME II 详解 | LIVE by Po-Shen Loh

1.

六棵苹果树上结的苹果数构成一个等差数列，其中苹果最多的一棵树所结的苹果数是苹果最少的一棵树的两倍。六棵树上的苹果总数为 $990$ 。求苹果最多的一棵树上的苹果数。

The numbers of apples growing on each of six apple trees form an arithmetic sequence where the greatest number of apples growing on any of the six trees is double the least number of apples growing on any of the six trees. The total number of apples growing on all six trees is $990.$ Find the greatest number of apples growing on any of the six trees.

答案

知识点：等差数列一次方程

难度评级：1850

小提示：

把苹果数写成 $a, a+d, \ldots, a+5d$ ，并把“最多是最少的两倍”转化为 $a$ 与 $d$ 的方程

Write the counts as $a, a+d, \ldots, a+5d$ and turn the doubling condition into an equation between $a$ and $d$

大提示：

由 $a + 5d = 2a$ 得 $a = 5d$ ，所以总数 $6a + 15d$ 化简为 $45d$

From $a + 5d = 2a$ we get $a = 5d,$ so the total $6a + 15d$ simplifies to $45d$

解答：

设六棵树上的苹果数为 $a, a+d, \ldots, a+5d$ ，公差为 $d \ge 0$ 。最多的苹果数是最少的两倍，所以 $a + 5d = 2a$ ，从而 $a = 5d$ 。总数为 $\begin{aligned} 6a + 15d &= 30d + 15d \\ &= 45d = 990 \end{aligned}\text{，}$ 因此 $d = 22$ 。

最多的苹果数是 $a + 5d = 10d = 220$ 。

Let the six counts be $a, a+d, \ldots, a+5d$ with common difference $d \ge 0.$ The greatest count is double the least, so $a + 5d = 2a,$ which gives $a = 5d.$ The total is $\begin{aligned} 6a + 15d &= 30d + 15d \\ &= 45d = 990, \end{aligned}$ so $d = 22.$

The greatest number of apples is $a + 5d = 10d = 220.$

2.

回忆：回文数是正着读和倒着读都相同的数。求小于 $1000$ 的最大整数，使它用十进制和八进制表示时都是回文数，例如 $292 = 444_8$ 。

Recall that a palindrome is a number that reads the same forward and backward. Find the greatest integer less than $1000$ that is a palindrome both when written in base ten and when written in base eight, such as $292 = 444_8.$

答案

知识点：回文数进制系统列举

难度评级：2110

小提示：

在 $512$ 与 $999$ 之间的八进制回文数有四位，形如 $\overline{1bb1}_8 = 513 + 72b$

Any base-eight palindrome between $512$ and $999$ has four base-eight digits and looks like $\overline{1bb1}_8 = 513 + 72b$

大提示：

三位八进制数至多为 $511$ ，所以只需从 $b = 6, 5, 4, \ldots$ 开始检验它的十进制表示是否为回文数

Three-digit base-eight numbers are at most $511,$ so just test $b = 6, 5, 4, \ldots$ for a base-ten palindrome

解答：

四位八进制数在 $512$ 与 $4095$ 之间，所以小于 $1000$ 的四位八进制回文数的首位（也是末位）必须是 $1$ ：它的形式为 $\overline{1bb1}_8 = 512 + 64b$ ${}+ 8b + 1$ $= 513 + 72b$ 。要使它小于 $1000$ ，需 $b \le 6$ ，得到候选数 $513, 585, 657, 729, 801, 873, 945$ 。

从大到小检查，其中唯一在十进制下也是回文数的是 $585 = 1111_8$ 。所有至多三位的八进制回文数至多为 $777_8 = 511 \lt 585$ ，所以答案是 $585$ 。

A four-digit base-eight number lies between $512$ and $4095,$ so a base-eight palindrome less than $1000$ with four digits must have leading (and trailing) digit $1:$ it has the form $\overline{1bb1}_8 = 512 + 64b$ ${}+ 8b + 1$ $= 513 + 72b.$ Keeping this below $1000$ requires $b \le 6,$ giving the candidates $513, 585, 657, 729, 801, 873, 945.$

Checking from the top, the only one of these that is also a palindrome in base ten is $585 = 1111_8.$ Every base-eight palindrome with at most three digits is at most $777_8 = 511 \lt 585,$ so the answer is $585.$

3.

设 $\triangle ABC$ 是等腰三角形，且 $\angle A = 90^\circ$ 。存在一点 $P$ 位于 $\triangle ABC$ 内，使得 $\angle PAB = \angle PBC = \angle PCA$ ，且 $AP = 10$ 。求 $\triangle ABC$ 的面积。

Let $\triangle ABC$ be an isosceles triangle with $\angle A = 90^\circ.$ There exists a point $P$ inside $\triangle ABC$ such that $\angle PAB = \angle PBC = \angle PCA$ and $AP = 10.$ Find the area of $\triangle ABC.$

答案

知识点：导角正弦定理三角学

难度评级：2460

小提示：

设公共角为 $\omega$ 。在三角形 $APC$ 中， $A$ 与 $C$ 处的角分别为 $90^\circ - \omega$ 和 $\omega$ ，所以 $\angle APC = 90^\circ$

Let $\omega$ be the common angle. In triangle $APC$ the angles at $A$ and $C$ are $90^\circ - \omega$ and $\omega,$ so $\angle APC = 90^\circ$

大提示：

在三角形 $ABP$ 中用正弦定理，并结合 $AC = \frac{AP}{\sin\omega}$ ；最后会化为 $\tan\omega = \frac{1}{2}$

Compare the law of sines in triangle $ABP$ with $AC = \frac{AP}{\sin\omega};$ everything reduces to $\tan\omega = \frac{1}{2}$

解答：

设公共角为 $\omega$ ，并令 $L = AB = AC$ 。因为 $\angle PAB = \omega$ ，所以 $\angle PAC = 90^\circ - \omega$ ，又 $\angle PCA = \omega$ ，三角形 $APC$ 的角和给出 $\angle APC = 90^\circ$ 。因此在直角三角形 $APC$ 中， $L = AC = \frac{AP}{\sin\omega} = \frac{10}{\sin\omega}\text{。}$

在三角形 $ABP$ 中， $A$ 处的角为 $\omega$ ， $B$ 处的角为 $45^\circ - \omega$ ，所以 $\angle APB = 135^\circ$ 。由正弦定理， $\frac{AP}{\sin(45^\circ - \omega)} = \frac{AB}{\sin 135^\circ}$ ，即 $10 \sin 135^\circ = L \sin(45^\circ - \omega)$ 。代入 $L = \frac{10}{\sin\omega}$ 并展开，得 $\begin{aligned} \sin\omega &= \sqrt{2}\,\sin(45^\circ - \omega) \\ &= \cos\omega - \sin\omega \end{aligned}\text{，}$ 所以 $\tan\omega = \frac{1}{2}$ ，并且 $\sin^2\omega = \frac{1}{5}$ 。

因此 $L^2 = \frac{100}{\sin^2\omega} = 500$ ，面积为 $\frac{1}{2}L^2 = 250$ 。

Let $\omega$ denote the common angle and $L = AB = AC.$ Since $\angle PAB = \omega,$ we have $\angle PAC = 90^\circ - \omega,$ and with $\angle PCA = \omega$ the angles of triangle $APC$ give $\angle APC = 90^\circ.$ Hence in right triangle $APC,$ $L = AC = \frac{AP}{\sin\omega} = \frac{10}{\sin\omega}.$

In triangle $ABP,$ the angle at $A$ is $\omega$ and the angle at $B$ is $45^\circ - \omega,$ so $\angle APB = 135^\circ.$ The law of sines gives $\frac{AP}{\sin(45^\circ - \omega)} = \frac{AB}{\sin 135^\circ},$ that is, $10 \sin 135^\circ = L \sin(45^\circ - \omega).$ Substituting $L = \frac{10}{\sin\omega}$ and expanding yields $\begin{aligned} \sin\omega &= \sqrt{2}\,\sin(45^\circ - \omega) \\ &= \cos\omega - \sin\omega, \end{aligned}$ so $\tan\omega = \frac{1}{2}$ and $\sin^2\omega = \frac{1}{5}.$

Therefore $L^2 = \frac{100}{\sin^2\omega} = 500,$ and the area is $\frac{1}{2}L^2 = 250.$

4.

设实数 $x$ 、 $y$ 、 $z$ 满足方程组 $\begin{aligned} xy + 4z &= 60, \\ yz + 4x &= 60, \\ zx + 4y &= 60 \end{aligned}\text{。}$

设 $S$ 为 $x$ 的所有可能取值组成的集合。求 $S$ 中所有元素的平方和。

Let $x,$ $y,$ and $z$ be real numbers satisfying the system of equations $\begin{aligned} xy + 4z &= 60, \\ yz + 4x &= 60, \\ zx + 4y &= 60. \end{aligned}$

Let $S$ be the set of possible values of $x.$ Find the sum of the squares of the elements of $S.$

答案

知识点：方程组因式分解对称性（代数）

难度评级：2460

小提示：

两两相减：前两个方程相减得到 $(y - 4)(x - z) = 0$

Subtract the equations in pairs: the first two give $(y - 4)(x - z) = 0$

大提示：

当 $x = z$ 时，消去 $y$ 得 $x^3 - 76x + 240 = 0$ ，再寻找较小的整数根

When $x = z,$ eliminate $y$ to get $x^3 - 76x + 240 = 0,$ then look for small integer roots

解答：

用第一个方程减去第二个方程，得 $xy - yz + 4z - 4x = 0$ 可因式分解为 $(y - 4)(x - z) = 0$ 。所以 $y = 4$ 或 $x = z$ 。

若 $y = 4$ ：第一个方程变为 $4x + 4z = 60$ ，所以 $x + z = 15$ ，第二个方程仍给出同一个条件 $4z + 4x = 60$ 。第三个方程给出 $zx = 44$ 。于是 $x$ 和 $z$ 是 $t^2 - 15t + 44 = (t - 4)(t - 11)$ 的根，所以 $x \in \{4, 11\}$ 。

若 $x = z$ ：第一个方程为 $x(y + 4) = 60$ ，所以 $y = \frac{60}{x} - 4$ ，第三个方程为 $x^2 + 4y = 60$ 。代入得 $\begin{gathered} x^2 + \frac{240}{x} - 16 = 60 \\ \Longrightarrow x^3 - 76x + 240 = 0 \\ = (x - 4)(x - 6)(x + 10) \end{gathered}\text{，}$ 所以 $x \in \{4, 6, -10\}$ ，并且每个都对应实数 $y$ 和 $z$ 。于是 $S = \{-10, 4, 6, 11\}$ ，平方和为 $100 + 16 + 36 + 121 = 273$ 。

Subtracting the second equation from the first gives $xy - yz + 4z - 4x = 0,$ which factors as $(y - 4)(x - z) = 0.$ So $y = 4$ or $x = z.$

If $y = 4:$ the first equation becomes $4x + 4z = 60,$ so $x + z = 15,$ and the second becomes $4z + 4x = 60$ again while the third gives $zx = 44.$ Then $x$ and $z$ are roots of $t^2 - 15t + 44 = (t - 4)(t - 11),$ so $x \in \{4, 11\}.$

If $x = z:$ the first equation reads $x(y + 4) = 60,$ so $y = \frac{60}{x} - 4,$ and the third reads $x^2 + 4y = 60.$ Substituting, $\begin{gathered} x^2 + \frac{240}{x} - 16 = 60 \\ \Longrightarrow x^3 - 76x + 240 = 0 \\ = (x - 4)(x - 6)(x + 10), \end{gathered}$ so $x \in \{4, 6, -10\},$ each with real $y$ and $z.$ Hence $S = \{-10, 4, 6, 11\}$ and the sum of squares is $100 + 16 + 36 + 121 = 273.$

5.

设 $S$ 为所有满足如下条件的正有理数 $r$ 的集合：当 $r$ 与 $55r$ 都写成最简分数时，一个分数的分子与分母之和等于另一个分数的分子与分母之和。集合 $S$ 中所有元素的和可表示为 $\frac{p}{q}$ ，其中 $p$ 与 $q$ 是互质的正整数。求 $p + q$ 。

Let $S$ be the set of all positive rational numbers $r$ such that when the two numbers $r$ and $55r$ are written as fractions in lowest terms, the sum of the numerator and denominator of one fraction is the same as the sum of the numerator and denominator of the other fraction. The sum of all the elements of $S$ can be expressed in the form $\frac{p}{q},$ where $p$ and $q$ are relatively prime positive integers. Find $p + q.$

答案

知识点：分数最大公约数分类讨论

难度评级：2740

小提示：

将 $r = \frac{a}{b}$ 写成最简分数； $\frac{55a}{b}$ 如何约分由 $\gcd(b, 55)$ 决定，而它只能是 $1$ 、 $5$ 、 $11$ 或 $55$

Write $r = \frac{a}{b}$ in lowest terms; how $\frac{55a}{b}$ reduces is governed by $\gcd(b, 55),$ which is $1,$ $5,$ $11,$ or $55$

大提示：

$\gcd = 5$ 与 $\gcd = 11$ 两种情况分别给出 $2b = 25a$ 和 $5b = 22a$ ；互质条件会分别确定唯一的分数

The cases $\gcd = 5$ and $\gcd = 11$ give $2b = 25a$ and $5b = 22a;$ coprimality pins down exactly one fraction in each case

解答：

将 $r = \frac{a}{b}$ 写成最简分数，并令 $g = \gcd(b, 55)$ 。则 $55r$ 的最简形式为 $\frac{\frac{55a}{g}}{\frac{b}{g}}$ （因为 $\gcd(a, b) = 1$ ，且 $55$ 不含平方因子，不会再有进一步约分）。条件为 $a + b = \frac{55a}{g} + \frac{b}{g}\text{。}$ 若 $g = 1$ ，则迫使 $a = 55a$ ，不可能；若 $g = 55$ ，则迫使 $b = \frac{b}{55}$ ，也不可能。

若 $g = 5$ ： $a + b = 11a + \frac{b}{5}$ ，得到 $\frac{4b}{5} = 10a$ ，所以 $2b = 25a$ 。由于 $\gcd(a, b) = 1$ ，必须有 $a = 2$ 、 $b = 25$ ，所以 $r = \frac{2}{25}$ （确实有 $2 + 25 = 27 = 22 + 5$ ，因为 $55r = \frac{22}{5}$ ）。若 $g = 11$ ： $a + b = 5a + \frac{b}{11}$ ，得到 $\frac{10b}{11} = 4a$ ，所以 $5b = 22a$ ，从而 $a = 5$ 、 $b = 22$ ， $r = \frac{5}{22}$ （此时 $5 + 22 = 27 = 25 + 2$ ，因为 $55r = \frac{25}{2}$ ）。

因此 $S = \left\{\frac{2}{25}, \frac{5}{22}\right\}$ ，和为 $\frac{2}{25} + \frac{5}{22} = \frac{44 + 125}{550} = \frac{169}{550}$ ，已是最简分数。答案是 $169 + 550 = 719$ 。

Write $r = \frac{a}{b}$ in lowest terms and let $g = \gcd(b, 55).$ Then $55r$ in lowest terms is $\frac{\frac{55a}{g}}{\frac{b}{g}}$ (no further cancellation is possible since $\gcd(a, b) = 1$ and $55$ is squarefree). The condition is $a + b = \frac{55a}{g} + \frac{b}{g}.$ If $g = 1$ this forces $a = 55a,$ impossible; if $g = 55$ it forces $b = \frac{b}{55},$ impossible.

If $g = 5:$ $a + b = 11a + \frac{b}{5}$ gives $\frac{4b}{5} = 10a,$ so $2b = 25a.$ Since $\gcd(a, b) = 1,$ we need $a = 2$ and $b = 25,$ so $r = \frac{2}{25}$ (indeed $2 + 25 = 27 = 22 + 5$ from $55r = \frac{22}{5}$ ). If $g = 11:$ $a + b = 5a + \frac{b}{11}$ gives $\frac{10b}{11} = 4a,$ so $5b = 22a,$ forcing $a = 5,$ $b = 22$ and $r = \frac{5}{22}$ (with $5 + 22 = 27 = 25 + 2$ from $55r = \frac{25}{2}$ ).

Hence $S = \left\{\frac{2}{25}, \frac{5}{22}\right\}$ and the sum is $\frac{2}{25} + \frac{5}{22} = \frac{44 + 125}{550} = \frac{169}{550},$ already in lowest terms. The answer is $169 + 550 = 719.$

6.

考虑如下图所示，由三个单位正方形沿边拼成的 L 形区域。从该区域内部独立且均匀随机地选取两点 $A$ 和 $B$ 。线段 $\overline{AB}$ 的中点也位于这个 L 形区域内的概率可表示为 $\frac{m}{n}$ ，其中 $m$ 与 $n$ 是互质的正整数。求 $m + n$ 。

Consider the L-shaped region formed by three unit squares joined at their sides, as shown below. Two points $A$ and $B$ are chosen independently and uniformly at random from inside the region. The probability that the midpoint of $\overline{AB}$ also lies inside this L-shaped region can be expressed as $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

答案

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

难度评级：2740

小提示：

三个正方形与缺失的第四个正方形可以拼成一个 $2 \times 2$ 正方形，所以中点只可能因落入缺失的正方形而失败

The three squares plus the missing fourth square tile a $2 \times 2$ square, so the midpoint can fail only by landing in the missing square

大提示：

失败需要一个点在上方正方形、另一个点在右侧正方形，然后每个坐标条件，如 $x_1 + x_2 \gt 2$ ，发生的概率都是 $\frac{1}{2}$

Failure needs one point in the top square and one in the right square, and then each coordinate condition, like $x_1 + x_2 \gt 2,$ holds with probability $\frac{1}{2}$

解答：

将区域放为 $[0,1]^2 \cup \bigl([0,1] \times [1,2]\bigr)$ $\cup \bigl([1,2] \times [0,1]\bigr)$ ，即一个 $2 \times 2$ 正方形去掉右上角单位正方形。中点的两个坐标都是 $[0, 2]$ 中两个数的平均值，所以中点一定在这个 $2 \times 2$ 正方形中；它不在 L 形区域内，当且仅当它落在缺失的正方形中，即 $x_A + x_B \gt 2$ 且 $y_A + y_B \gt 2$ 。

如果没有点在右侧正方形，则 $x_A + x_B \le 2$ ；如果没有点在上方正方形，则 $y_A + y_B \le 2$ 。所以失败要求一个点在上方正方形，另一个点在右侧正方形，这发生的概率为 $2 \cdot \frac{1}{3} \cdot \frac{1}{3} = \frac{2}{9}$ 。在这种情况下，一个 $x$ 坐标均匀分布在 $[0,1]$ ，另一个均匀分布在 $[1,2]$ ，所以 $x_A + x_B \gt 2$ 的概率为 $\frac{1}{2}$ ，同理且独立地， $y_A + y_B \gt 2$ 的概率为 $\frac{1}{2}$ 。

失败概率为 $\frac{2}{9} \cdot \frac{1}{4} = \frac{1}{18}$ ，所以所求概率为 $\frac{17}{18}$ ， $m + n = 17 + 18 = 35$ 。

Place the region as $[0,1]^2 \cup \bigl([0,1] \times [1,2]\bigr)$ $\cup \bigl([1,2] \times [0,1]\bigr),$ so it is the $2 \times 2$ square with the top-right unit square removed. Both coordinates of the midpoint are averages of numbers in $[0, 2],$ so the midpoint always lies in the $2 \times 2$ square; it fails to lie in the region exactly when it lands in the missing square, i.e. when $x_A + x_B \gt 2$ and $y_A + y_B \gt 2.$

If neither point is in the right square, then $x_A + x_B \le 2;$ if neither is in the top square, then $y_A + y_B \le 2.$ So failure requires one point in the top square and the other in the right square, which happens with probability $2 \cdot \frac{1}{3} \cdot \frac{1}{3} = \frac{2}{9}.$ In that case, one $x$ -coordinate is uniform on $[0,1]$ and the other on $[1,2],$ so $x_A + x_B \gt 2$ with probability $\frac{1}{2},$ and independently $y_A + y_B \gt 2$ with probability $\frac{1}{2}.$

The failure probability is $\frac{2}{9} \cdot \frac{1}{4} = \frac{1}{18},$ so the desired probability is $\frac{17}{18}$ and $m + n = 17 + 18 = 35.$

7.

正 $12$ 边形的每个顶点都要涂成红色或蓝色，因此共有 $2^{12}$ 种涂色。求其中满足如下性质的涂色数：不存在四个同色顶点恰好是一个矩形的四个顶点。

Each vertex of a regular dodecagon ( $12$ -gon) is to be colored either red or blue, and thus there are $2^{12}$ possible colorings. Find the number of these colorings with the property that no four vertices colored the same color are the four vertices of a rectangle.

答案

知识点：有限制的排列乘法原理分类讨论

难度评级：2600

小提示：

圆内接矩形的两条对角线必须都是直径，所以矩形对应于 $6$ 对对顶顶点中的两对

A rectangle inscribed in the circle must have both diagonals as diameters, so rectangles correspond to pairs of the $6$ antipodal pairs of vertices

大提示：

将每对对顶顶点分类为全红、全蓝或混合；一种涂色可行，当且仅当至多一对全红且至多一对全蓝

Classify each antipodal pair as both red, both blue, or mixed; a coloring works exactly when at most one pair is both red and at most one is both blue

解答：

十二个顶点在同一个圆上，而圆内接矩形的对角线必须经过圆心。因此这些顶点构成的矩形恰好对应于两条不同的直径，即从 $6$ 对对顶顶点中选两对。出现同色矩形，当且仅当有两对对顶顶点都被同一种颜色涂满。

每对对顶顶点独立地可以是全红（ $1$ 种）、全蓝（ $1$ 种）或混合（ $2$ 种）。一种涂色有效，当且仅当全红的对数至多为一，全蓝的对数也至多为一。按全红对数和全蓝对数计数： $\begin{gathered} 2^6 + 6 \cdot 2^5 \\ {}+ 6 \cdot 2^5 + 6 \cdot 5 \cdot 2^4 \\ = 64 + 192 + 192 + 480 \\ = 928 \end{gathered}\text{。}$

The twelve vertices lie on a circle, and a rectangle inscribed in a circle must have its diagonals pass through the center. So the rectangles with vertices among the twelve are exactly the pairs of distinct diameters, where the diameters join the $6$ antipodal pairs of vertices. A monochromatic rectangle appears exactly when two antipodal pairs are each colored solidly in the same color.

Each antipodal pair is independently both red ( $1$ way), both blue ( $1$ way), or mixed ( $2$ ways). A coloring is valid exactly when at most one pair is both red and at most one pair is both blue. Counting by the numbers of solid red and solid blue pairs: $\begin{gathered} 2^6 + 6 \cdot 2^5 \\ {}+ 6 \cdot 2^5 + 6 \cdot 5 \cdot 2^4 \\ = 64 + 192 + 192 + 480 \\ = 928. \end{gathered}$

8.

设 $\omega = \cos\frac{2\pi}{7} + i \cdot \sin\frac{2\pi}{7}$ ，其中 $i = \sqrt{-1}$ 。求下列乘积的值： $\prod_{k=0}^{6} \left(\omega^{3k} + \omega^k + 1\right)\text{。}$

Let $\omega = \cos\frac{2\pi}{7} + i \cdot \sin\frac{2\pi}{7},$ where $i = \sqrt{-1}.$ Find the value of the product $\prod_{k=0}^{6} \left(\omega^{3k} + \omega^k + 1\right).$

答案

知识点：单位根多项式复数

难度评级：2840

小提示：

$k = 0$ 的因子等于 $3$ ；其余部分是在所有本原七次单位根上计算 $\prod P(z)$ ，其中 $P(x) = x^3 + x + 1$

The $k = 0$ factor equals $3;$ the rest is $\prod P(z)$ over the primitive seventh roots of unity, where $P(x) = x^3 + x + 1$

大提示：

$\prod_{z^7 = 1} P(z) = \prod (1 - \beta^7)$ ，其中 $\beta$ 遍历 $P$ 的根；化简 $\beta^7$ 时使用 $\beta^3 = -\beta - 1$

$\prod_{z^7 = 1} P(z) = \prod (1 - \beta^7)$ over the roots $\beta$ of $P;$ reduce $\beta^7$ using $\beta^3 = -\beta - 1$

解答：

令 $P(x) = x^3 + x + 1$ ，则所求乘积为 $\prod_{k=0}^{6} P(\omega^k)$ ，其中 $\omega^0, \ldots, \omega^6$ 是全部七次单位根。因为 $x^7 - 1 = \prod_k (x - \omega^k)$ ，写出因式分解 $P(x)$ $= (x - \beta_1)(x - \beta_2)(x - \beta_3)$ ，再交换二重乘积的顺序，得 $\begin{gathered} \prod_{k=0}^{6} P(\omega^k) \\ = \prod_{j=1}^{3} \prod_{k=0}^{6} (\omega^k - \beta_j) \\ = \prod_{j=1}^{3} \bigl(-(\beta_j^7 - 1)\bigr) \\ = \prod_{j=1}^{3} (1 - \beta_j^7) \end{gathered}\text{。}$

若 $\beta$ 是 $P$ 的一个根，反复使用 $\beta^3 = -\beta - 1$ ，得到 $\beta^4 = -\beta^2 - \beta$ 、 $\beta^5 = -\beta^2 + \beta + 1$ 、 $\beta^6 = \beta^2 + 2\beta + 1$ ，以及 $\beta^7 = 2\beta^2 - 1$ 。因此 $1 - \beta^7 = 2(1 - \beta)(1 + \beta)$ ，并且 $\begin{gathered} \prod_{j} (1 - \beta_j^7) \\ = 2^3 \prod_j (1 - \beta_j) \prod_j (1 + \beta_j) \\ = 8 \cdot P(1) \cdot \bigl(-P(-1)\bigr) \\ = 8 \cdot 3 \cdot 1 = 24 \end{gathered}\text{。}$

所以所求乘积等于 $24$ 。

Let $P(x) = x^3 + x + 1,$ so the product is $\prod_{k=0}^{6} P(\omega^k),$ where $\omega^0, \ldots, \omega^6$ are all seventh roots of unity. Since $x^7 - 1 = \prod_k (x - \omega^k),$ writing the factorization $P(x)$ $= (x - \beta_1)(x - \beta_2)(x - \beta_3)$ and swapping the order of the double product gives $\begin{gathered} \prod_{k=0}^{6} P(\omega^k) \\ = \prod_{j=1}^{3} \prod_{k=0}^{6} (\omega^k - \beta_j) \\ = \prod_{j=1}^{3} \bigl(-(\beta_j^7 - 1)\bigr) \\ = \prod_{j=1}^{3} (1 - \beta_j^7). \end{gathered}$

For a root $\beta$ of $P,$ repeatedly using $\beta^3 = -\beta - 1$ gives $\beta^4 = -\beta^2 - \beta,$ $\beta^5 = -\beta^2 + \beta + 1,$ $\beta^6 = \beta^2 + 2\beta + 1,$ and $\beta^7 = 2\beta^2 - 1.$ Hence $1 - \beta^7 = 2(1 - \beta)(1 + \beta),$ and $\begin{gathered} \prod_{j} (1 - \beta_j^7) \\ = 2^3 \prod_j (1 - \beta_j) \prod_j (1 + \beta_j) \\ = 8 \cdot P(1) \cdot \bigl(-P(-1)\bigr) \\ = 8 \cdot 3 \cdot 1 = 24. \end{gathered}$

So the requested product equals $24.$

9.

圆 $\omega_1$ 和 $\omega_2$ 相交于两点 $P$ 和 $Q$ ，更靠近 $P$ 的公切线与 $\omega_1$ 和 $\omega_2$ 分别相切于点 $A$ 与点 $B$ 。与 $\overline{AB}$ 平行且过 $P$ 的直线第二次分别交 $\omega_1$ 和 $\omega_2$ 于点 $X$ 与 $Y$ 。已知 $PX = 10$ 、 $PY = 14$ 、 $PQ = 5$ 。则梯形 $XABY$ 的面积为 $m\sqrt{n}$ ，其中 $m$ 和 $n$ 是正整数，且 $n$ 不被任何素数的平方整除。求 $m + n$ 。

Circles $\omega_1$ and $\omega_2$ intersect at two points $P$ and $Q,$ and their common tangent line closer to $P$ intersects $\omega_1$ and $\omega_2$ at points $A$ and $B,$ respectively. The line parallel to $\overline{AB}$ that passes through $P$ intersects $\omega_1$ and $\omega_2$ for the second time at points $X$ and $Y,$ respectively. Suppose $PX = 10,$ $PY = 14,$ and $PQ = 5.$ Then the area of trapezoid $XABY$ is $m\sqrt{n},$ where $m$ and $n$ are positive integers and $n$ is not divisible by the square of any prime. Find $m + n.$

答案

知识点：圆幂根轴梯形

难度评级：2920

小提示：

$A$ 处的切线平行于弦 $XP$ ，所以从 $A$ 向直线 $XY$ 作垂线，垂足是 $XP$ 的中点； $B$ 处同理

The tangent at $A$ is parallel to chord $XP,$ so the foot of the perpendicular from $A$ to line $XY$ is the midpoint of $XP;$ the same holds at $B$

大提示：

直线 $QP$ 与 $AB$ 相交于后者的中点 $M$ ，且 $MA^2 = MP(MP + 5)$ 可确定 $MP$ ，从而确定梯形的高

Line $QP$ meets $AB$ at its midpoint $M,$ and $MA^2 = MP(MP + 5)$ determines $MP,$ hence the height of the trapezoid

解答：

因为 $\omega_1$ 在 $A$ 处的切线平行于弦 $XP$ ，点 $A$ 是弧 $XP$ 的中点，所以从 $A$ 向直线 $XY$ 作垂线会落在 $\overline{XP}$ 的中点；同理，从 $B$ 作垂线会落在 $\overline{PY}$ 的中点。由于 $X$ 和 $Y$ 位于 $P$ 的两侧，梯形的两条平行边为 $XY = 10 + 14 = 24$ 和 $AB = \frac{10}{2} + \frac{14}{2} = 12$ 。

直线 $PQ$ 是根轴，所以它与切线的交点 $M$ 满足 $MA^2 = MP \cdot MQ = MB^2$ ： $M$ 是 $\overline{AB}$ 的中点，并且 $MA = 6$ 、 $MQ = MP + 5$ ，于是 $\begin{gathered} 36 = MP(MP + 5), \\ MP = 4 \end{gathered}\text{。}$

沿 $AB$ 建立坐标： $A$ 和 $B$ 的垂足分别是 $XP$ 与 $PY$ 的中点，所以 $P$ 距第一个垂足 $5$ 个单位，而 $M$ 到 $A$ 的距离为 $6$ 。因此 $M$ 与 $P$ 的水平偏移为 $6 - 5 = 1$ ，梯形的高 $h$ 满足 $h^2 = MP^2 - 1 = 15$ 。面积为 $\frac{24 + 12}{2}\sqrt{15} = 18\sqrt{15}\text{，}$ 所以 $m + n = 18 + 15 = 33$ 。

Since the tangent to $\omega_1$ at $A$ is parallel to the chord $XP,$ the point $A$ is the midpoint of arc $XP,$ so the perpendicular from $A$ to line $XY$ lands at the midpoint of $\overline{XP};$ similarly the perpendicular from $B$ lands at the midpoint of $\overline{PY}.$ As $X$ and $Y$ are on opposite sides of $P,$ the parallel sides of the trapezoid are $XY = 10 + 14 = 24$ and $AB = \frac{10}{2} + \frac{14}{2} = 12.$

Line $PQ$ is the radical axis, so its intersection $M$ with the tangent line satisfies $MA^2 = MP \cdot MQ = MB^2:$ $M$ is the midpoint of $\overline{AB},$ and with $MA = 6$ and $MQ = MP + 5,$ $\begin{gathered} 36 = MP(MP + 5), \\ MP = 4. \end{gathered}$

Set up coordinates along $AB:$ the feet of $A$ and $B$ are the midpoints of $XP$ and $PY,$ so $P$ lies $5$ units from the first foot, while the distance from $M$ to $A$ is $6.$ Hence the horizontal offset between $M$ and $P$ is $6 - 5 = 1,$ and the height $h$ of the trapezoid satisfies $h^2 = MP^2 - 1 = 15.$ The area is $\frac{24 + 12}{2}\sqrt{15} = 18\sqrt{15},$ so $m + n = 18 + 15 = 33.$

10.

设 $N$ 为把整数 $1$ 到 $12$ 放入一个有 $12$ 个格子的 $2 \times 6$ 网格中的方式数，使得任何共边的两个格子中的数之差都不能被 $3$ 整除。下图给出了一种这样的放法。求 $N$ 的正整数因数个数。

Let $N$ be the number of ways to place the integers $1$ through $12$ in the $12$ cells of a $2 \times 6$ grid so that for any two cells sharing a side, the difference between the numbers in those cells is not divisible by $3.$ One way to do this is shown below. Find the number of positive integer divisors of $N.$

答案

知识点：模运算多重集排列因数个数

难度评级：2920

小提示：

共边格子的模 $3$ 余数必须不同；先数余数图案，再乘以 $(4!)^3$ 来放入实际数字

Cells sharing a side must have different residues mod $3;$ count the residue patterns first, then multiply by $(4!)^3$ to place the actual numbers

大提示：

每一列显示两个不同的余数；从任意一列出发，三种无序余数对中的每一种都能以恰好一种方向出现在下一列，而且每种余数对必须出现两次

Each column shows two distinct residues; from any column, each of the three unordered residue pairs can come next in exactly one orientation, and each pair must occur twice

解答：

条件等价于相邻格子的数模 $3$ 余数不同。在 $1, \ldots, 12$ 中，每个余数类恰好有 $4$ 个数，所以 $N = K \cdot (4!)^3$ ，其中 $K$ 是用余数 $0, 1, 2$ 填满网格的方式数，每个余数使用 $4$ 次，且相邻格子余数不同。

一列是一个有序对 $(a, b)$ ，其中两个余数不同。若当前列为 $(a, b)$ ， $e$ 为第三个余数，则下一列必须是 $(b, a)$ 、 $(b, e)$ 、 $(e, a)$ 之一：三种无序对 $\{a,b\}$ 、 $\{b,e\}$ 、 $\{a,e\}$ 都恰好以一种允许的方向出现。因此一个余数图案由六个无序对的序列以及第一列的方向决定。因为每个余数必须出现 $4$ 次，所以三种余数对都必须恰好使用两次，给出 $\frac{6!}{2!\,2!\,2!} = 90$ 个序列，且 $K = 2 \cdot 90 = 180$ 。

因此 $N = 180 \cdot 24^3$ $= 2{,}488{,}320$ $= 2^{11} \cdot 3^5 \cdot 5$ ，它有 $12 \cdot 6 \cdot 2 = 144$ 个正因数。

The condition says adjacent cells have different residues mod $3.$ Each residue class among $1, \ldots, 12$ has exactly $4$ members, so $N = K \cdot (4!)^3,$ where $K$ is the number of ways to fill the grid with residues $0, 1, 2,$ each used $4$ times, with adjacent cells different.

A column is an ordered pair $(a, b)$ of distinct residues. If the current column is $(a, b)$ and $e$ is the third residue, the next column must be one of $(b, a),$ $(b, e),$ $(e, a):$ each of the three unordered pairs $\{a,b\},$ $\{b,e\},$ $\{a,e\}$ occurs in exactly one allowed orientation. So a residue pattern is determined by the sequence of six unordered pairs together with the orientation of the first column. Since each residue must appear $4$ times, each of the three pairs must be used exactly twice, giving $\frac{6!}{2!\,2!\,2!} = 90$ sequences and $K = 2 \cdot 90 = 180.$

Therefore $N = 180 \cdot 24^3$ $= 2{,}488{,}320$ $= 2^{11} \cdot 3^5 \cdot 5,$ which has $12 \cdot 6 \cdot 2 = 144$ positive divisors.

11.

求由 $16$ 个 $\{1, 2, 3, 4, 5\}$ 的不同子集组成的集合族的个数，使得集合族中任意两个子集 $X$ 和 $Y$ 都满足 $X \cap Y \neq \emptyset$ 。

Find the number of collections of $16$ distinct subsets of $\{1, 2, 3, 4, 5\}$ with the property that for any two subsets $X$ and $Y$ in the collection, $X \cap Y \neq \emptyset.$

答案

知识点：子集图论分类讨论

难度评级：3060

小提示：

一个集合与它的补集不相交，所以集合族必须从 $16$ 对互补子集中每对恰好选一个集合

A set and its complement are disjoint, so the collection must contain exactly one set from each of the $16$ complementary pairs

大提示：

如果选了某个单元素集，则每个集合都必须包含这个元素。否则只有被选中的 $2$ 元子集可能冲突：它们必须两两相交或组成一个三角形。

If a singleton is chosen, every set must contain it. Otherwise only the chosen $2$ -element sets can conflict: they must pairwise share an element or form a triangle.

解答：

这 $32$ 个子集分成 $16$ 对互补子集 $\{X, X^{\mathsf{c}}\}$ ，任何集合族都不能同时包含一对中的两个集合（它们不相交）。一个包含 $16$ 个两两相交子集的集合族因此必须从每对互补子集中恰好选一个；特别地，它包含 $\{1,2,3,4,5\}$ ，且不包含 $\emptyset$ 。

如果选了某个单元素集 $\{x\}$ ，那么每个成员都必须与 $\{x\}$ 相交，也就是都包含 $x$ 。每对互补子集中恰好有一个集合包含 $x$ ，所以集合族必须正好是这 $16$ 个包含 $x$ 的子集；这给出 $5$ 个集合族。否则没有单元素集被选中，因此全部五个 $4$ 元子集都在集合族中。任意两个 $3$ 元子集在一个 $5$ 元集合中必然相交；一个 $4$ 元子集只与它的补集不相交；一个被选中的 $2$ 元子集和一个被选中的 $3$ 元子集只有在互为补集时才不相交，而这种情况不可能同时被选中。所以剩下的唯一条件是，被选中的 $2$ 元子集两两相交。

将 $2$ 元子集看作 $K_5$ 的边。两两相交的边集要么所有边都经过同一个公共顶点，要么是一个三角形。这样的边族数为：空族（ $1$ 个）、三角形（ $\binom{5}{3} = 10$ 个）、以及一个星形中的非空边族， $5(2^4 - 1) - 10 = 65$ 个（减去被两个端点都计数到的 $10$ 条单边）。总共是 $1 + 10 + 65 = 76$ 个集合族，因此总数为 $5 + 76 = 81$ 。

The $32$ subsets split into $16$ complementary pairs $\{X, X^{\mathsf{c}}\},$ and no collection can contain both members of a pair (they are disjoint). A collection of $16$ pairwise-intersecting subsets must therefore contain exactly one member of every pair; in particular it contains $\{1,2,3,4,5\}$ and not $\emptyset.$

If some singleton $\{x\}$ is chosen, every member must meet $\{x\},$ i.e. contain $x.$ Exactly one set in each complementary pair contains $x,$ so the collection must be exactly the $16$ subsets containing $x:$ this gives $5$ collections. Otherwise no singleton is chosen, so all five $4$ -element sets are in the collection. Any two $3$ -element subsets of a $5$ -element set intersect, a $4$ -element set is disjoint only from its complement, and a chosen $2$ -element set and a chosen $3$ -element set are disjoint only if they are complements, which cannot both be chosen. So the only remaining condition is that the chosen $2$ -element sets pairwise intersect.

Viewing $2$ -element sets as edges of $K_5,$ a pairwise-intersecting collection of edges either has all edges through one common vertex or is a triangle. The number of such edge families is: the empty family ( $1$ ), triangles ( $\binom{5}{3} = 10$ ), and nonempty families within a star, $5(2^4 - 1) - 10 = 65$ (subtracting the $10$ single edges counted at both endpoints). That is $1 + 10 + 65 = 76$ collections, for a total of $5 + 76 = 81.$

12.

在 $\triangle ABC$ 中，边长 $AB = 13$ 、 $BC = 14$ 、 $CA = 15$ ，令 $M$ 为 $\overline{BC}$ 的中点。令 $P$ 为 $\triangle ABC$ 外接圆上的一点，使得 $M$ 在 $\overline{AP}$ 上。存在唯一一点 $Q$ 在线段 $\overline{AM}$ 上，使得 $\angle PBQ = \angle PCQ$ 。则 $AQ$ 可写为 $\frac{m}{\sqrt{n}}$ ，其中 $m$ 和 $n$ 是互质的正整数。求 $m + n$ 。

In $\triangle ABC$ with side lengths $AB = 13,$ $BC = 14,$ and $CA = 15,$ let $M$ be the midpoint of $\overline{BC}.$ Let $P$ be the point on the circumcircle of $\triangle ABC$ such that $M$ is on $\overline{AP}.$ There exists a unique point $Q$ on segment $\overline{AM}$ such that $\angle PBQ = \angle PCQ.$ Then $AQ$ can be written as $\frac{m}{\sqrt{n}},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

答案

知识点：坐标几何圆幂向量

难度评级：3160

小提示：

使用坐标 $B = (0, 0)$ 、 $C = (14, 0)$ 、 $A = (5, 12)$ ；由点 $M$ 的幂得 $MA \cdot MP = MB \cdot MC = 49$

Use coordinates $B = (0, 0),$ $C = (14, 0),$ $A = (5, 12);$ power of the point $M$ gives $MA \cdot MP = MB \cdot MC = 49$

大提示：

用叉积和点积表示 $\tan\angle PBQ$ 与 $\tan\angle PCQ$ 并令它们相等；两个叉积成比例，剩下关于 $Q$ 的线性方程

Equate $\tan\angle PBQ$ and $\tan\angle PCQ$ using cross and dot products; the two cross products are proportional, leaving an equation linear in $Q$

解答：

取 $B = (0, 0)$ 、 $C = (14, 0)$ 、 $A = (5, 12)$ ，则 $M = (7, 0)$ ，并且 $AM = \sqrt{4 + 144} = 2\sqrt{37}$ 。由点 $M$ 关于外接圆的幂， $MA \cdot MP = MB \cdot MC = 49$ ，所以 $MP = \frac{49}{2\sqrt{37}}$ 。从 $A \to M$ 的方向继续延长这段长度，得到 $P = \left(\frac{567}{74}, -\frac{147}{37}\right)$ 。向量 $\overrightarrow{BP}$ 的方向与 $(27, -14)$ 成比例，向量 $\overrightarrow{CP}$ 的方向与 $-(67, 42)$ 成比例。

令 $Q = (5 + 2t,\ 12 - 12t)$ ，其中 $t \in (0, 1)$ ，于是 $AQ = t \cdot AM$ 。用 $\tan\theta = \frac{|u \times v|}{u \cdot v}$ 表示两条射线夹角的正切，得 $\begin{gathered} \tan\angle PBQ = \frac{394 - 296t}{222t - 33}, \\ \tan\angle PCQ = \frac{1182 - 888t}{370t + 99} \end{gathered}\text{，}$ 第二个分子恰好是 $3(394 - 296t)$ 。令两个正切相等，约去这个公共因子，留下 $370t + 99 = 3(222t - 33)$ ，所以 $296t = 198$ ， $t = \frac{99}{148}$ 。

因而 $AQ = \frac{99}{148} \cdot 2\sqrt{37}$ $= \frac{99}{148}\sqrt{148}$ $= \frac{99}{\sqrt{148}}$ ，由于 $\gcd(99, 148) = 1$ ，答案是 $99 + 148 = 247$ 。

Place $B = (0, 0),$ $C = (14, 0),$ $A = (5, 12),$ so $M = (7, 0)$ and $AM = \sqrt{4 + 144} = 2\sqrt{37}.$ By power of the point $M$ in the circumcircle, $MA \cdot MP = MB \cdot MC = 49,$ so $MP = \frac{49}{2\sqrt{37}}$ and extending $A \to M$ by that length gives $P = \left(\frac{567}{74}, -\frac{147}{37}\right).$ The direction of $\overrightarrow{BP}$ is proportional to $(27, -14),$ and the direction of $\overrightarrow{CP}$ is proportional to $-(67, 42).$

Write $Q = (5 + 2t,\ 12 - 12t)$ for $t \in (0, 1),$ so that $AQ = t \cdot AM.$ Using $\tan\theta = \frac{|u \times v|}{u \cdot v}$ for the angle between rays, $\begin{gathered} \tan\angle PBQ = \frac{394 - 296t}{222t - 33}, \\ \tan\angle PCQ = \frac{1182 - 888t}{370t + 99}, \end{gathered}$ and the second numerator is exactly $3(394 - 296t).$ Setting the two tangents equal cancels this common factor and leaves $370t + 99 = 3(222t - 33),$ so $296t = 198$ and $t = \frac{99}{148}.$

Then $AQ = \frac{99}{148} \cdot 2\sqrt{37}$ $= \frac{99}{148}\sqrt{148}$ $= \frac{99}{\sqrt{148}},$ and since $\gcd(99, 148) = 1,$ the answer is $99 + 148 = 247.$

13.

设 $A$ 为锐角，且 $\tan A = 2 \cos A$ 。求正整数 $n$ 的个数，其中这个数不超过 $1000$ ，且 $\sec^n A + \tan^n A$ 是个位数字为 $9$ 的正整数。

Let $A$ be an acute angle such that $\tan A = 2 \cos A.$ Find the number of positive integers $n$ less than or equal to $1000$ such that $\sec^n A + \tan^n A$ is a positive integer whose units digit is $9.$

答案

知识点：三角恒等式递推个位数字

难度评级：3060

小提示：

令 $s = \sec A$ 、 $t = \tan A$ ，条件给出 $st = 2$ ，且恒有 $s^2 - t^2 = 1$ ，所以 $s^2 + t^2 = \sqrt{17}$

With $s = \sec A$ and $t = \tan A,$ the condition says $st = 2,$ and always $s^2 - t^2 = 1,$ so $s^2 + t^2 = \sqrt{17}$

大提示：

$s^n + t^n$ 只有在 $4$ 整除 $n$ 时才是整数； $x_j = s^{4j} + t^{4j}$ 满足 $x_{j+1} = 9x_j - 16x_{j-1}$ ；再追踪个位数字

$s^n + t^n$ is an integer only when $4$ divides $n,$ and $x_j = s^{4j} + t^{4j}$ satisfies $x_{j+1} = 9x_j - 16x_{j-1};$ track the units digits

解答：

令 $s = \sec A$ 、 $t = \tan A$ 。条件 $\tan A = 2\cos A$ 等价于 $\tan A \sec A = 2$ ，即 $st = 2$ ，并且恒有 $s^2 - t^2 = 1$ 。于是 $(s^2 + t^2)^2$ $= (s^2 - t^2)^2 + 4s^2t^2$ $= 17$ ，所以 $u = s^2$ 与 $v = t^2$ 满足 $u + v = \sqrt{17}$ 、 $uv = 4$ 。和 $w_m = u^m + v^m$ 满足递推 $w_{m+1} = \sqrt{17}\,w_m - 4w_{m-1}$ ，且 $w_0 = 2$ 、 $w_1 = \sqrt{17}$ ；归纳可知，当 $m$ 为偶数时， $w_m$ 是正整数；当 $m$ 为奇数时，它是 $\sqrt{17}$ 的整数倍。

对偶数 $n = 2m$ 有 $s^n + t^n = w_m$ ，它是整数当且仅当 $m$ 为偶数，即 $4$ 整除 $n$ 。对奇数 $n$ ， $(s^n + t^n)^2$ $= w_n + 2 (st)^n$ $= w_n + 2^{n+1}$ 是无理数，所以 $s^n + t^n$ 不是整数。因此写 $n = 4j$ ，并令 $x_j = w_{2j}$ 。由于 $u^2 + v^2 = 9$ 且 $u^2 v^2 = 16$ ，整数 $x_j$ 满足 $\begin{gathered} x_{j+1} = 9x_j - 16x_{j-1}, \\ x_0 = 2, \\ x_1 = 9 \end{gathered}\text{，}$ 得到 $9, 49, 297, 1889, \ldots$ ，它们的个位数字以周期三重复： $9, 9, 7$ 。个位数字为 $7$ 当且仅当 $3$ 整除 $j$ ，否则为 $9$ 。

合格的 $n \le 1000$ 是 $n = 4j$ ，其中 $1 \le j \le 250$ 且 $j$ 不是 $3$ 的倍数：共有 $250 - 83 = 167$ 个。

Let $s = \sec A$ and $t = \tan A.$ The hypothesis $\tan A = 2\cos A$ says $\tan A \sec A = 2,$ i.e. $st = 2,$ and always $s^2 - t^2 = 1.$ Then $(s^2 + t^2)^2$ $= (s^2 - t^2)^2 + 4s^2t^2$ $= 17,$ so $u = s^2$ and $v = t^2$ satisfy $u + v = \sqrt{17},$ $uv = 4.$ The sums $w_m = u^m + v^m$ obey $w_{m+1} = \sqrt{17}\,w_m - 4w_{m-1}$ with $w_0 = 2,$ $w_1 = \sqrt{17};$ by induction, when $m$ is even, $w_m$ is a positive integer, and when $m$ is odd, it is an integer times $\sqrt{17}.$

For even $n = 2m,$ $s^n + t^n = w_m,$ an integer exactly when $m$ is even, i.e. $4$ divides $n.$ For odd $n,$ $(s^n + t^n)^2$ $= w_n + 2 (st)^n$ $= w_n + 2^{n+1}$ is irrational, so $s^n + t^n$ is not an integer. Thus write $n = 4j$ and $x_j = w_{2j}.$ Since $u^2 + v^2 = 9$ and $u^2 v^2 = 16,$ the integers $x_j$ satisfy $\begin{gathered} x_{j+1} = 9x_j - 16x_{j-1}, \\ x_0 = 2, \\ x_1 = 9, \end{gathered}$ giving $9, 49, 297, 1889, \ldots$ whose units digits repeat with period three: $9, 9, 7.$ The units digit is $7$ when $3$ divides $j$ and $9$ otherwise.

The valid $n \le 1000$ are $n = 4j$ with $1 \le j \le 250$ and $j$ not divisible by $3:$ there are $250 - 83 = 167$ of them.

14.

一个立方体形容器有顶点 $A$ 、 $B$ 、 $C$ 、 $D$ ，其中 $\overline{AB}$ 和 $\overline{CD}$ 是立方体的平行棱， $\overline{AC}$ 和 $\overline{BD}$ 是立方体面的对角线，如图所示。把立方体的顶点 $A$ 放在水平平面 $\mathcal{P}$ 上，使得矩形 $ABDC$ 所在平面垂直于 $\mathcal{P}$ ，顶点 $B$ 的高度为 $2$ 米（相对于 $\mathcal{P}$ ），顶点 $C$ 的高度为 $8$ 米（相对于 $\mathcal{P}$ ），顶点 $D$ 的高度为 $10$ 米（相对于 $\mathcal{P}$ ）。立方体中装有水，水面平行于 $\mathcal{P}$ ，且高度为 $7$ 米（相对于 $\mathcal{P}$ ）。水的体积为 $\frac{m}{n}$ 立方米，其中 $m$ 和 $n$ 是互质的正整数。求 $m + n$ 。

A cube-shaped container has vertices $A,$ $B,$ $C,$ and $D,$ where $\overline{AB}$ and $\overline{CD}$ are parallel edges of the cube, and $\overline{AC}$ and $\overline{BD}$ are diagonals of faces of the cube, as shown. Vertex $A$ of the cube is set on a horizontal plane $\mathcal{P}$ so that the plane of the rectangle $ABDC$ is perpendicular to $\mathcal{P},$ vertex $B$ is $2$ meters above $\mathcal{P},$ vertex $C$ is $8$ meters above $\mathcal{P},$ and vertex $D$ is $10$ meters above $\mathcal{P}.$ The cube contains water whose surface is parallel to $\mathcal{P}$ at a height of $7$ meters above $\mathcal{P}.$ The volume of water is $\frac{m}{n}$ cubic meters, where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

答案

知识点：正方体体积坐标几何微积分

难度评级：3270

小提示：

给立方体设坐标 $[0, s]^3$ ； $B$ 和 $C$ 的高度以及垂直条件会迫使 $s = 6$ ，竖直方向为 $\frac{1}{3}(1, 2, 2)$

Give the cube coordinates $[0, s]^3;$ the heights of $B$ and $C$ together with the perpendicularity condition force $s = 6$ and vertical direction $\frac{1}{3}(1, 2, 2)$

大提示：

水是 $[0, 6]^3$ 中满足 $x + 2y + 2z \le 21$ 的部分；对一个坐标积分横截面积

The water is the part of $[0, 6]^3$ with $x + 2y + 2z \le 21;$ integrate the cross-sectional area over one coordinate

解答：

为立方体建立坐标，使 $A$ 为原点，棱沿坐标轴方向，棱长为 $s$ ：则 $B = (s, 0, 0)$ 、 $C = (0, s, s)$ 、 $D = (s, s, s)$ 符合题意（ $\overline{AB} \parallel \overline{CD}$ 是棱， $\overline{AC}$ 、 $\overline{BD}$ 是面的对角线）。离 $\mathcal{P}$ 的高度是某个线性函数 $h(x, y, z) = u_1 x + u_2 y + u_3 z$ ，其中 $u$ 是单位向量。矩形 $ABDC$ 所在平面的法向量方向为 $(0, 1, -1)$ ，而它垂直于 $\mathcal{P}$ 意味着竖直方向 $u$ 位于该平面内，所以 $u_2 = u_3$ 。由 $B$ 和 $C$ 的高度， $s u_1 = 2$ 且 $s(u_2 + u_3) = 8$ ，所以 $su_2 = su_3 = 4$ ，再由 $|u| = 1$ ，得 $s^2 = 2^2 + 4^2 + 4^2 = 36$ 。因此 $s = 6$ ， $u = \frac{1}{3}(1, 2, 2)$ （也确实有 $h(D) = 10$ ）。

水所在区域是 $[0, 6]^3$ 中满足 $h \le 7$ 的部分，也就是 $x + 2y + 2z \le 21$ 。固定 $x = a$ 时，截面为 $\{(y, z) \in [0,6]^2 : y + z \le \tfrac{21 - a}{2}\}$ ，由于 $\frac{21 - a}{2}$ 介于 $6$ 和 $12$ 之间，截面积为 $36 - \frac{1}{2}\left(12 - \frac{21 - a}{2}\right)^2$ $= 36 - \frac{(3 + a)^2}{8}$ 。

积分得到 $\begin{gathered} V = \int_0^6 \left(36 - \frac{(3 + a)^2}{8}\right) da \\ = 216 - \frac{9^3 - 3^3}{24} \\ = 216 - \frac{702}{24} \\ = \frac{747}{4} \end{gathered}\text{，}$ 所以 $m + n = 747 + 4 = 751$ 。

Give the cube coordinates so that $A$ is the origin, the edges lie along the axes, and the edge length is $s:$ then $B = (s, 0, 0),$ $C = (0, s, s),$ $D = (s, s, s)$ satisfy the description ( $\overline{AB} \parallel \overline{CD}$ are edges and $\overline{AC},$ $\overline{BD}$ are face diagonals). Height above $\mathcal{P}$ is a linear function $h(x, y, z) = u_1 x + u_2 y + u_3 z$ for some unit vector $u.$ The plane of rectangle $ABDC$ has normal direction $(0, 1, -1),$ and perpendicularity to $\mathcal{P}$ means the vertical direction $u$ lies in that plane, so $u_2 = u_3.$ The heights of $B$ and $C$ give $s u_1 = 2$ and $s(u_2 + u_3) = 8,$ so $su_2 = su_3 = 4,$ and $|u| = 1$ forces $s^2 = 2^2 + 4^2 + 4^2 = 36.$ Thus $s = 6$ and $u = \frac{1}{3}(1, 2, 2)$ (and indeed $h(D) = 10$ ).

The water is the region of $[0, 6]^3$ where $h \le 7,$ i.e. $x + 2y + 2z \le 21.$ For fixed $x = a,$ the slice is $\{(y, z) \in [0,6]^2 : y + z \le \tfrac{21 - a}{2}\},$ and since $\frac{21 - a}{2}$ lies between $6$ and $12,$ its area is $36 - \frac{1}{2}\left(12 - \frac{21 - a}{2}\right)^2$ $= 36 - \frac{(3 + a)^2}{8}.$

Integrating, $\begin{gathered} V = \int_0^6 \left(36 - \frac{(3 + a)^2}{8}\right) da \\ = 216 - \frac{9^3 - 3^3}{24} \\ = 216 - \frac{702}{24} \\ = \frac{747}{4}, \end{gathered}$ so $m + n = 747 + 4 = 751.$

15.

对每个正整数 $n$ ，令 $a_n$ 为 $23$ 的最小正整数倍数，并满足 $a_n \equiv 1 \pmod{2^n}$ 。求正整数 $n$ 的个数，其中这个数不超过 $1000$ ，且满足 $a_n = a_{n+1}$ 。

For each positive integer $n$ let $a_n$ be the least positive integer multiple of $23$ such that $a_n \equiv 1 \pmod{2^n}.$ Find the number of positive integers $n$ less than or equal to $1000$ that satisfy $a_n = a_{n+1}.$

答案

知识点：模运算进制乘法阶

难度评级：3370

小提示：

$a_n = 23 b_n$ ，其中 $b_n$ 是 $23$ 在模 $2^n$ 下的逆元；于是 $a_n = a_{n+1}$ 当且仅当权为 $2^n$ 的二进制位在 $b_{n+1}$ 中是 $0$

$a_n = 23 b_n$ where $b_n$ is the inverse of $23$ mod $2^n;$ then $a_n = a_{n+1}$ exactly when the binary digit of weight $2^n$ in $b_{n+1}$ is $0$

大提示：

因为 $23 \cdot 89 = 2^{11} - 1$ ，这些二进制位以 $11$ 为周期重复；找出 $n$ 模 $11$ 时哪些四个余数会给出零位

Since $23 \cdot 89 = 2^{11} - 1,$ those binary digits repeat with period $11;$ find which four residues of $n$ mod $11$ give a zero digit

解答：

写 $a_n = 23 b_n$ ，其中 $b_n$ 是区间 $[1, 2^n]$ 中满足 $23 b_n \equiv 1 \pmod{2^n}$ 的唯一整数，也就是 $23$ 在模 $2^n$ 下的逆元。对模 $2^n$ 约化可知 $b_{n+1} \in \{b_n,\ b_n + 2^n\}$ ，所以 $a_n = a_{n+1}$ 当且仅当 $b_{n+1} = b_n$ ，也就是当且仅当权为 $2^n$ 的二进制位在 $b_{n+1}$ 中是 $0$ 。

因为 $23 \cdot 89 = 2047 = 2^{11} - 1$ ，令 $T_k = 1 + 2^{11} + 2^{22}$ ${}+ \cdots + 2^{11(k-1)}$ ，则 $23 \cdot 89\,T_k = 2^{11k} - 1$ ，所以 $\begin{gathered} 23\left(2^{11k} - 89\,T_k\right) \\ \equiv 1 \pmod{2^{11k}} \end{gathered}\text{，}$ 且所有 $b_n$ （其中 $n \le 11k$ ）都是 $2^{11k} - 89\,T_k$ 对模 $2^n$ 的约化。在二进制表示中， $89 = 1011001_2$ 的第 $0, 3, 4, 6$ 位为一；每个 $11$ 位的 $89\,T_k$ 区块都具有这一模式。由于 $89\,T_k$ 是奇数， $2^{11k} - 89\,T_k$ $= \bigl(2^{11k} - 1 - 89\,T_k\bigr) + 1$ 会保留第 $0$ 位为 $1$ ，并把第 $1$ 位到第 $11k - 1$ 位全部取反。

因此对 $n \ge 1$ ，权为 $2^n$ 的二进制位为 $0$ ，当且仅当 $n \equiv 0, 3, 4, 6 \pmod{11}$ 。在 $1 \le n \le 1000 = 90 \cdot 11 + 10$ 中，余数 $0$ 出现 $90$ 次，余数 $3$ 、 $4$ 、 $6$ 各出现 $91$ 次，总数为 $90 + 3 \cdot 91 = 363$ 。

Write $a_n = 23 b_n,$ where $b_n$ is the unique integer in $[1, 2^n]$ with $23 b_n \equiv 1 \pmod{2^n},$ i.e. the inverse of $23$ mod $2^n.$ Reducing mod $2^n$ shows $b_{n+1} \in \{b_n,\ b_n + 2^n\},$ so $a_n = a_{n+1}$ exactly when $b_{n+1} = b_n,$ which happens exactly when the binary digit of weight $2^n$ in $b_{n+1}$ is $0.$

Since $23 \cdot 89 = 2047 = 2^{11} - 1,$ setting $T_k = 1 + 2^{11} + 2^{22}$ ${}+ \cdots + 2^{11(k-1)}$ gives $23 \cdot 89\,T_k = 2^{11k} - 1,$ so $\begin{gathered} 23\left(2^{11k} - 89\,T_k\right) \\ \equiv 1 \pmod{2^{11k}}, \end{gathered}$ and every $b_n$ with $n \le 11k$ is the reduction of $2^{11k} - 89\,T_k$ mod $2^n.$ In binary, $89 = 1011001_2$ occupies positions $0, 3, 4, 6$ of each $11$ -bit block of $89\,T_k.$ Since $89\,T_k$ is odd, $2^{11k} - 89\,T_k$ $= \bigl(2^{11k} - 1 - 89\,T_k\bigr) + 1$ keeps digit $0$ equal to $1$ and complements every digit in positions $1$ through $11k - 1.$

So for $n \ge 1,$ the digit of weight $2^n$ is $0$ exactly when $n \equiv 0, 3, 4, 6 \pmod{11}.$ Among $1 \le n \le 1000 = 90 \cdot 11 + 10,$ the residue $0$ occurs $90$ times and the residues $3,$ $4,$ $6$ occur $91$ times each, for a total of $90 + 3 \cdot 91 = 363.$