设平面上有 $n\left( n\geqslant 4 \right)$ 个点 ${{V}_{1}}\text{,}{{V}_{2}}\text{,}\cdots \text{,}{{V}_{n}}$，任意三点不共线，某些点之间连有线段。把标号分别为 $1\text{,}2\text{,}\cdots \text{,}n$ 的 $n$ 枚棋子放置在这 $n$ 个点处，每个点处恰有一枚棋子。现对这 $n$ 枚棋子进行如下操作：每次选取若干枚棋子，将它们分别移动到与自己所在点有线段相连的另一点处；操作后每点处仍恰有一枚棋子，并且没有两枚棋子在操作前后交换位置。若一种连线段的方式使得无论开始时如何放置这 $n$ 枚棋子，总能经过有限次操作后，是每个标号为 $k$ 的棋子在点 ${{V}_{k}}$ 处，则称这种连线段的方式为“和谐的”。求在所有和谐的连线段的方式中，线段数目的最小值。
【难度】
【出处】
2009第8届CGMO试题
【标注】
【答案】
$n+1$
【解析】
所求的最小值为 $n+1$ 。首先，当线段数目不大于 $n$ 时，易知下面两种情形之一必然出现：（1）在 ${{V}_{1}}\text{,}{{V}_{2}}\text{,}\cdots \text{,}{{V}_{n}}$ 中存在一个点，它最多与另外一个点有线段相连；（2）对于 ${{V}_{1}}\text{,}{{V}_{2}}\text{,}\cdots \text{,}{{V}_{n}}$ 中的每一个点，恰有两个点与该点有线段相连。 如果情形（1）出现，不妨设这个点为 ${{V}_{1}}$ 。则可以证明开始在点 ${{V}_{1}}$ 的棋子只能一直停留在该点。若不然，设在某一次操作中这枚棋子到达了定点 ${{V}_{i}}$ 。由条件知，在这次操作中必然有另一顶点 ${{V}_{j}}$ 上的棋子被移动到 ${{V}_{1}}$ 。这样，${{V}_{i}}$、${{V}_{j}}$ 是两个不同的点，且都与 ${{V}_{1}}$ 有线段相连，这与假设矛盾。只要开始时，点 ${{V}_{1}}$ 处的棋子不是1号棋子，就无法通过有限次操作使得该棋子到达相应的顶点。因此这样的连线段方式是不和谐的。 如果情形（2）出现，已知所有的线段连成了一条或者多条封闭折线。如果是多条折线，则显然存在两个点 ${{V}_{i}}$、${{V}_{j}}$，使得 ${{V}_{i}}$ 上的棋子无法通过操作移动到 ${{V}_{j}}$ 上，故只要开始时，点 ${{V}_{1}}$ 处的棋子恰好是 $j$ 号棋子，就无法通过有限次操作使得该棋子到达相应的顶点，因此，这样的连线段方式是不和谐的；如果是一条折线，则不妨设点 ${{V}_{i}}$、${{V}_{i+1}}$ 之间连了线 $\left(i\text{=}1\text{,}2\text{,}\cdots \text{,}n\text{,}{{V}_{n+1}}\text{=}{{V}_{1}}\right)$ 。易知在一次操作中，或者所有的棋子均不动，或者点 ${{V}_{i}}$ 处的棋子移动到点 ${{V}_{i+1}}$，或者点 ${{V}_{i+1}}$ 处的棋子移动到点 ${{V}_{i}}$ $\left(i\text{=}1\text{,}2\text{,}\cdots \text{,}n \right)$，只要开始时 ${{V}_{1}}$、${{V}_{2}}$ 处的棋子恰好是1号、3号棋子，就无法通过有限次操作使得该棋子到达相应的顶点。因此这样的连线段方式是不和谐的。 另一方面，若将点 ${{V}_{i}}$、${{V}_{i+1}}$ 之间连线 $\left(i\text{=}1\text{,}2\text{,}\cdots \text{,}n\text{,}{{V}_{n+1}}\text{=}{{V}_{1}}\right)$，且将点 ${{V}_{n+1}}$、${{V}_{1}}$ 之间连线，则可以证明这样的连线段方式是和谐的。 事实上，这样的连线方式下，可以做下面两种操作。 操作 ${{M}_{1}}$：将在点 ${{V}_{i}}$ 处的棋子移动到点 ${{V}_{i+1}}$ 处 $\left(i\text{=}1\text{,}2\text{,}\cdots \text{,}n \right)$ 。 操作 ${{M}_{2}}$：将在点 ${{V}_{i}}$ 处的棋子移动到点 ${{V}_{i+1}}$ 处 $\left(i\text{=}1\text{,}2\text{,}\cdots \text{,}n-2 \right)$，将在点 ${{V}_{n+1}}$ 处的棋子移动到点 ${{V}_{1}}$ 处。 下面利用数学归纳法证明：对于任意的 $k\left( 1\leqslant k\leqslant n \right)$，可以经过有限次操作后，使得编号为 $1\text{,}2\text{,}\cdots\text{,}k$ 的棋子分别在点 ${{V}_{1}}\text{,}{{V}_{2}}\text{,}\cdots \text{,}{{V}_{k}}$ 处。 当 $k\text{=}1$ 时，设1号棋子开始时在点 ${{V}_{i}}$ 处，则进行 $n-i+1$ 次操作 ${{M}_{1}}$ 即可让1号棋子移动到点 ${{V}_{1}}$ 处。 假设在某次操作后，编号为 $1\text{,}2\text{,}\cdots \text{,}k$ 的棋子分别在点 ${{V}_{1}}\text{,}{{V}_{2}}\text{,}\cdots\text{,}{{V}_{k}}$ 处，设此时 $k+1$ 号棋子在点 ${{V}_{r}}\left( k+1\leqslant r\leqslant n \right)$ 处。则先进行 $n-r$ 次操作 ${{M}_{1}}$，再进行 $r-k-1$ 次操作 ${{M}_{2}}$，最后进行 $k+1$ 次操作 ${{M}_{1}}$，即可使编号为 $1\text{,}2\text{,}\cdots\text{,}k+1$ 的棋子分别在点 ${{V}_{1}}\text{,}{{V}_{2}}\text{,}\cdots\text{,}{{V}_{k+1}}$ 处。 由数学归纳法，最终可以在有限次操作后，使每个标号为 $k$ 的棋子在点 ${{V}_{k}}$ $\left( k=1,2,\cdots ,n\right)$ 处，因此这样的连线段方式是和谐的。 综上，和谐的连线段方式中，线段数目的最小值为 $n+1$ 。
答案
解析
备注
