有1000个开关，每个开关有 $A$，$B$，$C$，$D$ 4个位置，当每个开关位置改变时只可能从 $A$ 到 $B$，从 $B$ 到 $C$，从 $C$ 到 $D$ 或从 $D$ 到 $A$．开始时，每个开关都在位置 $A$ 上，这1000个开关上都用不同的整数 ${{2}^{x}}{{3}^{y}}{{5}^{z}}$ 标号，其中 $x$，$y$，$z$ 在 $0\tilde{ }9$ 中取值．
在有1000个步骤的操作中，到第 $i$ 个步骤时，第 $i$ 个开关位置前进一位，其他标号能整除第 $i$ 个开关标号的开关也前进一位．问当这1000个步骤执行完时，有多少个开关处在位置 $A$ 上？
在有1000个步骤的操作中，到第 $i$ 个步骤时，第 $i$ 个开关位置前进一位，其他标号能整除第 $i$ 个开关标号的开关也前进一位．问当这1000个步骤执行完时，有多少个开关处在位置 $A$ 上？
【难度】
【出处】
1999年第17届美国数学邀请赛（AIME）
【标注】
【答案】
650
【解析】
由题意知，当且仅当一个开关前进的次数为 $4k\left( k\in \mathbf{N} \right)$ 时，最后它才能处在位置 $A$ 上．
设 $S=\left\{{{2}^{x}}{{3}^{y}}{{5}^{z}}|x,y,z\in \left\{ 0,1,2,3,\cdots,9 \right\} \right\}$，由题意，当且仅当一个开关的标号在 $S$ 中有多少个倍数（包括自身），它就前进几次．对任意 ${{2}^{x}}{{3}^{y}}{{5}^{z}}\in S$，它在 $S$ 中的倍数有 $\left( 10-x \right)\left( 10-y \right)\left( 10-z \right)$ 个，故当且仅当 $4|\left(10-x \right)\left( 10-y \right)\left( 10-z \right)$ 时，标号为 ${{2}^{x}}{{3}^{y}}{{5}^{z}}$ 的开关最后处于位置 $A$．
又由于 $4\overset{}{\mathop{|}} \left(10-x \right)\left( 10-y \right)\left( 10-z \right)$ 时，$x$，$y$，$z$ 均为奇数，或者 $x$，$y$，$z$ 中有两个为奇数，另一个除以 $4$ 余 $0$，此时 $\left( x,y,z \right)$ 有 ${{5}^{3}}+{{5}^{2}}\cdot 3\cdot 3=350$ 个，故满足 $4|\left(10-x \right)\cdot \left( 10-y \right)\left( 10-z \right)$ 的 $\left( x , y,z \right)$ 有 ${{10}^{3}}-350=650$ 个，从而有650个开关处在位置 $A$ 上．
设 $S=\left\{{{2}^{x}}{{3}^{y}}{{5}^{z}}|x,y,z\in \left\{ 0,1,2,3,\cdots,9 \right\} \right\}$，由题意，当且仅当一个开关的标号在 $S$ 中有多少个倍数（包括自身），它就前进几次．对任意 ${{2}^{x}}{{3}^{y}}{{5}^{z}}\in S$，它在 $S$ 中的倍数有 $\left( 10-x \right)\left( 10-y \right)\left( 10-z \right)$ 个，故当且仅当 $4|\left(10-x \right)\left( 10-y \right)\left( 10-z \right)$ 时，标号为 ${{2}^{x}}{{3}^{y}}{{5}^{z}}$ 的开关最后处于位置 $A$．
又由于 $4\overset{}{\mathop{|}} \left(10-x \right)\left( 10-y \right)\left( 10-z \right)$ 时，$x$，$y$，$z$ 均为奇数，或者 $x$，$y$，$z$ 中有两个为奇数，另一个除以 $4$ 余 $0$，此时 $\left( x,y,z \right)$ 有 ${{5}^{3}}+{{5}^{2}}\cdot 3\cdot 3=350$ 个，故满足 $4|\left(10-x \right)\cdot \left( 10-y \right)\left( 10-z \right)$ 的 $\left( x , y,z \right)$ 有 ${{10}^{3}}-350=650$ 个，从而有650个开关处在位置 $A$ 上．
答案
解析
备注
