设 $ABCD$ 是块矩形的板，$|AB|=20$，$|BC|=12$，这块板分成 $20×12$ 个单位正方形．
设 $r$ 是给定的正整数，当且仅当这两个小方块的中心之间的距离等于 $\sqrt{r}$ 时，可以把放在其中一个小方块里的硬币移到另一个小方块中．
在以 $A$ 为顶点的小方块中放有一硬币，我们的工作是要找出一系列的移动，使这硬币移到以 $B$ 为顶点的小方块中．
（1）求证：当 $r$ 被 $2$ 或 $3$ 整除时，这一工作不可能完成；
（2）求证：当 $r=73$ 时，这项工作可以完成；
（3）当 $r=97$ 时，这项工作能否完成？（芬兰）
设 $r$ 是给定的正整数，当且仅当这两个小方块的中心之间的距离等于 $\sqrt{r}$ 时，可以把放在其中一个小方块里的硬币移到另一个小方块中．
在以 $A$ 为顶点的小方块中放有一硬币，我们的工作是要找出一系列的移动，使这硬币移到以 $B$ 为顶点的小方块中．
（1）求证：当 $r$ 被 $2$ 或 $3$ 整除时，这一工作不可能完成；
（2）求证：当 $r=73$ 时，这项工作可以完成；
（3）当 $r=97$ 时，这项工作能否完成？（芬兰）
【难度】
【出处】
1996年第37届IMO试题
【标注】
【答案】
略
【解析】
对小方格进行编号，用 $(i,j)$ 表示第 $i$ 行，第 $j$ 列的单位小方格，$i=1,2,\cdots,12;j=1,2,\cdots,20$．由题设可知，在 $(i_1,j_1)$ 中的硬币能够动到 $(i_2,j_2)$ 的条件为 $(i_1-i_2)^2+(j_1-j_2)^2=r$．
（1）若 $2|r$，则 $(i_1-i_2)^2+(j_1-j_2)^2$ 为偶数，从而 $i_1-i_2$ 与 $j_1-j_2$ 的奇偶性相同，即 $i_1-i_2\equiv j_1-j_2\pmod{2}$，从而 $i_1-j_1\equiv i_2-j_2\pmod{2}$．
由于 $A,B$ 的编号分别为 $(1,1),(1,20)$，而 $1-1\not\equiv 1-20\pmod{2}$，所以，不可能找出一系列的移动把硬币从 $(1,1)$ 移到 $(1,20)$．
若 $3|r$，则 $(i_1-i_2)^2+(j_1-j_2)^2\equiv 0\pmod{3}$，由于一个整数的平方模 $3$ 为 $0$ 或 $1$，故只能是 $i_1-i_2\equiv j_1-j_2\equiv 0\pmod{3}$，所以 $i_1-j_1\equiv i_2-j_2\pmod{3}$．
因为 $1-1\equiv 1-20\pmod{3}$，所以，不可能找出一系列的移动把硬币从 $(1,1)$ 移到 $(1,20)$．
（2）当 $r=73$ 时，因为 $73=8^2+3^2$，具体的移动步骤为 $(1,1)\rightarrow (4,9)\rightarrow (7,17)\rightarrow (10,9)\rightarrow (2,12)\rightarrow (5,20)\rightarrow (8,12)\rightarrow (11,20)\rightarrow (3,17)\rightarrow (6,9)\rightarrow (9,17)\rightarrow (1,20)$
（3）当 $r=97$ 时，答案是否定的，即不存在符合要求的一系列移动．若不然，$(i_1-i_2)^2+(j_1-j_2)^2=97$，而 $97=4^2+9^2$，因此 $|i_1-i-2|,|j_1,j_2|$ 中一个为 $4$，另一个为 $9$．把这块板按如下图所示的方式染色，于是，黑格中硬币只能移到黑格中，由于 $(1,1)$ 是黑格，$(1,20)$ 是白格，因此，无论怎样移动，不可能把硬币从 $(1,1)$ 移动 $(1,20)$．
（1）若 $2|r$，则 $(i_1-i_2)^2+(j_1-j_2)^2$ 为偶数，从而 $i_1-i_2$ 与 $j_1-j_2$ 的奇偶性相同，即 $i_1-i_2\equiv j_1-j_2\pmod{2}$，从而 $i_1-j_1\equiv i_2-j_2\pmod{2}$．
由于 $A,B$ 的编号分别为 $(1,1),(1,20)$，而 $1-1\not\equiv 1-20\pmod{2}$，所以，不可能找出一系列的移动把硬币从 $(1,1)$ 移到 $(1,20)$．
若 $3|r$，则 $(i_1-i_2)^2+(j_1-j_2)^2\equiv 0\pmod{3}$，由于一个整数的平方模 $3$ 为 $0$ 或 $1$，故只能是 $i_1-i_2\equiv j_1-j_2\equiv 0\pmod{3}$，所以 $i_1-j_1\equiv i_2-j_2\pmod{3}$．
因为 $1-1\equiv 1-20\pmod{3}$，所以，不可能找出一系列的移动把硬币从 $(1,1)$ 移到 $(1,20)$．
（2）当 $r=73$ 时，因为 $73=8^2+3^2$，具体的移动步骤为 $(1,1)\rightarrow (4,9)\rightarrow (7,17)\rightarrow (10,9)\rightarrow (2,12)\rightarrow (5,20)\rightarrow (8,12)\rightarrow (11,20)\rightarrow (3,17)\rightarrow (6,9)\rightarrow (9,17)\rightarrow (1,20)$
（3）当 $r=97$ 时，答案是否定的，即不存在符合要求的一系列移动．若不然，$(i_1-i_2)^2+(j_1-j_2)^2=97$，而 $97=4^2+9^2$，因此 $|i_1-i-2|,|j_1,j_2|$ 中一个为 $4$，另一个为 $9$．把这块板按如下图所示的方式染色，于是，黑格中硬币只能移到黑格中，由于 $(1,1)$ 是黑格，$(1,20)$ 是白格，因此，无论怎样移动，不可能把硬币从 $(1,1)$ 移动 $(1,20)$．
答案
解析
备注
