$ 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. a.) Show that if $ n < 1994$, the game must terminate. b.) Show that if $ n = 1994$ it cannot terminate.
Problem
Source: IMO Shortlist 1994, C5
Tags: combinatorics, invariant, IMO Shortlist, game, termination
orl
10.08.2008 22:12
A harder variant of this problem can be discussed here.
ophiophagous
18.08.2010 05:05
Denote the girl originally holding all coins $A$. If $n<1994$, we just remove the girl opposite $A$ and consider the girls sitting in a row with A in the center. We use a string to represent the coins in each girl's hand. I'll just write out the numbers to the right of $A$. 0 ... 20... 02... 101... 201... 011... 111... 211... 021... 202... Clearly, the string cycles between 20202020.... and 1111111... (in each cycle, another 20 and 11 appear) Thus, if $n<1994$, we get 111..... ($A$ is left with no coins if $n$ is even, and one coin if $n$ is odd), so the girl opposite $A$ never gets a coin. If n=1994, the 0's and 2's switch back and forth, i.e. 20202020..... 02020202..... so the game does not end.
Kayak
09.09.2017 14:19
@Above Sorry, your proof is probably very wrong - a person can have way more than $2$ cards.
Start from any girl, and number them $1, \cdots, 1994$, and denote $C[j]$ by the number of tokens of $j^{th}$ girl. The quantity $$ \sum_{j \; odd} C[j] \mod 2$$is always $0$
The quantity $$\sum_{0<j<1995} j*C[j] \mod 1994 $$is always $0$, following the notation of above.
TwilightZone
27.06.2020 02:32
We use invariants here. Let the 1994 girls have labels $G_1, G_2, ...G_1994$. Assign a weight of $I$ to each coin $G_i$ holds. Let $G_1$ start with $1994$ tokens originally. Notice that in each turn, the sum of the weights is invariant mod $1994$. However, in order for the game to terminate, each girl must have 1 token. The sum of the weights in this case is $1+2+..+1994$, which is NOT congruent to 0 mod 1994. Hence, the game can never terminate.