Maths Olympiad Prep

Library / /62 of 63

Combinatorics Difficulty 7.8 National olympiad, round 2 Prove it Japan

There are 20082008 pieces each of red cards and white cards. These 40164016 cards are mixed and put on a pile. Then, each of the 20082008 participating players is dealt 22 cards from the pile, and then all of the players are seated in a circular arrangement facing interior of the circle. At every turn of the game each player will perform the following act simultaneously:
If a player possesses at least one red card, he will pass one red card to the player sitting next to him on the left-side. If a player does not have any red card in his possession, then he will pass one white card to the player on his left.
Determine the maximum possible number of turns necessary to reach for the first time the situation where every player will have one each of red and white cards.

Solution

Pick some player and call him AA. Let A1A_1 be AA and for i=2,3,i = 2, 3, \dots designate by AiA_i the player sitting at the i1i-1-th position from the player AA counted clockwise. For a non-negative integer kk and a positive integer ii denote by F(k,i)F(k, i) the number obtained by subtracting the total number of red cards possessed by the players A1,A2,,AiA_1, A_2, \dots, A_i from the total number of white cards possessed by the same set of players after the kk-th turn. By 00-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 AA suitably, then we can make F(0,i)0F(0, i) \ge 0 for every positive integer ii.
Proof. Choose a player arbitrarily and call him BB. Define BiB_i and G(k,i)G(k, i) starting with BB in the same way as we defined AiA_i and F(k,i)F(k, i) from AA. As the total number of red cards possessed by the players B1,B2,,B2008B_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)G(0, i) = G(0, i + 2008), and therefore, we can choose a number mm (1m20081 \le m \le 2008) such that G(0,m)=mini1G(0,i)G(0, m) = \min_{i \ge 1} G(0, i). Now, let AA be Bm+1B_{m+1}, then since Ai=Bm+iA_i = B_{m+i}, F(0,i)F(0, i) equals the number obtained by subtracting the total number of red cards possessed initially by the players Bm+1,Bm+2,,Bm+iB_{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)0F(0, i) = G(0, m+i) - G(0, m) \ge 0.

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

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

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

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

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.