Card-passing puzzle

[Rob Arthan]

Dear All,

Thanks for all the interest! I have an argument about a variant of the game 
which covers the case of the original game when all cards are dealt to one 
player. Apologies if the presentation below is a bit long-winded:

In the variant, play is as before, but the players are sitting in a straight 
line; new players are recruited to join on the ends of the line as needed. 
Here's an example initial arrangement:

3 0 3 2 1

In this linear version of the game, we can number the players and the cards 
from left to right. So players are numbered by integers, say -2, -1, 0, 1, 2 
in the initial arrangement above. The cards are numbered 1,  2, .. n - 1 and 
are dealt in order from left to right. Thus (with n = 10):

-2 -> {1, 2, 3}, -1 -> {}, 0 -> {4, 5, 6}, 1 -> {7, 8}, 2 -> {9}

for our example:

The players then agree to pass their smallest card left and their highest card 
right if they have more than one card. In the case when player P would pass a 
card to player P+1 and vice versa, the players agree not to do the pointless 
exchange. So for the first round of play in the example, we need to recruit a 
new player -3 and the arrangement becomes:

-3 -> {1}, -2 -> {2}, -1 -> {3, 4}, 0 -> {5, 6}, 1 -> {7}, 2 -> {8, 9}


Let P_i be the number of the player who initially holds card i and let p_i and 
number of the player who holds card i at a typical stage of the game. The P_i 
and the p_i are a non-decreasing sequence of integers.

Then:

	p_1 + p_ 2 + .... + p_{n-1} = P_1 + P_2 _ ... P_n

because whenever a card i moves left there is a corresponding card i+j say 
that moves right (possibly with j > 1, as in the example above where card 4 
moved left corresponding to card 8 moving right). Thus whenever a p_i goes 
down by one a corresponding p_{i+j} goes up by one, so that play does not 
affect the above sum. This means that the centre of gravity of the cards is 
fixed.

Similarly, pairing up (p_i - 1 - p_1 + 1)^2 and (p_{i+j} + 1 - p_1)^2 you can 
see that the variance (p_1 - p_1 + 1)^2 + (p_2 - p_1 + 1)^2 + ... + (p_n - 
p_1 + 1)^2 increases (strictly) whenever a round of play is possible.

Also, I claim that for each i and j, and at every stage of the game:

	p_{i+j} - p_i <= P_{i+j} - P_i} + j + 1			(*)

Why? Well this is certainly true initially (when p_i = P_i), so assume that it 
holds (for all i and j) at some stage in the game. For given i and j consider 
the positions p'_i and p'_{i+j} of cards i and j after the round of play in 
this stage. If the cards have not moved or have moved closer together then 
clearly (*) still holds (for p'_i and p'_{i+j}). If they have moved further 
apart then either i has moved left or i+j has moved right or both. Let's just 
consider the case when both have moved (the other two cases are similar and 
simpler). As card i has moved, then before the round of play, cards i and i+1 
must have been held by the same player, and similarly cards i+j-1 and i+j 
must have been held by the same player. Thus:

	p'_i = p_i - 1 = p_{i+1} - 1
	p'_{i+j} = p_{i+j} + 1 = p_{i+j-1} + 1

but by assumption:

	p_{i+j-1} - p_{i+1} <= P_{i+j-1} - P_{i+1} + (j - 2) + 1
		<= P_{i+j} - P_i + j - 1

but then

	p'_{i+j} - p'_i = p_{i+j-1} - p_{i+1} + 2 <= P_{i+j} - P_i + j + 1

so the inequality (*) holds (for all i and j) after the round of play and so 
by induction it holds throughout the game. In particular:

	p_{i+j} - p_i <= p_{n-1} - p_1 <= P_{n-1} - P_1 + n - 1

Summing up: the centre of gravity of the cards is fixed throughout the game; 
the variance of the positions of the cards strictly increases whenever a 
round of play is possible and the distance between the cards and no two cards 
are ever more than C - n - 1 positions apart where C = P_{n-1} - P_1. The 
last condition means that the variance is bounded, and so play must terminate 
and in the terminating state the n - 1 cards must be distributed amongst C + 
n consecutive players each holding at most one card. Moreover during the 
course of the play no player other than these C + n has ever held a card.

This analysis of the linear variant of the game shows that the original 
circular version will terminate if all the cards are given to one player, 
since play in the circular game is just like play in the linear game until a 
card wraps around the circle, but by the above analysis (with C = 0) this 
will never happen.

Regards,

Rob.