2017 AIME II 真题与在线限时测验

计时

3:00:00

1.

求 $\{1, 2, 3, 4, 5, 6, 7, 8\}$ 的子集中，有多少个既不是 $\{1, 2, 3, 4, 5\}$ 的子集，也不是 $\{4, 5, 6, 7, 8\}$ 的子集。

Find the number of subsets of $\{1, 2, 3, 4, 5, 6, 7, 8\}$ that are subsets of neither $\{1, 2, 3, 4, 5\}$ nor $\{4, 5, 6, 7, 8\}.$

答案

答案：196

知识点：子集容斥原理

难度评级：1890

小提示：

计算补集：完全包含在 $\{1,2,3,4,5\}$ 中，或完全包含在 $\{4,5,6,7,8\}$ 中的子集

Count the complement: subsets that lie entirely inside $\{1,2,3,4,5\}$ or entirely inside $\{4,5,6,7,8\}$

大提示：

用容斥，重叠部分是 $\{4, 5\}$ 的子集，所以从 $2^8$ 中减去 $2^5 + 2^5 - 2^2$

By inclusion-exclusion, the overlap consists of the subsets of $\{4, 5\},$ so subtract $2^5 + 2^5 - 2^2$ from $2^8$

解答：

总共有 $2^8 = 256$ 个子集。要排除的是包含在 $\{1,2,3,4,5\}$ 中的子集（有 $2^5 = 32$ 个），或包含在 $\{4,5,6,7,8\}$ 中的子集（也有 $32$ 个）。同时属于两者的子集正好是交集 $\{4, 5\}$ 的子集，共有 $2^2 = 4$ 个。

由容斥，不符合条件的子集有 $32 + 32 - 4 = 60$ 个，因此满足要求的子集有 $256 - 60 = 196$ 个。

There are $2^8 = 256$ subsets in all. The ones to exclude are those contained in $\{1,2,3,4,5\}$ (there are $2^5 = 32$ ) or contained in $\{4,5,6,7,8\}$ (another $32$ ). A subset of both is exactly a subset of the intersection $\{4, 5\},$ and there are $2^2 = 4$ of those.

By inclusion-exclusion, $32 + 32 - 4 = 60$ subsets fail, so $256 - 60 = 196$ subsets have the required property.

2.

队伍 $T_1$ 、 $T_2$ 、 $T_3$ 和 $T_4$ 进入季后赛。半决赛中， $T_1$ 对阵 $T_4$ ， $T_2$ 对阵 $T_3$ 。这两场比赛的胜者将在决赛中相遇，决出冠军。当 $T_i$ 对阵 $T_j$ 时， $T_i$ 获胜的概率为 $\frac{i}{i+j}$ ，并且所有比赛结果相互独立。 $T_4$ 获得冠军的概率为 $\frac{p}{q}$ ，其中 $p$ 和 $q$ 是互质的正整数。求 $p + q$ 。

Teams $T_1,$ $T_2,$ $T_3,$ and $T_4$ are in the playoffs. In the semifinal matches, $T_1$ plays $T_4,$ and $T_2$ plays $T_3.$ The winners of those two matches will play each other in the final match to determine the champion. When $T_i$ plays $T_j,$ the probability that $T_i$ wins is $\frac{i}{i+j},$ and the outcomes of all the matches are independent. The probability that $T_4$ will be the champion is $\frac{p}{q},$ where $p$ and $q$ are relatively prime positive integers. Find $p + q.$

答案

答案：781

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

难度评级：2070

小提示：

$T_4$ 必须先在半决赛击败 $T_1$ ，再击败 $T_2$ 和 $T_3$ 中赢下另一场半决赛的队伍

$T_4$ must beat $T_1$ in its semifinal, then beat whichever of $T_2$ and $T_3$ wins the other semifinal

大提示：

按另一场半决赛分类： $T_2$ 进入决赛的概率是 $\frac{2}{5}$ ，而 $T_4$ 击败 $T_2$ 或 $T_3$ 的概率分别是 $\frac{4}{6}$ 和 $\frac{4}{7}$

Split into cases by the other semifinal: $T_2$ reaches the final with probability $\frac{2}{5},$ and $T_4$ beats $T_2$ or $T_3$ with probability $\frac{4}{6}$ or $\frac{4}{7}$

解答：

要成为冠军， $T_4$ 首先必须击败 $T_1$ ，概率为 $\frac{4}{4+1} = \frac{4}{5}$ 。另一场半决赛中， $T_2$ 进入决赛的概率为 $\frac{2}{2+3} = \frac{2}{5}$ ， $T_3$ 进入决赛的概率为 $\frac{3}{5}$ ；决赛中， $T_4$ 击败 $T_2$ 的概率为 $\frac{4}{4+2} = \frac{2}{3}$ ，击败 $T_3$ 的概率为 $\frac{4}{4+3} = \frac{4}{7}$ 。

因此 $T_4$ 成为冠军的概率为 $\begin{aligned} &\frac{4}{5}\left(\frac{2}{5} \cdot \frac{2}{3} + \frac{3}{5} \cdot \frac{4}{7}\right) \\ &= \frac{4}{5} \cdot \frac{64}{105} \\ &= \frac{256}{525} \end{aligned}\text{。}$ 因为 $256 = 2^8$ ，且 $525 = 3 \cdot 5^2 \cdot 7$ ，这个分数已经最简，所以 $p + q = 256 + 525 = 781$ 。

To be champion, $T_4$ must first beat $T_1,$ which happens with probability $\frac{4}{4+1} = \frac{4}{5}.$ The other semifinal sends $T_2$ to the final with probability $\frac{2}{2+3} = \frac{2}{5}$ and $T_3$ with probability $\frac{3}{5};$ in the final, $T_4$ beats $T_2$ with probability $\frac{4}{4+2} = \frac{2}{3}$ and beats $T_3$ with probability $\frac{4}{4+3} = \frac{4}{7}.$

The probability that $T_4$ is champion is therefore $\begin{aligned} &\frac{4}{5}\left(\frac{2}{5} \cdot \frac{2}{3} + \frac{3}{5} \cdot \frac{4}{7}\right) \\ &= \frac{4}{5} \cdot \frac{64}{105} \\ &= \frac{256}{525}. \end{aligned}$ Since $256 = 2^8$ and $525 = 3 \cdot 5^2 \cdot 7,$ this is in lowest terms, and $p + q = 256 + 525 = 781.$

3.

一个三角形的顶点为 $A(0, 0)$ 、 $B(12, 0)$ 和 $C(8, 10)$ 。在三角形内随机选一点，它到顶点 $B$ 的距离比到顶点 $A$ 和顶点 $C$ 的距离都近的概率可写成 $\frac{p}{q}$ ，其中 $p$ 和 $q$ 是互质的正整数。求 $p + q$ 。

A triangle has vertices $A(0, 0),$ $B(12, 0),$ and $C(8, 10).$ The probability that a randomly chosen point inside the triangle is closer to vertex $B$ than to either vertex $A$ or vertex $C$ can be written as $\frac{p}{q},$ where $p$ and $q$ are relatively prime positive integers. Find $p + q.$

答案

答案：409

知识点：几何概率垂直平分线坐标几何

难度评级：2230

小提示：

到 $B$ 比到 $A$ 更近的点位于 $\overline{AB}$ 的垂直平分线一侧；对 $C$ 也一样

The points closer to $B$ than to $A$ lie on one side of the perpendicular bisector of $\overline{AB};$ likewise for $C$

大提示：

两条垂直平分线是 $x = 6$ 和 $y = \frac{2}{5}x + 1$ ；求出它们在 $B$ 附近截出的四边形面积，再除以 $60$

The bisectors are $x = 6$ and $y = \frac{2}{5}x + 1;$ find the area of the quadrilateral they cut off near $B$ and divide by $60$

解答：

到 $B$ 比到 $A$ 更近的点位于 $\overline{AB}$ 的垂直平分线右侧，即直线 $x = 6$ 的右侧。到 $B$ 比到 $C$ 更近的点位于 $\overline{BC}$ 的垂直平分线下方。这条线经过中点 $(10, 5)$ ，斜率为 $\frac{2}{5}$ （边 $BC$ 的斜率 $-\frac{5}{2}$ 的负倒数），所以方程是 $y = \frac{2}{5}x + 1$ 。

在三角形内部，有利区域是一个四边形，其顶点为 $(6, 0)$ 、 $B(12, 0)$ 、 $\overline{BC}$ 的中点 $(10, 5)$ ，以及两条垂直平分线的交点 $\left(6, \frac{17}{5}\right)$ 。沿 $(6, 0)$ 到 $(10, 5)$ 的线段把它分成两块，面积为 $\begin{aligned} &\frac{1}{2} \cdot \frac{17}{5} \cdot 4 + \frac{1}{2} \cdot 6 \cdot 5 \\ &= \frac{34}{5} + 15 \\ &= \frac{109}{5} \end{aligned}\text{。}$

整个三角形面积为 $\frac{1}{2} \cdot 12 \cdot 10 = 60$ ，所以概率为 $\frac{\frac{109}{5}}{60} = \frac{109}{300}$ ，从而 $p + q = 109 + 300 = 409$ 。

The points closer to $B$ than to $A$ lie to the right of the perpendicular bisector of $\overline{AB},$ the line $x = 6.$ The points closer to $B$ than to $C$ lie below the perpendicular bisector of $\overline{BC},$ which passes through the midpoint $(10, 5)$ with slope $\frac{2}{5}$ (the negative reciprocal of the slope $-\frac{5}{2}$ of $BC$ ): the line $y = \frac{2}{5}x + 1.$

Inside the triangle, the favorable region is the quadrilateral with vertices $(6, 0),$ $B(12, 0),$ the midpoint $(10, 5)$ of $\overline{BC},$ and $\left(6, \frac{17}{5}\right),$ where the two bisectors meet. Splitting it along the segment from $(6, 0)$ to $(10, 5),$ its area is $\begin{aligned} &\frac{1}{2} \cdot \frac{17}{5} \cdot 4 + \frac{1}{2} \cdot 6 \cdot 5 \\ &= \frac{34}{5} + 15 \\ &= \frac{109}{5}. \end{aligned}$

The triangle has area $\frac{1}{2} \cdot 12 \cdot 10 = 60,$ so the probability is $\frac{\frac{109}{5}}{60} = \frac{109}{300},$ and $p + q = 109 + 300 = 409.$

4.

求不超过 $2017$ 的正整数中，有多少个的三进制表示不含数字 $0$ 。

Find the number of positive integers less than or equal to $2017$ whose base-three representation contains no digit equal to $0.$

答案

答案：222

知识点：进制数字分类讨论

难度评级：2230

小提示：

一个三进制表示不含数字 $0$ ，等价于每一位都是 $1$ 或 $2$ ；这样的 $k$ 位数有 $2^k$ 个

A base-three representation avoids the digit $0$ exactly when every digit is $1$ or $2;$ there are $2^k$ such $k$ -digit numbers

大提示：

因为 $2017 = 2202201_3$ ，判断哪些由 $1$ 和 $2$ 组成的 $7$ 位字符串不超过上界时，只需看前两位

Since $2017 = 2202201_3,$ decide which $7$ -digit strings of $1$ s and $2$ s stay below the bound by looking at the first two digits

解答：

一个正整数的三进制表示没有 $0$ ，当且仅当每一位都是 $1$ 或 $2$ 。对于 $k = 1, 2, \ldots, 6$ ，这样的 $k$ 位数有 $2^k$ 个，并且它们全都不超过 $222222_3 = 728 \lt 2017$ 。

因为 $2017 = 2202201_3$ ，一个由 $1$ 和 $2$ 组成的七位字符串不超过 $2017$ ，当且仅当它以 $11$ 、 $12$ 或 $21$ 开头：任何以 $22$ 开头的字符串都会在第三位超过 $2202201_3$ ，因为它的各位都非零。因此有 $3 \cdot 2^5 = 96$ 个七位数。

总数为 $2 + 4 + 8 + 16 + 32 + 64$ $+ 96 = 222$ 。

A positive integer has no $0$ in base three exactly when every digit is $1$ or $2.$ For $k = 1, 2, \ldots, 6$ there are $2^k$ such $k$ -digit numbers, and all of them are at most $222222_3 = 728 \lt 2017.$

Since $2017 = 2202201_3,$ a seven-digit string of $1$ s and $2$ s is at most $2017$ exactly when it begins with $11,$ $12,$ or $21:$ any string beginning $22$ already beats $2202201_3$ at the third digit, since its digits are nonzero. That gives $3 \cdot 2^5 = 96$ seven-digit numbers.

The total is $2 + 4 + 8 + 16 + 32 + 64$ $+ 96 = 222.$

5.

一个集合含有四个数。这个集合中不同元素两两相加得到的六个和，顺序不定，分别是 $189$ 、 $320$ 、 $287$ 、 $234$ 、 $x$ 和 $y$ 。求 $x + y$ 的最大可能值。

A set contains four numbers. The six pairwise sums of distinct elements of the set, in no particular order, are $189,$ $320,$ $287,$ $234,$ $x,$ and $y.$ Find the greatest possible value of $x + y.$

答案

答案：791

知识点：代数变形配对与分组最优化

难度评级：2390

小提示：

六个两两和可以分成三对互补的和，每一对的总和都等于集合所有元素的和 $a + b + c + d$

The six pairwise sums split into three complementary pairs, each pair adding up to the total $a + b + c + d$ of the set

大提示：

所以 $x + y = 3s - 1030$ ，其中共同的配对总和 $s$ 是四个已知数中某两个的和；让 $s$ 尽可能大

So $x + y = 3s - 1030,$ where the common pair total $s$ is a sum of two of the four given numbers; make $s$ as large as possible

解答：

设集合为 $\{a, b, c, d\}$ ，总和为 $s = a + b + c + d$ 。六个两两和可以分成三对互补的和： $\begin{aligned} &(a+b) + (c+d) \\ &= (a+c) + (b+d) \\ &= (a+d) + (b+c) = s \end{aligned}\text{。}$ 将 $189$ 、 $320$ 、 $287$ 、 $234$ 两两配对，没有任何一种配法能让两对总和相等（ $509 \ne 521$ 、 $476 \ne 554$ 、 $423 \ne 607$ ），所以 $x$ 和 $y$ 不会互相配对；它们各自与一个已知和配对，剩下两个已知和互相配对。把六个数全部相加， $x + y$ $= 3s - (189 + 320 + 287 + 234)$ $= 3s - 1030$ ，其中 $s$ 是两个已知数的和。

最大选择是 $s = 320 + 287 = 607$ ，得到 $x + y = 3 \cdot 607 - 1030 = 791$ 。这个值可以由集合 $\{51.5,\ 137.5,\ 182.5,\ 235.5\}$ 达到，其两两和为 $189$ 、 $234$ 、 $287$ 、 $320$ 、 $373$ 和 $418$ ，且 $373 + 418 = 791$ 。

Let the set be $\{a, b, c, d\}$ with total $s = a + b + c + d.$ The six pairwise sums come in three complementary pairs: $\begin{aligned} &(a+b) + (c+d) \\ &= (a+c) + (b+d) \\ &= (a+d) + (b+c) = s. \end{aligned}$ No two of the pairings of $189,$ $320,$ $287,$ $234$ into two pairs give equal totals ( $509 \ne 521,$ $476 \ne 554,$ $423 \ne 607$ ), so $x$ and $y$ are not paired with each other; each is paired with a given sum, and the remaining two given sums are paired together. Adding all six values, $x + y$ $= 3s - (189 + 320 + 287 + 234)$ $= 3s - 1030,$ where $s$ is the sum of two of the given numbers.

The largest choice is $s = 320 + 287 = 607,$ giving $x + y = 3 \cdot 607 - 1030 = 791.$ This is attained by the set $\{51.5,\ 137.5,\ 182.5,\ 235.5\},$ whose pairwise sums are $189,$ $234,$ $287,$ $320,$ $373,$ and $418,$ with $373 + 418 = 791.$

6.

求所有正整数 $n$ 的和，使得 $\sqrt{n^2 + 85n + 2017}$ 是整数。

Find the sum of all positive integers $n$ such that $\sqrt{n^2 + 85n + 2017}$ is an integer.

答案

答案：195

知识点：丢番图方程配方法平方差

难度评级：2450

小提示：

设 $n^2 + 85n + 2017 = m^2$ ，并乘以 $4$ ，使左边变成 $(2n + 85)^2 + 843$

Set $n^2 + 85n + 2017 = m^2$ and multiply by $4$ so the left side becomes $(2n + 85)^2 + 843$

大提示：

将 $4m^2 - (2n + 85)^2$ 分解为平方差； $843 = 3 \cdot 281$ 只有两种分解方式

Factor $4m^2 - (2n + 85)^2$ as a difference of squares; $843 = 3 \cdot 281$ has only two factorizations

解答：

设 $n^2 + 85n + 2017 = m^2$ ，其中 $m$ 是正整数。两边乘以 $4$ 并配方，得到 $(2n + 85)^2 + 843 = 4m^2$ ，所以 $\begin{aligned} &(2m - 2n - 85)(2m + 2n + 85) \\ &= 843 = 3 \cdot 281 \end{aligned}\text{，}$ 其中 $281$ 是质数。两个因数都是正数，且第二个更大，所以要么 $2m - 2n - 85 = 1$ 且 $2m + 2n + 85 = 843$ ，要么 $2m - 2n - 85 = 3$ 且 $2m + 2n + 85 = 281$ 。

第一个方程组给出 $m = 211$ 和 $n = 168$ ，并且确实有 $168^2 + 85 \cdot 168 + 2017$ $= 44521 = 211^2$ 。第二个方程组给出 $m = 71$ 和 $n = 27$ ，且 $27^2 + 85 \cdot 27 + 2017$ $= 5041 = 71^2$ 。

所求和为 $168 + 27 = 195$ 。

Suppose $n^2 + 85n + 2017 = m^2$ for a positive integer $m.$ Multiplying by $4$ and completing the square gives $(2n + 85)^2 + 843 = 4m^2,$ so $\begin{aligned} &(2m - 2n - 85)(2m + 2n + 85) \\ &= 843 = 3 \cdot 281, \end{aligned}$ where $281$ is prime. Both factors are positive with the second one larger, so either $2m - 2n - 85 = 1$ and $2m + 2n + 85 = 843,$ or $2m - 2n - 85 = 3$ and $2m + 2n + 85 = 281.$

The first system gives $m = 211$ and $n = 168,$ and indeed $168^2 + 85 \cdot 168 + 2017$ $= 44521 = 211^2.$ The second gives $m = 71$ and $n = 27,$ with $27^2 + 85 \cdot 27 + 2017$ $= 5041 = 71^2.$

The requested sum is $168 + 27 = 195.$

7.

求闭区间 $[-500, 500]$ 中整数 $k$ 的个数，使得方程 $\log(kx) = 2\log(x + 2)$ 恰好有一个实数解。

Find the number of integer values of $k$ in the closed interval $[-500, 500]$ for which the equation $\log(kx) = 2\log(x + 2)$ has exactly one real solution.

答案

答案：501

知识点：对数二次方程分类讨论

难度评级：2740

小提示：

方程等价于 $kx = (x + 2)^2$ ，但需满足定义域限制 $kx \gt 0$ 和 $x \gt -2$ ；分别处理 $k \lt 0$ 和 $k \gt 0$

The equation says $kx = (x + 2)^2$ with the domain restrictions $kx \gt 0$ and $x \gt -2;$ treat $k \lt 0$ and $k \gt 0$ separately

大提示：

对每个 $k \lt 0$ ，两图像在 $(-2, 0)$ 上恰好相交一次；对 $k \gt 0$ ，二次方程 $x^2 + (4 - k)x + 4$ 需要有一个重正根

For every $k \lt 0$ the two graphs cross exactly once on $(-2, 0);$ for $k \gt 0$ the quadratic $x^2 + (4 - k)x + 4$ needs a repeated positive root

解答：

方程要求 $x + 2 \gt 0$ 且 $kx \gt 0$ ，在这些限制下它等价于 $kx = (x + 2)^2$ ，也就是 $x^2 + (4 - k)x + 4 = 0$ 。

当 $k \lt 0$ 时，限制条件迫使 $-2 \lt x \lt 0$ 。在这个区间上， $kx$ 从 $-2k \gt 0$ 下降到 $0$ ，而 $(x + 2)^2$ 从 $0$ 增加到 $4$ ，所以两图像恰好相交一次。因此 $500$ 个负的 $k$ 全部满足条件，而 $k = 0$ 会使 $\log(kx)$ 无定义。

当 $k \gt 0$ 时，限制条件迫使 $x \gt 0$ 。二次方程的根的乘积为 $4$ ，所以若有实根，两根同号；判别式 $(4 - k)^2 - 16 = k(k - 8)$ 在 $0 \lt k \lt 8$ 时为负。当 $k \gt 8$ 时，有两个不同的正根（根和 $k - 4 \gt 0$ ），给出两个解；只有 $k = 8$ 给出恰好一个解，即重根 $x = 2$ 。总共有 $500 + 1 = 501$ 个 $k$ 满足条件。

The equation requires $x + 2 \gt 0$ and $kx \gt 0,$ and under those restrictions it is equivalent to $kx = (x + 2)^2,$ that is, $x^2 + (4 - k)x + 4 = 0.$

For $k \lt 0$ the restrictions force $-2 \lt x \lt 0.$ On this interval $kx$ decreases from $-2k \gt 0$ to $0$ while $(x + 2)^2$ increases from $0$ to $4,$ so the graphs cross exactly once. Hence every one of the $500$ negative values of $k$ works, while $k = 0$ makes $\log(kx)$ undefined.

For $k \gt 0$ the restrictions force $x \gt 0.$ The quadratic has root product $4,$ so any real roots have the same sign, and the discriminant $(4 - k)^2 - 16 = k(k - 8)$ is negative for $0 \lt k \lt 8.$ When $k \gt 8$ there are two distinct positive roots (root sum $k - 4 \gt 0$ ), giving two solutions; only $k = 8$ gives exactly one solution, the double root $x = 2.$ In total $500 + 1 = 501$ values of $k$ work.

8.

求小于 $2017$ 的正整数 $n$ 的个数，使得 $\begin{aligned} &1 + n + \frac{n^2}{2!} + \frac{n^3}{3!} + \frac{n^4}{4!} \\ &{}+ \frac{n^5}{5!} + \frac{n^6}{6!} \end{aligned}$ 是整数。

Find the number of positive integers $n$ less than $2017$ such that $\begin{aligned} &1 + n + \frac{n^2}{2!} + \frac{n^3}{3!} + \frac{n^4}{4!} \\ &{}+ \frac{n^5}{5!} + \frac{n^6}{6!} \end{aligned}$ is an integer.

答案

答案：134

知识点：整除性模运算阶乘分类讨论

难度评级：2840

小提示：

乘以 $6! = 720$ ：原和为整数当且仅当 $720$ 整除 $n^6 + 6n^5 + 30n^4$ $+ 120n^3 + 360n^2$ 成立

Multiply by $6! = 720:$ the sum is an integer exactly when $720$ divides $n^6 + 6n^5 + 30n^4$ $+ 120n^3 + 360n^2$

大提示：

模 $2$ 和模 $3$ 检查会迫使 $n$ 是 $6$ 的倍数；写成 $n = 6k$ 后，只剩下 $5$ 整除 $k(k + 1)$ 这个条件

Checking mod $2$ and mod $3$ forces $n$ to be a multiple of $6;$ write $n = 6k,$ and only the condition that $5$ divides $k(k + 1)$ survives

解答：

乘以 $6! = 720$ 后，原和为整数当且仅当 $\begin{aligned} &n^6 + 6n^5 + 30n^4 \\ &{}+ 120n^3 + 360n^2 \\ &\text{是 } 720 \text{ 的倍数} \end{aligned}\text{。}$ 如果 $n$ 是奇数，除 $n^6$ 外每一项都是偶数，总和为奇数。若 $n$ 不是 $3$ 的倍数，则模 $3$ 时除 $n^6$ 外每一项都为零，而 $n^6 \equiv 1 \pmod 3$ 。所以 $n$ 必须是 $6$ 的倍数。

写 $n = 6k$ 。此时 $30n^4 = 720 \cdot 54k^4$ ， $120n^3 = 720 \cdot 36k^3$ ，且 $360n^2 = 720 \cdot 18k^2$ 都能被 $720$ 整除；而 $n^6 + 6n^5 = 6^6 k^5(k + 1)$ 。由于 $6^6 = 2^6 3^6$ 已经提供了 $720 = 2^4 \cdot 3^2 \cdot 5$ 中的 $2^4$ 和 $3^2$ ，条件化为 $k(k + 1)$ 是 $5$ 的倍数，即 $k \equiv 0$ 或 $4 \pmod 5$ 。

对 $n = 6k \lt 2017$ ，需要 $1 \le k \le 336$ 。这个范围内有 $67$ 个 $5$ 的倍数，也有 $67$ 个满足 $k \equiv 4 \pmod 5$ 的数，所以这样的 $n$ 共有 $67 + 67 = 134$ 个。

Multiplying by $6! = 720,$ the sum is an integer exactly when $\begin{aligned} &n^6 + 6n^5 + 30n^4 \\ &{}+ 120n^3 + 360n^2 \\ &\text{is divisible by } 720. \end{aligned}$ If $n$ were odd, every term except $n^6$ would be even, making the total odd. If $n$ is not divisible by $3,$ then modulo $3$ every term except $n^6$ vanishes while $n^6 \equiv 1 \pmod 3.$ So $n$ must be a multiple of $6.$

Write $n = 6k.$ Then $30n^4 = 720 \cdot 54k^4,$ $120n^3 = 720 \cdot 36k^3,$ and $360n^2 = 720 \cdot 18k^2$ are all divisible by $720,$ while $n^6 + 6n^5 = 6^6 k^5(k + 1).$ Since $6^6 = 2^6 3^6$ supplies the factors $2^4$ and $3^2$ of $720 = 2^4 \cdot 3^2 \cdot 5,$ the condition reduces to $k(k + 1)$ being divisible by $5,$ that is, $k \equiv 0$ or $4 \pmod 5.$

For $n = 6k \lt 2017$ we need $1 \le k \le 336.$ That range contains $67$ multiples of $5$ and $67$ values with $k \equiv 4 \pmod 5,$ so there are $67 + 67 = 134$ such $n.$

9.

一副特殊纸牌有 $49$ 张牌，每张牌标有 $1$ 到 $7$ 中的一个数字，并涂有七种颜色中的一种。每一种数字与颜色的组合恰好出现一次。Sharon 将从这副牌中随机选出八张。已知她至少有一张每种颜色的牌，且至少有一张每个数字的牌，Sharon 能够弃掉其中一张牌，并且仍然至少有一张每种颜色的牌且至少有一张每个数字的牌的概率为 $\frac{p}{q}$ ，其中 $p$ 和 $q$ 是互质的正整数。求 $p + q$ 。

A special deck of cards contains $49$ cards, each labeled with a number from $1$ to $7$ and colored with one of seven colors. Each number-color combination appears on exactly one card. Sharon will select a set of eight cards from the deck at random. Given that she gets at least one card of each color and at least one card with each number, the probability that Sharon can discard one of her cards and still have at least one card of each color and at least one card with each number is $\frac{p}{q},$ where $p$ and $q$ are relatively prime positive integers. Find $p + q.$

答案

答案：13

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

难度评级：2990

小提示：

这样的手牌中恰好有一个数字重复、一个颜色重复；只有当同一张牌同时承载这两个重复时，才可以弃掉一张牌

In such a hand exactly one number and exactly one color repeat; a card can be discarded only if a single card carries both repeats

大提示：

分别计数两类手牌：一组彩虹 $7$ 张牌加任意一张额外牌，以及重复数字和重复颜色落在四张不同牌上的手牌

Count each type of hand: a rainbow $7$ -card set plus any extra card, versus hands where the repeated number and repeated color sit on four distinct cards

解答：

因为八张牌覆盖全部七个数字和全部七种颜色，所以恰好有一个数字出现两次，且恰好有一种颜色出现两次。Sharon 能弃掉一张牌，当且仅当某一张牌同时带有重复的数字和重复的颜色：这张牌就是唯一可弃的牌；如果没有这样的牌，去掉任何一张都会失去某个数字或某种颜色。

第一类手牌由一组彩虹七张牌组成，也就是每个数字和每种颜色各出现一次，这样的对应方式有 $7!$ 种；再加上剩余 $42$ 张牌中的任意一张，并且每手牌只会这样产生一次。因此有 $7! \cdot 42 = 211680$ 手。第二类中，先选重复的数字（ $7$ 种）和它的两种颜色（ $\binom{7}{2} = 21$ 种）；重复的颜色必须是另外 $5$ 种颜色之一，它对应的两个数字来自剩下的 $6$ 个数字（ $\binom{6}{2} = 15$ 种）；最后把剩下四个数字匹配给剩下四种颜色（ $4! = 24$ 种）。共有 $7 \cdot 21 \cdot 5 \cdot 15 \cdot 24 = 264600$ 手。

所求概率为 $\frac{211680}{211680 + 264600} = \frac{4}{9}$ ，所以 $p + q = 4 + 9 = 13$ 。

Since the eight cards cover all seven numbers and all seven colors, exactly one number and exactly one color appear twice. Sharon can discard a card exactly when a single card carries both the repeated number and the repeated color: that card is then the unique discardable one, while if no card carries both, removing any card loses a number or a color.

Hands of the first type consist of a rainbow set of seven cards — one of each number and each color, which is one of $7!$ permutation patterns — plus any of the remaining $42$ cards, and every such hand arises exactly once this way: $7! \cdot 42 = 211680$ hands. For the second type, choose the repeated number ( $7$ ways) and the two colors of its cards ( $\binom{7}{2} = 21$ ways); the repeated color must be one of the other $5$ colors, and the numbers of its two cards come from the remaining $6$ numbers ( $\binom{6}{2} = 15$ ways); finally match the last four numbers to the last four colors ( $4! = 24$ ways). That is $7 \cdot 21 \cdot 5 \cdot 15 \cdot 24 = 264600$ hands.

The probability is $\frac{211680}{211680 + 264600} = \frac{4}{9},$ so $p + q = 4 + 9 = 13.$

10.

长方形 $ABCD$ 的边长为 $AB = 84$ 和 $AD = 42$ 。点 $M$ 是 $\overline{AD}$ 的中点，点 $N$ 是 $\overline{AB}$ 上靠近 $A$ 的三等分点，点 $O$ 是 $\overline{CM}$ 和 $\overline{DN}$ 的交点。点 $P$ 位于四边形 $BCON$ 上，且 $\overline{BP}$ 平分 $BCON$ 的面积。求 $\triangle CDP$ 的面积。

Rectangle $ABCD$ has side lengths $AB = 84$ and $AD = 42.$ Point $M$ is the midpoint of $\overline{AD},$ point $N$ is the trisection point of $\overline{AB}$ closer to $A,$ and point $O$ is the intersection of $\overline{CM}$ and $\overline{DN}.$ Point $P$ lies on the quadrilateral $BCON,$ and $\overline{BP}$ bisects the area of $BCON.$ Find the area of $\triangle CDP.$

答案

答案：546

知识点：坐标几何鞋带公式三角形面积

难度评级：2920

小提示：

使用坐标 $A(0,0)$ ， $B(84,0)$ ， $C(84,42)$ ， $D(0,42)$ ；直线 $CM$ 与 $DN$ 交于 $O(12, 24)$

Use coordinates $A(0,0),$ $B(84,0),$ $C(84,42),$ $D(0,42);$ the lines $CM$ and $DN$ meet at $O(12, 24)$

大提示：

$[BCON] = 2184$ ，而 $[BCO] = 1512$ ，所以 $P$ 位于 $\overline{CO}$ 上；令它满足 $[BPC] = 1092$

$[BCON] = 2184$ while $[BCO] = 1512,$ so $P$ lies on $\overline{CO};$ place it so that $[BPC] = 1092$

解答：

取 $A = (0, 0)$ ， $B = (84, 0)$ ， $C = (84, 42)$ ， $D = (0, 42)$ ，于是 $M = (0, 21)$ ， $N = (28, 0)$ 。直线 $CM$ 为 $y = \frac{x}{4} + 21$ ，直线 $DN$ 为 $y = 42 - \frac{3x}{2}$ ，两者交于 $O = (12, 24)$ 。

由鞋带公式，四边形 $BCON$ 的面积为 $2184$ ，所以每一半面积为 $1092$ 。单独的三角形 $BCO$ 面积为 $\frac{1}{2} \cdot 42 \cdot 72 = 1512 \gt 1092$ （底边为 $\overline{BC}$ ，且 $O$ 到它的水平距离为 $72$ ），所以平分面积的线段终点 $P$ 在 $\overline{CO}$ 上。若 $[BPC] = 1092$ ，则 $P$ 到直线 $BC$ 的距离 $d$ 满足 $\frac{1}{2} \cdot 42 \cdot d = 1092$ ，所以 $d = 52$ ，从而 $P$ 的 $x$ -坐标为 $84 - 52 = 32$ 。因为 $P$ 位于直线 $CO$ 上，而该直线的方程为 $y = \frac{x}{4} + 21$ ，所以 $P = (32, 29)$ 。

三角形 $CDP$ 的底 $CD = 84$ 在直线 $y = 42$ 上，高为 $42 - 29 = 13$ ，所以面积为 $\frac{1}{2} \cdot 84 \cdot 13 = 546$ 。

Place $A = (0, 0),$ $B = (84, 0),$ $C = (84, 42),$ $D = (0, 42),$ so $M = (0, 21)$ and $N = (28, 0).$ Line $CM$ is $y = \frac{x}{4} + 21$ and line $DN$ is $y = 42 - \frac{3x}{2},$ which meet at $O = (12, 24).$

By the Shoelace Formula, quadrilateral $BCON$ has area $2184,$ so each half must have area $1092.$ Triangle $BCO$ alone has area $\frac{1}{2} \cdot 42 \cdot 72 = 1512 \gt 1092$ (base $\overline{BC},$ and $O$ is at horizontal distance $72$ from it), so the bisecting segment ends at a point $P$ on $\overline{CO}.$ For $[BPC] = 1092,$ the distance $d$ from $P$ to line $BC$ must satisfy $\frac{1}{2} \cdot 42 \cdot d = 1092,$ so $d = 52,$ giving $P$ the $x$ -coordinate $84 - 52 = 32.$ Since $P$ lies on line $CO,$ which is $y = \frac{x}{4} + 21,$ we get $P = (32, 29).$

Triangle $CDP$ has base $CD = 84$ on the line $y = 42$ and height $42 - 29 = 13,$ so its area is $\frac{1}{2} \cdot 84 \cdot 13 = 546.$

11.

五个城镇由道路系统连接。每一对城镇之间恰好有一条道路。求有多少种方法把所有道路改成单行道，使得仍然可以从任意一个城镇沿道路到达任意另一个城镇（途中可以经过其他城镇）。

Five towns are connected by a system of roads. There is exactly one road connecting each pair of towns. Find the number of ways there are to make all the roads one-way in such a way that it is still possible to get from any town to any other town using the roads (possibly passing through other towns on the way).

答案

答案：544

知识点：图论补集计数容斥原理

难度评级：3060

小提示：

这些单行道可行，当且仅当没有任何城镇的四条道路全都指向它，或全都从它指出

The one-way roads work if and only if no town has all four of its roads inbound or all four outbound

大提示：

计数不可行的方向分配：有一个全出城镇的有 $5 \cdot 2^6$ 种，全入城镇同样多；再减去被重复计数的 $5 \cdot 4 \cdot 2^3$ 种

Count the bad assignments: $5 \cdot 2^6$ with an all-outbound town, the same with an all-inbound town, minus $5 \cdot 4 \cdot 2^3$ counted twice

解答：

方向分配可行，当且仅当没有城镇的四条道路全入或全出。一方面很明显：全入的城镇无法离开，全出的城镇无法到达。反过来，假设每个城镇都有入路和出路，但从城镇 $A$ 无法到达城镇 $B$ 。令 $S$ 为从 $A$ 可到达的城镇集合（包括 $A$ ），令 $T$ 为可以到达 $B$ 的城镇集合（包括 $B$ ）。这两个集合不相交， $S$ 中城镇的每条出路都仍留在 $S$ 中， $T$ 中城镇的每条入路都来自 $T$ 中。因为 $A$ 有出路，所以 $|S| \ge 2$ ，同理 $|T| \ge 2$ ；又因为 $|S| + |T| \le 5$ ，两个集合中有一个恰好有两个城镇。若 $S = \{A, X\}$ ，则 $A$ 和 $X$ 的出路都必须留在 $S$ 内，迫使它们之间唯一的道路同时指向两个方向，产生矛盾（ $|T| = 2$ 的情况对称）。

现在在 $2^{10} = 1024$ 种总方向分配中计数含有全入或全出城镇的情况。选择一个城镇全出（ $5$ 种），剩余 $\binom{4}{2} = 6$ 条道路任意定向，得到 $5 \cdot 2^6 = 320$ 种分配；并且全出城镇最多只有一个。同理，有全入城镇的分配也有 $320$ 种。同时有全出和全入城镇的分配被重复计数：选全出城镇（ $5$ 种），选全入城镇（ $4$ 种），其他 $3$ 条道路任意定向，有 $5 \cdot 4 \cdot 2^3 = 160$ 种。因此不符合条件的分配有 $320 + 320 - 160 = 480$ 种。

可行的数量为 $1024 - 480 = 544$ 。

The assignment works if and only if no town has all four roads inbound or all four outbound. One direction is clear: an all-inbound town cannot be left, and an all-outbound town cannot be reached. Conversely, suppose every town has an inbound and an outbound road, yet town $B$ cannot be reached from town $A.$ Let $S$ be the set of towns reachable from $A$ (including $A$ ) and $T$ the set of towns from which $B$ is reachable (including $B$ ). These sets are disjoint, every outbound road of a town in $S$ stays inside $S,$ and every inbound road of a town in $T$ comes from inside $T.$ Since $A$ has an outbound road, $|S| \ge 2,$ and similarly $|T| \ge 2;$ as $|S| + |T| \le 5,$ one of the two sets has exactly two towns. If $S = \{A, X\},$ the outbound roads of $A$ and of $X$ must both stay inside $S,$ forcing the single road between them to point both ways — a contradiction (and $|T| = 2$ is symmetric).

Now count assignments with a bad town among the $2^{10} = 1024$ total. Choosing a town to be all-outbound ( $5$ ways) and orienting the remaining $\binom{4}{2} = 6$ roads freely gives $5 \cdot 2^6 = 320$ assignments, and there can be at most one all-outbound town. Similarly $320$ assignments have an all-inbound town. Assignments with both are counted twice: choose the all-outbound town ( $5$ ), the all-inbound town ( $4$ ), and the other $3$ roads freely, $5 \cdot 4 \cdot 2^3 = 160.$ So $320 + 320 - 160 = 480$ assignments fail.

The number that work is $1024 - 480 = 544.$

12.

圆 $C_0$ 的半径为 $1$ ，点 $A_0$ 在该圆上。圆 $C_1$ 的半径为 $r \lt 1$ ，且在点 $A_0$ 处内切于 $C_0$ 。点 $A_1$ 位于圆 $C_1$ 上，并且 $A_1$ 在 $C_1$ 上从 $A_0$ 逆时针转过 $90^\circ$ 的位置。圆 $C_2$ 的半径为 $r^2$ ，且在点 $A_1$ 处内切于 $C_1$ 。按这种方式构造一列圆 $C_1$ 、 $C_2$ 、 $C_3$ 、 $\ldots$ 和一列圆上的点 $A_1$ 、 $A_2$ 、 $A_3$ 、 $\ldots$ ：圆 $C_n$ 的半径为 $r^n$ ，并在点 $A_{n-1}$ 处内切于圆 $C_{n-1}$ ，而点 $A_n$ 位于 $C_n$ 上，且相对于点 $A_{n-1}$ 逆时针转过 $90^\circ$ ，如下图所示。有一个点 $B$ 位于所有这些圆的内部。当 $r = \frac{11}{60}$ 时，从 $C_0$ 的圆心到 $B$ 的距离为 $\frac{m}{n}$ ，其中 $m$ 和 $n$ 是互质的正整数。求 $m + n$ 。

Circle $C_0$ has radius $1,$ and the point $A_0$ is a point on the circle. Circle $C_1$ has radius $r \lt 1$ and is internally tangent to $C_0$ at point $A_0.$ Point $A_1$ lies on circle $C_1$ so that $A_1$ is located $90^\circ$ counterclockwise from $A_0$ on $C_1.$ Circle $C_2$ has radius $r^2$ and is internally tangent to $C_1$ at point $A_1.$ In this way a sequence of circles $C_1,$ $C_2,$ $C_3,$ $\ldots$ and a sequence of points on the circles $A_1,$ $A_2,$ $A_3,$ $\ldots$ are constructed, where circle $C_n$ has radius $r^n$ and is internally tangent to circle $C_{n-1}$ at point $A_{n-1},$ and point $A_n$ lies on $C_n$ $90^\circ$ counterclockwise from point $A_{n-1},$ as shown in the figure below. There is one point $B$ inside all of these circles. When $r = \frac{11}{60},$ the distance from the center of $C_0$ to $B$ is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

答案

答案：110

知识点：复数等比数列相切圆

难度评级：3060

小提示：

在复平面中， $C_{n+1}$ 的圆心等于 $C_n$ 的圆心加上 $(r^n - r^{n+1})\,i^n$

In the complex plane the center of $C_{n+1}$ equals the center of $C_n$ plus $(r^n - r^{n+1})\,i^n$

大提示：

圆心趋近于等比级数和 $\frac{1-r}{1-ir}$ ，它到原点的距离是 $\frac{1-r}{\sqrt{1+r^2}}$

The centers converge to the geometric series sum $\frac{1-r}{1-ir},$ whose distance from the origin is $\frac{1-r}{\sqrt{1+r^2}}$

解答：

在复平面中工作，令 $C_0$ 的圆心为 $O_0 = 0$ ，并令 $A_0 = 1$ ，设 $O_n$ 为 $C_n$ 的圆心。归纳可得 $A_n = O_n + r^n i^n$ ：当 $n = 0$ 时成立；若 $C_{n+1}$ 在 $A_n$ 处内切于 $C_n$ ，则它的圆心为 $O_{n+1} = A_n - r^{n+1} i^n$ ；此时从 $O_{n+1}$ 看， $A_n$ 位于方向 $i^n$ 上，因而逆时针旋转 $90^\circ$ 后有 $A_{n+1} = O_{n+1} + r^{n+1} i^{n+1}$ 。

因此 $O_{n+1} - O_n$ $= (r^n - r^{n+1})\, i^n$ $= (1 - r)(ir)^n$ 。这些圆是嵌套的，且半径趋于 $0$ ，所以公共点 $B$ 是圆心的极限： $B = (1 - r)\sum_{n=0}^{\infty} (ir)^n = \frac{1 - r}{1 - ir}\text{，}$ 它到原点的距离为 $\frac{1 - r}{|1 - ir|} = \frac{1 - r}{\sqrt{1 + r^2}}$ 。

当 $r = \frac{11}{60}$ 时，这个距离为 $\frac{\frac{49}{60}}{\frac{\sqrt{3721}}{60}} = \frac{49}{61}$ ，所以 $m + n = 49 + 61 = 110$ 。

Work in the complex plane with $C_0$ centered at $O_0 = 0$ and $A_0 = 1,$ and let $O_n$ be the center of $C_n.$ Inductively, $A_n = O_n + r^n i^n:$ this holds for $n = 0,$ and since $C_{n+1}$ is internally tangent to $C_n$ at $A_n,$ its center is $O_{n+1} = A_n - r^{n+1} i^n;$ then $A_n$ sits in direction $i^n$ from $O_{n+1},$ so rotating $90^\circ$ counterclockwise gives $A_{n+1} = O_{n+1} + r^{n+1} i^{n+1}.$

Therefore $O_{n+1} - O_n$ $= (r^n - r^{n+1})\, i^n$ $= (1 - r)(ir)^n.$ The circles are nested, and their radii shrink to $0,$ so the common point $B$ is the limit of the centers: $B = (1 - r)\sum_{n=0}^{\infty} (ir)^n = \frac{1 - r}{1 - ir},$ at distance $\frac{1 - r}{|1 - ir|} = \frac{1 - r}{\sqrt{1 + r^2}}$ from the origin.

For $r = \frac{11}{60}$ this equals $\frac{\frac{49}{60}}{\frac{\sqrt{3721}}{60}} = \frac{49}{61},$ so $m + n = 49 + 61 = 110.$

13.

对每个整数 $n \ge 3$ ，令 $f(n)$ 表示一个正 $n$ 边形的顶点中，由 $3$ 个顶点组成且能构成等腰三角形（包括等边三角形）的子集数量。求所有满足 $f(n+1) = f(n) + 78$ 的 $n$ 的和。

For each integer $n \ge 3,$ let $f(n)$ be the number of $3$ -element subsets of the vertices of a regular $n$ -gon that are the vertices of an isosceles triangle (including equilateral triangles). Find the sum of all values of $n$ such that $f(n+1) = f(n) + 78.$

答案

答案：245

知识点：正多边形图形中的形状计数取整函数分类讨论

难度评级：3270

小提示：

按顶角计数：每个顶点作为顶角时有 $\lfloor \frac{n-1}{2} \rfloor$ 个等腰三角形，但等边三角形会被数三次

Count by apex: each vertex is the apex of $\lfloor \frac{n-1}{2} \rfloor$ isosceles triangles, but equilateral triangles get counted three times

大提示：

用一个下取整函数写出 $f(n)$ ，再按 $n$ 模 $6$ 的各个余数分别计算 $f(n+1) - f(n)$

Write $f(n)$ with a floor function and compute $f(n+1) - f(n)$ separately in each residue class of $n$ modulo $6$

解答：

按顶角计数等腰三角形。对于正 $n$ 边形的一个顶点 $P$ ，两条相等边在 $P$ 相交的等腰三角形，其另外两个顶点关于过 $P$ 的直径对称，因此有 $\lfloor \frac{n-1}{2} \rfloor$ 对。对所有 $n$ 个顶点求和时，每个非等边的等腰三角形被数一次（它只有一个顶角），每个等边三角形被数三次；等边三角形恰好在 $n$ 是 $3$ 的倍数时存在，此时有 $\frac{n}{3}$ 个。因此 $f(n) = n \lfloor \frac{n-1}{2} \rfloor$ ，但当 $n$ 是 $3$ 的倍数时要减去 $\frac{2n}{3}$ 。

写 $n = 6k + j$ ，并在每个余数类中计算 $f(n+1) - f(n)$ ，得到当 $j = 0$ 时为 $13k$ ，当 $j = 1$ 时为 $3k$ ，当 $j = 2$ 时为 $5k + 1$ ，当 $j = 3$ 时为 $7k + 3$ ，当 $j = 4$ 时为 $9k + 6$ ，当 $j = 5$ 时为 $-(k + 2)$ 。分别令它们等于 $78$ ： $13k = 78$ 给出 $k = 6$ ， $n = 36$ ； $3k = 78$ 给出 $k = 26$ ， $n = 157$ ； $9k + 6 = 78$ 给出 $k = 8$ ， $n = 52$ ；另外三种情况没有正整数解。

所有这样的 $n$ 的和为 $36 + 157 + 52 = 245$ 。

Count isosceles triangles by apex. For a vertex $P$ of a regular $n$ -gon, the isosceles triangles whose two equal sides meet at $P$ have their other two vertices symmetric about the diameter through $P,$ giving $\lfloor \frac{n-1}{2} \rfloor$ such pairs. Summing over all $n$ vertices counts each non-equilateral isosceles triangle once (it has one apex) and each equilateral triangle three times; equilateral triangles exist exactly when $n$ is a multiple of $3,$ and then there are $\frac{n}{3}$ of them. Hence $f(n) = n \lfloor \frac{n-1}{2} \rfloor,$ minus $\frac{2n}{3}$ when $n$ is a multiple of $3.$

Writing $n = 6k + j$ and computing $f(n+1) - f(n)$ in each residue class gives $13k$ for $j = 0,$ $3k$ for $j = 1,$ $5k + 1$ for $j = 2,$ $7k + 3$ for $j = 3,$ $9k + 6$ for $j = 4,$ and $-(k + 2)$ for $j = 5.$ Setting each equal to $78:$ $13k = 78$ gives $k = 6,$ $n = 36;$ $3k = 78$ gives $k = 26,$ $n = 157;$ $9k + 6 = 78$ gives $k = 8,$ $n = 52;$ and the other three cases have no positive integer solutions.

The sum of all such $n$ is $36 + 157 + 52 = 245.$

14.

一个 $10 \times 10 \times 10$ 的点阵由空间中所有形如 $(i, j, k)$ 的点组成，其中 $i$ 、 $j$ 和 $k$ 是从 $1$ 到 $10$ （含端点）的整数。求恰好包含这些点中 $8$ 个点的不同直线数量。

A $10 \times 10 \times 10$ grid of points consists of all points in space of the form $(i, j, k),$ where $i,$ $j,$ and $k$ are integers between $1$ and $10,$ inclusive. Find the number of different lines that contain exactly $8$ of these points.

答案

答案：168

知识点：格点立体几何分类讨论对称性

难度评级：3370

小提示：

一条恰好含有 $8$ 个点的直线，要么位于一个平行于立方体面的平面中，要么方向为 $(\pm 1, \pm 1, \pm 1)$

A line with exactly $8$ points either lies in a plane parallel to a face of the cube or has direction $(\pm 1, \pm 1, \pm 1)$

大提示：

平行于立方体面的平面共有 $30$ 个，每个平面有 $4$ 条平移后的对角线含 $8$ 个点；对方向 $(1,1,1)$ ，计数坐标在 $\{1, 2, 3\}$ 中且同时用到 $1$ 和 $3$ 的起点

Each of the $30$ face-parallel planes has $4$ shifted diagonals with $8$ points; for direction $(1,1,1)$ count start points with coordinates in $\{1, 2, 3\}$ using both $1$ and $3$

解答：

取直线的本原方向向量为 $(a, b, c)$ 。任何非零分量的绝对值若至少为 $2$ ，这条线最多只能穿过 $5$ 个点阵点，所以每个分量只能是 $0$ 或 $\pm 1$ 。平行于坐标轴的直线含有 $10$ 个点，不会恰好含有 $8$ 个点。若恰有一个分量为 $0$ ，这条线位于 $30$ 个平行于立方体面的平面之一（ $3$ 种方向， $10$ 个位置）中；在这个 $10 \times 10$ 网格内，它是斜率为 $\pm 1$ 的对角线，并从中心对角线平移开。对两条主对角线各向两个方向平移 $2$ 都恰好得到 $8$ 个点。因此每个平面有 $4$ 条这样的线，并且每条只属于这 $30$ 个平面中的一个： $4 \cdot 30 = 120$ 条。

否则方向是四个空间对角线方向 $(1, \pm 1, \pm 1)$ 之一（不区分整体反向）；由对称性，只需计数平行于 $(1, 1, 1)$ 的直线再乘以 $4$ 。这样的直线 $(d + t,\ e + t,\ f + t)$ 与点阵相交于 $10$ $- (\max(d,e,f) - \min(d,e,f))$ 个点，因此恰好 $8$ 个点意味着 $\max - \min = 2$ 。把基点规范化为 $\min(d, e, f) = 1$ ，需要 $(d, e, f)$ 的各项在 $\{1, 2, 3\}$ 中并且同时用到 $1$ 和 $3$ ：共有 $27 - 8 - 8 + 1 = 12$ 个，因此每个方向有 $12$ 条线，总共 $4 \cdot 12 = 48$ 条。

总数为 $120 + 48 = 168$ 。

Take a primitive direction vector $(a, b, c)$ for the line. Any nonzero component of absolute value $2$ or more limits the line to at most $5$ grid points, so every component is $0$ or $\pm 1.$ Lines parallel to a coordinate axis contain $10$ points, never $8.$ If exactly one component is $0,$ the line lies in one of the $30$ planes parallel to a face of the cube ( $3$ orientations, $10$ positions), and within that $10 \times 10$ grid it is a diagonal of slope $\pm 1$ shifted off center; the shift by $2$ in either direction from each of the two main diagonals gives exactly $8$ points. That is $4$ lines per plane, and each lies in only one of the $30$ planes: $4 \cdot 30 = 120$ lines.

Otherwise the direction is one of the four space-diagonal directions $(1, \pm 1, \pm 1)$ up to sign; by symmetry, count lines parallel to $(1, 1, 1)$ and multiply by $4.$ Such a line $(d + t,\ e + t,\ f + t)$ meets the grid in $10$ $- (\max(d,e,f) - \min(d,e,f))$ points, so exactly $8$ points means $\max - \min = 2.$ Normalizing the base point so that $\min(d, e, f) = 1,$ we need $(d, e, f)$ with entries in $\{1, 2, 3\}$ using both $1$ and $3:$ there are $27 - 8 - 8 + 1 = 12$ of them, hence $12$ lines per direction and $4 \cdot 12 = 48$ in all.

The total is $120 + 48 = 168.$

15.

四面体 $ABCD$ 满足 $AD = BC = 28$ ， $AC = BD = 44$ ，且 $AB = CD = 52$ 。对空间中任意点 $X$ ，定义 $f(X) = AX + BX$ $+ CX + DX$ 。 $f(X)$ 的最小可能值可表示为 $m\sqrt{n}$ ，其中 $m$ 和 $n$ 是正整数，且 $n$ 不被任何质数的平方整除。求 $m + n$ 。

Tetrahedron $ABCD$ has $AD = BC = 28,$ $AC = BD = 44,$ and $AB = CD = 52.$ For any point $X$ in space, define $f(X) = AX + BX$ $+ CX + DX.$ The least possible value of $f(X)$ can be expressed as $m\sqrt{n},$ where $m$ and $n$ are positive integers, and $n$ is not divisible by the square of any prime. Find $m + n.$

答案

答案：682

知识点：立体几何中线（几何）三角不等式对称性

难度评级：3500

小提示：

$\overline{AB}$ 的中点 $M$ 和 $\overline{CD}$ 的中点 $N$ 位于这两条边的公共垂直平分线上，且对于直线 $MN$ 上的某点 $Q$ 有 $f(X) \ge f(Q)$

The midpoints $M$ of $\overline{AB}$ and $N$ of $\overline{CD}$ lie on the common perpendicular bisector of those edges, and $f(X) \ge f(Q)$ for a point $Q$ on line $MN$

大提示：

把 $D$ 绕直线 $MN$ 旋转到平面 $AMN$ 中：此时 $f(Q) = 2(AQ + D'Q) \ge 2AD'$ ，再用中线长公式求 $AD'$

Rotate $D$ about line $MN$ into the plane $AMN:$ then $f(Q) = 2(AQ + D'Q) \ge 2AD',$ and the median length formula gives $AD'$

解答：

令 $M$ 和 $N$ 分别为 $\overline{AB}$ 和 $\overline{CD}$ 的中点。从 $C$ 和从 $D$ 到 $\overline{AB}$ 的中线相等，因为三角形 $ABC$ 和 $BAD$ 由边边边（ $SSS$ ）判定全等。由中线长公式， $4MD^2 = 2 \cdot 28^2 + 2 \cdot 44^2$ $- 52^2$ $= 2736$ ，所以 $MC^2 = MD^2 = 684$ 。同理 $NA = NB$ 。于是 $MN$ ，作为等腰三角形 $MCD$ 和 $NAB$ 的中线，分别垂直于 $\overline{AB}$ 和 $\overline{CD}$ ，所以绕直线 $MN$ 的 $180^\circ$ 旋转会交换 $A \leftrightarrow B$ 和 $C \leftrightarrow D$ 。另外 $MN^2 = MD^2 - ND^2$ $= 684 - 26^2$ $= 8$ 。

对任意点 $X$ ，令 $X'$ 为它在该旋转下的像，并令 $\overline{XX'}$ 的中点为 $Q$ ，该点位于直线 $MN$ 上。此时 $BX = AX'$ ，且 $CX = DX'$ ，所以 $\begin{aligned} &f(X) = (AX + AX') \\ &{}+ (DX + DX') \\ &\ge 2AQ + 2DQ = f(Q) \end{aligned}\text{，}$ 因为三角形的一条中线不超过相邻两边之和的一半。因此只需在直线 $MN$ 上的点 $Q$ 中最小化 $f(Q) = 2(AQ + DQ)$ 。

把 $D$ 绕直线 $MN$ 旋转到 $A$ 与直线 $MN$ 所在的平面内，并落在 $MN$ 相对于 $A$ 的另一侧，得到点 $D'$ ，其中 $ND' = ND = 26$ 。对于直线 $MN$ 上的 $Q$ ， $AQ + DQ = AQ + D'Q \ge AD'$ ，当线段 $\overline{AD'}$ 与 $MN$ 相交时取等号。因为 $AM \perp MN$ 且 $D'N \perp MN$ ，并且 $AM = 26$ ， $ND' = 26$ ， $\begin{aligned} &AD'^2 = (AM + ND')^2 + MN^2 \\ &= 52^2 + 8 = 2712 \\ &= 4 \cdot 678 \end{aligned}\text{。}$ 因此 $f$ 的最小值为 $2AD' = 4\sqrt{678}$ ，而 $678 = 2 \cdot 3 \cdot 113$ 无平方因子，所以 $m + n = 4 + 678 = 682$ 。

Let $M$ and $N$ be the midpoints of $\overline{AB}$ and $\overline{CD}.$ The medians from $C$ and from $D$ to $\overline{AB}$ are equal, since triangles $ABC$ and $BAD$ are congruent by $SSS;$ by the median length formula, $4MD^2 = 2 \cdot 28^2 + 2 \cdot 44^2$ $- 52^2$ $= 2736,$ so $MC^2 = MD^2 = 684.$ Likewise $NA = NB.$ Then $MN,$ as a median of the isosceles triangles $MCD$ and $NAB,$ is perpendicular to both $\overline{AB}$ and $\overline{CD},$ so the $180^\circ$ rotation about line $MN$ swaps $A \leftrightarrow B$ and $C \leftrightarrow D.$ Also $MN^2 = MD^2 - ND^2$ $= 684 - 26^2$ $= 8.$

For any point $X,$ let $X'$ be its image under this rotation, and let $Q$ be the midpoint of $\overline{XX'},$ which lies on line $MN.$ Then $BX = AX'$ and $CX = DX',$ so $\begin{aligned} &f(X) = (AX + AX') \\ &{}+ (DX + DX') \\ &\ge 2AQ + 2DQ = f(Q), \end{aligned}$ because a median of a triangle is at most half the sum of the two adjacent sides. So it suffices to minimize $f(Q) = 2(AQ + DQ)$ over points $Q$ on line $MN.$

Rotate $D$ about line $MN$ into the plane of $A$ and line $MN,$ on the opposite side of $MN$ from $A,$ landing at $D'$ with $ND' = ND = 26.$ For $Q$ on line $MN,$ $AQ + DQ = AQ + D'Q \ge AD',$ with equality where segment $\overline{AD'}$ crosses $MN.$ Since $AM \perp MN$ and $D'N \perp MN$ with $AM = 26$ and $ND' = 26,$ $\begin{aligned} &AD'^2 = (AM + ND')^2 + MN^2 \\ &= 52^2 + 8 = 2712 \\ &= 4 \cdot 678. \end{aligned}$ Hence the minimum of $f$ is $2AD' = 4\sqrt{678},$ and since $678 = 2 \cdot 3 \cdot 113$ is squarefree, $m + n = 4 + 678 = 682.$