Card-passing puzzle

[Rob Arthan]

Dear All,

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.

Here is one sequence that arises from the game:

1, 4, 8, 14, 21, 29, 39, 51, 63, 77, 93, 110, 128, 148, 170, 192, 216 242, 
268, 296

where a(m) gives the number of rounds it takes for the game with n = 2m+1 to 
terminate in the case that all the cards are given to one of the players. 

These games are themselves quite pretty: here's m = 10.

 [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 18, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 16, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 16, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 14, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 14, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 1, 0, 3, 12, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 12, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 12, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 2, 0, 3, 10, 3, 0, 2, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 1, 0, 2, 2, 10, 2, 2, 0, 1, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 10, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 1, 1, 2, 1, 10, 1, 2, 1, 1, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 1, 2, 0, 3, 8, 3, 0, 2, 1, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 2, 0, 2, 2, 8, 2, 2, 0, 2, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 1, 0, 2, 1, 2, 8, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 1, 1, 0, 3, 1, 8, 1, 3, 0, 1, 1, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 1, 1, 1, 1, 3, 6, 3, 1, 1, 1, 1, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 6, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 1, 1, 2, 1, 2, 6, 2, 1, 2, 1, 1, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 1, 2, 0, 3, 1, 6, 1, 3, 0, 2, 1, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 2, 0, 2, 1, 3, 4, 3, 1, 2, 0, 2, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 1, 0, 2, 0, 3, 2, 4, 2, 3, 0, 2, 0, 1, 0, 0, 0, 0],
      [0, 0, 0, 0, 1, 1, 0, 2, 2, 2, 4, 2, 2, 2, 0, 1, 1, 0, 0, 0, 0],
      [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 4, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0],
      [0, 0, 0, 0, 1, 1, 1, 2, 1, 2, 4, 2, 1, 2, 1, 1, 1, 0, 0, 0, 0],
      [0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 4, 1, 3, 0, 2, 1, 1, 0, 0, 0, 0],
      [0, 0, 0, 0, 1, 2, 0, 2, 1, 3, 2, 3, 1, 2, 0, 2, 1, 0, 0, 0, 0],
      [0, 0, 0, 0, 2, 0, 2, 0, 3, 2, 2, 2, 3, 0, 2, 0, 2, 0, 0, 0, 0],
      [0, 0, 0, 1, 0, 2, 0, 2, 2, 2, 2, 2, 2, 2, 0, 2, 0, 1, 0, 0, 0],
      [0, 0, 0, 1, 1, 0, 2, 1, 2, 2, 2, 2, 2, 1, 2, 0, 1, 1, 0, 0, 0],
      [0, 0, 0, 1, 1, 1, 0, 3, 1, 2, 2, 2, 1, 3, 0, 1, 1, 1, 0, 0, 0],
      [0, 0, 0, 1, 1, 1, 1, 1, 3, 1, 2, 1, 3, 1, 1, 1, 1, 1, 0, 0, 0],
      [0, 0, 0, 1, 1, 1, 1, 2, 1, 3, 0, 3, 1, 2, 1, 1, 1, 1, 0, 0, 0],
      [0, 0, 0, 1, 1, 1, 2, 0, 3, 1, 2, 1, 3, 0, 2, 1, 1, 1, 0, 0, 0],
      [0, 0, 0, 1, 1, 2, 0, 2, 1, 3, 0, 3, 1, 2, 0, 2, 1, 1, 0, 0, 0],
      [0, 0, 0, 1, 2, 0, 2, 0, 3, 1, 2, 1, 3, 0, 2, 0, 2, 1, 0, 0, 0],
      [0, 0, 0, 2, 0, 2, 0, 2, 1, 3, 0, 3, 1, 2, 0, 2, 0, 2, 0, 0, 0],
      [0, 0, 1, 0, 2, 0, 2, 0, 3, 1, 2, 1, 3, 0, 2, 0, 2, 0, 1, 0, 0],
      [0, 0, 1, 1, 0, 2, 0, 2, 1, 3, 0, 3, 1, 2, 0, 2, 0, 1, 1, 0, 0],
      [0, 0, 1, 1, 1, 0, 2, 0, 3, 1, 2, 1, 3, 0, 2, 0, 1, 1, 1, 0, 0],
      [0, 0, 1, 1, 1, 1, 0, 2, 1, 3, 0, 3, 1, 2, 0, 1, 1, 1, 1, 0, 0],
      [0, 0, 1, 1, 1, 1, 1, 0, 3, 1, 2, 1, 3, 0, 1, 1, 1, 1, 1, 0, 0],
      [0, 0, 1, 1, 1, 1, 1, 1, 1, 3, 0, 3, 1, 1, 1, 1, 1, 1, 1, 0, 0],
      [0, 0, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 0, 0],
      [0, 0, 1, 1, 1, 1, 1, 2, 0, 3, 0, 3, 0, 2, 1, 1, 1, 1, 1, 0, 0],
      [0, 0, 1, 1, 1, 1, 2, 0, 2, 1, 2, 1, 2, 0, 2, 1, 1, 1, 1, 0, 0],
      [0, 0, 1, 1, 1, 2, 0, 2, 0, 3, 0, 3, 0, 2, 0, 2, 1, 1, 1, 0, 0],
      [0, 0, 1, 1, 2, 0, 2, 0, 2, 1, 2, 1, 2, 0, 2, 0, 2, 1, 1, 0, 0],
      [0, 0, 1, 2, 0, 2, 0, 2, 0, 3, 0, 3, 0, 2, 0, 2, 0, 2, 1, 0, 0],
      [0, 0, 2, 0, 2, 0, 2, 0, 2, 1, 2, 1, 2, 0, 2, 0, 2, 0, 2, 0, 0],
      [0, 1, 0, 2, 0, 2, 0, 2, 0, 3, 0, 3, 0, 2, 0, 2, 0, 2, 0, 1, 0],
      [0, 1, 1, 0, 2, 0, 2, 0, 2, 1, 2, 1, 2, 0, 2, 0, 2, 0, 1, 1, 0],
      [0, 1, 1, 1, 0, 2, 0, 2, 0, 3, 0, 3, 0, 2, 0, 2, 0, 1, 1, 1, 0],
      [0, 1, 1, 1, 1, 0, 2, 0, 2, 1, 2, 1, 2, 0, 2, 0, 1, 1, 1, 1, 0],
      [0, 1, 1, 1, 1, 1, 0, 2, 0, 3, 0, 3, 0, 2, 0, 1, 1, 1, 1, 1, 0],
      [0, 1, 1, 1, 1, 1, 1, 0, 2, 1, 2, 1, 2, 0, 1, 1, 1, 1, 1, 1, 0],
      [0, 1, 1, 1, 1, 1, 1, 1, 0, 3, 0, 3, 0, 1, 1, 1, 1, 1, 1, 1, 0],
      [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
      [0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 0, 2, 1, 1, 1, 1, 1, 1, 1, 1, 0],
      [0, 1, 1, 1, 1, 1, 1, 1, 2, 0, 2, 0, 2, 1, 1, 1, 1, 1, 1, 1, 0],
      [0, 1, 1, 1, 1, 1, 1, 2, 0, 2, 0, 2, 0, 2, 1, 1, 1, 1, 1, 1, 0],
      [0, 1, 1, 1, 1, 1, 2, 0, 2, 0, 2, 0, 2, 0, 2, 1, 1, 1, 1, 1, 0],
      [0, 1, 1, 1, 1, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 1, 1, 1, 1, 0],
      [0, 1, 1, 1, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 1, 1, 1, 0],
      [0, 1, 1, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 1, 1, 0],
      [0, 1, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 1, 0],
      [0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0],
      [1, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 1],
      [1, 1, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 1, 1],
      [1, 1, 1, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 1, 1, 1],
      [1, 1, 1, 1, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 1, 1, 1, 1],
      [1, 1, 1, 1, 1, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 1, 1, 1, 1, 1],
      [1, 1, 1, 1, 1, 1, 0, 2, 0, 2, 0, 2, 0, 2, 0, 1, 1, 1, 1, 1, 1],
      [1, 1, 1, 1, 1, 1, 1, 0, 2, 0, 2, 0, 2, 0, 1, 1, 1, 1, 1, 1, 1],
      [1, 1, 1, 1, 1, 1, 1, 1, 0, 2, 0, 2, 0, 1, 1, 1, 1, 1, 1, 1, 1],
      [1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 2, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
      [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

Any ideas about this gratefully received.

Regards,

Rob