China National Team Selection Test

The answer is $k=42925$.

Let the circumference of the table be 101, and the distance between two adjacent persons be 1. In the following, we consider the least transition times.

Denote the person who initially possesses $i$ cards by $[i-51]$. So, if $p>0$, then we can think of person $[p]$ as the source who should send out $p$ cards; and if $p<0$, person $[p]$ is the sink who should receive $-p$ cards.

Suppose that at the end of transitions, each person has 51 cards. If person $B$ possesses a card $u$ initially belonging to person $A$, we can think that $A$ carries card $u$ to $B$ by passing through the minor arc $AB$, the length of the route is the arc length $|AB|$ means the times of transitions.

Let seating order be as shown in the figure. Person $[i]$ transits all his $i$ cards to person $[-i]$ ($i=1,2,\dots ,50$) with route length $i$. So there are all together $1^2+2^2+\cdots +50^2=42925$ transitions. In the following, we will show that no less transitions can meet the requirement if persons are seated in this way.

We use the notion of "potential". Let potential at the highest position $[50]$ be 50; the neighbor positions $[49]$ and $[48]$ each has potential 49, . . . , the lowest position $[-49]$ and $[-50]$ each has potential 0. Then, the total potential at the beginning is $$S=101\times 50+(100+99)\times 49+\cdots +(2+1)\times 0.$$ And at the end of transitions, the total potential is $$T=51\times 50+(51+51)\times 49+\cdots +(51+51)\times 0.$$ The difference is $S-T=42,925$.

Since after each transition, the total potential changes at most 1, so at least 42,925 transitions are needed.

In the following, we show that whatever be the order of seating, there is always a way of no more than 42,925 transitions such that each person possesses 51 cards. To show this, we give two lemmas.

Lemma 1. Let $c,a_0,a_1,\dots ,a_{n-1}$ be integers with their sum zero, and $c\ge 0$, $a_0\le a_1\le \cdots \le a_{n-1}$. If $n+1$ persons denoted by $[c],[a_0],[a_1],\dots ,[a_{n-1}]$, possess $N+c,N+a_0,N+a_1,\dots$ and $N+a_{n-1}$ cards, respectively, where $N$ is a positive integer, such that $N+a_0>0$. Let the persons stand on 0, 1, ..., $n$ of the number axis, such that $[c]$ stands at $n$. Then there is a way of no more than $cn+{\sum }_{i=0}^{n-1}i{a}_i$ transitions, such that each person possesses $N$ cards.

Proof of Lemma 1. Suppose that $a_{n-1}\ge \cdots \ge a_s>0\ge a_{s-1}\ge \cdots \ge a_0$, then induction on $M=a_{n-1}+\cdots +a_s$. If $M=0$, then $[c]$ passes $c$ cards to $[a_i]$, such that $[a_i]$ obtains $-a_i$ cards ($0\le i\le s-1$). Suppose that person $[a_i]$ stands at $x_i$ ($0\le i\le n-1$), then $x_0,x_1,\dots ,x_{n-1}$ is a permutation of 0, 1, ..., $n-1$. Thus, a card that passes from $[c]$ to $[a_i]$ needs $n-x_i$ transitions. So the total transitions needed are $$\sum _{i=0}^{s-1}(n-x_i)(-a_i)=cn+\sum _{i=0}^{s-1}{x}_i{a}_i\le cn+\sum _{i=0}^{s-1}i{a}_i=cn+\sum _{i=0}^{n-1}i{a}_i.$$ Now suppose that the conclusion is true for integers smaller than $M$. Consider the case of integer $M$. Suppose that $$a_{n-1}=\cdots =a_{n-s}>a_{n-s-1},a_l>a_{l-1}=\cdots =a_0.$$ Then there is a person in $[a_{n-1}]$, ..., $[a_{n-s}]$ and a person in $[a_0]$, ..., $[a_{l-1}]$ such that their distance is no more than $n-s-l+1$. We may suppose that the distance between $[a_{n-s}]$ and $[a_{l-1}]$ is no more than $n-s-l+1$, then let person $[a_{n-s}]$ pass a card $u$ to $[a_{l-1}]$ by no more than $n-s-l+1$ transitions. Next, by induction on $c$ and $$\begin{array}{rl}{a}_{n-1}& \ge \cdots \ge a_{n-s+1}>a_{n-s}-1\ge a_{n-s-1}\\ & \ge \cdots \ge a_l\ge a_{l-1}+1>a_{l-2}\ge \cdots \ge a_0,\end{array}$$ we see that by taking no more than $$\begin{array}{rl}L& =cn+(n-1)a_{n-1}+\cdots +(n-s+1)a_{n-s+1}+\\ & (n-s)(a_{n-s}-1)+(n-s-1)a_{n-s-1}+\cdots +\\ & l{a}_l+(l-1)(a_{l-1}+1)+(l-2)a_{l-2}+\cdots +0\cdot a_0\end{array}$$ transitions, each person possesses $N$ cards. Addition of the transitions of card $u$, we know that there are no more than $$L+(n-s-l+1)=cn+\sum _{i=0}^{n-1}i{a}_i$$ transitions. The proof of Lemma 1 is completed.

Lemma 2. For any permutation of $[-50]$, $[-49]$, ..., $[49]$, $[50]$ on a circle, there always exists a person $[c]$, denote the line passing through $[c]$ and the origin by $l$, such that the sum of each side of $l$ (include $c$) in the brackets has the same sign of $c$.

Proof of Lemma 2. Let the permutation on the circle be $[a_1]$, $[a_2]$, ..., $[a_{101}]$ clockwise. Then there is a directed diameter $l$ of the circle such that $[a_1]$, $[a_2]$, ..., $[a_{50}]$ are on one side of $l$ and $[a_{51}]$, $[a_{52}]$, ..., $[a_{101}]$ are on the other side.

If ${\sum }_{i=1}^{50}{a}_i=0$, then take $c=a_{51}$; else, if ${\sum }_{i=1}^{50}{a}_i\ne 0$, then the sums of each side of $l$ have different sign. If we rotate $l$ 180° clockwise, we see that the sum of each side changes sign. So there exists a $[c]$ which meets the requirement of Lemma 2.

Take $[c]$ in Lemma 2. Suppose that $c\ge 0$ (else change each $[a_i]$ by $[-a_i]$ and change all the directions of the arc). Let $c=c_1+c_2,c_1,c_2\ge 0$, such that the sum of $c_1$ and the numbers on one side of (not include $c$) $l$ is zero. Denote 50 numbers on this side by $a_0\le a_1\le \cdots \le a_{49}$, and denote 50 numbers on the other side by $b_0\le b_1\le \cdots \le b_{49}$. Then the sum of $c_2$ and $b_0,b_1,\dots ,b_{49}$ is also zero. Using Lemma 1 to $c_1,a_0,a_1,\dots ,a_{49}$ and $c_2,b_0,b_1,\dots ,b_{49}$, respectively, we obtain that the transition times are no more than $$L=50c_1+\sum _{j=0}^{49}j{a}_j+50c_2+\sum _{j=0}^{49}j{b}_j.$$ Since $c,a_0,\dots ,a_{49},b_0,\dots ,b_{49}$ is a permutation of $-50,-49,\dots ,50$, by the order inequality $$\begin{array}{rl}L& =50c+\sum _{j=0}^{49}j(a_j+b_j)\\ & \le 50^2+\sum _{j=0}^{49}j(2j-50+2j-49)\\ & =42925.\end{array}$$ Summing up, the least positive integer $k=42925$. $\square$