Chinese Mathematical Olympiad

Proof One only needs to consider the case with the total number of cards equal $n^2+3n+1$. We take the following strategy. If there are at least three cards at some $A_i$, then use operation (1) at this position. Such operations can be done for only finitely many steps. Then we have no more than two cards at each $A_i$ and no less than $n^2+n+1$ at $O$.

We then take operation (2) for $n+1$ times. There are then at least $n+1$ cards at each $A_i$. We will now prove that one can increase the number of cards at $O$ to at least $n+1$, while keeping at least $n+1$ cards at each $A_i$.

Put $A_1,A_2,\dots ,A_n$ evenly and in increasing order on a circle with the center at $O$. We call a group of consecutive $A_i$'s, $G=\{A_i,A_{i+1},\dots ,A_{i+\lfloor n\rfloor -1}\},1\le i\le n,1\le l\le n$, on the circle a team, where for $j>n$ we define $A_j=A_{j-n}$. A team is good if after we take operation (1) once at each point in $G$, there are at least $n+1$ cards at every point in $G$. Write $a_1,a_2,\dots ,a_n$ as the number of cards at points $A_1,A_2,\dots ,A_n,a_i\ge n+1,i=1,2,\dots ,n$. Let $G=\{A_i\}$ be a team. Then, if there is only one point $A_i$ in $G$, $G$ is good iff $a_i\ge n+4$; a team of two points $G=\{A_i,A_{i+1}\}$ is good iff $a_i,a_{i+1}\ge n+3$; a team $G=\{A_i,A_{i+1},\dots ,A_{i+\lfloor n\rfloor -1}\}$ of $l$ points ($3\le l\le n-1$) is good iff $a_i,a_{i+\lfloor n\rfloor -1}\ge n+3$ and $a_j\ge n+2,i+1\le j\le i+l-2$; finally, the team $G=\{A_1,A_2,\dots ,A_n\}$ of all $n$ points is good iff $a_j\ge n+2,1\le j\le n$. We then prove that there must exist at least one good team if $a_1+a_2+\cdots +a_n\ge n^2+2n+1$.

Assume that there is no good team. Then each $a_i\in \{n+1,n+2,n+3\}$, otherwise there is a good team of one point at any $A_i$ with $a_i\ge n+4$. Suppose that the number of $n+1,n+2$ and $n+3$'s among $a_1,a_2,\dots ,a_n$ are $x,y,z$ respectively. We will show that $x\ge z$. Since $n^2+2n+1>n(n+2)$, $z\ge 1$. If $z=1$, then $x\ge 1$, otherwise all $a_i\ge n+2$ and $G=\{A_1,A_2,\dots ,A_n\}$ is a good team. If $z\ge 2$, the $z$ points with $n+3$ cards divide the circle into $z$ arcs (no two of these $z$ points are adjacent). Since there is no good team by assumption, there is at least one point on each arc with $n+1$ cards. So $x\ge z$, and the total number of cards at $A_1,A_2,\dots ,A_n$ is $$x(n+1)+y(n+2)+z(n+3)\le (x+y+z)(n+2)=n(n+2)<n^2+2n+1,$$ which is a contradiction. Thus, we have proven that when the number of cards at $O$ is less than $n+1$, there exists a good team. We use operation (1) on each point of a good team; the number of cards at $O$ is increased while the number of cards at each $A_1,A_2,\dots ,A_n$ is still no less than $n+1$. We can reiterate until there are at least $n+1$ cards at $O$.