Returning a deck of cards to its original state with overhand shuffle

Question

I am trying to figure out the minimum number of shuffles needed to return a deck to its original state based on the number of blocks within each shuffle. The number of cards in each block must add up to the sum of the deck. The number of cards in the deck is a variable as well as the number of blocks and the sizes of each block.

An example would be if we had a deck of abcdef, and we perform an overhand shuffle with 3 blocks, the first block is 2, the second is 3 and the last is 1. Performing this shuffle gives a result of fcdeab, as we take the first 2 letters "ab" and put them at the bottom, take the next 3 "cde" and put that on top of the "ab" and then take the last block of 1 "f" and put that on top giving "fcdeab".

For a 1 block shuffle equal to the number of cards in the deck the number of minimum shuffles is 1, for a 2 block shuffle the answer is 2 and for a 3+ block shuffle the answers the vary depending on the sizes of each block. So based on that is there an algorithm I can use to calculate the minimum number of shuffles for any given amount of deck size, the number of blocks, and the size of each block within a shuffle to return a deck to its original state?

Please let me know if you want me to clarify any details, Thanks!

Answer 1

The procedure for finding the minimum number of shuffles for a fixed group of blocks is straightforward; the general answer might be out of reach. I'll illustrate this with a few examples that show how wide the range of possibilities is.

But first, the method to solve this problem. First, suppose that we are doing a blocks shuffle with blocks of size $\langle 2,4\rangle$, which permutes $(1,2,3,4,5,6)$ to $(3,4,5,6,1,2)$. It's common, and useful for this particular problem (finding the order of a permutation) to write it in its cycle decomposition. In this case, that's $$(1\;5\;3)\;(2\;6\;4)$$ meaning that $1$ takes the place of $5$, $5$ takes the place of $3$, and $3$ takes the place of $1$ (the first cycle) while $2$ takes the place of $6$, $6$ takes the place of $4$, and $4$ takes the place of $2$ (the second cycle).

If we apply the same permutation multiple times, then the elements in a cycle will just keep rotating around that cycle. In this case, that means that after $3$ shuffles, the $(1\;5\;3)$ cycle will return to its original position, as will the $(2\;4\;6)$ cycle, so we'll get back the original deck.

For a more complicated example, consider the $\langle 1,1,3\rangle$ shuffle, which transforms $(1,2,3,4,5)$ into $(3,4,5,2,1)$, and has cycle decomposition $$(1\;5\;3)\;(2\;4).$$ The elements of the $(1\;5\;3)$ cycle will return to their original position every $3$ shuffles, but the elements of the $(2\;4)$ cycle will return to their original position every $2$ shuffles. It takes $6 = \operatorname{lcm}(2,3)$ shuffles for both cycles to line up the way they were in the original deck.

---

Some examples of the possibilities:

• For two blocks, an $\langle a,b\rangle$ shuffle results in a single cycle of length $a+b$ whenever $\gcd(a,b)=1$, so it returns to the start after $a+b$ shuffles. In general, when all the blocks have a common divisor $d$, they only move cards around in groups of $d$, and the $\langle a_1, \dots, a_k\rangle$ shuffle is equivalent to the $\langle \frac{a_1}{d}, \dots, \frac{a_k}{d}\rangle$ shuffle on the groups. This gives a general answer of $\frac{a+b}{\gcd(a,b)}$ in this case.
• A $\langle 1,1,k\rangle$ shuffle will produce two cycles $$(1\;(k+2)\;k\;\cdots\;5\;3) \; (2\;(k+1)\;(k-1)\;\cdots\;6\;4)$$ when $k$ is odd, and a single cycle $$(1\;(k+2)\;k\;\cdots\;6\;4\;2\;(k+1)\;(k-1)\;\cdots\;5\;3)$$ when $k$ is even, so it takes $\frac{k+3}{2}\cdot\frac{k+1}{2}$ shuffles to return to the beginning in the first case, and $k+2$ shuffles in the second case.
• A $\langle 1,2,k\rangle$ shuffle has similar behavior depending on $k \bmod 3$ instead. When $k \equiv 1 \pmod 3$, it produces three cycles $$(1\;(k+3)\;k\;\cdots\;4)\;(2\;(k+1)\;(k-2)\;\cdots\;5)\;(3\;(k+1)\;(k-2)\;\cdots\;6)$$ and the deck returns to its original state every $\frac{k+2}{3}\cdot \frac{k-1}{3}$ shuffles; for other $k$, it produces a single cycle, and the deck returns to its original state every $k+3$ shuffles.

Answer 2

I don't think the problem can be solved satisfactorily without knowing the specific values of $N$ (total cards) and numbers of cards in individual blocks.

To restore to the initial state, do you allow the blocks to be the same as those you used to shuffle?

If yes, then simply using the same block sizes and reverse the order of the moves.

If no, then the problem cannot be solved without knowing the details. Based on your example, if the restoring process allows only block size of 6, there is no way to restore to the initial state.