2004 AIME I 真题与在线限时测验

计时

3:00:00

1.

正整数 $n$ 的各位数字从左到右读时，是四个连续整数按递减顺序排列。 $n$ 除以 $37$ 时，所有可能余数的和是多少？

The digits of a positive integer $n$ are four consecutive integers in decreasing order when read from left to right. What is the sum of the possible remainders when $n$ is divided by $37?$

答案

答案：217

知识点：位值模运算

难度评级：1890

小提示：

把这个数写成 $1111a - 123$ ，其中 $a$ 是首位数字，且 $a = 3, 4, \ldots, 9$

Write the number as $1111a - 123,$ where $a$ is its leading digit and $a = 3, 4, \ldots, 9$

大提示：

因为 $1111 = 30 \cdot 37 + 1$ ，所以 $n$ 的余数是 $a + 25$ ，这个数已经小于 $37$

Since $1111 = 30 \cdot 37 + 1,$ the remainder of $n$ is $a + 25,$ which is already less than $37$

解答：

若首位数字是 $a$ ，则四个数字为 $a$ 、 $a - 1$ 、 $a - 2$ 、 $a - 3$ ，其中 $a = 3, 4, \ldots, 9$ ，所以 $\begin{aligned} n &= 1000a + 100(a-1) \\ &\quad {}+ 10(a-2) + (a-3) \\ &= 1111a - 123 \end{aligned}\text{。}$

因为 $1111 = 30 \cdot 37 + 1$ 且 $123 = 3 \cdot 37 + 12$ 可得 $n \equiv a - 12 \equiv a + 25 \pmod{37}$ 。当 $a = 3, \ldots, 9$ 时，数值 $a + 25$ 依次为 $28, 29, \ldots, 34$ 都已经小于 $37$ ，因此它们正是七个可能余数。

它们的和是 $28 + 29 + \cdots + 34$ $= 7 \cdot 31 = 217$ 。

If the leading digit is $a,$ the digits are $a,$ $a - 1,$ $a - 2,$ $a - 3$ with $a = 3, 4, \ldots, 9,$ so $\begin{aligned} n &= 1000a + 100(a-1) \\ &\quad {}+ 10(a-2) + (a-3) \\ &= 1111a - 123. \end{aligned}$

Since $1111 = 30 \cdot 37 + 1$ and $123 = 3 \cdot 37 + 12,$ we get $n \equiv a - 12 \equiv a + 25 \pmod{37}.$ For $a = 3, \ldots, 9$ the values $a + 25$ run through $28, 29, \ldots, 34,$ each already less than $37,$ so these are exactly the seven possible remainders.

Their sum is $28 + 29 + \cdots + 34$ $= 7 \cdot 31 = 217.$

2.

集合 $\mathcal{A}$ 由 $m$ 个连续整数组成，它们的和为 $2m$ ，集合 $\mathcal{B}$ 由 $2m$ 个连续整数组成，它们的和为 $m$ 。 $\mathcal{A}$ 中最大元素与 $\mathcal{B}$ 中最大元素之差的绝对值为 $99$ 。求 $m$ 。

Set $\mathcal{A}$ consists of $m$ consecutive integers whose sum is $2m,$ and set $\mathcal{B}$ consists of $2m$ consecutive integers whose sum is $m.$ The absolute value of the difference between the greatest element of $\mathcal{A}$ and the greatest element of $\mathcal{B}$ is $99.$ Find $m.$

答案

答案：201

知识点：等差数列平均数绝对值

难度评级：2110

小提示：

由 $m$ 个整数组成的 $\mathcal{A}$ 的平均值为 $2$ ，由 $2m$ 个整数组成的 $\mathcal{B}$ 的平均值为 $\frac{1}{2}$

The $m$ integers in $\mathcal{A}$ have mean $2,$ and the $2m$ integers in $\mathcal{B}$ have mean $\frac{1}{2}$

大提示：

最大元素分别是 $2 + \frac{m-1}{2}$ 和 $m$ 。令它们差的绝对值等于 $99$ 。

The greatest elements are $2 + \frac{m-1}{2}$ and $m.$ Set the absolute difference equal to $99.$

解答：

这 $m$ 个属于 $\mathcal{A}$ 的整数平均值是 $\frac{2m}{m} = 2$ ，所以它们以 $2$ 为中心。连续整数的平均值是整数时，项数必须为奇数，因此 $m$ 为奇数， $\mathcal{A}$ 中最大元素为 $2 + \frac{m-1}{2}$ 。这 $2m$ 个属于 $\mathcal{B}$ 的整数平均值为 $\frac{1}{2}$ ，所以它们是 $1 - m, \ldots, 0, 1, \ldots, m$ ，最大元素为 $m$ 。

条件给出 $\begin{aligned} \left| 2 + \frac{m-1}{2} - m \right| &= \left| \frac{3 - m}{2} \right| \\ &= 99 \end{aligned}\text{，}$ 所以 $|3 - m| = 198$ ，得 $m = 201$ （因为 $m \gt 0$ ）。确实 $201$ 是奇数，符合要求，因此 $m = 201$ 。

The $m$ integers of $\mathcal{A}$ have mean $\frac{2m}{m} = 2,$ so they are centered at $2;$ since the mean of consecutive integers is an integer only when there are an odd number of them, $m$ is odd and the greatest element of $\mathcal{A}$ is $2 + \frac{m-1}{2}.$ The $2m$ integers of $\mathcal{B}$ have mean $\frac{1}{2},$ so they are $1 - m, \ldots, 0, 1, \ldots, m,$ with greatest element $m.$

The condition is $\begin{aligned} \left| 2 + \frac{m-1}{2} - m \right| &= \left| \frac{3 - m}{2} \right| \\ &= 99, \end{aligned}$ so $|3 - m| = 198,$ giving $m = 201$ (since $m \gt 0$ ). Indeed $201$ is odd, as required, so $m = 201.$

3.

一个凸多面体 $P$ 有 $26$ 个顶点、 $60$ 条边和 $36$ 个面，其中 $24$ 个是三角形， $12$ 个是四边形。空间对角线是连接两个不相邻且不属于同一个面的顶点的线段。 $P$ 有多少条空间对角线？

A convex polyhedron $P$ has $26$ vertices, $60$ edges, and $36$ faces, $24$ of which are triangular, and $12$ of which are quadrilaterals. A space diagonal is a line segment connecting two non-adjacent vertices that do not belong to the same face. How many space diagonals does $P$ have?

答案

答案：241

知识点：多面体对角线补集计数

难度评级：2070

小提示：

任意一对顶点连成的线段，要么是一条边，要么是一个面的对角线，要么是一条空间对角线

Every pair of vertices spans an edge, a face diagonal, or a space diagonal

大提示：

顶点对共有 $\binom{26}{2}$ 个；三角形没有对角线，每个四边形面有 $2$ 条对角线

There are $\binom{26}{2}$ pairs in all; triangles have no diagonals and each quadrilateral face has $2$

解答：

任意一对顶点恰好决定三类对象之一：一条边、一个面的对角线，或一条空间对角线。顶点对总数为 $\binom{26}{2} = 325$ 。

其中 $60$ 对是边。 $24$ 个三角形面没有对角线，而 $12$ 个四边形面各有 $2$ 条对角线，共 $24$ 条面对角线（由于多面体是凸的，没有两个面会共享同一条对角线）。

空间对角线的条数为 $325 - 60 - 24 = 241$ 。

Every pair of vertices determines exactly one of three things: an edge, a diagonal of a face, or a space diagonal. There are $\binom{26}{2} = 325$ pairs of vertices in all.

Of these, $60$ are edges. The $24$ triangular faces have no diagonals, while each of the $12$ quadrilateral faces has $2,$ for $24$ face diagonals (no two faces share a diagonal, since the polyhedron is convex).

The number of space diagonals is $325 - 60 - 24 = 241.$

4.

一个正方形的边长为 $2$ 。集合 $\mathcal{S}$ 是所有长度为 $2$ 、且端点分别在该正方形相邻两边上的线段的集合。集合 $\mathcal{S}$ 中线段的中点围成一个区域，其面积四舍五入到百分位为 $k$ 。求 $100k$ 。

A square has sides of length $2.$ Set $\mathcal{S}$ is the set of all line segments that have length $2$ and whose endpoints are on adjacent sides of the square. The midpoints of the line segments in set $\mathcal{S}$ enclose a region whose area to the nearest hundredth is $k.$ Find $100k.$

答案

答案：86

知识点：中线（几何）直角三角形圆面积

难度评级：2270

小提示：

放置端点的两条相邻边交于一个顶点，而这条线段是一个直角三角形的斜边，两条直角边沿着这两条边

The two adjacent sides holding the endpoints meet at a corner, and the segment is the hypotenuse of a right triangle with legs along those sides

大提示：

直角三角形斜边上的中线等于斜边的一半，所以每个中点到最近顶点的距离都是 $1$

The median to the hypotenuse of a right triangle is half the hypotenuse, so every midpoint is at distance $1$ from the nearest corner

解答：

设线段 $\overline{PQ}$ 属于 $\mathcal{S}$ ，其端点在交于顶点 $A$ 的两条边上，且 $M$ 是其中点。三角形 $PAQ$ 在 $A$ 处为直角，斜边 $PQ = 2$ ，而直角三角形斜边上的中线等于斜边的一半，因此 $AM = 1$ 。反过来，从某个顶点出发、位于两条相邻边之间且距离该顶点为 $1$ 的每个点都是这样的中点。所以这些中点形成四段半径为 $1$ 、以正方形顶点为圆心的四分之一圆弧。

这些圆弧围成的区域是从正方形中去掉四个四分之一圆盘，面积为 $4 - 4 \cdot \frac{\pi}{4} = 4 - \pi \approx 0.86\text{。}$ 因此 $100k = 86$ 。

Let a segment $\overline{PQ}$ in $\mathcal{S}$ have endpoints on two sides meeting at corner $A,$ and let $M$ be its midpoint. Triangle $PAQ$ is right-angled at $A$ with hypotenuse $PQ = 2,$ and the median to the hypotenuse of a right triangle is half the hypotenuse, so $AM = 1.$ Conversely every point at distance $1$ from a corner (between the two adjacent sides) is such a midpoint, so the midpoints form four quarter-circle arcs of radius $1$ centered at the corners of the square.

The region these arcs enclose is the square with the four quarter-disks removed, of area $4 - 4 \cdot \frac{\pi}{4} = 4 - \pi \approx 0.86.$ Therefore $100k = 86.$

5.

阿尔法和贝塔都参加了一个为期两天的解题竞赛。第二天结束时，每人尝试的问题总分都是 $500$ 分。阿尔法第一天得到 $160$ 分，尝试的问题总分为 $300$ 分；第二天得到 $140$ 分，尝试的问题总分为 $200$ 分。贝塔第一天尝试的总分不是 $300$ 分，并且两天每天都得到正整数分数；贝塔每天的成功率（得分除以尝试分数）都低于阿尔法当天的成功率。阿尔法两天总成功率为 $\frac{300}{500} = \frac{3}{5}$ 。贝塔可能达到的最大两天总成功率为 $\frac{m}{n}$ ，其中 $m$ 和 $n$ 是互质正整数。求 $m + n$ ？

Alpha and Beta both took part in a two-day problem-solving competition. At the end of the second day, each had attempted questions worth a total of $500$ points. Alpha scored $160$ points out of $300$ points attempted on the first day, and scored $140$ points out of $200$ points attempted on the second day. Beta, who did not attempt $300$ points on the first day, had a positive integer score on each of the two days, and Beta’s daily success ratio (points scored divided by points attempted) on each day was less than Alpha’s on that day. Alpha’s two-day success ratio was $\frac{300}{500} = \frac{3}{5}.$ The largest possible two-day success ratio that Beta could have achieved is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. What is $m + n?$

答案

答案：849

知识点：比与比例不等式极端原理

难度评级：2480

小提示：

贝塔两天每天的成功率都低于 $\frac{7}{10}$ ，所以贝塔的总得分小于 $\frac{7}{10}$ 乘以 $500$

Both of Beta’s daily ratios are below $\frac{7}{10},$ so Beta’s total score is less than $\frac{7}{10}$ of $500$

大提示：

说明略低于 $350$ 的上界可以达到：第一天得到 $1$ 分，而尝试的问题总分为 $2$ 分

Show the bound just below $350$ is attainable: try $1$ point out of $2$ attempted on day one

解答：

阿尔法两天的成功率分别为 $\frac{160}{300} = \frac{8}{15}$ 和 $\frac{140}{200} = \frac{7}{10}$ 。因为 $\frac{8}{15} \lt \frac{7}{10}$ ，贝塔每天的得分都小于当天尝试分数的 $\frac{7}{10}$ ，所以贝塔的总得分小于 $\frac{7}{10} \cdot 500 = 350$ ，因而至多为 $349$ 。

总分 $349$ 可以达到：贝塔第一天可得 $1$ 分，尝试的问题总分为 $2$ 分（且 $\frac{1}{2} \lt \frac{8}{15}$ ）；第二天可得 $348$ 分，尝试的问题总分为 $498$ 分（且 $\frac{348}{498} \lt \frac{7}{10}$ ，因为 $3480 \lt 3486$ ）。

因此贝塔可能的最大两天总成功率是 $\frac{349}{500}$ ，由于 $349$ 是质数，这已经是最简分数，所以 $m + n = 349 + 500 = 849$ 。

Alpha’s daily ratios were $\frac{160}{300} = \frac{8}{15}$ and $\frac{140}{200} = \frac{7}{10}.$ Since $\frac{8}{15} \lt \frac{7}{10},$ Beta’s score was less than $\frac{7}{10}$ of the points attempted on each day, so Beta’s total score was less than $\frac{7}{10} \cdot 500 = 350,$ hence at most $349.$

A total of $349$ is achievable: Beta can score $1$ out of $2$ points attempted on day one (and $\frac{1}{2} \lt \frac{8}{15}$ ) and $348$ out of $498$ on day two (and $\frac{348}{498} \lt \frac{7}{10}$ because $3480 \lt 3486$ ).

So Beta’s largest possible two-day ratio is $\frac{349}{500},$ which is in lowest terms since $349$ is prime, and $m + n = 349 + 500 = 849.$

6.

如果一个整数的十进制表示 $a_1 a_2 a_3 \ldots a_k$ 满足 $a_i \lt a_{i+1}$ （ $i$ 为奇数）和 $a_i \gt a_{i+1}$ （ $i$ 为偶数），则称这个整数为蛇形数。在 $1000$ 到 $9999$ 之间，有多少个四位数字互不相同的蛇形数？

An integer is called snakelike if its decimal representation $a_1 a_2 a_3 \ldots a_k$ satisfies $a_i \lt a_{i+1}$ if $i$ is odd and $a_i \gt a_{i+1}$ if $i$ is even. How many snakelike integers between $1000$ and $9999$ have four distinct digits?

答案

答案：882

知识点：有限制的排列数字分类讨论

难度评级：2510

小提示：

数字满足 $a_1 \lt a_2 \gt a_3 \lt a_4$ 。按 $0$ 是否在四个数字中分情况讨论。

The digits satisfy $a_1 \lt a_2 \gt a_3 \lt a_4.$ Split into cases by whether $0$ is among the four digits.

大提示：

每组四个不同的非零数字恰好给出 $5$ 种蛇形排列；包含 $0$ 时，只有 $3$ 种不会让首位为零

Each set of four distinct nonzero digits gives exactly $5$ snakelike orders; with $0$ included, only $3$ avoid a leading zero

解答：

四位蛇形数满足 $a_1 \lt a_2 \gt a_3 \lt a_4$ 。先数任意四个不同数字 $w \lt x \lt y \lt z$ 排成这种模式的方式。最大数字 $z$ 必须在第 $2$ 位或第 $4$ 位。若 $z$ 在第 $4$ 位，其余三个数字形成 $a_1 \lt a_2 \gt a_3$ ，因此其中最大者在第 $2$ 位，剩下两个可以任意交换： $2$ 种。若 $z$ 在第 $2$ 位，其余三个数字中任意一个可作 $a_1$ ，然后 $a_3 \lt a_4$ 决定其余位置： $3$ 种。因此每组四个数字恰好有 $5$ 种蛇形排列。

若数字中不含 $0$ ，所有 $5$ 种排列都给出有效数字： $\binom{9}{4} \cdot 5 = 630$ 。若数字中含 $0$ ，注意 $0$ 必须在第 $1$ 位或第 $3$ 位（第 $2$ 位和第 $4$ 位都必须大于某个相邻数字），而第 $1$ 位是不允许的。当 $0$ 在第 $3$ 位时，其余三个数字中任意一个可作 $a_4$ ，然后 $a_1 \lt a_2$ 决定其余位置，所以原来的 $5$ 种排列中保留下来的有 $3$ 种： $\binom{9}{3} \cdot 3 = 252$ 。

总数为 $630 + 252 = 882$ 。

A four-digit snakelike number satisfies $a_1 \lt a_2 \gt a_3 \lt a_4.$ First count the arrangements of any four distinct digits $w \lt x \lt y \lt z$ into this pattern. The largest digit $z$ must sit in position $2$ or $4.$ If $z$ is in position $4,$ the other three form $a_1 \lt a_2 \gt a_3,$ so the largest of them takes position $2$ and the remaining two can go in either order: $2$ ways. If $z$ is in position $2,$ any of the other three digits can be $a_1,$ and then $a_3 \lt a_4$ fixes the rest: $3$ ways. So each set of four digits admits exactly $5$ snakelike orders.

If $0$ is not among the digits, all $5$ orders give valid numbers: $\binom{9}{4} \cdot 5 = 630.$ If $0$ is among them, note $0$ must occupy position $1$ or $3$ (positions $2$ and $4$ must exceed a neighbor), and position $1$ is forbidden. With $0$ in position $3,$ any of the other three digits can be $a_4,$ and $a_1 \lt a_2$ fixes the rest, so $3$ of the $5$ orders survive: $\binom{9}{3} \cdot 3 = 252.$

The total is $630 + 252 = 882.$

7.

设 $C$ 为以下乘积展开式中 $x^2$ 的系数： $\begin{aligned} &(1 - x)(1 + 2x)(1 - 3x) \cdots \\ &\quad {}\cdot (1 + 14x)(1 - 15x) \end{aligned}$ 求 $|C|$ 。

Let $C$ be the coefficient of $x^2$ in the expansion of the product $\begin{aligned} &(1 - x)(1 + 2x)(1 - 3x) \cdots \\ &\quad {}\cdot (1 + 14x)(1 - 15x). \end{aligned}$ Find $|C|.$

答案

答案：588

知识点：多项式代数变形前n项平方和

难度评级：2390

小提示：

$x^2$ 的系数是从 $-1, 2, -3, \ldots, 14, -15$ 中取两项相乘后对所有成对选择求和

The $x^2$ coefficient is the sum of the products of pairs from $-1, 2, -3, \ldots, 14, -15$

大提示：

使用 $2\sum_{i \lt j} a_i a_j = \left(\sum a_i\right)^2 - \sum a_i^2$ ，且交错和为 $-8$

Use $2\sum_{i \lt j} a_i a_j = \left(\sum a_i\right)^2 - \sum a_i^2,$ and the alternating sum is $-8$

解答：

将乘积写成 $\prod_{k=1}^{15} (1 + a_k x)$ ，其中 $a_k = (-1)^k k$ 。 $x^2$ 项来自从两个因式中选出 $x$ 项，因此 $C = \sum_{i \lt j} a_i a_j$ ，并且 $C = \frac{\left(\sum a_k\right)^2 - \sum a_k^2}{2}\text{。}$

交错和为 $\begin{aligned} &(-1 + 2) + (-3 + 4) \\ &\quad {}+ \cdots + (-13 + 14) - 15 \\ &= 7 - 15 \\ &= -8 \end{aligned}\text{，}$ 并且 $\begin{aligned} \sum a_k^2 &= 1^2 + 2^2 + \cdots + 15^2 \\ &= \frac{15 \cdot 16 \cdot 31}{6} \\ &= 1240 \end{aligned}\text{。}$

因此 $C = \frac{64 - 1240}{2} = -588$ ，所以 $|C| = 588$ 。

Write the product as $\prod_{k=1}^{15} (1 + a_k x)$ with $a_k = (-1)^k k.$ An $x^2$ term arises by choosing the $x$ -term from two factors, so $C = \sum_{i \lt j} a_i a_j,$ and $C = \frac{\left(\sum a_k\right)^2 - \sum a_k^2}{2}.$

The alternating sum is $\begin{aligned} &(-1 + 2) + (-3 + 4) \\ &\quad {}+ \cdots + (-13 + 14) - 15 \\ &= 7 - 15 \\ &= -8, \end{aligned}$ and $\begin{aligned} \sum a_k^2 &= 1^2 + 2^2 + \cdots + 15^2 \\ &= \frac{15 \cdot 16 \cdot 31}{6} \\ &= 1240. \end{aligned}$

Thus $C = \frac{64 - 1240}{2} = -588,$ so $|C| = 588.$

8.

定义一个正 $n$ 角星为 $n$ 条线段 $\overline{P_1 P_2}$ 、 $\overline{P_2 P_3}$ 、 $\ldots$ 、 $\overline{P_n P_1}$ 的并集，并满足：

• 点 $P_1$ 、 $P_2$ 、 $\ldots$ 、 $P_n$ 共面，且任意三点不共线；

• 每一条这 $n$ 条线段都至少与另一条线段在非端点处相交；

• 在 $P_1$ 、 $P_2$ 、 $\ldots$ 、 $P_n$ 处的所有角都全等；

• 这 $n$ 条线段 $\overline{P_1 P_2}$ 、 $\overline{P_2 P_3}$ 、 $\ldots$ 、 $\overline{P_n P_1}$ 都全等；并且

• 路径 $P_1 P_2 \ldots P_n P_1$ 在每个顶点都以小于 $180^\circ$ 的角逆时针转向。

不存在正 $3$ 角星、正 $4$ 角星或正 $6$ 角星。所有正 $5$ 角星都相似，但有两个不相似的正 $7$ 角星。有多少个不相似的正 $1000$ 角星？

Define a regular $n$ -pointed star to be the union of $n$ line segments $\overline{P_1 P_2},$ $\overline{P_2 P_3},$ $\ldots,$ $\overline{P_n P_1}$ such that

• the points $P_1,$ $P_2,$ $\ldots,$ $P_n$ are coplanar and no three of them are collinear,

• each of the $n$ line segments intersects at least one of the other line segments at a point other than an endpoint,

• all of the angles at $P_1,$ $P_2,$ $\ldots,$ $P_n$ are congruent,

• all of the $n$ line segments $\overline{P_1 P_2},$ $\overline{P_2 P_3},$ $\ldots,$ $\overline{P_n P_1}$ are congruent, and

• the path $P_1 P_2 \ldots P_n P_1$ turns counterclockwise at an angle of less than $180^\circ$ at each vertex.

There are no regular $3$ -pointed, $4$ -pointed, or $6$ -pointed stars. All regular $5$ -pointed stars are similar, but there are two non-similar regular $7$ -pointed stars. How many non-similar regular $1000$ -pointed stars are there?

答案

答案：199

知识点：欧拉函数正多边形配对与分组

难度评级：2710

小提示：

正 $n$ 角星每隔 $d$ 个点连接一次，这些点是圆上的 $n$ 个等距点；其中 $d$ 与 $n$ 互质

A regular $n$ -pointed star joins every $d$ th of $n$ equally spaced points on a circle, where $d$ is relatively prime to $n$

大提示：

排除 $d = 1$ 和 $d = n - 1$ ，它们给出凸多边形，并注意 $d$ 与 $n - d$ 描出相似的星形

Exclude $d = 1$ and $d = n - 1,$ which give a convex polygon, and note that $d$ and $n - d$ trace similar stars

解答：

全等的角和全等的线段迫使正星形的顶点等距地位于同一个圆上，并且按固定步长访问：将 $n$ 个等距点编号为 $0, 1, \ldots, n - 1$ ，每隔 $d$ 个点连接一次。路径恰好访问全部 $n$ 个点的条件是 $\gcd(d, n) = 1$ ；而真正发生交叉（形成星形而非凸多边形）恰好在 $2 \le d \le n - 2$ 时。步长 $d$ 和 $n - d$ 以相反方向描出同一图形，而除此之外不同的步长给出不相似的星形，因为若用伸缩变换匹配圆，就还必须匹配转角。

对于 $n = 1000 = 2^3 \cdot 5^3$ ，这样的 $d$ 满足 $\gcd(d, 1000) = 1$ ，共有 $1000\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{5}\right) = 400$ 个。去掉 $d = 1$ 和 $d = 999$ 后剩下 $398$ 个值，它们按 $\{d, 1000 - d\}$ 成对，所以不相似的正 $1000$ 角星个数是 $\frac{398}{2} = 199$ 。

The congruent angles and congruent segments force the vertices of a regular star to be equally spaced on a circle, visited by taking a constant step: number $n$ equally spaced points $0, 1, \ldots, n - 1$ and connect every $d$ th point. The path visits all $n$ points exactly when $\gcd(d, n) = 1,$ and the segments actually cross (making a star rather than a convex polygon) exactly when $2 \le d \le n - 2.$ Steps $d$ and $n - d$ trace the same figure in opposite directions, while different values otherwise give non-similar stars, since a dilation matching the circles would have to match the turning angles.

For $n = 1000 = 2^3 \cdot 5^3,$ the number of $d$ with $\gcd(d, 1000) = 1$ is $1000\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{5}\right) = 400.$ Removing $d = 1$ and $d = 999$ leaves $398$ values, which pair up as $\{d, 1000 - d\},$ so the number of non-similar regular $1000$ -pointed stars is $\frac{398}{2} = 199.$

9.

设 $ABC$ 是边长为 $3$ 、 $4$ 、 $5$ 的三角形， $DEFG$ 是一个 $6$ 乘 $7$ 的矩形。画一条线段将三角形 $ABC$ 分成一个三角形 $U_1$ 和一个梯形 $V_1$ ，再画另一条线段将矩形 $DEFG$ 分成一个三角形 $U_2$ 和一个梯形 $V_2$ ，使得 $U_1$ 与 $U_2$ 相似，且 $V_1$ 与 $V_2$ 相似。 $U_1$ 面积的最小值可写成 $\frac{m}{n}$ ，其中 $m$ 和 $n$ 是互质正整数。求 $m + n$ 。

Let $ABC$ be a triangle with sides $3,$ $4,$ and $5,$ and $DEFG$ be a $6$ -by- $7$ rectangle. A segment is drawn to divide triangle $ABC$ into a triangle $U_1$ and a trapezoid $V_1,$ and another segment is drawn to divide rectangle $DEFG$ into a triangle $U_2$ and a trapezoid $V_2$ such that $U_1$ is similar to $U_2$ and $V_1$ is similar to $V_2.$ The minimum value of the area of $U_1$ can be written in the form $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

答案

答案：35

知识点：相似面积比分类讨论

难度评级：2990

小提示：

将矩形切成一个三角形和一个梯形时，线段必须从一个顶点连到一条非相邻边，所以 $U_2$ 是直角三角形，且 $U_1 \sim ABC$

Cutting the rectangle into a triangle and a trapezoid requires the segment to join a vertex to a nonadjacent side, so $U_2$ is a right triangle and $U_1 \sim ABC$

大提示：

匹配 $V_1$ 和 $V_2$ 的锐角会迫使 $ABC$ 中的切线平行于长度为 $3$ 的边；两种可能的矩形切法给出底边比 $5:14$ 和 $1:8$

Matching the acute angles of $V_1$ and $V_2$ forces the cut in $ABC$ parallel to the side of length $3;$ the two possible rectangle cuts give base ratios $5:14$ and $1:8$

解答：

一条线段只有从矩形的一个顶点连到一条非相邻边，才能把矩形切成一个三角形和一个梯形，因此 $U_2$ 是一个直角三角形，其两条直角边沿矩形两边，其中一条是完整边（ $6$ 或 $7$ ）。因为 $U_1 \sim U_2$ ， $3$ - $4$ - $5$ 直角三角形 $ABC$ 中的切线也必须产生一个直角三角形，所以它平行于一条直角边，于是 $U_1 \sim ABC$ 。因此 $U_2$ 也是一个 $3$ - $4$ - $5$ 三角形：其直角边为 $6$ 和 $\frac{9}{2}$ （完整边为 $6$ ），或 $7$ 和 $\frac{21}{4}$ （完整边为 $7$ ）；其他方向需要直角边为 $8$ 或 $\frac{28}{3}$ ，放不进矩形。

两种情形下，梯形 $V_2$ 都有两个直角，且切线与较长底边所成锐角的正切为 $\frac{6}{\frac{9}{2}} = \frac{7}{\frac{21}{4}} = \frac{4}{3}$ 。在三角形 $ABC$ 中，平行于长度为 $3$ 的边作切线会使 $V_1$ 中相应锐角的正切为 $\frac{4}{3}$ 可以匹配；而平行于长度为 $4$ 的边会给出正切 $\frac{3}{4}$ ，无法匹配。所以切线平行于长度为 $3$ 的边，且 $V_1$ 的两条平行底边是切出的线段 $s$ 和长度为 $3$ 的边。

梯形相似要求 $s : 3$ 等于 $V_2$ 的底边比，在第一种情形中为 $\frac{7 - \frac{9}{2}}{7} = \frac{5}{14}$ ，第二种情形中为 $\frac{6 - \frac{21}{4}}{6} = \frac{1}{8}$ 。于是 $[U_1] = \left(\frac{s}{3}\right)^2 [ABC]$ ，得到 $\left(\frac{5}{14}\right)^2 \cdot 6 = \frac{75}{98}$ 或 $\left(\frac{1}{8}\right)^2 \cdot 6 = \frac{3}{32}$ 。最小值是 $\frac{3}{32}$ ，所以 $m + n = 3 + 32 = 35$ 。

A segment cuts the rectangle into a triangle and a trapezoid only if it runs from a vertex to a point on a nonadjacent side, so $U_2$ is a right triangle whose legs lie along two sides of the rectangle, one leg being a full side ( $6$ or $7$ ). Since $U_1 \sim U_2,$ the cut in the $3$ - $4$ - $5$ right triangle $ABC$ must also produce a right triangle, so it is parallel to a leg, and then $U_1 \sim ABC.$ Hence $U_2$ is a $3$ - $4$ - $5$ triangle too: its legs are $6$ and $\frac{9}{2}$ (full side $6$ ) or $7$ and $\frac{21}{4}$ (full side $7$ ); the other orientations need legs $8$ or $\frac{28}{3},$ which do not fit.

In both cases the trapezoid $V_2$ has two right angles and an acute angle between the cut and its longer base with tangent $\frac{6}{\frac{9}{2}} = \frac{7}{\frac{21}{4}} = \frac{4}{3}.$ In triangle $ABC,$ a cut parallel to the leg of length $3$ gives $V_1$ an acute angle with tangent $\frac{4}{3},$ matching, while a cut parallel to the leg of length $4$ gives tangent $\frac{3}{4},$ which cannot match. So the cut is parallel to the side of length $3,$ and the parallel bases of $V_1$ are the cut segment $s$ and the side of length $3.$

Similarity of the trapezoids forces $s : 3$ to equal the ratio of the bases of $V_2,$ which is $\frac{7 - \frac{9}{2}}{7} = \frac{5}{14}$ in the first case and $\frac{6 - \frac{21}{4}}{6} = \frac{1}{8}$ in the second. Then $[U_1] = \left(\frac{s}{3}\right)^2 [ABC],$ giving $\left(\frac{5}{14}\right)^2 \cdot 6 = \frac{75}{98}$ or $\left(\frac{1}{8}\right)^2 \cdot 6 = \frac{3}{32}.$ The minimum is $\frac{3}{32},$ so $m + n = 3 + 32 = 35.$

10.

一个半径为 $1$ 的圆被随机放入一个 $15$ 乘 $36$ 的矩形 $ABCD$ 中，且圆完全位于矩形内部。已知该圆不会碰到对角线 $\overline{AC}$ 的概率为 $\frac{m}{n}$ ，其中 $m$ 和 $n$ 是互质正整数，求 $m + n$ 。

A circle of radius $1$ is randomly placed in a $15$ -by- $36$ rectangle $ABCD$ so that the circle lies completely within the rectangle. Given that the probability that the circle will not touch diagonal $\overline{AC}$ is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers, find $m + n.$

答案

答案：817

知识点：几何概率坐标几何距离公式

难度评级：2790

小提示：

圆心在一个 $34 \times 13$ 的矩形中均匀分布；圆避开对角线恰好等价于圆心到该直线的距离大于 $1$

The circle’s center is uniform over a $34 \times 13$ rectangle, and the circle misses the diagonal exactly when the center is more than $1$ from that line

大提示：

有利区域是两条与对角线平行且距离为 $1$ 的直线切出的两个直角三角形；每个三角形的直角边为 $30$ 和 $\frac{25}{2}$

The favorable region is two right triangles cut off by the lines parallel to the diagonal at distance $1;$ each has legs $30$ and $\frac{25}{2}$

解答：

设 $A = (0, 0)$ 、 $B = (36, 0)$ 、 $C = (36, 15)$ 。为使圆位于矩形内，圆心必须在矩形 $[1, 35] \times [1, 14]$ 中，其面积为 $34 \cdot 13 = 442$ ，且圆心在其中均匀分布。对角线 $\overline{AC}$ 位于直线 $5x - 12y = 0$ 上；圆避开它恰好等价于圆心到该直线的距离 $\frac{|5x - 12y|}{13}$ 大于 $1$ ，即 $|5x - 12y| \gt 13$ 。

直线 $5x - 12y = 13$ 与 $y = 1$ 交于 $x = 5$ ，与 $x = 35$ 交于 $y = \frac{27}{2}$ ，所以对角线下方的有利区域是顶点为 $(5, 1)$ 、 $(35, 1)$ 、 $(35, \tfrac{27}{2})$ 的直角三角形，直角边为 $30$ 和 $\frac{25}{2}$ ，面积为 $\frac{1}{2} \cdot 30 \cdot \frac{25}{2} = \frac{375}{2}$ 。将图形旋转 $180^\circ$ ，旋转中心为位于对角线上的矩形中心 $(18, \tfrac{15}{2})$ ，会把内矩形和对角线映到自身，所以对角线上方区域面积相同。

概率为 $\frac{375}{442}$ ，又因为 $442 = 2 \cdot 13 \cdot 17$ 与 $375 = 3 \cdot 5^3$ ，没有公因数，所以 $m + n = 375 + 442 = 817$ 。

Place $A = (0, 0),$ $B = (36, 0),$ $C = (36, 15).$ For the circle to lie in the rectangle, its center must lie in the rectangle $[1, 35] \times [1, 14],$ of area $34 \cdot 13 = 442,$ and the center is uniformly distributed there. The diagonal $\overline{AC}$ lies on the line $5x - 12y = 0,$ and the circle misses it exactly when the center’s distance $\frac{|5x - 12y|}{13}$ exceeds $1,$ that is, $|5x - 12y| \gt 13.$

The line $5x - 12y = 13$ meets $y = 1$ at $x = 5$ and $x = 35$ at $y = \frac{27}{2},$ so below the diagonal the favorable region is the right triangle with vertices $(5, 1),$ $(35, 1),$ $(35, \tfrac{27}{2}),$ with legs $30$ and $\frac{25}{2}$ and area $\frac{1}{2} \cdot 30 \cdot \frac{25}{2} = \frac{375}{2}.$ Rotating $180^\circ$ about the rectangle’s center $(18, \tfrac{15}{2}),$ which lies on the diagonal, maps the inner rectangle and the diagonal to themselves, so the region above the diagonal has the same area.

The probability is $\frac{375}{442},$ and since $442 = 2 \cdot 13 \cdot 17$ shares no factor with $375 = 3 \cdot 5^3,$ we get $m + n = 375 + 442 = 817.$

11.

一个直圆锥形状的实心体高 $4$ 英寸，底面半径为 $3$ 英寸。整个圆锥表面，包括底面，都被涂上了油漆。一个平行于圆锥底面的平面将圆锥分成两个实心体：一个较小的圆锥形实心体 $\mathcal{C}$ 和一个圆台形实心体 $\mathcal{F}$ ，使得 $\mathcal{C}$ 与 $\mathcal{F}$ 的已涂表面积之比，和 $\mathcal{C}$ 与 $\mathcal{F}$ 的体积之比，都等于 $k$ 。已知 $k = \frac{m}{n}$ ，其中 $m$ 和 $n$ 是互质正整数，求 $m + n$ 。

A solid in the shape of a right circular cone is $4$ inches tall and its base has a $3$ -inch radius. The entire surface of the cone, including its base, is painted. A plane parallel to the base of the cone divides the cone into two solids, a smaller cone-shaped solid $\mathcal{C}$ and a frustum-shaped solid $\mathcal{F},$ in such a way that the ratio between the areas of the painted surfaces of $\mathcal{C}$ and $\mathcal{F}$ and the ratio between the volumes of $\mathcal{C}$ and $\mathcal{F}$ are both equal to $k.$ Given that $k = \frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers, find $m + n.$

答案

答案：512

知识点：圆锥表面积长度、面积与体积的缩放关系

难度评级：2710

小提示：

若从顶点到切面的长度与圆锥高之比为 $t$ ，则 $\mathcal{C}$ 的已涂面积为 $15\pi t^2$ ，而总已涂面积为 $24\pi$ ，体积分数是 $t^3$

If the cut is at fraction $t$ of the way up, $\mathcal{C}$ has painted area $15\pi t^2$ of the total painted $24\pi,$ and volume fraction $t^3$

大提示：

令 $\frac{15t^2}{24 - 15t^2} = \frac{t^3}{1 - t^3}$ 可化简为 $15 = 24t$

Equating $\frac{15t^2}{24 - 15t^2} = \frac{t^3}{1 - t^3}$ simplifies to $15 = 24t$

解答：

该圆锥半径为 $3$ ，高为 $4$ ，斜高为 $5$ ，所以已涂表面包括侧面积 $\pi \cdot 3 \cdot 5 = 15\pi$ 和底面积 $9\pi$ ，总共 $24\pi$ 。设切割得到的相似比为 $t$ ，即 $\mathcal{C}$ 是半径 $3t$ 、斜高 $5t$ 的圆锥。那么 $\mathcal{C}$ 的已涂表面只有其侧面积 $15\pi t^2$ ，而 $\mathcal{F}$ 的已涂表面是剩余部分 $24\pi - 15\pi t^2$ 。体积之比为 $t^3$ 比 $1 - t^3$ 。

令两个比值相等， $\frac{15 t^2}{24 - 15 t^2} = \frac{t^3}{1 - t^3}\text{，}$ 所以 $15 t^2 (1 - t^3) = t^3 (24 - 15 t^2)$ ，化简得 $15 t^2 = 24 t^3$ ，因而 $t = \frac{5}{8}$ 。

于是 $k = \frac{t^3}{1 - t^3} = \frac{\frac{125}{512}}{\frac{387}{512}} = \frac{125}{387}$ ，这已经是最简分数，因为 $387 = 3^2 \cdot 43$ ，所以 $m + n = 125 + 387 = 512$ 。

The cone has radius $3,$ height $4,$ and slant height $5,$ so its painted surface consists of lateral area $\pi \cdot 3 \cdot 5 = 15\pi$ and base area $9\pi,$ totaling $24\pi.$ Suppose the cut is at similarity ratio $t,$ so $\mathcal{C}$ is a cone with radius $3t$ and slant height $5t.$ Then $\mathcal{C}$ ’s painted surface is only its lateral area $15\pi t^2,$ and $\mathcal{F}$ ’s painted surface is the rest, $24\pi - 15\pi t^2.$ The volumes are in ratio $t^3$ to $1 - t^3.$

Setting the two ratios equal, $\frac{15 t^2}{24 - 15 t^2} = \frac{t^3}{1 - t^3},$ so $15 t^2 (1 - t^3) = t^3 (24 - 15 t^2),$ which simplifies to $15 t^2 = 24 t^3,$ giving $t = \frac{5}{8}.$

Then $k = \frac{t^3}{1 - t^3} = \frac{\frac{125}{512}}{\frac{387}{512}} = \frac{125}{387},$ which is in lowest terms since $387 = 3^2 \cdot 43,$ so $m + n = 125 + 387 = 512.$

12.

设 $\mathcal{S}$ 为所有有序数对 $(x, y)$ 的集合，满足 $0 \lt x \le 1$ 、 $0 \lt y \le 1$ ，且 $\left\lfloor \log_2\left(\frac{1}{x}\right) \right\rfloor$ 与 $\left\lfloor \log_5\left(\frac{1}{y}\right) \right\rfloor$ 都是偶数。已知 $\mathcal{S}$ 的图形面积为 $\frac{m}{n}$ ，其中 $m$ 和 $n$ 是互质正整数，求 $m + n$ 。记号 $\lfloor z \rfloor$ 表示小于或等于 $z$ 的最大整数。

Let $\mathcal{S}$ be the set of ordered pairs $(x, y)$ such that $0 \lt x \le 1,$ $0 \lt y \le 1,$ and $\left\lfloor \log_2\left(\frac{1}{x}\right) \right\rfloor$ and $\left\lfloor \log_5\left(\frac{1}{y}\right) \right\rfloor$ are both even. Given that the area of the graph of $\mathcal{S}$ is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers, find $m + n.$ The notation $\lfloor z \rfloor$ denotes the greatest integer that is less than or equal to $z.$

答案

答案：14

知识点：取整函数对数等比数列

难度评级：2840

小提示：

$\lfloor \log_2(\frac{1}{x}) \rfloor = 2k$ 恰好等价于 $2^{-2k-1} \lt x \le 2^{-2k}$

$\lfloor \log_2(\frac{1}{x}) \rfloor = 2k$ exactly when $2^{-2k-1} \lt x \le 2^{-2k}$

大提示：

该区域是若干 $x$ 区间组成的集合与若干 $y$ 区间组成的集合的乘积；分别用等比级数求总长度再相乘

The region is a product of a set of $x$ -intervals and a set of $y$ -intervals; sum each set of lengths as a geometric series and multiply

解答：

对于 $0 \lt x \le 1$ ，条件 $\lfloor \log_2(\frac{1}{x}) \rfloor = 2k$ （其中 $k \ge 0$ 为整数）表示 $2k \le \log_2(\frac{1}{x}) \lt 2k + 1$ ，即 $x \in \left(2^{-2k-1}, 2^{-2k}\right]$ 。这些区间的总长度为 $\sum_{k \ge 0} 2^{-2k-1} = \frac{\frac{1}{2}}{1 - \frac{1}{4}} = \frac{2}{3}\text{。}$ 同理， $\lfloor \log_5(\frac{1}{y}) \rfloor$ 为偶数时， $y \in \left(5^{-2k-1}, 5^{-2k}\right]$ ，这些区间的总长度为 $\sum_{k \ge 0} \frac{4}{5} \cdot 25^{-k} = \frac{\frac{4}{5}}{1 - \frac{1}{25}} = \frac{5}{6}$ 。

$\mathcal{S}$ 的图形是这两个集合的笛卡尔积，所以面积为 $\frac{2}{3} \cdot \frac{5}{6} = \frac{5}{9}$ ，因此 $m + n = 5 + 9 = 14$ 。

For $0 \lt x \le 1,$ the condition $\lfloor \log_2(\frac{1}{x}) \rfloor = 2k$ (for an integer $k \ge 0$ ) means $2k \le \log_2(\frac{1}{x}) \lt 2k + 1,$ i.e. $x \in \left(2^{-2k-1}, 2^{-2k}\right].$ These intervals have total length $\sum_{k \ge 0} 2^{-2k-1} = \frac{\frac{1}{2}}{1 - \frac{1}{4}} = \frac{2}{3}.$ Similarly, $\lfloor \log_5(\frac{1}{y}) \rfloor$ is even for $y \in \left(5^{-2k-1}, 5^{-2k}\right],$ intervals of total length $\sum_{k \ge 0} \frac{4}{5} \cdot 25^{-k} = \frac{\frac{4}{5}}{1 - \frac{1}{25}} = \frac{5}{6}.$

The graph of $\mathcal{S}$ is the product of these two sets, so its area is $\frac{2}{3} \cdot \frac{5}{6} = \frac{5}{9},$ and $m + n = 5 + 9 = 14.$

13.

多项式 $\begin{aligned} P(x) &= \small (1 + x + x^2 + \cdots + x^{17})^2 \\ &\quad {}- x^{17} \end{aligned}$ 有 $34$ 个形如 $z_k$ $= r_k[\cos(2\pi\alpha_k) + i\sin(2\pi\alpha_k)]$ 的复数零点，其中 $k = 1$ 、 $2$ 、 $3$ 、 $\ldots$ 、 $34$ ， $0 \lt \alpha_1 \le \alpha_2 \le \alpha_3$ $\le \cdots \le \alpha_{34} \lt 1$ ，且 $r_k \gt 0$ 。已知 $\alpha_1 + \alpha_2 + \alpha_3 + \alpha_4 + \alpha_5 = \frac{m}{n}$ ，其中 $m$ 和 $n$ 是互质正整数，求 $m + n$ 。

The polynomial $\begin{aligned} P(x) &= \small (1 + x + x^2 + \cdots + x^{17})^2 \\ &\quad {}- x^{17} \end{aligned}$ has $34$ complex zeros of the form $z_k$ $= r_k[\cos(2\pi\alpha_k) + i\sin(2\pi\alpha_k)],$ $k = 1,$ $2,$ $3,$ $\ldots,$ $34,$ with $0 \lt \alpha_1 \le \alpha_2 \le \alpha_3$ $\le \cdots \le \alpha_{34} \lt 1$ and $r_k \gt 0.$ Given that $\alpha_1 + \alpha_2 + \alpha_3 + \alpha_4 + \alpha_5 = \frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers, find $m + n.$

答案

答案：482

知识点：单位根等比数列因式分解

难度评级：3060

小提示：

将 $P(x)$ 乘以 $(x - 1)^2$ ，并写作 $1 + x + \cdots + x^{17} = \frac{x^{18} - 1}{x - 1}$

Multiply $P(x)$ by $(x - 1)^2,$ writing $1 + x + \cdots + x^{17} = \frac{x^{18} - 1}{x - 1}$

大提示：

$(x^{18} - 1)^2 - x^{17}(x - 1)^2$ $= (x^{19} - 1)(x^{17} - 1)$ ，所以零点是 $17$ 次和 $19$ 次单位根

$(x^{18} - 1)^2 - x^{17}(x - 1)^2$ $= (x^{19} - 1)(x^{17} - 1),$ so the zeros are $17$ th and $19$ th roots of unity

解答：

当 $x \ne 1$ 时，写成 $1 + x + \cdots + x^{17} = \frac{x^{18} - 1}{x - 1}$ ，所以 $\begin{aligned} \scriptsize (x - 1)^2 P(x) &= (x^{18} - 1)^2 \\ &\quad {}- x^{17}(x - 1)^2 \\ &= x^{36} - x^{19} - x^{17} + 1 \\ &= (x^{19} - 1)(x^{17} - 1) \end{aligned}\text{。}$ 因此 $P$ 的 $34$ 个零点是除 $1$ 之外满足 $x^{17} = 1$ 或 $x^{19} = 1$ 的复数；它们都在单位圆上，对应角度为 $\alpha = \frac{k}{17}$ ，其中 $k = 1, \ldots, 16$ ，以及 $\alpha = \frac{k}{19}$ ，其中 $k = 1, \ldots, 18$ 。

其中最小的五个角为 $\frac{1}{19} \lt \frac{1}{17} \lt \frac{2}{19} \lt \frac{2}{17} \lt \frac{3}{19}\text{，}$ 它们的和为 $\frac{6}{19} + \frac{3}{17} = \frac{102 + 57}{323} = \frac{159}{323}$ 。因为 $159 = 3 \cdot 53$ ， $323 = 17 \cdot 19$ ，这个分数已是最简，所以 $m + n = 159 + 323 = 482$ 。

For $x \ne 1,$ write $1 + x + \cdots + x^{17} = \frac{x^{18} - 1}{x - 1},$ so $\begin{aligned} \scriptsize (x - 1)^2 P(x) &= (x^{18} - 1)^2 \\ &\quad {}- x^{17}(x - 1)^2 \\ &= x^{36} - x^{19} - x^{17} + 1 \\ &= (x^{19} - 1)(x^{17} - 1). \end{aligned}$ Hence the zeros of $P$ are the $34$ complex numbers other than $1$ satisfying $x^{17} = 1$ or $x^{19} = 1;$ all lie on the unit circle, with angles $\alpha = \frac{k}{17}$ for $k = 1, \ldots, 16$ and $\alpha = \frac{k}{19}$ for $k = 1, \ldots, 18.$

The five smallest of these angles are $\frac{1}{19} \lt \frac{1}{17} \lt \frac{2}{19} \lt \frac{2}{17} \lt \frac{3}{19},$ whose sum is $\frac{6}{19} + \frac{3}{17} = \frac{102 + 57}{323} = \frac{159}{323}.$ Since $159 = 3 \cdot 53$ and $323 = 17 \cdot 19,$ this is in lowest terms, and $m + n = 159 + 323 = 482.$

14.

一只独角兽被一根 $20$ 英尺长的银绳拴在一座魔法师圆柱形塔的底部，塔的半径为 $8$ 英尺。绳子一端固定在塔的地面高度处，另一端系在独角兽身上，离地高度为 $4$ 英尺。独角兽把绳子拉紧，绳子的末端距塔上最近点 $4$ 英尺，且绳子接触塔的长度为 $\frac{a - \sqrt{b}}{c}$ 英尺，其中 $a$ 、 $b$ 、 $c$ 是正整数，且 $c$ 是质数。求 $a + b + c$ 。

A unicorn is tethered by a $20$ -foot silver rope to the base of a magician’s cylindrical tower whose radius is $8$ feet. The rope is attached to the tower at ground level and to the unicorn at a height of $4$ feet. The unicorn has pulled the rope taut, the end of the rope is $4$ feet from the nearest point on the tower, and the length of the rope that is touching the tower is $\frac{a - \sqrt{b}}{c}$ feet, where $a,$ $b,$ and $c$ are positive integers, and $c$ is prime. Find $a + b + c.$

答案

答案：813

知识点：圆柱展开图（立体几何）切线勾股定理

难度评级：3270

小提示：

展开圆柱侧面后，绷紧的绳子成为一条直线段，因此整根绳子和其水平投影始终保持 $20 : \sqrt{20^2 - 4^2}$ 的比例

Unrolling the cylinder makes the taut rope one straight segment, so length and horizontal projection stay in the ratio $20 : \sqrt{20^2 - 4^2}$ along the whole rope

大提示：

从上方看，绳子离开塔的部分与半径为 $8$ 的圆相切，其另一端距圆心 $12$ ，所以投影长度为 $4\sqrt{5}$

Seen from above, the free part of the rope is tangent to the circle of radius $8$ from a point $12$ from the center, so its projection has length $4\sqrt{5}$

解答：

绳子从塔底固定点 $A$ 出发，沿墙面贴到一点 $P$ ，再直线连到末端 $Q$ ，其高度为 $4$ ，到塔轴的距离为 $8 + 4 = 12$ 。将圆柱侧面展开成平面：绷紧的绳子成为一条长度为 $20$ 、上升 $4$ 英尺的直线段，所以其水平投影长度为 $\sqrt{20^2 - 4^2} = 8\sqrt{6}$ ，而绳子的每一段都有相同的长度与水平投影之比 $\frac{20}{8\sqrt{6}} = \frac{5}{2\sqrt{6}}$ 。

从上方看，自由段 $PQ$ 与半径为 $8$ 的圆相切，切点为 $P$ ，其另一端距圆心 $12$ ，所以其水平投影长度为 $\sqrt{12^2 - 8^2} = 4\sqrt{5}$ 。因此 $\begin{aligned} PQ &= \frac{5}{2\sqrt{6}} \cdot 4\sqrt{5} \\ &= \frac{10\sqrt{5}}{\sqrt{6}} \\ &= \frac{5\sqrt{30}}{3} \end{aligned}\text{。}$

接触塔的绳长为 $20 - \frac{5\sqrt{30}}{3} = \frac{60 - \sqrt{750}}{3}$ ，且 $c = 3$ 是质数，所以 $a + b + c = 60 + 750 + 3 = 813$ 。

The rope runs from its anchor $A$ at the base of the tower, hugs the wall up to a point $P,$ then goes straight to its end $Q,$ which is at height $4$ and at distance $8 + 4 = 12$ from the tower’s axis. Unroll the cylinder’s wall into a plane: a taut rope becomes a single straight segment of length $20$ rising $4$ feet, so its horizontal projection has length $\sqrt{20^2 - 4^2} = 8\sqrt{6},$ and every piece of the rope has the same ratio $\frac{20}{8\sqrt{6}} = \frac{5}{2\sqrt{6}}$ of length to horizontal projection.

Viewed from above, the free portion $PQ$ is tangent to the circle of radius $8$ at $P$ from a point at distance $12,$ so its horizontal projection has length $\sqrt{12^2 - 8^2} = 4\sqrt{5}.$ Therefore $\begin{aligned} PQ &= \frac{5}{2\sqrt{6}} \cdot 4\sqrt{5} \\ &= \frac{10\sqrt{5}}{\sqrt{6}} \\ &= \frac{5\sqrt{30}}{3}. \end{aligned}$

The rope touching the tower has length $20 - \frac{5\sqrt{30}}{3} = \frac{60 - \sqrt{750}}{3},$ and $c = 3$ is prime, so $a + b + c = 60 + 750 + 3 = 813.$

15.

对所有正整数 $x$ ，定义 $f(x) = \scriptsize\begin{cases} 1 & \text{若 } x = 1, \\ \frac{x}{10} & \text{若 } x \text{ 是 } 10 \text{的倍数}, \\ x + 1 & \text{否则，} \end{cases}$ 并按如下方式定义一个数列： $x_1 = x$ ，且 $x_{n+1} = f(x_n)$ 对所有正整数 $n$ 成立。令 $d(x)$ 为最小正整数 $n$ ，使 $x_n = 1$ 。（例如， $d(100) = 3$ ， $d(87) = 7$ 。）设 $m$ 为正整数 $x$ 中满足 $d(x) = 20$ 的个数。求 $m$ 的不同质因数之和。

For all positive integers $x,$ let $f(x) = \scriptsize\begin{cases} 1 & \text{if } x = 1, \\ \frac{x}{10} & \text{if } x \text{ is divisible by } 10, \\ x + 1 & \text{otherwise,} \end{cases}$ and define a sequence as follows: $x_1 = x$ and $x_{n+1} = f(x_n)$ for all positive integers $n.$ Let $d(x)$ be the smallest $n$ such that $x_n = 1.$ (For example, $d(100) = 3$ and $d(87) = 7.$ ) Let $m$ be the number of positive integers $x$ such that $d(x) = 20.$ Find the sum of the distinct prime factors of $m.$

答案

答案：511

知识点：递推计数树状图逆推法

难度评级：3370

小提示：

从 $1$ 倒推：每个 $z$ 都有原像 $10z$ ，另外还有 $z - 1$ ，除非 $z$ 以 $1$ 结尾或 $z = 2$

Work backwards from $1:$ each $z$ has preimages $10z,$ and $z - 1$ unless $z$ ends in $1$ or $z = 2$

大提示：

如果每个顶点都有两个子节点，原像树第 $20$ 列会有 $2^{18}$ 个数；每遇到一个只有一个子节点的顶点，就减去 $2^{19-k}$ ，其中该顶点位于第 $k$ 列

Column $20$ of the preimage tree would have $2^{18}$ numbers if every vertex had two children; subtract $2^{19-k}$ for each one-child vertex in column $k$

解答：

倒推：若 $f(z') = z$ ，则 $z' = 10z$ （总是可以）；还可能有 $z' = z - 1$ ，前提是 $z - 1$ 不是 $10$ 的倍数且 $z - 1 \ne 1$ ，即 $z$ 不以 $1$ 结尾且 $z \ne 2$ 。因此满足 $d(x) = n$ 的整数构成树的第 $n$ 列，而这棵树以 $1$ 为根：前几列为 $\{1\}$ 、 $\{10\}$ 、 $\{9, 100\}$ 、 $\{8, 90, 99, 1000\}$ ，并且除 $2$ 和以 $1$ 结尾的顶点以外，每个顶点都有两个子节点；那些例外只有子节点 $10z$ 。

找出这些只有一个子节点的顶点。因为 $2 \to 3 \to \cdots \to 10 \to 1$ ，顶点 $2$ 位于第 $10$ 列。以 $1$ 结尾的顶点可通过反复减去 $1$ 到达，起点是以 $0$ 结尾的顶点，共减九次。因此这类顶点要再过 $9$ 列才出现；作为起点的是 $10$ 的倍数。第 $2$ 到第 $10$ 列完全翻倍（那之前没有只有一个子节点的顶点），所以第 $j$ 列有 $2^{j-2}$ 个顶点，其中 $10$ 的倍数，也就是子节点 $10z$ ，来自第 $j - 1$ 列，共有 $2^{j-3}$ 个。因此对 $12 \le k \le 19$ ，第 $k$ 列含有 $2^{k-12}$ 个以 $1$ 结尾的顶点（第 $11$ 列没有，因为其中涉及的 $10$ 的倍数来自第 $2$ 列，也就是 $10$ 本身；它的后代 $1$ 被排除，而这个排除正好就是 $2$ 缺少的那个子节点）。

第 $k$ 列中一个只有一个子节点的顶点，会去掉 $2^{19-k}$ 个潜在顶点；原本共有 $2^{18}$ 个，位于第 $20$ 列。因此 $\begin{aligned} m &= 2^{18} - 2^{9} \\ &\quad {}- \sum_{k=12}^{19} 2^{k-12} \cdot 2^{19-k} \\ &= 2^{18} - 2^9 - 8 \cdot 2^7 \\ &= 2^9(2^9 - 1 - 2) \\ &= 2^9 \cdot 509 \end{aligned}\text{。}$ 因为 $509$ 是质数， $m$ 的不同质因数之和为 $2 + 509 = 511$ 。

Work backwards: $f(z') = z$ for $z' = 10z$ (always) and for $z' = z - 1$ (provided $z - 1$ is not a multiple of $10$ and $z - 1 \ne 1,$ i.e. $z$ does not end in $1$ and $z \ne 2$ ). So the integers with $d(x) = n$ form column $n$ of a tree rooted at $1:$ the columns begin $\{1\},$ $\{10\},$ $\{9, 100\},$ $\{8, 90, 99, 1000\},$ and every vertex has two children except $2$ and the vertices ending in $1,$ which have only the child $10z.$

Locate those one-child vertices. Since $2 \to 3 \to \cdots \to 10 \to 1,$ the vertex $2$ sits in column $10.$ A vertex ending in $1$ is reached by subtracting $1$ nine times from a vertex ending in $0,$ so such vertices sit $9$ columns after the multiples of $10$ in the tree. Columns $2$ through $10$ double perfectly (no one-child vertices occur that early), so column $j$ has $2^{j-2}$ vertices, of which the multiples of $10$ — the children $10z$ of column $j - 1$ — number $2^{j-3}.$ Hence for $12 \le k \le 19,$ column $k$ contains $2^{k-12}$ vertices ending in $1$ (column $11$ has none, because the multiple of $10$ in column $2$ is $10$ itself, whose descendant $1$ is excluded — that exclusion is exactly the missing child of $2$ ).

A one-child vertex in column $k$ removes $2^{19-k}$ of the potential $2^{18}$ vertices from column $20.$ Therefore $\begin{aligned} m &= 2^{18} - 2^{9} \\ &\quad {}- \sum_{k=12}^{19} 2^{k-12} \cdot 2^{19-k} \\ &= 2^{18} - 2^9 - 8 \cdot 2^7 \\ &= 2^9(2^9 - 1 - 2) \\ &= 2^9 \cdot 509. \end{aligned}$ Since $509$ is prime, the sum of the distinct prime factors of $m$ is $2 + 509 = 511.$