设 $A=\{1,2,3, \cdots, 17\}$．对于映射 $f : A \rightarrow A$，记 $f^{[1]}(x)=f(x), f^{[k+1]}(x)=f\left(f^{[k]}(x)\right)(k \in \mathbf{N})$ 设从 $A$ 到 $A$ 的一一射射f满足条件：存在自然数 $M$，使得
（1）当 $m<M, 1 \leqslant i \leqslant 16$ 时，有 $f^{[m]}(i+1)-f^{[m]}(i) \not\equiv \pm 1(\bmod 17)$，$f^{[m]}(1)-f^{[m]}(17) \not\equiv \pm 1(\bmod 17)$
（2）当 $1 \leqslant i \leqslant 16$ 时，有 $f^{[M]}(i+1)-f^{[M]}(i) \equiv 1$ 或 $-1(\bmod 17)$；$f^{[M]}(1)-f^{[M]}(17)\equiv 1$ 或 $-1(\bmod 17)$
试对满足上述条件的一切 $f$，求所对应的 $M$ 的最大可能值，并证明你的结论．
（1）当 $m<M, 1 \leqslant i \leqslant 16$ 时，有 $f^{[m]}(i+1)-f^{[m]}(i) \not\equiv \pm 1(\bmod 17)$，$f^{[m]}(1)-f^{[m]}(17) \not\equiv \pm 1(\bmod 17)$
（2）当 $1 \leqslant i \leqslant 16$ 时，有 $f^{[M]}(i+1)-f^{[M]}(i) \equiv 1$ 或 $-1(\bmod 17)$；$f^{[M]}(1)-f^{[M]}(17)\equiv 1$ 或 $-1(\bmod 17)$
试对满足上述条件的一切 $f$，求所对应的 $M$ 的最大可能值，并证明你的结论．
【难度】
【出处】
1997第12届CMO试题
【标注】
【答案】
略
【解析】
所求 $M_0= 8$．先证 $M_0\geqslant 8$．
事实上，可令映射 $f(i)\equiv 3 i-2(\bmod 17)$，其中 $i \in A, f(i) \in A$．若 $f(i) \equiv f(j)(\bmod 17)$ 则 $3 i-2\equiv3 j-2(\bmod 17)$ 有 $i \equiv j(\bmod 17)$ 所以 $i=j$
映射 $f$ 为从 $A$ 到 $A$ 的一一映射，又由映射 $f$ 的定义，易知 $f^{[n]}(i) \equiv 3^{n} \cdot i-3^{n}+1(\bmod 17)$ 若 $\begin{cases}
f^{[M]}(i+1)-f^{[M]}(i) \equiv 1 或 -1(\bmod 17)\\
f^{[M]}(1)-f^{[M]}(17)\equiv 1 或 -1(\bmod 17)\\
\end{cases}$ 则
$\begin{cases}
\left[3^{M}(i+1)-3^{M}+1\right]-\left[3^{M} \cdot i-3^{M}+1\right] \equiv+1或-1(\bmod 17)\\
1-\left[3^{M} \times 17-3^{M}+1\right] \equiv+1或-1(\bmod 17)\\
\end{cases}$
即 $3^{M} \equiv+1或 -1(\bmod 17)$ 但 $3^{1} \equiv 3,3^{2} \equiv 9,3^{3} \equiv 10,3^{4} \equiv 13,3^{5} \equiv 5,3^{6} \equiv 15,3^{7}\equiv 11,3^{8} \equiv-1(\bmod 17)$，故 $M_0\geqslant 8$．
任作一个凸 $17$ 边形，$A_1A_2\cdots A_{17}$，记作 $G$．我们先规定：
当 $i + 1=18$ 时，取 $i + 1 $ 为1；当 $i - 1 = 0$ 时，取 $i-1=17$．
然后按如下规则连线段：若 $1 \leqslant m<M_{0}, f^{[m]}(i)=a, f^{[m]}(i+1)=b$ 时，就连线段 $A_{a} A_{b}$．显然，所连线段必为 $G$ 的对角线．可以证明：所连的对角线没有重复．事实上，若有两条连线相同，即存在 $i,j$ 及 $M_{0}>p>q>0$，使 $\begin{aligned} f^{[p]}(i) &=f^{f [q ]}(j) , f^{[p]}(i+1) =f^{f [q ]}(j+1) \end{aligned}$ 或 $f^{[p]}(i+1)=f^{f [q ]}(j-1)$ 于是，有
$\left\{\begin{array}{l}{f^{[p-q]}(i)=j} \\ {f^{[p-q]}(i+1)=j+1或 f^{[p-q]}(i+1)=j-1 }\end{array}\right.$
且 $M_{0}>p-q>0$，这显然与 $M_0$ 的定义矛盾．所连对角线没有重复．
但 $G$ 共有 $17 \times 7$ 条对角线．所以 $17 \times\left(M_{0}-1\right) \leqslant 17 \times 7$ 故 $M_{0} \leqslant 8$．
事实上，可令映射 $f(i)\equiv 3 i-2(\bmod 17)$，其中 $i \in A, f(i) \in A$．若 $f(i) \equiv f(j)(\bmod 17)$ 则 $3 i-2\equiv3 j-2(\bmod 17)$ 有 $i \equiv j(\bmod 17)$ 所以 $i=j$
映射 $f$ 为从 $A$ 到 $A$ 的一一映射，又由映射 $f$ 的定义，易知 $f^{[n]}(i) \equiv 3^{n} \cdot i-3^{n}+1(\bmod 17)$ 若 $\begin{cases}
f^{[M]}(i+1)-f^{[M]}(i) \equiv 1 或 -1(\bmod 17)\\
f^{[M]}(1)-f^{[M]}(17)\equiv 1 或 -1(\bmod 17)\\
\end{cases}$ 则
$\begin{cases}
\left[3^{M}(i+1)-3^{M}+1\right]-\left[3^{M} \cdot i-3^{M}+1\right] \equiv+1或-1(\bmod 17)\\
1-\left[3^{M} \times 17-3^{M}+1\right] \equiv+1或-1(\bmod 17)\\
\end{cases}$
即 $3^{M} \equiv+1或 -1(\bmod 17)$ 但 $3^{1} \equiv 3,3^{2} \equiv 9,3^{3} \equiv 10,3^{4} \equiv 13,3^{5} \equiv 5,3^{6} \equiv 15,3^{7}\equiv 11,3^{8} \equiv-1(\bmod 17)$，故 $M_0\geqslant 8$．
任作一个凸 $17$ 边形，$A_1A_2\cdots A_{17}$，记作 $G$．我们先规定：
当 $i + 1=18$ 时，取 $i + 1 $ 为1；当 $i - 1 = 0$ 时，取 $i-1=17$．
然后按如下规则连线段：若 $1 \leqslant m<M_{0}, f^{[m]}(i)=a, f^{[m]}(i+1)=b$ 时，就连线段 $A_{a} A_{b}$．显然，所连线段必为 $G$ 的对角线．可以证明：所连的对角线没有重复．事实上，若有两条连线相同，即存在 $i,j$ 及 $M_{0}>p>q>0$，使 $\begin{aligned} f^{[p]}(i) &=f^{f [q ]}(j) , f^{[p]}(i+1) =f^{f [q ]}(j+1) \end{aligned}$ 或 $f^{[p]}(i+1)=f^{f [q ]}(j-1)$ 于是，有
$\left\{\begin{array}{l}{f^{[p-q]}(i)=j} \\ {f^{[p-q]}(i+1)=j+1或 f^{[p-q]}(i+1)=j-1 }\end{array}\right.$
且 $M_{0}>p-q>0$，这显然与 $M_0$ 的定义矛盾．所连对角线没有重复．
但 $G$ 共有 $17 \times 7$ 条对角线．所以 $17 \times\left(M_{0}-1\right) \leqslant 17 \times 7$ 故 $M_{0} \leqslant 8$．
答案
解析
备注
