Card-passing puzzle

[Edwin Clark]

On Wed, 8 Oct 2003, Rob Arthan wrote:

> 
> Someone recently posted a challenge on sci.math that may be of interest to 
> sequence fans and may have some interesting sequences associated with it.
> 
> It is a game played by n players with n-1 cards. Each player is dealt a random 
> number of the cards. Play then proceeds in rounds: in each round, each player 
> with at least two cards passes one card left and one card right. I'm taking 
> this as meaning all players play in parallel in each round, not in turn.
> 
> The challenge is to prove that the game always terminates. I.e., eventually no 
> player will have more than one card. I have signally failed to do this so 
> far.
> 


For fixed n this is, of course, a cellular automaton. You can allow any
positive integer states for each of the n cells. The transition rule is
such that if a cell has state x >=2 then the state never exceeds x and if
it has state x < 2 then it either stays the same or increase by 1 or 2. 

If N is the maximum value of a cell state, then the maximum value of the
states in the next generation can be at most N, unless N = 2 and then a
maximum of 3 is possible in the next generation. It follows that there are
there are only a finite number of possible "global" states, so eventually
it is periodic. 

One question might be to figure out which of Wolfram's "four" classes this
cellular automaton lies in. 

These remarks don't answer your question, but  may be of some interest.

--Edwin