Question

有 $1000$ 个开关，每个开关有四个位置，记为 $A$ 、 $B$ 、 $C$ 和 $D$ 。任意开关改变位置时，只会从 $A$ 到 $B$ 、从 $B$ 到 $C$ 、从 $C$ 到 $D$ 或从 $D$ 到 $A$ 。初始时每个开关都在位置 $A$ 。这些开关分别标有 $1000$ 个不同的整数 $2^x 3^y 5^z$ ，其中 $x$ 、 $y$ 和 $z$ 分别取 $0$ 、 $1$ 、 $\ldots$ 、 $9$ 。在第 $i$ 步（整个过程共有 $1000$ 步），第 $i$ 个开关前进一档，同时所有标签能整除第 $i$ 个开关标签的其他开关也前进一档。完成第 $1000$ 步后，有多少个开关会在位置 $A$ ？

There is a set of $1000$ switches, each of which has four positions, called $A,$ $B,$ $C,$ and $D.$ When the position of any switch changes, it is only from $A$ to $B,$ from $B$ to $C,$ from $C$ to $D,$ or from $D$ to $A.$ Initially each switch is in position $A.$ The switches are labeled with the $1000$ different integers $2^x 3^y 5^z,$ where $x,$ $y,$ and $z$ take on the values $0,$ $1,$ $\ldots,$ $9.$ At step $i$ of a $1000$ -step process, the $i$ th switch is advanced one step, and so are all the other switches whose labels divide the label on the $i$ th switch. After step $1000$ has been completed, how many switches will be in position $A?$

答案

答案：650

知识点：质因数分解模运算补集计数

难度评级：2650

小提示：

每遇到一个标签为 $d$ 的倍数的步骤，标签为 $d$ 的开关就会前进一次；用指数来计算这些倍数

The switch labeled $d$ is advanced once for every label that is a multiple of $d;$ count those multiples in terms of the exponents

大提示：

标签 $2^x 3^y 5^z$ 会前进 $(10 - x)(10 - y)(10 - z)$ 次；数出使这个乘积不是 $4$ 的倍数的三元组

The label $2^x 3^y 5^z$ advances $(10 - x)(10 - y)(10 - z)$ times; count the triples for which this product is not a multiple of $4$

解答：

标签为 $d$ 的开关，恰好会在第 $i$ 个开关的标签为 $d$ 的倍数时前进一步。在这些标签中， $2^x 3^y 5^z$ 的倍数为 $2^{x'} 3^{y'} 5^{z'}$ ，其中 $x \le x' \le 9$ 等条件成立，所以这个开关会前进 $(10 - x)(10 - y)(10 - z)$ 次。它回到位置 $A$ 当且仅当这个次数是 $4$ 的倍数。

令 $a = 10 - x$ 、 $b = 10 - y$ 、 $c = 10 - z$ ，每个都从 $1$ 到 $10$ 取值。我们计算 $abc$ 不被 $4$ 整除的三元组：要么三者全为奇数，要么恰有一个是偶数但不被 $4$ 整除。在 $1, \ldots, 10$ 中有 $5$ 个奇数，以及 $3$ 个数（ $2$ 、 $6$ 、 $10$ ）是奇数的两倍。第一类有 $5^3 = 125$ 个，第二类有 $3 \cdot 3 \cdot 5^2 = 225$ 个，共 $350$ 个。

因此 $1000 - 350 = 650$ 个开关最终在位置 $A$ 。

The switch labeled $d$ is advanced exactly once for each step $i$ whose label is a multiple of $d.$ The multiples of $2^x 3^y 5^z$ among the labels are the $2^{x'} 3^{y'} 5^{z'}$ with $x \le x' \le 9,$ etc., so that switch advances $(10 - x)(10 - y)(10 - z)$ times. It returns to position $A$ exactly when this count is a multiple of $4.$

Write $a = 10 - x,$ $b = 10 - y,$ $c = 10 - z,$ each ranging over $1$ through $10.$ We count the triples where $abc$ is not divisible by $4:$ either all three are odd, or exactly one is even but not divisible by $4.$ Among $1, \ldots, 10$ there are $5$ odd values and $3$ values ( $2,$ $6,$ $10$ ) that are twice an odd number. That gives $5^3 = 125$ triples of the first kind and $3 \cdot 3 \cdot 5^2 = 225$ of the second, or $350$ in all.

Therefore $1000 - 350 = 650$ switches end in position $A.$

1999 AIME 第 7 题

答案：650

难度评级：2650

小提示：

大提示：

解答：

其他年份的第 7 题