1994 girls are seated at a round table. Initially one girl holds n tokens. Each turn a girl who is holding more than one token passes one token to each of her neighbours. Show that if n < 1994, the game must terminate. Show that if n = 1994 it cannot terminate. As a variant, take 1991 girls and show that the game cannot terminate for n <= 1991.
Solution
Suppose that the first time a card is passed from girl A to her neighbor girl B or from girl B to girl A, it is marked AB. Suppose further that whenever girl A passes cards she never passes the marked card to anyone except girl B. Similarly whenever girl B passes cards she never passes the marked card to anyone except girl A. It is clear that this procedure does not interfere with the conditions of the problem. But it means that the marked card can never go anywhere except girl A or girl B. We do this for each adjacent pair of girls. Then cards can only pass from girl A to her neighbor B if there is a card marked AB. If n < 1994, there are less than 1994 cards and hence less than 1994 marked cards, so there must be two adjacent girls who never pass cards to each other.
If the game does not terminate, then there must be a girl who passes cards infinitely many times. Hence there must be two adjacent girls, one of whom passes cards infinitely many times and one of whom does not (otherwise there could not be two adjacent girls who never pass cards to each other). But that means that the girl who only passes finitely many times will accumulate infinitely many cards from her neighbor. Contradiction (since she can accumulate at most n cards). So for n < 1994 the game must terminate.
Suppose n = 1994. Label the girls 1, 2, ... , 1994 (with i adjacent to i-1 and i+1 and 1994 adjacent to 1993 and 1). Let S = S i ci, where ci is the number of cards held by girl i. If girl i passes cards for 1 < i < 1994, then S does not change. If girl 1 passes cards, then S increases by 1994. If girl 1994 passes cards, then S decreases by 1994. Initially, S = 1994i for some i, so S is always a multiple of 1994. But if the game terminates, then each girl ends up with 1 card, so S = 1 + 2 + ... + 1994 = 997.1995 = odd. Contradiction. So the game cannot terminate.
For 1991 girls, the argument for n < 1991 is the same. But the argument for the number of cards equal to the number of girls breaks down.
We show first that for n = 1991 it is possible for the game to end after finitely many moves. Label the girls -995, -994, ... , -1, 0, 1, ... 995, with girl 0 initially holding all the cards. Now play the game so that girl -i only plays immediately after girl i. This is always possible because it means that girls i and -i always hold the same number of cards except immediately after girl i-1, i or i+1 has played. It follows that girl 0 never plays except after a girl with positive number, so girl 0 always has an odd number of cards. So she can mark one card and never play it. Accordingly, the game is the same as a game with only 1990 cards and hence must terminate. At termination girl 0 must have 0 unmarked cards (because she must have an even number and if she had 2 or more the game would not have terminated), and hence 1 card in total. All the other girls must have at most 1 card (or the game would not have terminated) and hence exactly 1 card.
Represent a game as x1, x2, x3, ... where xi is the number of the girl who passes cards on move i. Let X = (x1, ... , xt) be the terminating game found above. Suppose there is a game Y = (y1, y2, y3, ... ) which is non-terminating. Let r be the smallest i such that xi ≠ yi. [Note that there must be such an i, because if xi = yi for i = 1, 2, ... , t, then X and Y have the same distribution of cards after t moves, but X terminates, so Y must also terminate. Contradiction.] Choose Y so that r is as large as possible. In a non-terminating game every girl must pass cards infinitely often (this is a simple induction - at least one girl must. Hence her neighbor must to avoid accumulating infinitely many cards. Hence her neighbor must, and so on). So there must be some s > r with ys = xr. Take the smallest such. Let Z be the game (z1, z2, z3, ... ), where z1 = y1 = x1, ... , zr-1 = yr-1 = xr-1, zr = ys = xr, zr+1 = yr, ... , zs = ys-1, zs+1 = ys+1, ... . Note that Z is identical to Y and hence to X up to move r-1. On move r, girl ys passes cards instead of girl yr. Now girls yr, yr+1, ... , ys-1 are (by definition) all different from girl ys (because s is the smallest index > r with ys = xr). So they still have enough cards in Z to be able to pass. After move s, the girls have the same number of cards in the two games and the moves are again identical. So Z is also non-terminating. But it agrees with X up to move r, contradicting the definition of Y. So there cannot be a non-terminating game.
© John Scholes
jscholes@kalva.demon.co.uk
18 Sep 2002