IMO 1994 SL C5

Origin: SWE | Category: Combinatorics

Problem

At a round table are 1994 girls, playing a game with a deck of n cards. Initially, one girl holds all the cards. In each turn, if at least one girl holds at least two cards, one of these girls must pass a card to each of her two neighbors. The game ends when and only when each girl is holding at most one card. (a) Prove that if n \geq1994, then the game cannot end. (b) Prove that if n < 1994, then the game must end.

Solution

(a) The case n > 1994 is trivial. Suppose that n = 1994. Label the girls G1 to G1994, and let G1 initially hold all the cards. At any moment give to each card the value i, i = 1, . . . , 1994, if Gi holds it. Define the characteristic C of a position as the sum of all these values. Initially C = 1994. In each move, if Gi passes cards to Gi−1 and Gi+1 (where G0 = G1994 and G1995 = G1), C changes for \pm1994 or does not change, so that it remains divisible by 1994. But if the game ends, the characteristic of the final position will be C = 1 + 2 + \cdot \cdot \cdot + 1994 = 997 \cdot 1995, which is not divisible by 1994. (b) Whenever a card is passed from one girl to another for the first time, let the girls sign their names on it. Thereafter, if one of them passes a card to her neighbor, we shall assume that the passed card is exactly the one signed by both of them. Thus each signed card is stuck between two neighboring girls, so if n < 1994, there are two neighbors who never exchange cards. Consequently, there is a girl G who played only a finite number of times. If her neighbor plays infinitely often, then after her last move, G will continue to accumulate cards indefinitely, which is impossible. Hence every girl plays finitely many times.