Card shuffling to Even Decks

I have an interesting math question I've developed while playing cards with my family and wonder if anyone has a way to approach the problem.

Say I have n people who each have a deck of cards. Each deck has a different number of cards in it. We are shuffling the cards for a game and in the end we all want to have the same number of cards to shuffle. Each individual can do one of two actions per round of shuffling. They can shuffle their deck, or they can split their deck in half and swap one half of their deck with half of another person's deck. My question is, is there an equation based on n to describe a method of swapping that will eventually give all n players the same amount of cards? Furthermore, how many rounds does it take? (In my mind, I define a round as a period of time where everyone performs one action. A player can only perform one action per round and the round ends when all players have performed one action)

To make the problem simpler, you can assume that each individual can only do one action: split their deck and swap with any other player.

The problem is trivial when n is a power of 2. For example if we have 2 people, they split their decks, swap, and they have the same number of cards. It takes one round.

For 4 people, you split them into 2 groups of 2 people and perform the swap internally in the group. Then you make 2 groups with one person from each group in round one and have them swap. This takes 2 rounds.

I would like to see if there is an simple elegant solution when n is not a power of 2.

(You can also assume that each deck splits evenly every time, which is a big assumption but should give a good basis for how to solve the problem. A similar problem would be to replace the cards with cups of liquid which gets rid of passing half of cards around.)

-

There is a standard problem (I often assign it in linear algebra, and I was assigned the problem in representation theory); seems like it might be related.

Suppose you have $n$ people sitting in a circular table, each of them with two neighbors. They each have a bowl of porridge in front of them, and a spoon in each hand. Unhappy with their individual portions, they all simultaneously grab half the porridge from their left-hand neighbor, half the porridge from the right-hand neighbor, and they put it in their bowl (which has been emptied by his neighbors doing the same). What happens to the distribution of porridge over time?

Edit: More explicit, applied to the cards. So, let's consider the case of three eaters/shufflers. I'm assuming for convenience now that the cards are, as Moron suggests, "liquid"; we'll get back to the discrete case presently. Let $x_i(n)$ be the number of cards that the $i$th person has after $n$ steps, with $\mathbf{x}(0) = (a_0,b_0,c_0)$ being the initial distribution of cards (so $a_0,b_0,c_0\geq 0$). Then the procedure can be represented as $$\begin{array}{rcrcrcl} x_1(n+1) &=& & &\frac{1}{2}x_2(n) & + & \frac{1}{2}x_3(n)\\ x_2(n+1) & = & \frac{1}{2}x_1(n) & & &+& \frac{1}{2}x_3(n)\\ x_3(n+1) & = & \frac{1}{2}x_1(n) & + & \frac{1}{2}x_2(n) \end{array}$$ So we can view this as the linear system $\mathbf{x}(n+1) = A\mathbf{x}(n)$, where $$A = \left(\begin{array}{lll} 0 & 0.5 & 0.5\\ 0.5 & 0 & 0.5\\ 0.5 & 0.5 & 0 \end{array}\right).$$ The characteristic polynomial of $A$ is $-t(t-0.5)^2$. Since the rows all add up to $1$, then $(1,1,1)^T$ is an eigenvector of $\lambda=1$ (that is, if everyone starts with $1$, then after applying the procedure they all end up again with $1$: $(1,1,1)^T$ is mapped to one times itself). A basis for the eigenspace corresponding to $\lambda=-\frac{1}{2}$ is $(1,-1,0)^T$ and $(1,0,-1)^T$. If, for instance, player one began with one card, and player two with one "anti-card" (a card made of antimatter, say), then after the first step, player three got half a card from 1 and half an anti-card from 2, which vanished in a puff of smoke; player 2 now has half a card he got from 1, and player 1 has half an anti-card he got from 2. So $(1,-1,0)^T$ is mapped to $(-\frac{1}{2},\frac{1}{2},0)$. Similarly with $(1,0,-1)$.

Now, because $(1,1,1), (1,-1,0), (1,0,-1)$ is a basis for $\mathbb{R}^3$, our original distribution $\mathbf{x}(0)$ can be written uniquely as $\mathbf{x}(0) = a(1,1,1) + b(1,-1,0) + c(1,0,-1),$ for some $a$, $b$, and $c$. Note that the number of cards among all three players is $3a$. If we apply the procedure $n$ times to get $\mathbf{x}(n)$, we will get: \begin{align*} \mathbf{x}(n) &= A^n\mathbf{x}(0)\\ &= A^n(a(1,1,1)^T + b(1,-1,0)^T + c(1,0,-1)^T)\\ &= (a,a,a)^T + (-0.5)^n(b,-b,0)^T + (-0.5)^n(c,0,-c)^T\\ &= (a + (-0.5)^n(b+c), a-(0.5)^nb, a-(0.5)^nc)^T. \end{align*} Now, in reality we are interested in the floor of these quantities (since we are really dealing with actual cards, no negative and fractional cards). As soon as $(0.5)^nb$ and $(0.5)^nc$ are both smaller than $\frac{1}{4}$, the given distribution will be essentially the even distribution $(a,a,a)$.

For an explicit example: suppose that we start with Player 1 having $30$ cards, Player $2$ with $16$ cards, and player $3$ with $22$ cards (I picked the numbers at random). First, we write $(30,16,22)$ as a linear combination of $(1,1,1)$, $(1,-1,0)$, and $(1,0,-1)$. Solving the corresponding system we get: $$(30,16,22) = \frac{68}{3}(1,1,1) + \frac{20}{3}(1,-1,0) + \frac{2}{3}(1,0,-1).$$ So after $n$ applications of the procedure, we will have $$\mathbf{x}(n) = \frac{68}{3}(1,1,1) + \frac{(-1)^n20}{3(2^n)}(1,-1,0) + \frac{(-1)^n2}{3(2^n)}(1,0,-1).$$

So each player will have exactly one third of the cards, modified by a bit. If $n=2$, then the coefficient of $(1,-1,0)$ is $1.67$ and the coefficient of $(1,0,-1)$ is $0.167$; so you would expect the first player to have the nearest integer to $\frac{68}{3}+1.67$ cards, namely about $24$; the second player should have the nearest integer to $\frac{68}{3} -1.67$ cards, so about $21$ cards; and the third player the nearest integer to $\frac{68}{3}-0.167$ cards; this is almost $22.5$, so he'll have $23$ cards (to complete the tally).

If $n=3$, you get about $22$ cards for the first player, $23$ for the second, and $23$ for the third). If $n=4$, the first player should have approximately $23$ cards; the second player should have approximately $22$ cards; and the third player should have approximately $23$ cards. After this point, you'll just be shuffling around who is one card short.

A similar phenomenon occurs with any odd number of people. This may not be the fastest procedure for dividing them among an odd number of players, though.

If you try to do this with $n=4$ people, then the matrix you get is: $$A = \left(\begin{array}{llll} 0 & 0.5 & 0 & 0.5\\ 0.5 & 0 & 0.5 & 0\\ 0 & 0.5 & 0 & 0.5\\ 0.5 & 0 & 0.5 & 0 \end{array}\right).$$ This time, the characteristic polynomial is $t^2(t-1)(t+1)$, so you have one eigenvalue $\lambda=1$ (with corresponding eigenvector $(1,1,1,1)$, which is associated to "the cards are evenly distributed"); you get one eigenvalue $\lambda=-1$, with corresponding eigenvector $(1,-1,1,-1)$; and you get two eigenvectors mapping to $0$; for instance $(0,1,0,-1)$ and $(1,0,-1,0)$.

Once you express your original distribution as a linear combination of these, $(x_1(0),x_2(0),x_3(0),x_4(0)) = \alpha(1,1,1,1) + \beta(1,-1,1,-1) + \gamma(0,1,0,-1) + \delta(1,0,-1,0),$ the last two components don't matter after the first go around, so you end up with $\mathbf{x}(n) = \bigl( \alpha + (-1)^n\beta, \alpha - (-1)^n\beta, \alpha+(-1)^n\beta, \alpha-(-1)^n\beta\bigr).$ So depending you are going to have a certain portion of the cards evenly distributed (corresponding to $\alpha$), and a certain portion of the cards (corresponding to $\beta$) swapping between even- and odd-numbered players at each step.

Edit: Another way of looking at the $n=4$ case: A better way of seeing what is happening in this case is to replace the vector $(1,-1,1,-1)$ with the vector $(2,0,2,0)$ (the sum of the eigenvector and $(1,1,1,1)$); we still have a basis, so we can write any initial distribution as $$(x_1(0),x_2(0),x_3(0),x_4(0)) = \alpha(1,1,1,1) + \beta(2,0,2,0) + \gamma(0,1,0,-1) + \delta(1,0,-1,0).$$ But now, when you apply $A$, the vector $(2,0,2,0)$ transforms into the vector $(0,2,0,2)$, and this vector is in turn transformed back into $(2,0,2,0)$. The total number of cards is $4(\alpha+\beta)$. Of these, $4\alpha$ of the cards will eventually end up evenly distributed among the players, but the remaining $4\beta$ cards will end up evenly distributed between two non-adjacent players, and then swapped over to the other two players, then swapped back. If you imagine you are in a bridge table, first the North-South partnership has the extra $4\beta$ cards, $2\beta$ cards each, then they go to East-West, then back to North-South, then back ot East-West, etc.

A similar phenomenon occurs with any even number of players.

Added: Back to the discrete case. Okay, above we were dealing with the "liquid cards"/"porridge" case, where the cards are divisible any way we want. What happens if we are playing actual cards that we don't want to split up? Notice that each player is only required to divide his cards in half; so the only problem arises if a player has an odd number of cards. In that case, the player can just give the extra card to whichever of his neighbors he likes the most, or randomly; the final distribution in this case is very close to the ideal "continuous" distribution: each of his neighbors was supposed to get $x$-and-a-half cards from him, but got either $x$ or $x+1$; so the most that any one person can be off from the "ideal" result of applying the procedure is $1$ card (half a card from one neighbor, half a card from the other). This vector will be fairly close to the "ideal" continuous vector, and so the result of applying the procedure to this distribution will also result in a distribution which is fairly close to what the ideal distribution is. (Linear maps are continuous, and in this case the eigenvalues are all of absolute value less than or equal to $1$, so the approximation will not get worse as time goes on; it will either remain the same, or get better). You can see this in the example I worked out for $n=3$. If you start with $(30,16,22)$, then after the first step you get $(19,26,23)$; at the next step, the "predicted" distribution is $(24,21,23)$. The actual distributions you get are either $(24,22,22)$, $(25,21,22)$, $(24,21,23)$, or $(25,20,23)$, depending on how the extra cards get distributed. The sup-distance to the predicted distribution is 1 in all cases. Do it a third time, and depending on how things break you will end up in either $(22,24,22)$, $(21,24,23)$, $(22,23,23)$, $(21,23,24)$, $(23,23,22)$, or $(21,25,22)$. The "worst" distribution (the last one) is still better than the worst distribution in the previous step. And so on.

In summary: the "give half your cards to each of your neighbors and get half of each of their cards" will yield an even distribution after a fairly small-ish number of steps if there is an odd number of players, but will not necessarily yield and even distribution if there is an even number of players. In the latter case, part of the deck will get evenly distributed, while the other part ends up swapping between adjacent "teams". One advantage of this, at least for an odd number of players, is that it is a single procedure that is repeated a number of times (much like riffle-shuffling a deck) in order to achieve uniformity, rather than a more complex algorithm that involves different actions at different steps.

-
Thanks. Now I have to go and remember what an Eigenvalue is but I'll look into the porridge problem to see if it gives me any insight into the behavior of my problem. I have one question. You address the odd number of people in both the 2nd and 4th paragraph of your answer, but don't mention the even number of people. Is there a typo somewhere or did I miss something? Thanks again. – thattolleyguy Nov 9 '10 at 20:00
How can we apply this procedure to the discrete case? Won't you end up splitting cards into fractions? Don't you have to round off after each iteration? – Aryabhata Nov 9 '10 at 21:53
@Moron: Yes, you round off at each iteration (any way you want, really; give the extra card to your favorite neighbor). It still converges towards the given distributions (evenly distributed if $n$ is odd, part-evenly-distributed and part being alternated if $n$ is even). You are just applying the same procedure/matrix to a vector which is very close to the image of the original, and the difference between your vector and the "actual" solution becomes negligible because it is $\pm 1$ card, and the eigenvalue $-0.5$ quickly makes it very small. – Arturo Magidin Nov 9 '10 at 21:58
@Moron: (cont) Note that since each person is just dividing his deck in two, the only possible "rounding" necessary is that you have an odd number of cards with a left-over card; so each person can be at most 1 card off from the continuous distribution (half a card from one neighbor, half a card from the other). – Arturo Magidin Nov 9 '10 at 21:59
@Arturo: Why don't you edit the answer to make that clear? – Aryabhata Nov 9 '10 at 22:03

It depends on the number of cards each person holds.

For instance with 3 people, one holding 8 cards, one 16 and the other 32 you can never get each to have the same number, as the total is not divisible by 3.

EDIT:

If the cards were "liquid" (or basically arbitrary real numbers), even then, there is no procedure (independent of the cards each person holds), which will end in finite number of steps.

After a finite number of steps each will have a finite representation when written in base 2, but $4/3$ does not have a finite representation in base 2.