Another Mathematical Card Trick

Posted in math on Friday, May 06 2016

Matt Parker recently posted a video with a neat mathematical card trick. Like all good things in life it involves lots tedious counting and shuffling, so brace yourself.

The steps are these:

1. Deal out some number of cards (if you are a proper showman you will get the audience to give you some positive integer less or equal to 52)
2. Take a peak at the last card you deal and remember that (if you are a proper showman you won't announce to the audience that you're doing that)
3. Pick a number greater than half the number of cards you just dealt
4. Deal out that lesser number, placing the remaining cards on top
5. Do this three times.
6. The card you were supposed to remember? Yeah, it's now the top card.

This is neat, and it is pretty easy to show that this will happen by just tediously working through the shuffling operations!

Suppose we have $N$ cards in a set $\{ N, \dots, 3, 2, 1 \}$, we are going to deal from the right, so the top of this deck is card number 1.

Suppose we have a number $m$ such that $N > m > \frac{N}{2}$. Just to make accounting later easier let's take an $n$ such that $N = n + m$, clearly $n < m$.

The Deals

First Deal

We deal out the first $m$ cards, which is the first $n$ cards and the middle $m-n$ cards now in reverse order

$$\{ 1, 2, 3, \dots, n \} + \{ n+1, \dots, m \}$$

Adding the remaining $n$ cards $\{ N, N-1, \dots, m+1 \}$ gives us the final deck: $$\{ 1, 2, 3, \dots, n, n+1, \dots, m, N, N-1, \dots, m+1 \}$$

I think at this point you can see what's going on here, in terms of reversing the deck. But let's continue.

Second Deal

We deal out the first $m$ cards, which is the remainders from before reversed, plus the additional $m-n$ cards now doubly reversed: $$\{ m+1, m+2, \dots, N-1, N \} + \{ m, m-1, \dots, n+1 \}$$

and place the remaining $n$ cards on top to get: $$\{ m+1, \dots, N, m, m-1, \dots, n+1 , 1, 2, \dots n \}$$

Third Deal

We deal out the first $m$ cards, which is the set of size $n$ from before reversed, plus an additional $m-n$ cards

$$\{ n, n-1, \dots, 1 \} + \{ n+1, \dots m \}$$

and place the remaining cards on top to get: $$\{ n, n-1, \dots, 1, n+1, \dots m, m+1, \dots, N \}$$

So clearly the $N$ card migrates from the bottom of the deck to the top, making the trick. But if we shuffle once more:

Fouth Deal

We deal out the first $m$ cards:

$$\{ N, N-1, \dots, n+1 \}$$

Add the remaining cards in their original order:

$$\{ N, N-1, \dots, n+1, n, n-1, \dots 1 \}$$

And we end up with the original sequence.

Operators

Reversing Sequences

Suppose we just ignore the order the cards are in overall, and instead look at three subsets: the first $n$ cards, the middle $m-n$ cards, the last $n$ cards. I'm going to mark original order with a + and reversed order with a -.

Shuffle $\{ N, N-1, \dots, m+1 \}$ $\{ m, m-1, \dots, n+1 \}$ $\{ n, \dots, 3,2,1 \}$
0 + + +
1 + - -
2 - + -
3 - - +
4 + + +

Each shuffle reverses the order of one of the sets of $n$ cards on the ends, as well as the middle $m-n$ cards. By taking the un-reversed cards and putting them on top we guarantee that we alternate which set of $n$ gets reversed. However in each shuffle the middle bit is guaranteed to be reversed.

Cycling Sequences

Now let's ignore the order of those three subsets and just look at where they end up in the deck, marking their position as (1, 2, 3) for bottom, middle, top (respectively)

Shuffle $\{ N, N-1, \dots, m+1 \}$ $\{ m, m-1, \dots, n+1 \}$ $\{ n, \dots, 3,2,1 \}$
0 1 2 3
1 3 2 1
2 1 2 3
3 3 2 1
4 1 2 3

Each time we split the deck into sets of $m$ and $n$ cards we flip the top set of $n$ and the bottom set of $n$ back and forth.

A "Linear Combination"

If we just "add" the two tables together we get, where "+1" means "in position 1, original order" and "-3" means "in position 3, reverse order"

Shuffle $\{ N, N-1, \dots, m+1 \}$ $\{ m, m-1, \dots, n+1 \}$ $\{ n, \dots, 3,2,1 \}$
0 +1 +2 +3
1 +3 -2 -1
2 -1 +2 -3
3 -3 -2 +1
4 +1 +2 +3

The two operations of flipping the top and bottom $n$ cardds and reversing their orders line up nicely to allow us to cycle through the 4 possible combinations (from our starting point).