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

1.

求最小正整数 $n$ ，使得无论怎样把 $10^n$ 表示为两个正整数的乘积，这两个整数中至少有一个含有数字 $0$ 。

Find the least positive integer $n$ such that no matter how $10^n$ is expressed as the product of any two positive integers, at least one of these two integers contains the digit $0.$

答案

知识点：质因数分解数字

难度评级：2110

小提示：

$10^n$ 的每个因子都形如 $2^x 5^y$ ，而任何同时被 $2$ 和 $5$ 整除的因子都以数字 $0$ 结尾。

Every factor of $10^n$ has the form $2^x 5^y,$ and any factor divisible by both $2$ and $5$ ends in the digit $0$

大提示：

因此，要使两个因子都不含数字零，唯一可能的拆分是 $2^n \times 5^n$ ；找出第一个使 $2^n$ 或 $5^n$ 含有数字 $0$ 的 $n$ 。

So the only candidate splitting is $2^n \times 5^n;$ find the first $n$ for which $2^n$ or $5^n$ contains a digit $0$

解答：

任意因式分解可写为 $10^n = (2^x 5^y)(2^{n-x} 5^{n-y})$ 。若某因子同时被 $2$ 和 $5$ 整除，它就是 $10$ 的倍数，末位为 $0$ 。所以，要使两个因子都不含数字零，唯一可能的分解是 $10^n = 2^n \cdot 5^n$ ，我们要找最小的 $n$ ，使得 $2^n$ 或 $5^n$ 含有数字 $0$ 。

$2^1, \ldots, 2^8$ 为 $2, 4, 8, 16, 32, 64, 128, 256$ ，均不含零。 $5^1, \ldots, 5^7$ 为 $5, 25, 125, 625$ 、 $3125, 15625, 78125$ ，均不含零，但 $5^8 = 390625$ 含有 $0$ 。

因此 $10^8$ 的每个分解都含有一个带数字 $0$ 的因子，而 $10^7 = 2^7 \cdot 5^7 = 128 \cdot 78125$ 不满足条件。答案是 $8$ 。

Every factorization is $10^n = (2^x 5^y)(2^{n-x} 5^{n-y}).$ If a factor is divisible by both $2$ and $5,$ it is a multiple of $10$ and ends in the digit $0.$ So the only possible zero-free factorization is $10^n = 2^n \cdot 5^n,$ and we need the least $n$ for which $2^n$ or $5^n$ contains a digit $0.$

The powers $2^1, \ldots, 2^8$ are $2, 4, 8, 16, 32, 64, 128, 256$ — no zeros. The powers $5^1, \ldots, 5^7$ are $5, 25, 125, 625,$ $3125, 15625, 78125$ — no zeros — but $5^8 = 390625$ contains a $0.$

Hence every factorization of $10^8$ contains a digit $0,$ while $10^7 = 2^7 \cdot 5^7 = 128 \cdot 78125$ does not, so the answer is $8.$

2.

设 $u$ 和 $v$ 是满足 $0 \lt v \lt u$ 的整数。令 $A = (u, v)$ ，令 $B$ 为 $A$ 关于直线 $y = x$ 的反射，令 $C$ 为 $B$ 关于 $y$ -轴的反射，令 $D$ 为 $C$ 关于 $x$ -轴的反射，令 $E$ 为 $D$ 关于 $y$ -轴的反射。五边形 $ABCDE$ 的面积为 $451$ 。求 $u + v$ 。

Let $u$ and $v$ be integers satisfying $0 \lt v \lt u.$ Let $A = (u, v),$ let $B$ be the reflection of $A$ across the line $y = x,$ let $C$ be the reflection of $B$ across the $y$ -axis, let $D$ be the reflection of $C$ across the $x$ -axis, and let $E$ be the reflection of $D$ across the $y$ -axis. The area of pentagon $ABCDE$ is $451.$ Find $u + v.$

答案

知识点：变换坐标几何面积分割因式分解

难度评级：2300

小提示：

计算各顶点： $B = (v, u)$ 、 $C = (-v, u)$ 、 $D = (-v, -u)$ 、 $E = (v, -u)$ 。

Compute the vertices: $B = (v, u),$ $C = (-v, u),$ $D = (-v, -u),$ $E = (v, -u)$

大提示：

这个五边形是一个 $2v \times 2u$ 的长方形加上一个三角形；面积可因式分解为 $u(u + 3v)$ ，且 $451 = 11 \cdot 41$ 。

The pentagon is a $2v \times 2u$ rectangle plus a triangle; its area factors as $u(u + 3v),$ and $451 = 11 \cdot 41$

解答：

依次反射得到 $B = (v, u)$ 、 $C = (-v, u)$ 、 $D = (-v, -u)$ 、 $E = (v, -u)$ 。点 $B, C, D, E$ 形成宽 $2v$ 、高 $2u$ 的长方形，面积为 $4uv$ 。点 $A = (u, v)$ 向右突出，三角形 $ABE$ 的竖直底边 $BE$ 长为 $2u$ ，水平高为 $u - v$ ，面积为 $u(u - v)$ 。

五边形面积为 $\begin{aligned} 4uv + u(u - v) &= u^2 + 3uv \\ &= u(u + 3v) \\ &= 451 = 11 \cdot 41 \end{aligned}\text{。}$ 因为 $0 \lt v \lt u$ 有 $u \lt u + 3v \lt 4u$ ，排除 $1 \cdot 451$ 。因此 $u = 11$ 、 $u + 3v = 41$ ，得 $v = 10$ ， $v \lt u$ 。

所以 $u + v = 11 + 10 = 21$ 。

Carrying out the reflections, $B = (v, u),$ $C = (-v, u),$ $D = (-v, -u),$ and $E = (v, -u).$ The points $B, C, D, E$ form a rectangle of width $2v$ and height $2u,$ with area $4uv,$ and $A = (u, v)$ sticks out to its right. Triangle $ABE$ has vertical base $BE$ of length $2u$ and horizontal height $u - v,$ so its area is $u(u - v).$

The pentagon’s area is therefore $\begin{aligned} 4uv + u(u - v) &= u^2 + 3uv \\ &= u(u + 3v) \\ &= 451 = 11 \cdot 41. \end{aligned}$ Since $0 \lt v \lt u,$ we have $u \lt u + 3v \lt 4u,$ which rules out the factorization $1 \cdot 451.$ So $u = 11$ and $u + 3v = 41,$ giving $v = 10,$ which indeed satisfies $v \lt u.$

Thus $u + v = 11 + 10 = 21.$

3.

在 $(ax + b)^{2000}$ 的展开式中， $a$ 和 $b$ 是互质的正整数，且 $x^2$ 项和 $x^3$ 项的系数相等。求 $a + b$ 。

In the expansion of $(ax + b)^{2000},$ where $a$ and $b$ are relatively prime positive integers, the coefficients of $x^2$ and $x^3$ are equal. Find $a + b.$

答案

知识点：二项式定理最大公约数

难度评级：1890

小提示：

令系数 $\binom{2000}{2} a^2 b^{1998}$ 和 $\binom{2000}{3} a^3 b^{1997}$ 相等。

Set the coefficients $\binom{2000}{2} a^2 b^{1998}$ and $\binom{2000}{3} a^3 b^{1997}$ equal

大提示：

约去公共因子得到 $3b = 1998a$ ，再利用 $a$ 和 $b$ 互质这一条件。

Cancel common factors to get $3b = 1998a,$ then use that $a$ and $b$ are relatively prime

解答：

由二项式定理， $x^2$ 项和 $x^3$ 项的系数分别为 $\binom{2000}{2} a^2 b^{1998}$ 和 $\binom{2000}{3} a^3 b^{1997}$ 。令它们相等并约去 $a^2 b^{1997}$ ，得 $\binom{2000}{2} b = \binom{2000}{3} a\text{，}$ 所以 $b = \frac{1998}{3}\,a = 666a\text{。}$

因为 $\gcd(a, b) = 1$ ，只能 $a = 1$ 、 $b = 666$ 。因此 $a + b = 667$ 。

By the binomial theorem, the coefficients of $x^2$ and $x^3$ are $\binom{2000}{2} a^2 b^{1998}$ and $\binom{2000}{3} a^3 b^{1997}.$ Setting them equal and cancelling $a^2 b^{1997}$ gives $\binom{2000}{2} b = \binom{2000}{3} a,$ so $b = \frac{1998}{3}\,a = 666a.$

Since $\gcd(a, b) = 1,$ we must have $a = 1$ and $b = 666,$ so $a + b = 667.$

4.

图中长方形被分割成九个互不重叠的正方形。已知该长方形的宽和高是互质正整数，求长方形的周长。

The diagram shows a rectangle that has been dissected into nine non-overlapping squares. Given that the width and the height of the rectangle are relatively prime positive integers, find the perimeter of the rectangle.

答案

知识点：矩形正方形（几何）方程组

难度评级：2400

小提示：

设两个最小正方形的边长为 $x$ 和 $y$ ，并用它们表示其他所有正方形的边长。

Let the two smallest squares have sides $x$ and $y,$ and express every other square’s side in terms of them

大提示：

将长方形左侧和右侧得到的高度表达式相等，可得 $5x = 2y$ 。

Equate the two expressions for the rectangle’s height (left side versus right side) to get $5x = 2y$

解答：

设中间最小正方形边长为 $x$ ，其右下方的小正方形边长为 $y$ 。沿图中边长追踪，其余正方形边长依次可表示为 $x + y$ 、 $(x + y) + x = 2x + y$ 、 $(x + y) + (2x + y) = 3x + 2y$ 、 $(2x + y) + (3x + 2y) = 5x + 3y$ 。右侧高正方形的边长为 $4x + 4y$ ，右下方正方形边长为 $(4x + 4y) + y = 4x + 5y$ ，左下方正方形边长为 $x$ $+ (2x + y)$ $+ (5x + 3y)$ $= 8x + 4y$ 。

从左侧和右侧量长方形高度： $\begin{aligned} &(8x + 4y) + (5x + 3y) \\ &= (4x + 5y) \\ &\quad {}+ (4x + 4y) \end{aligned}\text{，}$ 化简得 $5x = 2y$ 。取最小正整数 $x = 2$ 、 $y = 5$ ，九个正方形边长为 $2, 5, 7, 9, 16, 25, 28, 33, 36$ ，长方形尺寸为 $(36 + 33) \times (36 + 25) = 69 \times 61$ 。这两个数互质，而且面积也核对无误： $69 \cdot 61 = 4209$ ，恰好等于九个正方形的面积之和。

周长为 $2(69 + 61) = 260$ 。

Let the tiniest square (in the middle) have side $x$ and the small square just below and to its right have side $y.$ Chasing edge lengths through the figure, the remaining squares have sides $x + y,$ then $(x + y) + x = 2x + y,$ then $(x + y) + (2x + y) = 3x + 2y,$ then $(2x + y) + (3x + 2y) = 5x + 3y$ (the top-left square). The tall square on the right spans the previous three along its left edge minus overlaps, giving side $4x + 4y;$ the bottom-right square has side $(4x + 4y) + y = 4x + 5y;$ and the bottom-left square has side $x$ $+ (2x + y)$ $+ (5x + 3y)$ $= 8x + 4y.$

Measuring the rectangle’s height along its left and right sides, $\begin{aligned} &(8x + 4y) + (5x + 3y) \\ &= (4x + 5y) \\ &\quad {}+ (4x + 4y), \end{aligned}$ which simplifies to $5x = 2y.$ Taking the smallest positive integers, $x = 2$ and $y = 5,$ the nine squares have sides $2, 5, 7, 9, 16, 25, 28, 33, 36,$ and the rectangle is $(36 + 33) \times (36 + 25) = 69 \times 61.$ These dimensions are relatively prime (any common scaling would break that), and the areas check: $69 \cdot 61 = 4209$ equals the sum of the nine squares’ areas.

The perimeter is $2(69 + 61) = 260.$

5.

两个盒子中各有黑、白两色弹珠，两个盒子中的弹珠总数为 $25$ 。从每个盒子中随机取出一个弹珠。两个都是黑色的概率为 $\frac{27}{50}$ ，两个都是白色的概率为 $\frac{m}{n}$ ，其中 $m$ 和 $n$ 是互质正整数。求 $m + n$ 。

Each of two boxes contains both black and white marbles, and the total number of marbles in the two boxes is $25.$ One marble is taken out of each box randomly. The probability that both marbles are black is $\frac{27}{50},$ and the probability that both marbles are white is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. What is $m + n?$

答案

知识点：基本概率整除性分类讨论

难度评级：2300

小提示：

若两个盒子分别有 $a$ 个和 $b$ 个弹珠，则 $ab$ 必须能被 $50$ 整除，这是由黑球同时被取出的概率分母为 $50$ 得到的。

If the boxes hold $a$ and $b$ marbles, then $ab$ is divisible by $50,$ since the black-black probability has denominator $50$

大提示：

在 $a + b = 25$ 下，只有 $\{5, 20\}$ 和 $\{10, 15\}$ 可行；再找黑球数乘积为 $\frac{27ab}{50}$ 的情况。

With $a + b = 25,$ only $\{5, 20\}$ and $\{10, 15\}$ work; find black counts whose product is $\frac{27ab}{50}$

解答：

设两个盒子分别有 $a$ 个和 $b$ 个弹珠，且 $a + b = 25$ ，其中黑球数分别为 $p$ 和 $q$ 。于是 $\frac{pq}{ab} = \frac{27}{50}$ ，所以 $50pq = 27ab$ 。由于 $\gcd(27, 50) = 1$ ，必须使 $ab$ 能被 $50$ 整除。检查 $a = 1, \ldots, 12$ 时的 $a(25 - a)$ ，只有 $\{a, b\} = \{20, 5\}$ 和 $\{10, 15\}$ 能给出 $50$ 的倍数。

若盒子大小为 $20$ 和 $5$ ： $pq = \frac{27 \cdot 100}{50} = 54$ 。因为每盒也都有白球， $p \le 19$ 且 $q \le 4$ ，只能 $p = 18$ 、 $q = 3$ 。白球数为 $2$ 和 $2$ ，所以白白概率为 $\frac{2}{20} \cdot \frac{2}{5} = \frac{1}{25}$ 。若盒子大小为 $10$ 和 $15$ ： $pq = \frac{27 \cdot 150}{50} = 81$ ，且 $p \le 9$ 、 $q \le 14$ ，所以 $p = q = 9$ 。白球数为 $1$ 和 $6$ ，再次得到 $\frac{1}{10} \cdot \frac{6}{15} = \frac{1}{25}$ 。

两种情况下概率都是 $\frac{1}{25}$ ，所以 $m + n = 1 + 25 = 26$ 。

Say the boxes hold $a$ and $b$ marbles with $a + b = 25,$ containing $p$ and $q$ black marbles. Then $\frac{pq}{ab} = \frac{27}{50},$ so $50pq = 27ab,$ and since $\gcd(27, 50) = 1,$ we need $ab$ to be divisible by $50.$ Checking $a(25 - a)$ for $a = 1, \ldots, 12,$ only $\{a, b\} = \{20, 5\}$ and $\{10, 15\}$ give a multiple of $50.$

For sizes $20$ and $5:$ $pq = \frac{27 \cdot 100}{50} = 54,$ and since each box also holds a white marble, $p \le 19$ and $q \le 4,$ forcing $p = 18,$ $q = 3.$ The white counts are $2$ and $2,$ so the white-white probability is $\frac{2}{20} \cdot \frac{2}{5} = \frac{1}{25}.$ For sizes $10$ and $15:$ $pq = \frac{27 \cdot 150}{50} = 81,$ and $p \le 9,$ $q \le 14$ force $p = q = 9.$ The white counts are $1$ and $6,$ giving $\frac{1}{10} \cdot \frac{6}{15} = \frac{1}{25}$ again.

Either way the probability is $\frac{1}{25},$ so $m + n = 1 + 25 = 26.$

6.

有多少个整数有序对 $(x, y)$ 满足 $0 \lt x \lt y \lt 10^6$ ，且 $x$ 和 $y$ 的算术平均数恰好比 $x$ 和 $y$ 的几何平均数大 $2$ ？

For how many ordered pairs $(x, y)$ of integers is it true that $0 \lt x \lt y \lt 10^6$ and that the arithmetic mean of $x$ and $y$ is exactly $2$ more than the geometric mean of $x$ and $y?$

答案

知识点：完全平方数根式代数变形

难度评级：2230

小提示：

条件可整理为 $(\sqrt{y} - \sqrt{x})^2 = 4$ ，所以 $\sqrt{y} = \sqrt{x} + 2$ 。

The condition rearranges to $(\sqrt{y} - \sqrt{x})^2 = 4,$ so $\sqrt{y} = \sqrt{x} + 2$

大提示：

证明 $\sqrt{x}$ 必须是整数，于是 $x = a^2$ 、 $y = (a + 2)^2$ ；再数满足 $y \lt 10^6$ 的 $a$ 。

Show $\sqrt{x}$ must be an integer, so $x = a^2$ and $y = (a + 2)^2;$ count the $a$ with $y \lt 10^6$

解答：

条件为 $\frac{x + y}{2} = \sqrt{xy} + 2$ ，即 $x + y - 2\sqrt{xy} = 4$ ，所以 $(\sqrt{y} - \sqrt{x})^2 = 4$ 。由于 $y \gt x$ 有 $\sqrt{y} - \sqrt{x} = 2$ 。注意 $\sqrt{xy} = \frac{x + y - 4}{2}$ 是有理数，因此 $\sqrt{y} + \sqrt{x} = \frac{y - x}{\sqrt{y} - \sqrt{x}} = \frac{y - x}{2}$ 也是有理数，所以 $\sqrt{x}$ 和 $\sqrt{y}$ 都是有理数；整数的有理平方根必为整数。

因此 $x = a^2$ ， $y = (a + 2)^2$ ，其中 $a$ 为正整数。约束 $y \lt 10^6$ 等价于 $a + 2 \le 999$ ，所以 $a$ 可取 $1, 2, \ldots, 997$ ，每个值都给出一个有效有序对。

所以共有 $997$ 个有序对。

The condition is $\frac{x + y}{2} = \sqrt{xy} + 2,$ that is, $x + y - 2\sqrt{xy} = 4,$ so $(\sqrt{y} - \sqrt{x})^2 = 4$ and (as $y \gt x$ ) $\sqrt{y} - \sqrt{x} = 2.$ Note $\sqrt{xy} = \frac{x + y - 4}{2}$ is rational, hence $\sqrt{y} + \sqrt{x} = \frac{y - x}{\sqrt{y} - \sqrt{x}} = \frac{y - x}{2}$ is rational too, so $\sqrt{x}$ and $\sqrt{y}$ are rational — and a rational square root of an integer is an integer.

Therefore $x = a^2$ and $y = (a + 2)^2$ for a positive integer $a.$ The constraint $y \lt 10^6$ means $a + 2 \le 999,$ so $a$ ranges over $1, 2, \ldots, 997,$ and each value gives a valid pair.

Hence there are $997$ ordered pairs.

7.

设 $x$ 、 $y$ 、 $z$ 是满足 $xyz = 1$ 、 $x + \frac{1}{z} = 5$ 和 $y + \frac{1}{x} = 29$ 的三个正数。若 $z + \frac{1}{y} = \frac{m}{n}$ ，其中 $m$ 和 $n$ 是互质正整数，求 $m + n$ 。

Suppose that $x,$ $y,$ and $z$ are three positive numbers that satisfy the equations $xyz = 1,$ $x + \frac{1}{z} = 5,$ and $y + \frac{1}{x} = 29.$ Then $z + \frac{1}{y} = \frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

答案

知识点：方程组代数变形对称性（代数）

难度评级：2330

小提示：

将三个表达式 $x + \frac{1}{z}$ 、 $y + \frac{1}{x}$ 、 $z + \frac{1}{y}$ 相乘并展开。

Multiply the three expressions $x + \frac{1}{z},$ $y + \frac{1}{x},$ $z + \frac{1}{y}$ together and expand

大提示：

由于 $xyz = 1$ ，这个乘积等于 $2$ 加上这三个表达式的和。

Because $xyz = 1,$ the product equals $2$ plus the sum of the same three expressions

解答：

令 $t = z + \frac{1}{y}$ 。展开三个表达式的乘积： $\begin{aligned} &\left(x + \frac{1}{z}\right)\!\left(y + \frac{1}{x}\right)\!\left(z + \frac{1}{y}\right) \\ &= xyz + \frac{1}{xyz} + \left(x + \frac{1}{z}\right) \\ &\quad {}+ \left(y + \frac{1}{x}\right) + \left(z + \frac{1}{y}\right) \end{aligned}\text{。}$ 因为 $xyz = 1$ ，左边为 $5 \cdot 29 \cdot t = 145t$ ，右边为 $2 + 5 + 29 + t = 36 + t$ 。

所以 $145t = 36 + t$ ，得到 $t = \frac{36}{144} = \frac{1}{4}$ 。因此 $m + n = 1 + 4 = 5$ 。

Let $t = z + \frac{1}{y}.$ Expanding the product of all three expressions, $\begin{aligned} &\left(x + \frac{1}{z}\right)\!\left(y + \frac{1}{x}\right)\!\left(z + \frac{1}{y}\right) \\ &= xyz + \frac{1}{xyz} + \left(x + \frac{1}{z}\right) \\ &\quad {}+ \left(y + \frac{1}{x}\right) + \left(z + \frac{1}{y}\right). \end{aligned}$ Since $xyz = 1,$ the left side is $5 \cdot 29 \cdot t = 145t$ and the right side is $2 + 5 + 29 + t = 36 + t.$

So $145t = 36 + t,$ giving $t = \frac{36}{144} = \frac{1}{4}.$ Thus $m + n = 1 + 4 = 5.$

8.

一个右圆锥形容器高 $12$ 英寸，底面半径为 $5$ 英寸。容器中密封有液体，当圆锥尖端朝下、底面水平放置时，液体深 $9$ 英寸。当圆锥尖端朝上、底面水平放置时，液体深度为 $m - n\sqrt[3]{p}$ 英寸，其中 $m$ 、 $n$ 、 $p$ 是正整数，且 $p$ 不被任何质数的立方整除。求 $m + n + p$ 。

A container in the shape of a right circular cone is $12$ inches tall and its base has a $5$ -inch radius. The liquid that is sealed inside is $9$ inches deep when the cone is held with its point down and its base horizontal. When the cone is held with its point up and its base horizontal, the liquid is $m - n\sqrt[3]{p}$ inches deep, where $m,$ $n,$ and $p$ are positive integers and $p$ is not divisible by the cube of any prime number. Find $m + n + p.$

答案

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

难度评级：2390

小提示：

尖端朝下时，液体形成一个与容器相似、比例为 $\frac{9}{12}$ 的圆锥，所以占总体积的 $\frac{27}{64}$ 。

Point down, the liquid is a cone similar to the container with ratio $\frac{9}{12},$ so it fills $\frac{27}{64}$ of the volume

大提示：

尖端朝上时，上方空隙是一个相似圆锥，占总体积的 $\frac{37}{64}$ ；取立方根求它的高度。

Point up, the empty space is a similar cone at the top; its share of the volume is $\frac{37}{64},$ so take a cube root to get its height

解答：

尖端朝下时，液体形成一个与容器相似的圆锥，线性比例为 $\frac{9}{12} = \frac{3}{4}$ ，所以体积占比为 $\left(\frac{3}{4}\right)^3 = \frac{27}{64}$ 。

尖端朝上时，顶端空隙是相似圆锥，体积占比为 $1 - \frac{27}{64} = \frac{37}{64}$ ，所以其高度为 $12 \sqrt[3]{\frac{37}{64}} = \frac{12 \sqrt[3]{37}}{4} = 3\sqrt[3]{37}\text{。}$ 因此液体深度为 $12 - 3\sqrt[3]{37}$ 英寸。

$37$ 不含质数的立方因子，所以 $m + n + p = 12 + 3 + 37 = 52$ 。

Held point down, the liquid forms a cone similar to the container with ratio $\frac{9}{12} = \frac{3}{4},$ so its volume is $\left(\frac{3}{4}\right)^3 = \frac{27}{64}$ of the container’s volume.

Held point up, the empty space is a similar cone at the apex with $1 - \frac{27}{64} = \frac{37}{64}$ of the volume, so its height is $12 \sqrt[3]{\frac{37}{64}} = \frac{12 \sqrt[3]{37}}{4} = 3\sqrt[3]{37}$ inches. The liquid is therefore $12 - 3\sqrt[3]{37}$ inches deep.

Since $37$ is cube-free, $m + n + p = 12 + 3 + 37 = 52.$

9.

方程组 $\begin{aligned} &\log_{10}(2000xy) \\ &\quad {}- (\log_{10} x)(\log_{10} y) = 4 \end{aligned}$ $\log_{10}(2yz) - (\log_{10} y)(\log_{10} z) = 1$ $\log_{10}(zx) - (\log_{10} z)(\log_{10} x) = 0$ 有两个解 $(x_1, y_1, z_1)$ 和 $(x_2, y_2, z_2)$ 。求 $y_1 + y_2$ 。

The system of equations $\begin{aligned} &\log_{10}(2000xy) \\ &\quad {}- (\log_{10} x)(\log_{10} y) = 4 \end{aligned}$ $\log_{10}(2yz) - (\log_{10} y)(\log_{10} z) = 1$ $\log_{10}(zx) - (\log_{10} z)(\log_{10} x) = 0$ has two solutions $(x_1, y_1, z_1)$ and $(x_2, y_2, z_2).$ Find $y_1 + y_2.$

答案

知识点：对数方程组换元法因式分解

难度评级：2560

小提示：

代换 $a = \log_{10} x$ 、 $b = \log_{10} y$ 、 $c = \log_{10} z$ ，把每个方程都化为关于 $a$ 、 $b$ 、 $c$ 的多项式方程。

Substitute $a = \log_{10} x,$ $b = \log_{10} y,$ $c = \log_{10} z$ to make each equation polynomial in $a,$ $b,$ $c$

大提示：

三个方程可因式分解：前两个变为 $(1 - a)(1 - b)$ $= (1 - b)(1 - c)$ $= \log_{10} 2$ ，第三个变为 $(1 - c)(1 - a) = 1$ 。

Each equation factors: the first two become $(1 - a)(1 - b)$ $= (1 - b)(1 - c)$ $= \log_{10} 2,$ and the third $(1 - c)(1 - a) = 1$

解答：

令 $a = \log_{10} x$ 、 $b = \log_{10} y$ 、 $c = \log_{10} z$ 。由 $\log_{10} 2000 = 4 - \log_{10} 5$ ，第一个方程化为 $a + b - ab = \log_{10} 5$ ，也就是 $(1 - a)(1 - b)$ $= 1 - \log_{10} 5$ $= \log_{10} 2$ 。同理，第二个方程给出 $(1 - b)(1 - c)$ $= 1 - (1 - \log_{10} 2)$ $= \log_{10} 2$ ，第三个方程给出 $(1 - c)(1 - a) = 1$ 。

前两个式子相除（ $1 - b \ne 0$ ），得 $1 - a = 1 - c$ 。由第三式， $(1 - a)^2 = 1$ ，所以 $1 - a = \pm 1$ 。若 $1 - a = 1$ ，则 $1 - b = \log_{10} 2$ ，因而 $b = 1 - \log_{10} 2 = \log_{10} 5$ 、 $y = 5$ ，对应解 $(x, y, z) = (1, 5, 1)$ 。若 $1 - a = -1$ ，则 $1 - b = -\log_{10} 2$ ，因而 $b = \log_{10} 20$ 、 $y = 20$ ，对应解 $(x, y, z) = (100, 20, 100)$ 。

因此 $y_1 + y_2 = 5 + 20 = 25$ 。

Let $a = \log_{10} x,$ $b = \log_{10} y,$ $c = \log_{10} z.$ Using $\log_{10} 2000 = 4 - \log_{10} 5,$ the first equation becomes $a + b - ab = \log_{10} 5,$ which factors as $(1 - a)(1 - b)$ $= 1 - \log_{10} 5$ $= \log_{10} 2.$ Similarly the second equation gives $(1 - b)(1 - c)$ $= 1 - (1 - \log_{10} 2)$ $= \log_{10} 2,$ and the third gives $(1 - c)(1 - a) = 1.$

Dividing the first two (note $1 - b \ne 0$ ) yields $1 - a = 1 - c,$ and then the third equation gives $(1 - a)^2 = 1,$ so $1 - a = \pm 1.$ If $1 - a = 1,$ then $1 - b = \log_{10} 2,$ so $b = 1 - \log_{10} 2 = \log_{10} 5$ and $y = 5$ (indeed $(x, y, z) = (1, 5, 1)$ works). If $1 - a = -1,$ then $1 - b = -\log_{10} 2,$ so $b = \log_{10} 20$ and $y = 20$ (from $(x, y, z) = (100, 20, 100)$ ).

Therefore $y_1 + y_2 = 5 + 20 = 25.$

10.

数列 $x_1$ ， $x_2$ ， $x_3$ ， $\ldots$ ， $x_{100}$ 满足：对每个从 $1$ 到 $100$ （含端点）的整数 $k$ ， $x_k$ 比其余 $99$ 个数之和小 $k$ 。已知 $x_{50} = \frac{m}{n}$ ，其中 $m$ 和 $n$ 是互质的正整数。求 $m + n$ 。

A sequence of numbers $x_1,$ $x_2,$ $x_3,$ $\ldots,$ $x_{100}$ has the property that, for every integer $k$ between $1$ and $100,$ inclusive, the number $x_k$ is $k$ less than the sum of the other $99$ numbers. Given that $x_{50} = \frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers, find $m + n.$

答案

知识点：方程组求和

难度评级：2330

小提示：

若 $S$ 是全部 $100$ 个数的和，条件为 $x_k = S - x_k - k$ 。

If $S$ is the sum of all $100$ numbers, the condition says $x_k = S - x_k - k$

大提示：

先用 $S$ 和 $k$ 表示 $x_k$ ，再把 $100$ 个等式相加求 $S$ 。

Solve for $x_k$ in terms of $S$ and $k,$ then add up all $100$ equations to find $S$

解答：

设 $S = x_1 + x_2 + \cdots + x_{100}$ 。条件给出 $x_k = (S - x_k) - k$ ，所以对每个 $k$ 都有 $x_k = \frac{S - k}{2}$ 。对 $k = 1, \ldots, 100$ 求和： $\begin{aligned} S &= \frac{100S - (1 + 2 + \cdots + 100)}{2} \\ &= \frac{100S - 5050}{2} \end{aligned}\text{，}$ 因此 $98S = 5050$ ，即 $S = \frac{2525}{49}$ 。

所以 $\begin{aligned} x_{50} &= \frac{S - 50}{2} \\ &= \frac{2525 - 2450}{98} = \frac{75}{98} \end{aligned}\text{，}$ 该分数已最简，故 $m + n = 75 + 98 = 173$ 。

Let $S = x_1 + x_2 + \cdots + x_{100}.$ The condition says $x_k = (S - x_k) - k,$ so $x_k = \frac{S - k}{2}$ for every $k.$ Summing over $k = 1, \ldots, 100,$ $\begin{aligned} S &= \frac{100S - (1 + 2 + \cdots + 100)}{2} \\ &= \frac{100S - 5050}{2}, \end{aligned}$ so $98S = 5050$ and $S = \frac{2525}{49}.$

Then $\begin{aligned} x_{50} &= \frac{S - 50}{2} \\ &= \frac{2525 - 2450}{98} = \frac{75}{98}, \end{aligned}$ which is in lowest terms, so $m + n = 75 + 98 = 173.$

11.

令 $S$ 为所有形如 $\frac{a}{b}$ 的数之和，其中 $a$ 和 $b$ 是 $1000$ 的互质正因数。求不超过 $\frac{S}{10}$ 的最大整数。

Let $S$ be the sum of all numbers of the form $\frac{a}{b},$ where $a$ and $b$ are relatively prime positive divisors of $1000.$ What is the greatest integer that does not exceed $\frac{S}{10}?$

答案

知识点：因数质因数分解等比数列

难度评级：2450

小提示：

因为 $1000 = 2^3 5^3$ ，且 $a, b$ 互质，质数 $2$ 最多出现在其中一个数中， $5$ 也一样。

Since $1000 = 2^3 5^3$ and $a, b$ are coprime, the prime $2$ appears in at most one of them, and likewise for $5$

大提示：

因此 $S$ 分解为 $\left(1 + 2 + 4 + 8 + \frac12 + \frac14 + \frac18\right)$ 乘以对应的 $5$ 的和。

So $S$ factors as $\left(1 + 2 + 4 + 8 + \frac12 + \frac14 + \frac18\right)$ times the analogous sum with $5$ s

解答：

写 $a = 2^i 5^j$ 、 $b = 2^k 5^l$ ，其中各指数均在 $0$ 到 $3$ 之间。互质意味着 $\min(i, k) = 0$ 且 $\min(j, l) = 0$ ，这两个条件彼此独立。当 $(a, b)$ 遍历所有互质数对时，因子 $2^{i - k}$ 恰好遍历 $\{2^{-3}, \ldots, 2^{3}\}$ 中的每个值， $5^{j - l}$ 也同理。因此 $\begin{aligned} S &= \scriptsize \left(1 + 2 + 4 + 8 + \tfrac{1}{2} + \tfrac{1}{4} + \tfrac{1}{8}\right) \\ &\quad \scriptsize {}\cdot \left(1 + 5 + 25 + 125 + \tfrac{1}{5} + \tfrac{1}{25} + \tfrac{1}{125}\right) \\ &= \frac{127}{8} \cdot \frac{19531}{125} \end{aligned}\text{。}$

这等于 $\frac{2480437}{1000} = 2480.437$ ，所以 $\frac{S}{10} = 248.0437$ 。不超过它的最大整数是 $248$ 。

Write $a = 2^i 5^j$ and $b = 2^k 5^l$ with exponents between $0$ and $3.$ Coprimality means $\min(i, k) = 0$ and $\min(j, l) = 0,$ and these two constraints are independent. So as $(a, b)$ runs over all coprime pairs, the factor $2^{i - k}$ independently takes each value in $\{2^{-3}, \ldots, 2^{3}\}$ exactly once, and similarly for $5^{j - l}.$ Hence $\begin{aligned} S &= \scriptsize \left(1 + 2 + 4 + 8 + \tfrac{1}{2} + \tfrac{1}{4} + \tfrac{1}{8}\right) \\ &\quad \scriptsize {}\cdot \left(1 + 5 + 25 + 125 + \tfrac{1}{5} + \tfrac{1}{25} + \tfrac{1}{125}\right) \\ &= \frac{127}{8} \cdot \frac{19531}{125}. \end{aligned}$

This equals $\frac{2480437}{1000} = 2480.437,$ so $\frac{S}{10} = 248.0437,$ and the greatest integer not exceeding it is $248.$

12.

给定函数 $f$ ，对所有实数 $x$ 都满足 $\begin{aligned} f(x) &= f(398 - x) \\ &= f(2158 - x) \\ &= f(3214 - x) \end{aligned}$ 列表 $f(0)$ ， $f(1)$ ， $f(2)$ ， $\ldots$ ， $f(999)$ 中最多能出现多少个不同的值？

Given a function $f$ for which $\begin{aligned} f(x) &= f(398 - x) \\ &= f(2158 - x) \\ &= f(3214 - x) \end{aligned}$ holds for all real $x,$ what is the largest number of different values that can appear in the list $f(0),$ $f(1),$ $f(2),$ $\ldots,$ $f(999)?$

答案

知识点：函数方程最大公约数对称性

难度评级：2920

小提示：

两个反射对称复合成一个平移： $f(398 - x) = f(2158 - x)$ 强制 $f(t) = f(t + 1760)$ ，类似地 $f(t) = f(t + 1056)$ 。

Two reflection symmetries compose to a translation: $f(398 - x) = f(2158 - x)$ forces $f(t) = f(t + 1760),$ and similarly $f(t) = f(t + 1056)$

大提示：

因此 $f$ 的周期为 $\gcd(1760, 1056) = 352$ ，并且还有对称性 $f(x) = f(46 - x)$ ；对模 $352$ 的剩余类按配对计数。

So $f$ has period $\gcd(1760, 1056) = 352,$ plus the symmetry $f(x) = f(46 - x);$ count residues mod $352$ up to that pairing

解答：

由于 $f(398 - x) = f(2158 - x)$ 对所有 $x$ 都成立，令 $t = 398 - x$ ，得到 $f(t) = f(t + 1760)$ ；同理， $f(2158 - x) = f(3214 - x)$ 给出周期 $1056$ 。因此 $f$ 有周期 $\gcd(1760, 1056) = 352$ 。把 $398$ 对模 $352$ 化简，原对称性 $f(x) = f(398 - x)$ 变为 $f(x) = f(46 - x)$ 。

因此 $f$ 由模 $352$ 的剩余类决定，且剩余类 $r$ 与 $46 - r$ 被迫取同值。配对方程 $2r \equiv 46 \pmod{352}$ 有两个固定点： $r = 23$ 和 $r = 199$ 。所以最多有 $\frac{352 - 2}{2} + 2 = 177$ 个等价类；又 $0, 1, \ldots, 999$ 覆盖模 $352$ 的所有剩余类，列表中最多有 $177$ 个不同值。

这个上界可达到：例如 $f(x) = \cos\frac{2\pi(x - 23)}{352}$ 满足给定三个对称性（ $398$ 、 $2158$ 、 $3214$ 都 $\equiv 46$ 模 $352$ ），并且只有被配对的剩余类会取相同值。所以答案是 $177$ 。

Since $f(398 - x) = f(2158 - x)$ for all $x,$ substituting $t = 398 - x$ gives $f(t) = f(t + 1760);$ likewise $f(2158 - x) = f(3214 - x)$ gives period $1056.$ Combining, $f$ has period $\gcd(1760, 1056) = 352.$ Reducing $398$ mod $352,$ the symmetry $f(x) = f(398 - x)$ becomes $f(x) = f(46 - x).$

So $f$ is determined by residues mod $352,$ with residues $r$ and $46 - r$ forced to share a value. This pairing has exactly two fixed points, from $2r \equiv 46 \pmod{352}:$ $r = 23$ and $r = 199.$ Hence there are at most $\frac{352 - 2}{2} + 2 = 177$ classes, and since $0, 1, \ldots, 999$ covers every residue mod $352,$ the list contains at most $177$ different values.

This is achievable: $f(x) = \cos\frac{2\pi(x - 23)}{352}$ satisfies all three given symmetries (each of $398,$ $2158,$ $3214$ is $\equiv 46$ mod $352$ ), and two integers get equal values only when their residues are paired. So the answer is $177.$

13.

在广阔草原中央，一辆消防车停在两条互相垂直的笔直公路交叉口。车在公路上的速度为每小时 $50$ 英里，在草原上的速度为每小时 $14$ 英里。考虑消防车在六分钟内可以到达的所有点所组成的区域。该区域的面积为 $\frac{m}{n}$ 平方英里，其中 $m$ 和 $n$ 是互质的正整数。求 $m + n$ 。

In the middle of a vast prairie, a firetruck is stationed at the intersection of two perpendicular straight highways. The truck travels at $50$ miles per hour along the highways and at $14$ miles per hour across the prairie. Consider the set of points that can be reached by the firetruck within six minutes. The area of this region is $\frac{m}{n}$ square miles, where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

答案

知识点：坐标几何切线面积最优化

难度评级：3160

小提示：

六分钟内，车可在公路上行驶 $5$ 英里，或在草原上行驶 $1.4$ 英里。先只看第一象限。

In six minutes the truck covers $5$ miles on highway or $1.4$ miles across the prairie. Work in one quadrant.

大提示：

若从公路上的 $(d, 0)$ 离开，可到达半径为 $1.4\left(1 - \frac{d}{5}\right)$ 的圆盘；这些圆盘并集的边界是从 $(5, 0)$ 到半径为 $1.4$ 的圆所作的切线。

Leaving the highway at $(d, 0)$ reaches a disk of radius $1.4\left(1 - \frac{d}{5}\right);$ the union of these disks is bounded by the tangent line from $(5, 0)$ to the circle of radius $1.4$

解答：

六分钟内车可沿公路行驶 $5$ 英里，或穿过草原行驶 $1.4$ 英里。最优路线是一段公路加一段直线草原路。以公路为坐标轴，在第一象限中，若先行驶到 $(d, 0)$ ，用时 $\frac{d}{50}$ 小时，剩余草原可达半径为 $14\left(\frac{1}{10} - \frac{d}{50}\right) = 1.4\left(1 - \frac{d}{5}\right)$ 英里。当 $d$ 从 $0$ 变到 $5$ 时，这些圆盘线性缩小到一点，所以它们的并集是以原点为圆心、半径 $1.4$ 的圆盘和点 $(5, 0)$ 的凸包，由从 $(5, 0)$ 作圆的切线围成。切线长为 $\sqrt{5^2 - 1.4^2} = 4.8$ ，对应 $7$ - $24$ - $25$ 比例，所以切线为 $7x + 24y = 35$ 。 $y$ -轴方向给出对称区域，其边界为 $24x + 7y = 35$ 。

两条切线交于 $P = \left(\frac{35}{31}, \frac{35}{31}\right)$ ，它到原点的距离为 $\frac{35\sqrt{2}}{31} \gt 1.4$ ，在圆外。因此第一象限可达区域恰好是顶点为 $(0, 0)$ 、 $(5, 0)$ 、 $P$ 、 $(0, 5)$ 的非凸四边形。沿原点到 $P$ 的对角线分成两个三角形，每个面积为 $\frac{1}{2} \cdot 5 \cdot \frac{35}{31}$ ，所以第一象限面积为 $\frac{175}{31}$ 。

整个区域由四份组成，面积为 $\frac{700}{31}$ 平方英里。因为 $\gcd(700, 31) = 1$ ，所以答案是 $700 + 31 = 731$ 。

In six minutes the truck can drive $5$ miles on a highway or $1.4$ miles across the prairie, and an optimal route is a highway stretch followed by a straight prairie segment. Work in the first quadrant with the highways as axes. Driving to $(d, 0)$ takes $\frac{d}{50}$ hours, leaving a prairie range of $14\left(\frac{1}{10} - \frac{d}{50}\right) = 1.4\left(1 - \frac{d}{5}\right)$ miles. As $d$ runs from $0$ to $5,$ these disks shrink linearly to a point, so their union is the “cone”: the convex hull of the disk of radius $1.4$ about the origin and the point $(5, 0),$ bounded by the tangent line from $(5, 0).$ The tangent length is $\sqrt{5^2 - 1.4^2} = 4.8,$ so the ratios are $7$ – $24$ – $25$ and the tangent line is $7x + 24y = 35.$ The $y$ -axis gives the mirror-image region bounded by $24x + 7y = 35.$

The two tangent lines meet at $P = \left(\frac{35}{31}, \frac{35}{31}\right),$ which lies at distance $\frac{35\sqrt{2}}{31} \gt 1.4$ from the origin — outside the circle — so in the first quadrant the reachable set is exactly the (non-convex) quadrilateral with vertices $(0, 0),$ $(5, 0),$ $P,$ $(0, 5).$ Splitting it along the diagonal from the origin to $P$ gives two triangles, each with area $\frac{1}{2} \cdot 5 \cdot \frac{35}{31},$ for a quadrant area of $\frac{175}{31}.$

The full region is four copies, with area $\frac{700}{31}$ square miles. Since $\gcd(700, 31) = 1,$ the answer is $700 + 31 = 731.$

14.

在三角形 $ABC$ 中，角 $B$ 与角 $C$ 相等。点 $P$ 和 $Q$ 分别在 $\overline{AC}$ 和 $\overline{AB}$ 上，且 $AP = PQ = QB = BC$ 。角 $ACB$ 的大小是角 $APQ$ 的 $r$ 倍，其中 $r$ 是正实数。求不超过 $1000r$ 的最大整数。

In triangle $ABC,$ it is given that angles $B$ and $C$ are congruent. Points $P$ and $Q$ lie on $\overline{AC}$ and $\overline{AB},$ respectively, so that $AP = PQ = QB = BC.$ Angle $ACB$ is $r$ times as large as angle $APQ,$ where $r$ is a positive real number. Find the greatest integer that does not exceed $1000r.$

答案

知识点：等腰三角形正弦定理三角恒等式

难度评级：2990

小提示：

设 $\angle A = \alpha$ ，并令 $AP = 1$ 。等腰三角形 $APQ$ 给出 $\angle AQP = \alpha$ 和 $AQ = 2\cos\alpha$ 。

Let $\angle A = \alpha$ and $AP = 1.$ Isosceles triangle $APQ$ gives $\angle AQP = \alpha$ and $AQ = 2\cos\alpha$

大提示：

因为 $BC = 1$ ，正弦定理给出 $AB = \frac{1}{2\sin(\frac{\alpha}{2})}$ ，而 $AQ + QB = AB$ 化为 $\sin\frac{3\alpha}{2} = \frac{1}{2}$ 。

With $BC = 1,$ the law of sines gives $AB = \frac{1}{2\sin(\frac{\alpha}{2})},$ and $AQ + QB = AB$ reduces to $\sin\frac{3\alpha}{2} = \frac{1}{2}$

解答：

设 $\angle A = \alpha$ ，并按比例缩放使 $AP = PQ = QB = BC = 1$ 。在三角形 $APQ$ 中， $AP = PQ$ ，所以 $\angle AQP = \angle A = \alpha$ ，从而 $\angle APQ = 180^\circ - 2\alpha$ ，且 $AQ = \frac{\sin 2\alpha}{\sin \alpha} = 2\cos\alpha$ 。在三角形 $ABC$ 中， $\angle B = \angle C = 90^\circ - \frac{\alpha}{2}$ ，所以 $\begin{aligned} AB &= \frac{BC \sin C}{\sin A} \\ &= \frac{\cos(\frac{\alpha}{2})}{\sin\alpha} = \frac{1}{2\sin(\frac{\alpha}{2})} \end{aligned}\text{。}$

由 $AQ + QB = AB$ ， $\begin{aligned} 2\cos\alpha + 1 &= \frac{1}{2\sin(\frac{\alpha}{2})} \\ &\quad\Longrightarrow\quad 4\sin\tfrac{\alpha}{2}\cos\alpha \\ &\quad {}+ 2\sin\tfrac{\alpha}{2} = 1 \end{aligned}\text{。}$ 由积化和差公式， $4\sin\frac{\alpha}{2}\cos\alpha$ $= 2\sin\frac{3\alpha}{2}$ $- 2\sin\frac{\alpha}{2}$ ，所以方程化为 $\sin\frac{3\alpha}{2} = \frac{1}{2}$ 。于是 $\alpha = 20^\circ$ 或 $\alpha = 100^\circ$ ，但后者会使 $AQ = 2\cos\alpha$ 为负，故 $\alpha = 20^\circ$ 。

此时 $\angle ACB = 80^\circ$ ， $\angle APQ = 140^\circ$ ，所以 $r = \frac{80}{140} = \frac{4}{7}$ 。于是 $\lfloor 1000r \rfloor = \left\lfloor \frac{4000}{7} \right\rfloor = 571$ 。

Let $\angle A = \alpha,$ and scale so $AP = PQ = QB = BC = 1.$ In triangle $APQ,$ the equal sides $AP = PQ$ give $\angle AQP = \angle A = \alpha,$ so $\angle APQ = 180^\circ - 2\alpha$ and, by the law of sines, $AQ = \frac{\sin 2\alpha}{\sin \alpha} = 2\cos\alpha.$ In triangle $ABC,$ $\angle B = \angle C = 90^\circ - \frac{\alpha}{2},$ so $\begin{aligned} AB &= \frac{BC \sin C}{\sin A} \\ &= \frac{\cos(\frac{\alpha}{2})}{\sin\alpha} = \frac{1}{2\sin(\frac{\alpha}{2})}. \end{aligned}$

Since $AQ + QB = AB,$ $\begin{aligned} 2\cos\alpha + 1 &= \frac{1}{2\sin(\frac{\alpha}{2})} \\ &\quad\Longrightarrow\quad 4\sin\tfrac{\alpha}{2}\cos\alpha \\ &\quad {}+ 2\sin\tfrac{\alpha}{2} = 1. \end{aligned}$ By the product-to-sum identity, $4\sin\frac{\alpha}{2}\cos\alpha$ $= 2\sin\frac{3\alpha}{2}$ $- 2\sin\frac{\alpha}{2},$ so the equation collapses to $\sin\frac{3\alpha}{2} = \frac{1}{2}.$ Then $\alpha = 20^\circ$ or $\alpha = 100^\circ,$ but the latter makes $AQ = 2\cos\alpha$ negative, so $\alpha = 20^\circ.$

Now $\angle ACB = 80^\circ$ and $\angle APQ = 140^\circ,$ so $r = \frac{80}{140} = \frac{4}{7},$ and $\lfloor 1000r \rfloor = \left\lfloor \frac{4000}{7} \right\rfloor = 571.$

15.

一叠 $2000$ 张卡片分别标有 $1$ 到 $2000$ ，每张卡片标号不同，原始顺序不是数字顺序。先取走顶端卡片放到桌上，再把下一张卡片移到底部。然后再取走新的顶端卡片，放在桌上已有卡片的右侧，再把下一张卡片移到底部。这个过程一直重复，直到所有卡片都放到桌上。结果从左到右读出卡片标号恰为升序 $1$ ， $2$ ， $3$ ， $\ldots$ ， $1999$ ， $2000$ 。在原始卡堆中，标号为 $1999$ 的卡片上方有多少张卡片？

A stack of $2000$ cards is labelled with the integers from $1$ to $2000,$ with different integers on different cards. The cards in the stack are not in numerical order. The top card is removed from the stack and placed on the table, and the next card is moved to the bottom of the stack. The new top card is removed from the stack and placed on the table, to the right of the card already there, and the next card in the stack is moved to the bottom of the stack. The process — placing the top card to the right of the cards already on the table and moving the next card in the stack to the bottom of the stack — is repeated until all cards are on the table. It is found that, reading from left to right, the labels on the cards are now in ascending order: $1,$ $2,$ $3,$ $\ldots,$ $1999,$ $2000.$ In the original stack of cards, how many cards were above the card labelled $1999?$

答案

知识点：排列过程模拟找规律

难度评级：3060

小提示：

跟踪原始位置组成的队列：取走队首，再把新的队首移到队尾。标号为 $k$ 的卡片是第 $k$ 张被取走的卡片。

Track original positions in a queue: remove the front card, then send the next card to the back. The card labelled $k$ is the $k$ -th one removed.

大提示：

每一轮会取走幸存者中的隔一个位置：先取奇数位置，再取 $\equiv 2 \pmod 4$ 的位置，再取 $\equiv 4 \pmod 8$ 的位置，如此追踪到最后两张。

Each pass removes every other survivor: first the odd positions, then positions $\equiv 2 \pmod 4,$ then $\equiv 4 \pmod 8,$ and so on. Follow the process down to the last two cards.

解答：

将原始位置编号为 $1$ （顶端）到 $2000$ （底端），并把它们放入队列。每步取走队首位置（得到下一个标号 $1, 2, 3, \ldots$ ），再把新的队首移到队尾。因此标号 $1999$ 的卡片是倒数第二张被取走的卡片，我们要找其原始位置。

第一轮取走奇数位置 $1, 3, \ldots, 1999$ ，它们获得标号 $1$ 到 $1000$ 。这一轮结束时将 $2000$ 移到队尾，所以下一轮仍从队列 $2, 4, \ldots, 2000$ 的队首开始。后续各轮依次取走 $2, 6, \ldots, 1998$ （即满足 $\equiv 2 \bmod 4$ 的位置）、 $4, 12, \ldots, 1996$ 、 $8, 24, \ldots, 1992$ ，再取走 $16, 48, \ldots, 1968, 2000$ （共 $63$ 个满足 $\equiv 16 \bmod 32$ 的位置）。该轮从奇数个 $125$ 张牌中交替取牌，所以队列的交替方向发生偏移；剩下的 $62$ 个 $32$ 的倍数在队列中按 $64, 96, \ldots, 1984, 32$ 排列。

继续同样的过程，接下来各轮依次取走 $64, 128, \ldots, 1984$ 、 $96, 224, \ldots, 1888, 32$ 、 $288, 544, \ldots, 1824$ 、 $160, 672, 1184, 1696$ 、 $416, 1440$ 。最后两张被取走的是 $928$ 和 $1952$ 。所以标号 $1999$ 位于原始位置 $928$ ，其上方有 $927$ 张卡片。

Number the original positions $1$ (top) through $2000$ (bottom) and put them in a queue. Each step removes the front position (which receives the next label $1, 2, 3, \ldots$ ) and sends the new front to the back. So the card labelled $1999$ is the next-to-last card removed, and we must find which original position survives that long.

The first pass removes the odd positions $1, 3, \ldots, 1999$ (labels $1$ through $1000$ ) and, since it ends by sending $2000$ to the back, the next pass again starts by removing the front of the queue $2, 4, \ldots, 2000.$ Successive passes therefore remove $2, 6, \ldots, 1998$ (the positions $\equiv 2 \bmod 4$ ), then $4, 12, \ldots, 1996,$ then $8, 24, \ldots, 1992,$ then $16, 48, \ldots, 1968, 2000$ (the $63$ positions $\equiv 16 \bmod 32$ ). That last pass ran through an odd number ( $125$ ) of cards, so the alternation shifts: the $62$ surviving multiples of $32$ now sit in the queue as $64, 96, \ldots, 1984, 32.$

Continuing the same removal pattern from that queue, the next rounds remove $64, 128, \ldots, 1984;$ then $96, 224, \ldots, 1888, 32;$ then $288, 544, \ldots, 1824;$ then $160, 672, 1184, 1696;$ then $416, 1440;$ and the final two cards removed are $928$ and $1952.$ So label $1999$ goes to the card at original position $928,$ which had $927$ cards above it.