What is the maximum amount of shuffled a deck of cards can be?

Question

I had this question pop into my head a few days ago and I've been thinking about it since. It has a fairly simple set up: you have 52 cards.

Take the amount of "shuffling" to be the average distance between where each card started, and where it ended up after the shuffle. For example, given $N$ cards, the maximum shuffling would be decided as:

$$\text{maximum shuffling} = \max \Bigg\{ \sum_{n=1}^{N} \frac{|\text{new}_n - \text{old}_n|}{N} \Bigg\}.$$

The old positioning of the card is arbitrary, they must simply be different, so I came up with:

$$\text{maximum shuffling} = \max \Bigg\{ \sum_{n=1}^{N} \frac{|f(n, N) - n|}{N} \Bigg\}.$$

Such that $f(n, N):(\mathbb{N} \leq N)\times \mathbb{N} \to \mathbb(\mathbb{N} \leq N)$ is bijective.

For $N=1$, the maximum shuffling is $0$. For $N=2$, the maximum shuffling is $1$. For $N=3$, the maximum shuffling is $\frac{5}{3}$.

I do not know what it is for $N=4$. My goal is to find $N=52$.

How would I go about this?

Answer 1

The maximum shuffle, as defined here, can be achieved simply by reversing the order of the cards. Think of it this way. For any given arrangement of the cards, if card $1$ is in position $k$ and $k\not=N$, then you can swap it with the card in position $k+1$, and the "shuffle" will either stay the same (if the value of the card in position $k+1$ is less than $k+1$) or will increase, by $2$ (if the value of the card in position $k+1$ is greater than $k$). So moving card $1$ all the way to the bottom cannot lessen the shuffle.

Likewise, moving card $N$ all the way to the top cannot decrease the shuffle. But once you've done so, cards $2$ through $N-1$ now constitute their own deck of $N-2$ shuffled cards, and, by induction (making use of the OP's base cases $N=1$ and $N=2$), we know that their maximum shuffle can be achieved by reversing their order. So we're done!

Remark (added later): The same argument that lets you move the $1$ to the bottom of the deck and the $N$ to the top, now lets you reverse the order of the cards in the top and bottom halves of the deck, respectively: Each swap preserves the shuffle, because one card in each swap gets further from its natural position while the other card gets closer. We thus see that "cutting" an unshuffled deck precisely in half if $N$ is even, or leaving the middle card alone while swapping the top and bottom halves if $N$ is odd, also maximizes the "shuffle." For $N$ even, each card is precisely $N/2$ positions away from its unshuffled position, so the maximum shuffle is $N/2$. If $N=2n+1$, each of the non-middle cards is $n+1$ positions away, for a maximum shuffle of $2n(n+1)/(2n+1)$.

Answer 2

A maximum shuffle in your definition, is any pattern which puts the first half of the cards into the second half and puts the second half into the first half.

It does not matter what order you put the cards in their respective halves: you can easily see that swapping two cards in the same half brings one closer to its original position and pushes one further away by an equal and opposite amount, so having no net effect.

So if $N$ is even then the maximum shuffle value is $\frac N2$ since you could simply move each card by a absolute distance $\frac N2$ so the average is also $\frac N2$.

When $N=2$ this is $1$ and when $N=52$ it is $26$.

When $N$ is odd there is a slight complication of the middle card. But the same argument applies about swapping two cards, so you can treat the middle card as being in the first half, or being in the second half, or being in neither half and not moving. The calculation is then a little more complicated, but you could for example move every card apart from the middle card by an absolute distance of $\frac{N+1}{2}$ making the average $\frac{N-1}{N}\frac{N+1}{2} =\frac{N^2-1}{2N}$.

When $N=3$ this is $\frac{4}{3}$ rather than your $\frac53$, and is achieved when $(1,2,3)$ is shuffled to any of $(3,1,2)$ (middle card treated as being in first half so moving to second half) or $(2,3,1)$ (middle card treated as being in second half so moving to first half) or $(3,2,1)$ (middle card stays in the same place and not moving)