从左到右编号为 ${{B}_{1}},{{B}_{2}},\cdots ,{{B}_{n}}$ 的 $n$ 个盒子共装有 $n$ 个小球，每次可以选择一个盒子 ${{B}_{k}}$ 进行如下操作：若 $k=1$，且 ${{B}_{1}}$ 中至少有一个小球，则可以从 ${{B}_{1}}$ 中移1个小球至 ${{B}_{2}}$ 中；若 $k=n$，且 ${{B}_{n}}$ 中至少有一个小球，则可以从 ${{B}_{n}}$ 中移1个小球至 ${{B}_{n-1}}$ 中；若 $2\leqslant k\leqslant n-1$，且 ${{B}_{k}}$ 中至少有两个小球，则可以从 ${{B}_{k}}$ 中分别移1个小球至 ${{B}_{k-1}}$ 和 ${{B}_{k+1}}$ 中。证明：无论初始时这些小球如何放置，总能经过有限次操作，使得每个盒子中恰有一个小球。
【难度】
【出处】
2011第10届CGMO试题
【标注】
【答案】
略
【解析】
对于任意两个向量 $x=({{x}_{1}},{{x}_{2}},\cdots,{{x}_{n}})$ 和 $y=({{y}_{1}},y{}_{2},\cdots ,{{y}_{n}})$，若存在 $k(1\leqslant k\leqslant n)$ 使得
${{x}_{1}}={{y}_{1}},{{x}_{2}}={{y}_{2}},\cdots,{{x}_{k-1}}={{y}_{k-1}},{{x}_{k}}>{{y}_{k}}$，则记 $x>y$ 。
用一非负整数向量 $x=({{x}_{1}},{{x}_{2}},\cdots ,{{x}_{n}})$ 表示各盒子中的小球数目。
经过一次对 ${{B}_{k}}$ 的操作后，各盒子中的小球数目从 $x$ 变成 $x+{{\alpha }_{k}}$，其中
${{\alpha }_{1}}=(-1,1,0,\cdots ,0)$，${{\alpha }_{k}}=(\underbrace{0,\cdots ,0}_{k-2},1,-2,1,0,\ldots,0)(2\leqslant k\leqslant n-1)$，${{\alpha }_{n}}=(0,\cdots,0,1,-1)$
当 $k\geqslant 2$ 时，总有 $x+{{\alpha}_{k}}>x$ 。
因此，对于任意初始状态，总可以通过一系列对 ${{B}_{2}},{{B}_{3}},\cdots,{{B}_{n}}$ 的操作（只要 $k\geqslant 2$，且 ${{B}_{k}}$ 中至少有两个小球，就对 ${{B}_{k}}$ 施行操作），使得操作之后的小球数目 $y=({{y}_{1}},{{y}_{2}},\cdots,{{y}_{n}})$ 满足 ${{y}_{k}}\leqslant 1(k\geqslant 2)$ 。
若 ${{y}_{2}}={{y}_{3}}=\cdots ={{y}_{n}}=1$，则已满足题目要求；否则，有 ${{y}_{1}}\geqslant 2$ 。设 $i$ 是满足 ${{y}_{i}}=0$ 的最小整数，通过一系列对 ${{B}_{1}}.{{B}_{2}},\cdots,{{B}_{i-1}}$ 的操作，可以使得小球数目变为 $({{y}_{1}}-1,1,\cdots,1,{{y}_{i+1}},\ldots ,{{y}_{n}})$，具体操作如下：
$\begin{matrix}
&({{y}_{1}},1,\cdots ,1,0,{{y}_{i+1}},\cdots ,{{y}_{n}})\xrightarrow{{{B}_{1}},{{B}_{2}},\cdots,{{B}_{i-1}}}({{y}_{1}},1,\cdots ,1,0,1,{{y}_{i+1}},\cdots ,{{y}_{n}}) \\
&\xrightarrow{{{B}_{1}},{{B}_{2}},\cdots ,{{B}_{i-2}}}({{y}_{1}},1,\cdots,1,0,1,1,{{y}_{i+1}},\cdots ,{{y}_{n}})\to \cdots \to ({{y}_{1}},0,1,\cdots,1,{{y}_{i+1}},\cdots ,{{y}_{n}}) \\
&\xrightarrow{{{B}_{1}}}({{y}_{1}}-1,1,\cdots ,1,{{y}_{i+1}},\cdots ,{{y}_{n}})\\
& \\
\end{matrix}$
重复以上操作，最终可使小球数目满足题目要求。
${{x}_{1}}={{y}_{1}},{{x}_{2}}={{y}_{2}},\cdots,{{x}_{k-1}}={{y}_{k-1}},{{x}_{k}}>{{y}_{k}}$，则记 $x>y$ 。
用一非负整数向量 $x=({{x}_{1}},{{x}_{2}},\cdots ,{{x}_{n}})$ 表示各盒子中的小球数目。
经过一次对 ${{B}_{k}}$ 的操作后，各盒子中的小球数目从 $x$ 变成 $x+{{\alpha }_{k}}$，其中
${{\alpha }_{1}}=(-1,1,0,\cdots ,0)$，${{\alpha }_{k}}=(\underbrace{0,\cdots ,0}_{k-2},1,-2,1,0,\ldots,0)(2\leqslant k\leqslant n-1)$，${{\alpha }_{n}}=(0,\cdots,0,1,-1)$
当 $k\geqslant 2$ 时，总有 $x+{{\alpha}_{k}}>x$ 。
因此，对于任意初始状态，总可以通过一系列对 ${{B}_{2}},{{B}_{3}},\cdots,{{B}_{n}}$ 的操作（只要 $k\geqslant 2$，且 ${{B}_{k}}$ 中至少有两个小球，就对 ${{B}_{k}}$ 施行操作），使得操作之后的小球数目 $y=({{y}_{1}},{{y}_{2}},\cdots,{{y}_{n}})$ 满足 ${{y}_{k}}\leqslant 1(k\geqslant 2)$ 。
若 ${{y}_{2}}={{y}_{3}}=\cdots ={{y}_{n}}=1$，则已满足题目要求；否则，有 ${{y}_{1}}\geqslant 2$ 。设 $i$ 是满足 ${{y}_{i}}=0$ 的最小整数，通过一系列对 ${{B}_{1}}.{{B}_{2}},\cdots,{{B}_{i-1}}$ 的操作，可以使得小球数目变为 $({{y}_{1}}-1,1,\cdots,1,{{y}_{i+1}},\ldots ,{{y}_{n}})$，具体操作如下：
$\begin{matrix}
&({{y}_{1}},1,\cdots ,1,0,{{y}_{i+1}},\cdots ,{{y}_{n}})\xrightarrow{{{B}_{1}},{{B}_{2}},\cdots,{{B}_{i-1}}}({{y}_{1}},1,\cdots ,1,0,1,{{y}_{i+1}},\cdots ,{{y}_{n}}) \\
&\xrightarrow{{{B}_{1}},{{B}_{2}},\cdots ,{{B}_{i-2}}}({{y}_{1}},1,\cdots,1,0,1,1,{{y}_{i+1}},\cdots ,{{y}_{n}})\to \cdots \to ({{y}_{1}},0,1,\cdots,1,{{y}_{i+1}},\cdots ,{{y}_{n}}) \\
&\xrightarrow{{{B}_{1}}}({{y}_{1}}-1,1,\cdots ,1,{{y}_{i+1}},\cdots ,{{y}_{n}})\\
& \\
\end{matrix}$
重复以上操作，最终可使小球数目满足题目要求。
答案
解析
备注
