我们对放置于点 $A_{1}, A_{2}, \cdots, A_{n}(n \geqslant 3)$ 及点 $O$ 处的卡片进行操作．所谓一次操作是指进行下面的一种操作：
（1）若某个点 $A_i$ 处的卡片数目不少于 $3$，则可从中取出 $3$ 张，在点 $A_{i-1}, A_{i+1}$ 及 $O$ 处各放一张 $\left(A_{0}=A_{n}, A_{n+1}=A_{1}\right)$；
（2）若点 $O$ 处的卡片数目不少于 $n$，则可以从中取出 $n$ 张，在点 $A_{1}, A_{2}, \cdots, A_{n}$ 处各放一张．
证明：只要放置于这 $n+1$ 个点处的卡片总数不少于 $n^2 +3n+1$，则总能通过若干次操作，使每个点处卡片数目均不小于 $n+1$．
（1）若某个点 $A_i$ 处的卡片数目不少于 $3$，则可从中取出 $3$ 张，在点 $A_{i-1}, A_{i+1}$ 及 $O$ 处各放一张 $\left(A_{0}=A_{n}, A_{n+1}=A_{1}\right)$；
（2）若点 $O$ 处的卡片数目不少于 $n$，则可以从中取出 $n$ 张，在点 $A_{1}, A_{2}, \cdots, A_{n}$ 处各放一张．
证明：只要放置于这 $n+1$ 个点处的卡片总数不少于 $n^2 +3n+1$，则总能通过若干次操作，使每个点处卡片数目均不小于 $n+1$．
【难度】
【出处】
2010第25届CMO试题
【标注】
【答案】
略
【解析】
只需考虑卡片总数等于 $n^2 +3n+1$ 的情况．
采取如下策略．
如果有某个点 $A_i$ 处的卡片数不少于 $3$，则对点 $A_i$ 处的卡片进行操作（1）．这样的一次操作使得点 $O$ 处的卡片数增加 $1$，于是，经过有限次操作（1）后，将不能再进行操作（1）．此时，每个点 $A_i$ 处的卡片数不超过 $2$，点 $O$ 处的卡片数不少于 $n^2 +n+1$．然后对点 $O$ 处的卡片进行 $n+1$ 次操作（2），此时，每个点 $A_i$ 处的卡片数不少于 $n+1$
下面在保持每个点 $A_i$ 处的卡片数不少于 $n+1$ 的情况下，使点 $O$ 处的卡片数增加到至少 $n+1$．
设想 $A_{1}, A_{2}, \cdots, A_{n}$ 顺次排列在 $O$ 为圆心的圆周上．称连续相邻的若干个点的集合 $G=\left\{A_{i}, A_{i+1}, \cdots, A_{i+l-1}\right\}(1 \leqslant i \leqslant n)$ 为一个“团”，这里若有下标 $j>n$，则 $A_{j}=A_{j-n}$．
如果对团 $G$ 中每点处的卡片都做一次操作（1）后，$G$ 中每点处的卡片数仍然不少于 $n+1$，则称团 $G$ 为“好团”．
设 $a_{1}, a_{2}, \cdots, a_{n}\left(a_{i} \geqslant n+1, i=1,2, \cdots, n\right)$ 分别为点 $A_{1}, A_{2}, \cdots, A_{n}$ 处的卡片数．则好团需满足如下的充要条件：
一个点的团 $G$ 是好团 $\Leftrightarrow a_{i} \geqslant n+4$；
两个点的团 $G$ 是好团 $\Leftrightarrow a_{i}, a_{i+1} \geqslant n+3$；
$l(3 \leqslant l \leqslant n-1)$ 个点的团 $G$ 是好团 $\Leftrightarrow a_{i}, a_{i+l-1} \geqslant n+3$，且 $a_{j} \geqslant n+2(i+1 \leqslant j \leqslant i+l-2)$；
全部 $n$ 个点的团 $G$ 是好团 $\Leftrightarrow a_{j} \geqslant n+2(1 \leqslant j \leqslant n)$．
下面证明：当点 $O$ 处的卡片数少于 $ n+1$ 时，或等价地，当 $a_{1}+a_{2}+\cdots+a_{n} \geqslant n^{2}+2 n+1$ 时，必存在好团．
假设不存在好团．
于是，每个 $a_{i} \in\{n+1, n+2, n+3\}$，否则会有某个点 $A_i$ 处的卡片数 $a_{i} \geqslant n+4$，使得 $G=\left\{A_{i}\right\}$ 是一个好团．
设 $a_{1}, a_{2}, \cdots, a_{n}$ 中有 $x$ 个 $n+1$，$y$ 个 $n+2$，$z$ 个 $n+3$．下面说明：一定有 $x \geqslant z$．
由于 $n^{2}+2 n+1>n(n+2)$，故 $z\geqslant 1$．
若 $ z=1$，则有 $x\geqslant 1$，否则所有 $a_{i} \geqslant n+2$，使得 $G=\left\{A_{1}, A_{2}, \cdots, A_{n}\right\}$ 是一个好团．
若 $z\geqslant 2$，有 $n+3$ 张卡片的 $z$ 个点将圆周分成 $z$ 段圆弧，由于不存在好团，这 $z$ 个点没有两点相邻，且每段圆弧上都存在一个点只
有 $n+1$ 张卡片．故 $x\geqslant z$．此时，点 $A_{1}, A_{2}, \cdots,A_n$ 处的卡片总数为
$x(n+1)+y(n+2)+z(n+3)\leqslant(x+y+z)(n+2)=n(n+2)<n^{2}+2 n+1$，矛盾．这样就证明了当点 $O$ 处的卡片数少于 $n+1$ 时，点 $A_{1}, A_{2}, \cdots, A_{n}$ 中总存在好团．于是，每次对一个好团中的每个点做操作（1），直至点 $O$ 处的卡片数不少于 $n+1$，而点 $A_{1}, A_{2}, \cdots, A_{n}$ 处的卡片数也不少于 $n+1$．
采取如下策略．
如果有某个点 $A_i$ 处的卡片数不少于 $3$，则对点 $A_i$ 处的卡片进行操作（1）．这样的一次操作使得点 $O$ 处的卡片数增加 $1$，于是，经过有限次操作（1）后，将不能再进行操作（1）．此时，每个点 $A_i$ 处的卡片数不超过 $2$，点 $O$ 处的卡片数不少于 $n^2 +n+1$．然后对点 $O$ 处的卡片进行 $n+1$ 次操作（2），此时，每个点 $A_i$ 处的卡片数不少于 $n+1$
下面在保持每个点 $A_i$ 处的卡片数不少于 $n+1$ 的情况下，使点 $O$ 处的卡片数增加到至少 $n+1$．
设想 $A_{1}, A_{2}, \cdots, A_{n}$ 顺次排列在 $O$ 为圆心的圆周上．称连续相邻的若干个点的集合 $G=\left\{A_{i}, A_{i+1}, \cdots, A_{i+l-1}\right\}(1 \leqslant i \leqslant n)$ 为一个“团”，这里若有下标 $j>n$，则 $A_{j}=A_{j-n}$．
如果对团 $G$ 中每点处的卡片都做一次操作（1）后，$G$ 中每点处的卡片数仍然不少于 $n+1$，则称团 $G$ 为“好团”．
设 $a_{1}, a_{2}, \cdots, a_{n}\left(a_{i} \geqslant n+1, i=1,2, \cdots, n\right)$ 分别为点 $A_{1}, A_{2}, \cdots, A_{n}$ 处的卡片数．则好团需满足如下的充要条件：
一个点的团 $G$ 是好团 $\Leftrightarrow a_{i} \geqslant n+4$；
两个点的团 $G$ 是好团 $\Leftrightarrow a_{i}, a_{i+1} \geqslant n+3$；
$l(3 \leqslant l \leqslant n-1)$ 个点的团 $G$ 是好团 $\Leftrightarrow a_{i}, a_{i+l-1} \geqslant n+3$，且 $a_{j} \geqslant n+2(i+1 \leqslant j \leqslant i+l-2)$；
全部 $n$ 个点的团 $G$ 是好团 $\Leftrightarrow a_{j} \geqslant n+2(1 \leqslant j \leqslant n)$．
下面证明：当点 $O$ 处的卡片数少于 $ n+1$ 时，或等价地，当 $a_{1}+a_{2}+\cdots+a_{n} \geqslant n^{2}+2 n+1$ 时，必存在好团．
假设不存在好团．
于是，每个 $a_{i} \in\{n+1, n+2, n+3\}$，否则会有某个点 $A_i$ 处的卡片数 $a_{i} \geqslant n+4$，使得 $G=\left\{A_{i}\right\}$ 是一个好团．
设 $a_{1}, a_{2}, \cdots, a_{n}$ 中有 $x$ 个 $n+1$，$y$ 个 $n+2$，$z$ 个 $n+3$．下面说明：一定有 $x \geqslant z$．
由于 $n^{2}+2 n+1>n(n+2)$，故 $z\geqslant 1$．
若 $ z=1$，则有 $x\geqslant 1$，否则所有 $a_{i} \geqslant n+2$，使得 $G=\left\{A_{1}, A_{2}, \cdots, A_{n}\right\}$ 是一个好团．
若 $z\geqslant 2$，有 $n+3$ 张卡片的 $z$ 个点将圆周分成 $z$ 段圆弧，由于不存在好团，这 $z$ 个点没有两点相邻，且每段圆弧上都存在一个点只
有 $n+1$ 张卡片．故 $x\geqslant z$．此时，点 $A_{1}, A_{2}, \cdots,A_n$ 处的卡片总数为
$x(n+1)+y(n+2)+z(n+3)\leqslant(x+y+z)(n+2)=n(n+2)<n^{2}+2 n+1$，矛盾．这样就证明了当点 $O$ 处的卡片数少于 $n+1$ 时，点 $A_{1}, A_{2}, \cdots, A_{n}$ 中总存在好团．于是，每次对一个好团中的每个点做操作（1），直至点 $O$ 处的卡片数不少于 $n+1$，而点 $A_{1}, A_{2}, \cdots, A_{n}$ 处的卡片数也不少于 $n+1$．
答案
解析
备注
