1998 AIME 详解 | LIVE by Po-Shen Loh

1.

有多少个 $k$ 值，使 $12^{12}$ 是正整数 $6^6$ 、 $8^8$ 和 $k$ 的最小公倍数？

For how many values of $k$ is $12^{12}$ the least common multiple of the positive integers $6^6,$ $8^8,$ and $k?$

答案

知识点：最小公倍数质因数分解

难度评级：1890

小提示：

把所有数都分解成 $2$ 和 $3$ 的幂： $12^{12} = 2^{24} 3^{12}$ ， $6^6 = 2^6 3^6$ ， $8^8 = 2^{24}$

Factor everything into powers of $2$ and $3:$ $12^{12} = 2^{24} 3^{12},$ $6^6 = 2^6 3^6,$ $8^8 = 2^{24}$

大提示：

$6^6$ 和 $8^8$ 的最小公倍数已经提供了 $2^{24}$ ，但只提供 $3^6$ ，所以 $k$ 必须恰好提供 $3^{12}$

The lcm of $6^6$ and $8^8$ already supplies $2^{24}$ but only $3^6,$ so $k$ must contribute exactly $3^{12}$

解答：

因为 $12^{12} = 2^{24} 3^{12}$ ， $6^6 = 2^6 3^6$ ，且 $8^8 = 2^{24}$ ，所以 $k$ 不能含有 $2$ 和 $3$ 以外的质因数。设 $k = 2^a 3^b$ 。这三个数的最小公倍数为 $2^{\max(24,\,a)} \, 3^{\max(6,\,b)}$ 。

要等于 $2^{24} 3^{12}$ ，必须有 $\max(24, a) = 24$ ，即 $0 \le a \le 24$ ，并且 $\max(6, b) = 12$ ，即 $b = 12$ 。这样共有 $25$ 种 $a$ 的选择， $b$ 有一种选择，所以共有 $25$ 个 $k$ 的值。

Since $12^{12} = 2^{24} 3^{12},$ $6^6 = 2^6 3^6,$ and $8^8 = 2^{24},$ the number $k$ can involve no primes other than $2$ and $3,$ so write $k = 2^a 3^b.$ The least common multiple of the three numbers is then $2^{\max(24,\,a)} \, 3^{\max(6,\,b)}.$

Matching this to $2^{24} 3^{12}$ requires $\max(24, a) = 24,$ i.e. $0 \le a \le 24,$ and $\max(6, b) = 12,$ i.e. $b = 12.$ That gives $25$ choices for $a$ and one for $b,$ so there are $25$ values of $k.$

2.

求正整数有序对 $(x, y)$ 的个数，其中 $x \le 2y \le 60$ 且 $y \le 2x \le 60$ 。

Find the number of ordered pairs $(x, y)$ of positive integers that satisfy $x \le 2y \le 60$ and $y \le 2x \le 60.$

答案

知识点：数对计数不等式补集计数对称性

难度评级：2110

小提示：

四个限制条件合起来把 $(x, y)$ 限制在正方形 $1 \le x, y \le 30$ 中

All four constraints together confine $(x, y)$ to the square $1 \le x, y \le 30$

大提示：

在这个正方形内，减去满足 $y \gt 2x$ 的有序对和满足 $x \gt 2y$ 的有序对；这两个不合格集合互不相交且大小相同

Inside that square, subtract the pairs with $y \gt 2x$ and those with $x \gt 2y;$ the two bad sets are disjoint and have equal size

解答：

两个链式不等式展开为四个条件： $x \le 2y$ 、 $2y \le 60$ 、 $y \le 2x$ 和 $2x \le 60$ 。所以 $(x, y)$ 位于正方形 $1 \le x, y \le 30$ 内，并且要排除 $x \gt 2y$ 和 $y \gt 2x$ ，这两个条件不可能同时发生。

对于满足 $y \gt 2x$ 的有序对，当 $x$ 从 $1$ 到 $14$ 时， $y = 2x + 1, \ldots, 30$ 都可行，因此共有 $\sum_{x=1}^{14} (30 - 2x)$ $= 420 - 210$ $= 210$ 对。由交换 $x$ 与 $y$ 的对称性，也有 $210$ 对满足 $x \gt 2y$ 的有序对。

所以答案是 $30 \cdot 30 - 210 - 210 = 480$ 。

The chains unpack into four conditions: $x \le 2y,$ $2y \le 60,$ $y \le 2x,$ and $2x \le 60.$ So $(x, y)$ lies in the square $1 \le x, y \le 30,$ and within it we must avoid $x \gt 2y$ and $y \gt 2x,$ which cannot both happen.

Pairs with $y \gt 2x:$ for each $x$ from $1$ to $14$ the values $y = 2x + 1, \ldots, 30$ work, giving $\sum_{x=1}^{14} (30 - 2x)$ $= 420 - 210$ $= 210$ pairs. By the symmetry swapping $x$ and $y,$ there are also $210$ pairs with $x \gt 2y.$

The answer is $30 \cdot 30 - 210 - 210 = 480.$

3.

方程 $y^2 + 2xy + 40|x| = 400$ 的图像把平面分成若干区域。求有界区域的面积。

The graph of $y^2 + 2xy + 40|x| = 400$ partitions the plane into several regions. What is the area of the bounded region?

答案

知识点：绝对值坐标几何因式分解平行四边形

难度评级：2340

小提示：

当 $x \ge 0$ 时，方程可整理为 $2x(y + 20) = 400 - y^2$ ，右边可以因式分解

For $x \ge 0$ the equation rearranges to $2x(y + 20) = 400 - y^2,$ and the right side factors

大提示：

每种符号情形都会给出两条直线；这四条射线围成一个平行四边形，其水平边在 $y = 20$ 和 $y = -20$ 上

Each sign case yields two lines; the four rays bound a parallelogram with horizontal sides on $y = 20$ and $y = -20$

解答：

当 $x \ge 0$ 时，把方程改写为 $2x(y + 20)$ $= 400 - y^2$ $= (20 - y)(20 + y)$ ，所以 $y = -20$ 或 $y = 20 - 2x$ 。当 $x \le 0$ 时，方程变为 $2x(y - 20) = -(y - 20)(y + 20)$ ，所以 $y = 20$ 或 $y = -20 - 2x$ 。因此图像由两条水平射线和两条斜率为 $-2$ 的射线组成。

这些射线围成一个平行四边形：上边从 $(-20, 20)$ 到 $(0, 20)$ ，在 $y = 20$ 上；下边从 $(0, -20)$ 到 $(20, -20)$ ，在 $y = -20$ 上；两条斜率为 $-2$ 的斜边把它们连接起来。

这个平行四边形的水平底为 $20$ ，高为 $40$ ，也就是两条直线 $y = 20$ 和 $y = -20$ 之间的距离，所以面积为 $20 \cdot 40 = 800$ 。

For $x \ge 0$ rewrite the equation as $2x(y + 20)$ $= 400 - y^2$ $= (20 - y)(20 + y),$ so either $y = -20$ or $y = 20 - 2x.$ For $x \le 0$ it becomes $2x(y - 20) = -(y - 20)(y + 20),$ so either $y = 20$ or $y = -20 - 2x.$ The graph therefore consists of two horizontal rays and two rays of slope $-2.$

These rays bound a parallelogram: the top edge runs from $(-20, 20)$ to $(0, 20)$ along $y = 20,$ the bottom edge from $(0, -20)$ to $(20, -20)$ along $y = -20,$ and the two slanted edges of slope $-2$ connect them.

The parallelogram has horizontal base $20$ and height $40$ between the lines $y = 20$ and $y = -20,$ so its area is $20 \cdot 40 = 800.$

4.

九张牌分别编号为 $1$ 、 $2$ 、 $3$ 、 $\ldots$ 、 $9$ 。三名玩家各自随机选择并保留三张牌，然后求自己三张牌上的数之和。三名玩家所得和全为奇数的概率为 $\frac{m}{n}$ ，其中 $m$ 和 $n$ 是互质正整数。求 $m + n$ 。

Nine tiles are numbered $1,$ $2,$ $3,$ $\ldots,$ $9,$ respectively. Each of three players randomly selects and keeps three of the tiles, and sums those three values. The probability that all three players obtain an odd sum is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

答案

知识点：基本概率奇偶性组合

难度评级：2350

小提示：

一名玩家的和为奇数，当且仅当他拿到奇数张奇数牌；总共有五张奇数牌

A player’s sum is odd exactly when the player holds an odd number of odd tiles; there are five odd tiles in all

大提示：

奇数牌必须按 $3$ 、 $1$ 、 $1$ 分给三名玩家。分别计算奇数牌和偶数牌的分配方式。

The odd tiles must split $3,$ $1,$ $1$ among the players. Count the ways to deal odds and evens separately.

解答：

一名玩家的三张牌之和为奇数，当且仅当他拿到奇数张奇数牌，也就是一张或三张。九张牌中有五张奇数牌和四张偶数牌，把五张奇数牌分到三个组中且每组奇数牌数为一或三，唯一的分法类型是 $3 + 1 + 1$ 。

计算有利的发牌方式：选择哪名玩家得到三张奇数牌，有 $3$ 种；选择这名玩家的三张奇数牌，有 $\binom{5}{3} = 10$ 种；把剩下两张奇数牌各给另外两名玩家，有 $2$ 种；再把四张偶数牌按二二分给这两名玩家，有 $\binom{4}{2} = 6$ 种。因此有利发牌方式为 $3 \cdot 10 \cdot 2 \cdot 6 = 360$ 种。总发牌方式为 $\binom{9}{3}\binom{6}{3} = 84 \cdot 20 = 1680$ 种。

概率为 $\frac{360}{1680} = \frac{3}{14}$ ，所以 $m + n = 3 + 14 = 17$ 。

A player’s three tiles have an odd sum exactly when the player holds an odd number of odd tiles — one or three. The nine tiles include five odd and four even, and the only way to split five odd tiles into three groups of size one or three is $3 + 1 + 1.$

Count favorable deals: choose which player gets three odd tiles ( $3$ ways), choose that player’s odd tiles ( $\binom{5}{3} = 10$ ways), give one of the two remaining odd tiles to each other player ( $2$ ways), then split the four even tiles two and two between those players ( $\binom{4}{2} = 6$ ways), for $3 \cdot 10 \cdot 2 \cdot 6 = 360$ deals. The total number of deals is $\binom{9}{3}\binom{6}{3} = 84 \cdot 20 = 1680.$

The probability is $\frac{360}{1680} = \frac{3}{14},$ so $m + n = 3 + 14 = 17.$

5.

已知 $A_k = \frac{k(k - 1)}{2}\cos\frac{k(k - 1)\pi}{2}$ ，求 $|A_{19} + A_{20} + \cdots + A_{98}|$ 。

Given that $A_k = \frac{k(k - 1)}{2}\cos\frac{k(k - 1)\pi}{2},$ find $|A_{19} + A_{20} + \cdots + A_{98}|.$

答案

知识点：三角形数奇偶性求和配对与分组

难度评级：2400

小提示：

$\frac{k(k-1)}{2}$ 是整数，所以每个余弦值都是 $\pm 1$ ，其符号只取决于 $k \bmod 4$

$\frac{k(k-1)}{2}$ is an integer, so each cosine is $\pm 1,$ with sign depending only on $k \bmod 4$

大提示：

把这 $80$ 项从 $k = 19$ 开始分成连续的四项一组；相邻三角形数相差 $k$ ，所以每组都会化简

Group the $80$ terms into consecutive blocks of four starting at $k = 19;$ consecutive triangular numbers differ by $k,$ so each block collapses

解答：

因为 $k(k-1)$ 为偶数， $n_k = \frac{k(k-1)}{2}$ 是整数，且 $\cos\frac{k(k-1)\pi}{2}$ $= \cos(n_k \pi)$ $= (-1)^{n_k}$ 。三角形数 $n_k$ 的奇偶性只取决于 $k \bmod 4$ ：当 $k \equiv 0, 1 \pmod 4$ 时为偶数，当 $k \equiv 2, 3 \pmod 4$ 时为奇数。所以 $A_k = n_k$ 当 $k \equiv 0, 1 \pmod 4$ ，而 $A_k = -n_k$ 当 $k \equiv 2, 3 \pmod 4$ 。

把这 $80$ 项分成 $20$ 个连续四项组，从 $k = 19 \equiv 3 \pmod 4$ 开始。利用 $n_{j+1} - n_j = j$ ，每个 $k \equiv 3 \pmod 4$ 的组都化简为 $\begin{aligned} &A_k + A_{k+1} \\ &\quad {}+ A_{k+2} + A_{k+3} \\ &= (n_{k+1} - n_k) \\ &\quad {}- (n_{k+3} - n_{k+2}) \\ &= k - (k + 2) \\ &= -2 \end{aligned}\text{。}$

总和为 $20 \cdot (-2) = -40$ ，所以所求绝对值为 $40$ 。

Since $k(k-1)$ is even, $n_k = \frac{k(k-1)}{2}$ is an integer and $\cos\frac{k(k-1)\pi}{2}$ $= \cos(n_k \pi)$ $= (-1)^{n_k}.$ The parity of the triangular number $n_k$ depends only on $k \bmod 4:$ it is even for $k \equiv 0, 1 \pmod 4$ and odd for $k \equiv 2, 3 \pmod 4.$ So $A_k = n_k$ when $k \equiv 0, 1 \pmod 4$ and $A_k = -n_k$ when $k \equiv 2, 3 \pmod 4.$

Group the $80$ terms into $20$ consecutive blocks of four starting at $k = 19 \equiv 3 \pmod 4.$ Using $n_{j+1} - n_j = j,$ each block with $k \equiv 3 \pmod 4$ collapses: $\begin{aligned} &A_k + A_{k+1} \\ &\quad {}+ A_{k+2} + A_{k+3} \\ &= (n_{k+1} - n_k) \\ &\quad {}- (n_{k+3} - n_{k+2}) \\ &= k - (k + 2) \\ &= -2. \end{aligned}$

The total is $20 \cdot (-2) = -40,$ so the requested absolute value is $40.$

6.

设 $ABCD$ 是一个平行四边形。将 $\overline{DA}$ 经过 $A$ 延长到点 $P$ ，并令 $\overline{PC}$ 与 $\overline{AB}$ 交于 $Q$ ，与 $\overline{DB}$ 交于 $R$ 。已知 $PQ = 735$ 且 $QR = 112$ ，求 $RC$ 。

Let $ABCD$ be a parallelogram. Extend $\overline{DA}$ through $A$ to a point $P,$ and let $\overline{PC}$ meet $\overline{AB}$ at $Q$ and $\overline{DB}$ at $R.$ Given that $PQ = 735$ and $QR = 112,$ find $RC.$

答案

知识点：相似平行四边形二次方程

难度评级：2510

小提示：

有两组相似三角形： $AQ \parallel DC$ 给出 $\frac{PQ}{PC} = \frac{PA}{PD}$ ，而 $BC \parallel PD$ 给出 $\frac{RC}{RP} = \frac{BC}{PD}$

Two pairs of similar triangles: $AQ \parallel DC$ gives $\frac{PQ}{PC} = \frac{PA}{PD},$ and $BC \parallel PD$ gives $\frac{RC}{RP} = \frac{BC}{PD}$

大提示：

令 $a = \frac{PA}{AD}$ ，这些比值给出 $PQ : QR : RC$ $= a(a+2) : 1 : (a+1)$ ；用 $\frac{PQ}{QR} = \frac{735}{112}$ 求出 $a$

With $a = \frac{PA}{AD},$ the ratios give $PQ : QR : RC$ $= a(a+2) : 1 : (a+1);$ use $\frac{PQ}{QR} = \frac{735}{112}$ to find $a$

解答：

令 $a = \frac{PA}{AD}$ 。因为 $AQ \parallel DC$ ，三角形 $PAQ$ 与 $PDC$ 相似，所以 $\frac{PQ}{PC} = \frac{PA}{PD} = \frac{a}{a+1}$ 。因为 $BC \parallel AD$ ，也就是 $BC \parallel PD$ ，三角形 $RBC$ 与 $RDP$ 相似，所以 $\frac{RC}{RP} = \frac{BC}{PD} = \frac{1}{a+1}$ ，从而 $\frac{RC}{PC} = \frac{1}{a+2}$ 。

设 $PC = L$ ，则 $PQ = \frac{a}{a+1}L$ ， $RC = \frac{L}{a+2}$ ，并且 $\begin{aligned} QR &= L - PQ - RC \\ &= \frac{L}{(a+1)(a+2)} \end{aligned}\text{。}$ 因此 $\frac{PQ}{QR} = a(a+2) = \frac{735}{112} = \frac{105}{16}$ ，所以 $16a^2 + 32a - 105 = 0$ ，因式分解为 $(4a - 7)(4a + 15) = 0$ ，得到 $a = \frac{7}{4}$ 。

最后 $RC = (a + 1)\,QR$ $= \frac{11}{4} \cdot 112$ $= 308$ 。

Let $a = \frac{PA}{AD}.$ Since $AQ \parallel DC,$ triangles $PAQ$ and $PDC$ are similar, so $\frac{PQ}{PC} = \frac{PA}{PD} = \frac{a}{a+1}.$ Since $BC \parallel AD,$ i.e. $BC \parallel PD,$ triangles $RBC$ and $RDP$ are similar, so $\frac{RC}{RP} = \frac{BC}{PD} = \frac{1}{a+1},$ which gives $\frac{RC}{PC} = \frac{1}{a+2}.$

Writing $PC = L,$ we get $PQ = \frac{a}{a+1}L,$ $RC = \frac{L}{a+2},$ and $\begin{aligned} QR &= L - PQ - RC \\ &= \frac{L}{(a+1)(a+2)}. \end{aligned}$ Hence $\frac{PQ}{QR} = a(a+2) = \frac{735}{112} = \frac{105}{16},$ so $16a^2 + 32a - 105 = 0,$ which factors as $(4a - 7)(4a + 15) = 0,$ giving $a = \frac{7}{4}.$

Finally $RC = (a + 1)\,QR$ $= \frac{11}{4} \cdot 112$ $= 308.$

7.

设 $n$ 为正奇整数有序四元组 $(x_1, x_2, x_3, x_4)$ 的个数，这些四元组满足 $x_1 + x_2 + x_3 + x_4 = 98$ 。求 $\frac{n}{100}$ 。

Let $n$ be the number of ordered quadruples $(x_1, x_2, x_3, x_4)$ of positive odd integers that satisfy $x_1 + x_2 + x_3 + x_4 = 98.$ Find $\frac{n}{100}.$

答案

知识点：隔板法换元法奇偶性

难度评级：2010

小提示：

代入 $x_i = 2y_i - 1$ ，把奇数变量转化为任意正整数变量

Substitute $x_i = 2y_i - 1$ to turn the odd variables into arbitrary positive integers

大提示：

新方程是 $y_1 + y_2 + y_3 + y_4 = 51$ ；用插板法计算它的正整数解个数

The new equation is $y_1 + y_2 + y_3 + y_4 = 51;$ count its positive solutions with stars and bars

解答：

令 $x_i = 2y_i - 1$ ，其中每个 $y_i$ 都是正整数。于是 $x_1 + x_2 + x_3 + x_4 = 98$ 变为 $2(y_1 + y_2 + y_3 + y_4) - 4 = 98$ ，所以 $y_1 + y_2 + y_3 + y_4 = 51$ 。

由插板法，正整数解的个数为 $\binom{50}{3} = 19600$ 。因此 $\frac{n}{100} = 196$ 。

Write $x_i = 2y_i - 1$ where each $y_i$ is a positive integer. Then $x_1 + x_2 + x_3 + x_4 = 98$ becomes $2(y_1 + y_2 + y_3 + y_4) - 4 = 98,$ so $y_1 + y_2 + y_3 + y_4 = 51.$

By stars and bars, the number of solutions in positive integers is $\binom{50}{3} = 19600.$ Therefore $\frac{n}{100} = 196.$

8.

除前两项外，数列 $1000$ 、 $x$ 、 $1000 - x$ 、 $\ldots$ 的每一项都是用前前一项减去前一项得到的。数列的最后一项是遇到的第一个负数。哪个正整数 $x$ 能使这个数列的长度最大？

Except for the first two terms, each term of the sequence $1000,$ $x,$ $1000 - x,$ $\ldots$ is obtained by subtracting the preceding term from the one before that. The last term of the sequence is the first negative term encountered. What positive integer $x$ produces a sequence of maximum length?

答案

知识点：斐波那契数列递推极限情形界定

难度评级：2510

小提示：

写出各项： $1000 - x$ 、 $2x - 1000$ 、 $2000 - 3x$ 、 $5x - 3000, \ldots$ ，系数是斐波那契数

Write out terms: $1000 - x,$ $2x - 1000,$ $2000 - 3x,$ $5x - 3000, \ldots$ — the coefficients are Fibonacci numbers

大提示：

要让第十二项和第十三项非负，会把 $x$ 限制在 $\frac{55000}{89}$ 和 $\frac{89000}{144}$ 之间，这个区间内恰好有一个整数

Keeping the twelfth and thirteenth terms nonnegative pins $x$ between $\frac{55000}{89}$ and $\frac{89000}{144},$ an interval containing exactly one integer

解答：

逐项计算得 $a_3 = 1000 - x$ 、 $a_4 = 2x - 1000$ 、 $a_5 = 2000 - 3x$ 、 $a_6 = 5x - 3000$ 。一般地， $\begin{aligned} a_{2k+1} &= 1000 F_{2k-1} - x F_{2k}, \\ a_{2k+2} &= x F_{2k+1} - 1000 F_{2k}\text{，} \end{aligned}$ 其中 $F_1 = F_2 = 1$ 、 $F_3 = 2, \ldots$ 是斐波那契数。数列能继续的充要条件是各项保持非负，所以要让数列越来越长， $\frac{x}{1000}$ 必须夹在 $\frac{F_{2k}}{F_{2k+1}}$ 和 $\frac{F_{2k-1}}{F_{2k}}$ 之间，其中 $k$ 越来越大。

要使前 $13$ 项非负，需要 $a_{12} = 89x - 55000 \ge 0$ 且 $a_{13} = 89000 - 144x \ge 0$ ，即 $617.9\ldots \le x \le 618.05\ldots$ ，所以 $x = 618$ 。若 $x \le 617$ ，数列到 $a_{12}$ 时已经变负；若 $x \ge 619$ ，数列到 $a_{13}$ 时已经变负，因此其他整数都会给出更短的数列。

事实上 $x = 618$ 时得到 $1000, 618, 382, 236, 146$ 、 $90, 56, 34, 22, 12$ 、 $10, 2, 8, -6$ ，这是长度最大的 $14$ 项数列。答案是 $618$ 。

Computing terms, $a_3 = 1000 - x,$ $a_4 = 2x - 1000,$ $a_5 = 2000 - 3x,$ $a_6 = 5x - 3000,$ and in general $\begin{aligned} a_{2k+1} &= 1000 F_{2k-1} - x F_{2k}, \\ a_{2k+2} &= x F_{2k+1} - 1000 F_{2k}, \end{aligned}$ where $F_1 = F_2 = 1,$ $F_3 = 2, \ldots$ are the Fibonacci numbers. The sequence keeps going exactly as long as its terms stay nonnegative, so a long sequence requires $\frac{x}{1000}$ to be squeezed between the ratios $\frac{F_{2k}}{F_{2k+1}}$ and $\frac{F_{2k-1}}{F_{2k}}$ for larger and larger $k.$

For the first $13$ terms to be nonnegative we need $a_{12} = 89x - 55000 \ge 0$ and $a_{13} = 89000 - 144x \ge 0,$ i.e. $617.9\ldots \le x \le 618.05\ldots,$ so $x = 618.$ If $x \le 617$ the sequence turns negative by $a_{12},$ and if $x \ge 619$ it turns negative by $a_{13},$ so every other integer gives a shorter sequence.

Indeed $x = 618$ yields $1000, 618, 382, 236, 146,$ $90, 56, 34, 22, 12,$ $10, 2, 8, -6,$ a sequence of $14$ terms, the maximum possible. The answer is $618.$

9.

两位数学家每天上午都喝咖啡休息。他们独立地在上午 $9$ 点到 $10$ 点之间的随机时刻到达自助餐厅，并停留恰好 $m$ 分钟。其中一人到达时另一人正在自助餐厅的概率为 $40\%$ ，且 $m = a - b\sqrt{c}$ ，其中 $a$ 、 $b$ 和 $c$ 是正整数，且 $c$ 不被任何质数的平方整除。求 $a + b + c$ 。

Two mathematicians take a morning coffee break each day. They arrive at the cafeteria independently, at random times between $9$ a.m. and $10$ a.m., and stay for exactly $m$ minutes. The probability that either one arrives while the other is in the cafeteria is $40\%,$ and $m = a - b\sqrt{c},$ where $a,$ $b,$ and $c$ are positive integers, and $c$ is not divisible by the square of any prime. Find $a + b + c.$

答案

知识点：几何概率对立事件概率

难度评级：2400

小提示：

把两人的到达时间画成 $60 \times 60$ 正方形中的一个点；他们相遇当且仅当 $|x - y| \lt m$

Plot the two arrival times as a point in a $60 \times 60$ square; they meet exactly when $|x - y| \lt m$

大提示：

补集由两个直角三角形组成，合起来面积等于一个边长为 $60 - m$ 的正方形，所以 $(60 - m)^2 = \frac{3}{5} \cdot 3600$

The complement consists of two right triangles that fit together into a square of side $60 - m,$ so $(60 - m)^2 = \frac{3}{5} \cdot 3600$

解答：

令两人的到达时间分别为 $x$ 分钟和 $y$ 分钟，单位是上午 $9$ 点后的分钟，则 $(x, y)$ 在一个 $60 \times 60$ 的正方形中均匀分布。两人相遇当且仅当 $|x - y| \lt m$ 。

不相遇区域 $|x - y| \ge m$ 由两个直角边长为 $60 - m$ 的直角三角形组成，总面积为 $(60 - m)^2$ 。相遇概率为 $40\%$ ，意味着 $(60 - m)^2 = 0.6 \cdot 3600 = 2160\text{，}$ 所以 $60 - m = \sqrt{2160} = 12\sqrt{15}$ 。

因此 $m = 60 - 12\sqrt{15}$ ，且 $a + b + c = 60 + 12 + 15 = 87$ 。

Let the arrival times be $x$ and $y$ minutes after $9$ a.m., so $(x, y)$ is uniform in a $60 \times 60$ square. The two people meet exactly when $|x - y| \lt m.$

The non-meeting region $|x - y| \ge m$ consists of two right triangles with legs $60 - m,$ with total area $(60 - m)^2.$ Meeting with probability $40\%$ means $(60 - m)^2 = 0.6 \cdot 3600 = 2160,$ so $60 - m = \sqrt{2160} = 12\sqrt{15}.$

Thus $m = 60 - 12\sqrt{15},$ and $a + b + c = 60 + 12 + 15 = 87.$

10.

八个半径为 $100$ 的球放在一个平面上，使得每个球都与另外两个球相切，并且它们的球心是一个正八边形的顶点。第九个球也放在这个平面上，并且与其他八个球都相切。这个最后放入的球的半径为 $a + b\sqrt{c}$ ，其中 $a$ 、 $b$ 和 $c$ 是正整数，且 $c$ 不被任何质数的平方整除。求 $a + b + c$ 。

Eight spheres of radius $100$ are placed on a flat surface so that each sphere is tangent to two others and their centers are the vertices of a regular octagon. A ninth sphere is placed on the flat surface so that it is tangent to each of the other eight spheres. The radius of this last sphere is $a + b\sqrt{c},$ where $a,$ $b,$ and $c$ are positive integers, and $c$ is not divisible by the square of any prime. Find $a + b + c.$

答案

知识点：球立体几何正多边形勾股定理

难度评级：2510

小提示：

八个球心都在高度 $100$ 处，并位于边长为 $200$ 的正八边形顶点上；第九个球心在八边形中心正上方，高度为 $r$

All eight centers lie at height $100$ at the vertices of an octagon of side $200;$ the ninth center is at height $r$ above the octagon’s center

大提示：

相切给出 $R^2 + (r - 100)^2 = (r + 100)^2$ ，其中 $R$ 是外接圆半径，且 $200 = 2R\sin 22.5^\circ$

Tangency gives $R^2 + (r - 100)^2 = (r + 100)^2,$ where $R$ is the circumradius and $200 = 2R\sin 22.5^\circ$

解答：

八个球心高度均为 $100$ ，位于边长为 $200$ 的正八边形顶点上，因为相邻球相切。若第九个球半径为 $r$ ，则它放在平面上，球心在八边形中心正上方，高度为 $r$ 。它与每个球相切，给出 $\sqrt{R^2 + (r - 100)^2} = r + 100$ ，其中 $R$ 是八边形的外接圆半径。因此 $\begin{aligned} R^2 &= (r + 100)^2 - (r - 100)^2 \\ &= 400r \end{aligned}\text{。}$

正八边形的一条边在圆心处所对圆心角为 $45^\circ$ ，所以 $200 = 2R \sin 22.5^\circ$ 。利用 $\sin^2 22.5^\circ = \frac{1 - \cos 45^\circ}{2} = \frac{2 - \sqrt{2}}{4}$ ，得 $\begin{aligned} R^2 &= \frac{10000}{\sin^2 22.5^\circ} \\ &= \frac{40000}{2 - \sqrt{2}} \\ &= 20000\,(2 + \sqrt{2}) \end{aligned}\text{。}$

于是 $r = \frac{R^2}{400}$ $= 50\,(2 + \sqrt{2})$ $= 100 + 50\sqrt{2}$ ，所以 $a + b + c = 100 + 50 + 2 = 152$ 。

The eight centers are at height $100,$ at the vertices of a regular octagon of side $200$ (adjacent spheres are tangent). If the ninth sphere has radius $r,$ it rests on the surface with its center at height $r$ directly above the octagon’s center, and tangency to each sphere gives $\sqrt{R^2 + (r - 100)^2} = r + 100,$ where $R$ is the octagon’s circumradius. Hence $\begin{aligned} R^2 &= (r + 100)^2 - (r - 100)^2 \\ &= 400r. \end{aligned}$

A side of a regular octagon subtends $45^\circ$ at the center, so $200 = 2R \sin 22.5^\circ$ and, using $\sin^2 22.5^\circ = \frac{1 - \cos 45^\circ}{2} = \frac{2 - \sqrt{2}}{4},$ $\begin{aligned} R^2 &= \frac{10000}{\sin^2 22.5^\circ} \\ &= \frac{40000}{2 - \sqrt{2}} \\ &= 20000\,(2 + \sqrt{2}). \end{aligned}$

Then $r = \frac{R^2}{400}$ $= 50\,(2 + \sqrt{2})$ $= 100 + 50\sqrt{2},$ so $a + b + c = 100 + 50 + 2 = 152.$

11.

一个立方体的三条棱为 $\overline{AB}$ 、 $\overline{BC}$ 和 $\overline{CD}$ ，且 $\overline{AD}$ 是一条体对角线。点 $P$ 、 $Q$ 和 $R$ 分别在 $\overline{AB}$ 、 $\overline{BC}$ 和 $\overline{CD}$ 上，满足 $AP = 5$ 、 $PB = 15$ 、 $BQ = 15$ 且 $CR = 10$ 。平面 $PQR$ 与立方体相交所得多边形的面积是多少？

Three of the edges of a cube are $\overline{AB},$ $\overline{BC},$ and $\overline{CD},$ and $\overline{AD}$ is an interior diagonal. Points $P,$ $Q,$ and $R$ are on $\overline{AB},$ $\overline{BC},$ and $\overline{CD},$ respectively, so that $AP = 5,$ $PB = 15,$ $BQ = 15,$ and $CR = 10.$ What is the area of the polygon that is the intersection of plane $PQR$ and the cube?

答案

知识点：正方体坐标几何鞋带公式

难度评级：2840

小提示：

设 $B = (0,0,0)$ 、 $A = (20,0,0)$ 、 $C = (0,20,0)$ 、 $D = (0,20,20)$ ，并求过 $P$ 、 $Q$ 、 $R$ 的平面

Set $B = (0,0,0),$ $A = (20,0,0),$ $C = (0,20,0),$ $D = (0,20,20),$ and find the plane through $P,$ $Q,$ $R$

大提示：

平面 $2x + 2y - z = 30$ 截出一个六边形。投影到 $xy$ -平面时，面积会乘以单位法向量的竖直分量 $\frac{1}{3}$

The plane $2x + 2y - z = 30$ cuts a hexagon. Projecting to the $xy$ -plane scales area by $\frac{1}{3},$ the vertical component of the unit normal.

解答：

立方体边长为 $20$ 。取 $B = (0,0,0)$ 、 $A = (20,0,0)$ 、 $C = (0,20,0)$ ，以及 $D = (0,20,20)$ ，这样 $\overline{AD}$ 是一条体对角线。于是 $P = (15, 0, 0)$ 、 $Q = (0, 15, 0)$ 、 $R = (0, 20, 10)$ ，过这三点的平面为 $2x + 2y - z = 30$ 。

在立方体各顶点处代入 $2x + 2y - z$ ，并检查十二条棱，可知平面还经过棱上的 $(5, 20, 20)$ 、 $(20, 5, 20)$ 和 $(20, 0, 10)$ ，所以截面是按顺序顶点为 $(15,0,0)$ 、 $(0,15,0)$ 、 $(0,20,10)$ 、 $(5,20,20)$ 、 $(20,5,20)$ 、 $(20,0,10)$ 的六边形。它在 $xy$ -平面上的投影是六边形 $(15,0)$ 、 $(0,15)$ 、 $(0,20)$ 、 $(5,20)$ 、 $(20,5)$ 、 $(20,0)$ ，用鞋带公式可得面积为 $175$ 。

该平面的单位法向量 $\frac{1}{3}(2, 2, -1)$ 的竖直分量绝对值为 $\frac{1}{3}$ ，所以投影到 $xy$ -平面会把面积乘以 $\frac{1}{3}$ 。因此截面面积为 $3 \cdot 175 = 525$ 。

The cube has side $20.$ Take $B = (0,0,0),$ $A = (20,0,0),$ $C = (0,20,0),$ and $D = (0,20,20),$ so $\overline{AD}$ is an interior diagonal. Then $P = (15, 0, 0),$ $Q = (0, 15, 0),$ $R = (0, 20, 10),$ and the plane through them is $2x + 2y - z = 30.$

Evaluating $2x + 2y - z$ at the cube’s vertices and checking all twelve edges, the plane also crosses the edges at $(5, 20, 20),$ $(20, 5, 20),$ and $(20, 0, 10),$ so the cross-section is the hexagon with vertices $(15,0,0),$ $(0,15,0),$ $(0,20,10),$ $(5,20,20),$ $(20,5,20),$ $(20,0,10)$ in order. Its projection onto the $xy$ -plane is the hexagon $(15,0),$ $(0,15),$ $(0,20),$ $(5,20),$ $(20,5),$ $(20,0),$ whose area by the shoelace formula is $175.$

The plane’s unit normal $\frac{1}{3}(2, 2, -1)$ has vertical component of magnitude $\frac{1}{3},$ so projecting onto the $xy$ -plane multiplies area by $\frac{1}{3}.$ The cross-section therefore has area $3 \cdot 175 = 525.$

12.

设 $ABC$ 为等边三角形， $D$ 、 $E$ 和 $F$ 分别为 $\overline{BC}$ 、 $\overline{CA}$ 和 $\overline{AB}$ 的中点。存在点 $P$ 、 $Q$ 和 $R$ ，分别在 $\overline{DE}$ 、 $\overline{EF}$ 和 $\overline{FD}$ 上，满足 $P$ 在 $\overline{CQ}$ 上， $Q$ 在 $\overline{AR}$ 上，且 $R$ 在 $\overline{BP}$ 上。三角形 $ABC$ 的面积与三角形 $PQR$ 的面积之比为 $a + b\sqrt{c}$ ，其中 $a$ 、 $b$ 和 $c$ 是整数，且 $c$ 不被任何质数的平方整除。求 $a^2 + b^2 + c^2$ ？

Let $ABC$ be equilateral, and $D,$ $E,$ and $F$ be the midpoints of $\overline{BC},$ $\overline{CA},$ and $\overline{AB},$ respectively. There exist points $P,$ $Q,$ and $R$ on $\overline{DE},$ $\overline{EF},$ and $\overline{FD},$ respectively, with the property that $P$ is on $\overline{CQ},$ $Q$ is on $\overline{AR},$ and $R$ is on $\overline{BP}.$ The ratio of the area of triangle $ABC$ to the area of triangle $PQR$ is $a + b\sqrt{c},$ where $a,$ $b,$ and $c$ are integers, and $c$ is not divisible by the square of any prime. What is $a^2 + b^2 + c^2?$

答案

知识点：等边三角形坐标几何面积比对称性

难度评级：2990

小提示：

将 $P$ 、 $Q$ 、 $R$ 分别用比例 $x$ 、 $y$ 、 $z$ 参数化，使它们依次位于 $DE$ 、 $EF$ 、 $FD$ 上；把三个共线条件转化为方程

Parameterize $P,$ $Q,$ and $R$ by separate fractions $x,$ $y,$ and $z$ along $DE,$ $EF,$ and $FD$ ; translate the three collinearities into equations

大提示：

三个方程是 $x(1+y)=1$ 、 $y(1+z)=1$ 和 $z(1+x)=1$ ；证明它们推出 $x=y=z$ ，再比较两个等边三角形公共中心到顶点的距离平方

The equations are $x(1+y)=1,$ $y(1+z)=1,$ and $z(1+x)=1;$ show they force $x=y=z,$ then compare squared distances from the common center of the two equilateral triangles

解答：

取 $A = (0, \sqrt{3})$ 、 $B = (-1, 0)$ 、 $C = (1, 0)$ ，于是 $D = (0, 0)$ 、 $E = \left(\frac{1}{2}, \frac{\sqrt{3}}{2}\right)$ 、 $F = \left(-\frac{1}{2}, \frac{\sqrt{3}}{2}\right)$ 。设 $P=D+x(E-D)$ 、 $Q=E+y(F-E)$ 、 $R=F+z(D-F)$ ，其中 $0\le x,y,z\le1$ 。计算三个二维叉积，三个共线条件 $C,P,Q$ 、 $A,Q,R$ 和 $B,R,P$ 分别给出 $\begin{gathered} x(1+y)=1,\\ y(1+z)=1,\\ z(1+x)=1 \end{gathered}\text{。}$

令 $f(u)=\frac{1}{1+u}$ 。这些方程表示 $x=f(y)$ 、 $y=f(z)$ 、 $z=f(x)$ ，所以 $x=f(f(f(x)))=\frac{x+2}{2x+3}\text{。}$ 因此 $x^2+x-1=0$ ，由正性得 $x=\frac{\sqrt5-1}{2}$ 。这些方程进而推出 $y=z=x$ ；把这个公共值记为 $t$ 。这证明了所求构型确实具有对称性，而不是预先假设它对称。

此时 $P = \left(\frac{t}{2}, \frac{t\sqrt{3}}{2}\right)$ ， $Q = \left(\frac{1}{2} - t, \frac{\sqrt{3}}{2}\right)$ 。两个三角形都是等边三角形，且中心同为 $G = \left(0, \frac{\sqrt{3}}{3}\right)$ ，所以面积比为 $\frac{GA^2}{GP^2}$ 。利用 $t^2 = 1 - t$ ， $\begin{aligned} GP^2 &= \frac{t^2}{4} + 3\left(\frac{t}{2} - \frac{1}{3}\right)^2 \\ &= t^2 - t + \frac{1}{3} \\ &= \frac{7}{3} - \sqrt{5}, \\ GA^2 &= \frac{4}{3} \end{aligned}\text{。}$

因此 $\begin{aligned} \frac{[ABC]}{[PQR]} &= \frac{\frac{4}{3}}{\frac{7}{3} - \sqrt{5}} \\ &= \frac{4}{7 - 3\sqrt{5}} \\ &= 7 + 3\sqrt{5} \end{aligned}\text{，}$ 所以 $a = 7$ 、 $b = 3$ 、 $c = 5$ ，且 $a^2 + b^2 + c^2 = 49 + 9 + 25 = 83$ 。

Place $A = (0, \sqrt{3}),$ $B = (-1, 0),$ $C = (1, 0),$ so $D = (0, 0),$ $E = \left(\frac{1}{2}, \frac{\sqrt{3}}{2}\right),$ $F = \left(-\frac{1}{2}, \frac{\sqrt{3}}{2}\right).$ Write $P=D+x(E-D),$ $Q=E+y(F-E),$ and $R=F+z(D-F),$ where $0\le x,y,z\le1.$ Computing the three two-dimensional cross products, the collinearities $C,P,Q;$ $A,Q,R;$ and $B,R,P$ give, respectively, $\begin{gathered} x(1+y)=1,\\ y(1+z)=1,\\ z(1+x)=1. \end{gathered}$

Let $f(u)=\frac{1}{1+u}.$ The equations say $x=f(y),$ $y=f(z),$ and $z=f(x),$ so $x=f(f(f(x)))=\frac{x+2}{2x+3}.$ Hence $x^2+x-1=0,$ and positivity gives $x=\frac{\sqrt5-1}{2}.$ The equations then force $y=z=x;$ call this common value $t.$ Thus the desired configuration really is the symmetric one, rather than merely being assumed to be.

With $P = \left(\frac{t}{2}, \frac{t\sqrt{3}}{2}\right)$ and $Q = \left(\frac{1}{2} - t, \frac{\sqrt{3}}{2}\right),$ both triangles are equilateral with center $G = \left(0, \frac{\sqrt{3}}{3}\right).$ Therefore the area ratio is $\frac{GA^2}{GP^2}.$ Using $t^2 = 1 - t,$ $\begin{aligned} GP^2 &= \frac{t^2}{4} + 3\left(\frac{t}{2} - \frac{1}{3}\right)^2 \\ &= t^2 - t + \frac{1}{3} \\ &= \frac{7}{3} - \sqrt{5}, \\ GA^2 &= \frac{4}{3}. \end{aligned}$

Hence $\begin{aligned} \frac{[ABC]}{[PQR]} &= \frac{\frac{4}{3}}{\frac{7}{3} - \sqrt{5}} \\ &= \frac{4}{7 - 3\sqrt{5}} \\ &= 7 + 3\sqrt{5}, \end{aligned}$ so $a = 7,$ $b = 3,$ $c = 5,$ and $a^2 + b^2 + c^2 = 49 + 9 + 25 = 83.$

13.

若 $\{a_1, a_2, a_3, \ldots, a_n\}$ 是一个实数集合，并按 $a_1 \lt a_2 \lt a_3 \lt \cdots \lt a_n$ 编号，则它的复幂和定义为 $a_1 i + a_2 i^2 + a_3 i^3 + \cdots + a_n i^n$ ，其中 $i^2 = -1$ 。令 $S_n$ 为 $\{1, 2, \ldots, n\}$ 的所有非空子集的复幂和之和。已知 $S_8 = -176 - 64i$ ，且 $S_9 = p + qi$ ，其中 $p$ 和 $q$ 是整数。求 $|p| + |q|$ 。

If $\{a_1, a_2, a_3, \ldots, a_n\}$ is a set of real numbers, indexed so that $a_1 \lt a_2 \lt a_3 \lt \cdots \lt a_n,$ its complex power sum is defined to be $a_1 i + a_2 i^2 + a_3 i^3 + \cdots + a_n i^n,$ where $i^2 = -1.$ Let $S_n$ be the sum of the complex power sums of all nonempty subsets of $\{1, 2, \ldots, n\}.$ Given that $S_8 = -176 - 64i$ and $S_9 = p + qi,$ where $p$ and $q$ are integers, find $|p| + |q|.$

答案

知识点：复数递推二项式定理

难度评级：2920

小提示：

将 $\{1, \ldots, 9\}$ 的子集按是否包含 $9$ 来划分；不含 $9$ 的子集贡献 $S_8$

Split the subsets of $\{1, \ldots, 9\}$ by whether they contain $9;$ those without $9$ contribute $S_8$

大提示：

在 $T \cup \{9\}$ 中，元素 $9$ 总是最大元素，并贡献 $9i^{|T|+1}$ ；对所有 $T \subseteq \{1, \ldots, 8\}$ 求和得到 $9i(1+i)^8$

In $T \cup \{9\},$ the element $9$ is always largest and adds $9i^{|T|+1};$ summing over all $T \subseteq \{1, \ldots, 8\}$ gives $9i(1+i)^8$

解答：

将 $\{1, \ldots, 9\}$ 的非空子集按是否包含 $9$ 来划分。不含 $9$ 的子集贡献 $S_8$ 。包含 $9$ 的子集可写成 $T \cup \{9\}$ ，其中 $T \subseteq \{1, \ldots, 8\}$ 可以为空；因为 $9$ 是其中最大的元素，它的复幂和等于 $T$ 的复幂和再加上 $9i^{|T| + 1}$ 。对所有 $T$ 求和，又得到一个 $S_8$ 外加 $\sum_{k=0}^{8} \binom{8}{k}\, 9\, i^{k+1} = 9i\,(1 + i)^8\text{。}$

因为 $(1 + i)^2 = 2i$ ，所以 $(1 + i)^8 = (2i)^4 = 16$ ，于是 $\begin{aligned} S_9 &= 2S_8 + 144i \\ &= 2(-176 - 64i) + 144i \\ &= -352 + 16i \end{aligned}\text{。}$

因此 $|p| + |q| = 352 + 16 = 368$ 。

Split the nonempty subsets of $\{1, \ldots, 9\}$ by whether they contain $9.$ Those without $9$ contribute $S_8.$ A subset containing $9$ is $T \cup \{9\}$ for a (possibly empty) $T \subseteq \{1, \ldots, 8\},$ and since $9$ is its largest element, its complex power sum is the complex power sum of $T$ plus $9i^{|T| + 1}.$ Summing over all $T$ gives another $S_8$ plus $\sum_{k=0}^{8} \binom{8}{k}\, 9\, i^{k+1} = 9i\,(1 + i)^8.$

Since $(1 + i)^2 = 2i,$ we get $(1 + i)^8 = (2i)^4 = 16,$ so $\begin{aligned} S_9 &= 2S_8 + 144i \\ &= 2(-176 - 64i) + 144i \\ &= -352 + 16i. \end{aligned}$

Therefore $|p| + |q| = 352 + 16 = 368.$

14.

一个 $m \times n \times p$ 长方体的体积是一个 $(m + 2) \times (n + 2) \times (p + 2)$ 长方体体积的一半，其中 $m$ 、 $n$ 和 $p$ 是整数，且 $m \le n \le p$ 。 $p$ 的最大可能值是多少？

An $m \times n \times p$ rectangular box has half the volume of an $(m + 2) \times (n + 2) \times (p + 2)$ rectangular box, where $m,$ $n,$ and $p$ are integers, and $m \le n \le p.$ What is the largest possible value of $p?$

答案

知识点：丢番图方程西蒙最爱的因式分解技巧极限情形界定

难度评级：2740

小提示：

把体积条件改写为 $\left(1 + \frac{2}{m}\right)\left(1 + \frac{2}{n}\right)\left(1 + \frac{2}{p}\right) = 2$ ，并测试较小的 $m$

Rewrite the volume condition as $\left(1 + \frac{2}{m}\right)\left(1 + \frac{2}{n}\right)\left(1 + \frac{2}{p}\right) = 2$ and test small $m$

大提示：

$m = 1, 2$ 不可能，且 $m \ge 4$ 会把 $p$ 限制得较小；当 $m = 3$ 时，方程因式分解为 $(n - 10)(p - 10) = 120$

$m = 1, 2$ are impossible and $m \ge 4$ caps $p$ low; for $m = 3$ the equation factors as $(n - 10)(p - 10) = 120$

解答：

条件 $2mnp = (m + 2)(n + 2)(p + 2)$ 可改写为 $\begin{aligned} &\left(1 + \frac{2}{m}\right)\left(1 + \frac{2}{n}\right)\left(1 + \frac{2}{p}\right) \\ &= 2 \end{aligned}\text{。}$ 若 $m = 1$ ，第一个因子本身就是 $3 \gt 2$ ；若 $m = 2$ ，第一个因子等于 $2$ ，而其他因子都大于 $1$ 。两者都不可能。若 $m \ge 5$ ，则由于 $n \ge m$ ，前两个因子至多为 $\left(\frac{7}{5}\right)^2 = \frac{49}{25}$ ，从而迫使 $1 + \frac{2}{p} \ge \frac{50}{49}$ ，即 $p \le 98$ 。

当 $m = 4$ 时，方程变为 $4np = 3(n + 2)(p + 2)$ ，即 $(n - 6)(p - 6) = 48$ ，所以 $p \le 54$ 。当 $m = 3$ 时，方程变为 $6np = 5(n + 2)(p + 2)$ ，即 $np - 10n - 10p - 20 = 0$ ，或 $(n - 10)(p - 10) = 120$ 。两个因子必须为正；若 $n, p \lt 10$ ，乘积 $(10 - n)(10 - p)$ 至多为 $49$ 。因此最大的 $p$ 来自 $n - 10 = 1$ ： $n = 11$ ， $p = 130$ 。确实有 $2 \cdot 3 \cdot 11 \cdot 130 = 8580$ $= 5 \cdot 13 \cdot 132$ 。

因为其他所有情况都给出 $p \le 98$ ，所以最大可能值是 $p = 130$ 。

The condition $2mnp = (m + 2)(n + 2)(p + 2)$ rewrites as $\begin{aligned} &\left(1 + \frac{2}{m}\right)\left(1 + \frac{2}{n}\right)\left(1 + \frac{2}{p}\right) \\ &= 2. \end{aligned}$ If $m = 1$ the first factor alone is $3 \gt 2,$ and if $m = 2$ it equals $2$ while the other factors exceed $1;$ both are impossible. If $m \ge 5,$ then since $n \ge m$ the first two factors are at most $\left(\frac{7}{5}\right)^2 = \frac{49}{25},$ forcing $1 + \frac{2}{p} \ge \frac{50}{49},$ i.e. $p \le 98.$

For $m = 4$ the equation becomes $4np = 3(n + 2)(p + 2),$ i.e. $(n - 6)(p - 6) = 48,$ so $p \le 54.$ For $m = 3$ it becomes $6np = 5(n + 2)(p + 2),$ i.e. $np - 10n - 10p - 20 = 0,$ or $(n - 10)(p - 10) = 120.$ Both factors must be positive (if $n, p \lt 10$ the product $(10 - n)(10 - p)$ is at most $49$ ), so the largest $p$ comes from $n - 10 = 1:$ $n = 11$ and $p = 130.$ Indeed $2 \cdot 3 \cdot 11 \cdot 130 = 8580$ $= 5 \cdot 13 \cdot 132.$

Since every other case yields $p \le 98,$ the largest possible value is $p = 130.$

15.

定义一张多米诺牌为一个由不同正整数组成的有序对。一个合法的多米诺序列是一列互不相同的多米诺牌，其中第一张之后每张牌的第一坐标都等于前一张牌的第二坐标，并且 $(i, j)$ 与 $(j, i)$ 对任意 $i$ 和 $j$ 都不能同时出现。令 $D_{40}$ 为所有坐标不大于 $40$ 的多米诺牌组成的集合。求使用 $D_{40}$ 中的多米诺牌所能形成的最长合法多米诺序列的长度。

Define a domino to be an ordered pair of distinct positive integers. A proper sequence of dominos is a list of distinct dominos in which the first coordinate of each pair after the first equals the second coordinate of the immediately preceding pair, and in which $(i, j)$ and $(j, i)$ do not both appear for any $i$ and $j.$ Let $D_{40}$ be the set of all dominos whose coordinates are no larger than $40.$ Find the length of the longest proper sequence of dominos that can be formed using the dominos of $D_{40}.$

答案

知识点：图论奇偶性

难度评级：3160

小提示：

多米诺牌就是 $40$ 个顶点完全图中的边，而合法序列就是一条迹，也就是不重复边的游走

Dominos are the edges of the complete graph on $40$ vertices, and a proper sequence is a trail — a walk repeating no edge

大提示：

所有 $40$ 个顶点的度都是奇数 $39$ ，但一条迹只允许有两个奇度顶点，所以必须有一些边不用；用互不相交的不用边来修正奇偶性

All $40$ vertices have odd degree $39,$ but a trail allows only two odd-degree vertices, so some edges must go unused; disjoint unused edges fix the parities

解答：

一张多米诺牌 $(i, j)$ 是顶点 $1, \ldots, 40$ 上完全图的一条有向边，而 $(i, j)$ 与 $(j, i)$ 不能同时出现的规则意味着 $\binom{40}{2} = 780$ 条无向边每条至多使用一次。一个合法序列正是一条迹：不重复边的游走。在任何迹中，除两个端点外，每个顶点进入和离开的次数相等，所以它在已用边集合中的度为偶数。

完全图中每个顶点的度都是奇数 $39$ ，所以在未用边集合中至少有 $38$ 个顶点必须是奇度顶点，而一个有 $38$ 个奇度顶点的图至少有 $\frac{38}{2} = 19$ 条边。因此最多能使用 $780 - 19 = 761$ 张多米诺牌。

反过来，先放弃 $19$ 条互不相交的边 $(3,4)$ 、 $(5,6)$ 、 $\ldots$ 、 $(39,40)$ 。剩下的图连通，且只有顶点 $1$ 和 $2$ 为奇度顶点，所以存在一条遍历剩余全部 $761$ 条边的欧拉迹；按这条迹行进的方向给每条边定向，就得到长度为 $761$ 的合法序列。

A domino $(i, j)$ is an oriented edge of the complete graph on vertices $1, \ldots, 40,$ and the rule that $(i, j)$ and $(j, i)$ cannot both appear means each of the $\binom{40}{2} = 780$ edges is available at most once. A proper sequence is exactly a trail: a walk that repeats no edge. In any trail, every vertex other than the two endpoints is entered and left equally often, so it has even degree in the set of edges used.

In the complete graph every vertex has odd degree $39,$ so at least $38$ vertices must have odd degree in the set of unused edges, and a graph with $38$ odd-degree vertices has at least $\frac{38}{2} = 19$ edges. Hence at most $780 - 19 = 761$ dominos can be used.

Conversely, set aside the $19$ disjoint edges $(3,4),$ $(5,6),$ $\ldots,$ $(39,40).$ The remaining graph is connected and only vertices $1$ and $2$ have odd degree, so it has an Euler trail traversing all $761$ remaining edges; orienting each edge in the direction of travel gives a proper sequence of length $761.$