Cards Shuffle problem: How to prove solution exists? Is there a formula for the solution?

Question

Problem

You have a pile of N cards sorted from 1 to N where card 1 is the one on top and card N is the one at the bottom. We do a shuffle operation on the N cards and the shuffle consists of going through the cards from top to bottom and placing them alternatively one at the bottom and one at the top in order to create a new shuffled pile of cards (i.e: take card 1 place it at the bottom of a new pile, card 2 goes to the top, card 3 goes to the bottom, card 4 goes to the top, etc).

We then take the new pile of cards and shuffle it again using the same procedure.

Example: N = 4

Initial state:    1 - 2 - 3 - 4  (pile of 4 cards from top to bottom)
After 1 shuffle:  4 - 2 - 1 - 3
After 2 shuffles: 3 - 2 - 4 - 1
After 3 shuffles: 1 - 2 - 3 - 4 (Now back to sorted pile of cards, we're done)
So it takes 3 shuffles to get back to initial state.

The question is: given N cards

• How many shuffle operations does it take to get back to sorted cards (1 to N)?
• Is there a mathematical formula to it?
• How to prove mathematically that the cards will always come back in the sorted order?

Answer 1

Let me write out an example to help illustrate what's going on, and that'll help develop an intuition as to how to prove it. Let us take an example of $N=6$. Now, $B$ means a bottom sort, and $T$ a top sort. For this sorting, a card in a particular position will be shuffled to a known new position. Hence, we have a cycle associated with each position

For the 1st number (1), we have the following position shuffle

$$1 - 4 - 2 - 3 - 5 - 6- 1$$

For the 2nd number (2), we have the following

$$2 - 3 - 5- 6- 1 -4 -2$$

Are you noticing something? Let's look at the third number (3)

$$3 - 5 - 6 - 1 - 4 -2 - 3$$

I don't think I have to write any more down. Basically, this shuffle for a given N is a permutation, and if you repeat the same permutation you will always eventually end up with the same sequence as the one you started with.

Rethink is this way for the general $N$ case to see how many moves it should take

Answer 2

The third question is easy.

This shuffling is a deterministic and invertible operation and as the number of permutations is finite, you will cycle among the permutations, unavoidably coming back to the initial configuration.

Answer 3

You can write the permutation in cycle notation. In your four card case the permutation is $(143)(2)$ because $1$ goes to where $4$ was and so on. Having done so, the order will repeat in the least common multiple of the lengths of the cycles. If you do the same thing for seven cards, the resulting deck is $6421357$ which in cycle notation is $(142356)(7)$ so will repeat in six shuffles. For eight cards the deck is $86421357$ which in cycle notation is $(5781)(2436)$ so it will repeat after four shuffles. For ten cards it is $A864213579$ which in cycle notation is $(16379A)(258)(4)$ so it will repeat in six shuffles. For twelve cards it is $CA864213579B$ which in cycle notation is $(17A26459BC)(38)$ so it will repeat in ten shuffles. An odd deck will repeat in the same time as the preceding even deck because the last card just becomes a $1-$cycle at the end.