Japan Mathematical Olympiad

Pick some player and call him $A$. Let $A_1$ be $A$ and for $i=2,3,\dots$ designate by $A_i$ the player sitting at the $i-1$-th position from the player $A$ counted clockwise. For a non-negative integer $k$ and a positive integer $i$ denote by $F(k,i)$ the number obtained by subtracting the total number of red cards possessed by the players $A_1,A_2,\dots ,A_i$ from the total number of white cards possessed by the same set of players after the $k$-th turn. By $0$-th turn we mean the initial distribution of red and white cards. Let us first prove the following lemma.

Lemma 1. If we choose the player $A$ suitably, then we can make $F(0,i)\ge 0$ for every positive integer $i$. Proof. Choose a player arbitrarily and call him $B$. Define $B_i$ and $G(k,i)$ starting with $B$ in the same way as we defined $A_i$ and $F(k,i)$ from $A$. As the total number of red cards possessed by the players $B_1,B_2,\dots ,B_{2008}$ equals the total number of white cards possessed by the same set of players, we have $G(0,i)=G(0,i+2008)$, and therefore, we can choose a number $m$ ($1\le m\le 2008$) such that $G(0,m)={\min }_{i\ge 1}G(0,i)$. Now, let $A$ be $B_{m+1}$, then since $A_i=B_{m+i}$, $F(0,i)$ equals the number obtained by subtracting the total number of red cards possessed initially by the players $B_{m+1},B_{m+2},\dots ,B_{m+i}$ from the total number of white cards possessed initially by the same set of players. Consequently, we have $F(0,i)=G(0,m+i)-G(0,m)\ge 0$.

From now on we consider the player $A$ satisfying the condition of Lemma 1. We can now prove the following lemma.

Lemma 2. $F(k,i)\ge 0$ holds for every choice of the nonnegative integer $k$ and the positive integer $i$. Proof. We prove the assertion by using the mathematical induction on $k$. The assertion is valid for $k=0$ by our choice of $A$. Suppose the assertion holds for the case $k=l$. We will show that the existence of $j$ for which $F(l+1,j)<0$ will lead to a contradiction. As $F(l+1,j)=F(l+1,j+2008)$, we may suppose that $j\ge 2$. We see from the definition of $F(l,j)$ and the fact that the total number of cards possessed by $A_1,A_2,\dots ,A_j$ is even that $F(l,j)$ is also even. The value of $F(l,j)-F(l+1,j)$ is determined completely by the kind of cards $A_1$ receives and $A_j$ passes on at the $l+1$-th turn, and this value is $-2$, $0$ or $2$. Since $F(l,j)\ge 0$ and $F(l+1,j)<0$, we see that only possible combination is $F(l,j)=0$ and $F(l+1,j)=-2$ and this can happen only if $A_1$ receives a red card and $A_j$ passes on a white card at the $l$-th turn. But if $A_j$ passes on a white card at the $l$-th turn, this means that $A_j$ must have $2$ white cards at the end of the $l$-th turn, which implies that $F(l,j-1)=F(l,j)-2=-2<0$, which contradicts the induction hypothesis. Thus, we must have $F(l+1,i)\ge 0$ for all positive integers $i$. This completes the mathematical induction and the proof of Lemma 2.

By letting $i=2007$ in Lemma 2, we get $F(k,2007)\ge 0$ for every $k\ge 0$. Combined with the fact $F(k,2008)=0$ for every $k\ge 0$, we can conclude that $A_{2008}$ always possesses at least one red card, and consequently, $A_1$ receives a red card at every turn. Starting with this fact, we can prove by using mathematical induction on $n$ that for every positive integer $n$, every one of the players $A_1,A_2,\dots ,A_n$ possesses at least $1$ red card at the end of $n$-th turn. Combined with the fact that $A_{2008}$ always possesses at least $1$ red card, this tells us that every one of the players $A_1,A_2,\dots ,A_{2008}$ possesses at least $1$ red card at the end of $2007$-th turn. Since the total number of red cards is $2008$, this means that every player has exactly $1$ red card at the end of $2007$-th turn, which implies that the situation where every player possesses exactly $1$ white and $1$ red cards must be reached in at most $2007$ turns.

On the other hand, if initially a certain player has $2$ white cards, the player sitting on his right has $2$ red cards and every other player has exactly $1$ white and $1$ red cards, the situation where every player has exactly $1$ white and $1$ red cards can be reached for the first time at the end of the $2007$-th turn.

Thus, the maximum number of turns necessary to achieve the desired situation is $2007$.