You are given a deck of 52 shuffled cards. What is the minimum number of times you need to sort the cards in order to return them to their original sorted order?

The card sorting problem or card cyclicity problem is a combinatorial problem that can be solved using group theory, specifically the notion of permutation cycles and the concept of least common multiple (LCM).

Given a deck of 52 shuffled cards, suppose we want to sort the cards in ascending order, which for simplicity, can be represented by the numbers 1 to 52. This means that we want every card to be in its original (sorted) position in the deck. Let us formalize this with being a permutation (a bijection) of the deck, such that:

σ : {1, 2, …, 52} → {1, 2, …, 52}

For a given shuffle represented by the permutation σ, we want to find the minimum number n such that applying the permutation n times returns the deck to the original sorted order. That is, we want to find the smallest integer n such that σⁿ(i) = i for all 1 ≤ i ≤ 52.

Now, let’s consider the decomposition of the given permutation σ into its disjoint cycles. A permutation cycle of length k is a sequence of integers c₁, c₂, ..., c_k such that applying the permutation k times brings each element back to its original position:

σ^k(c_i) = c_i + 1;

for i = 1, 2, …, k − 1 and

σ^k(c_k) = c₁.

Since the cycles are disjoint, each card belongs to exactly one cycle. Let’s say the given shuffle σ can be decomposed into disjoint cycles with lengths: c₁, c₂, ..., c_m.

To find the minimum number of times we need to sort the cards to return them to their original sorted order, we need to apply the permutation the least common multiple of cycle lengths times, i.e.,

n = lcm (c₁, c₂, ..., c_m).

This is because the least common multiple ensures that all cards in all cycles cycle back to their original positions simultaneously.

Therefore, the minimum number of times you need to sort the deck is the least common multiple of the lengths of the disjoint cycles of the given permutation.

As an example, let’s take a simple deck of 4 cards, with the given shuffle σ = (14)(23), which is already expressed in its cycle notation. The lengths of the cycles here are 2 and 2, i.e., (c₁, c₂) = (2, 2). The least common multiple of these lengths is:

lcm (2, 2) = 2.

Thus, in this example, we need to sort the cards at least 2 times to return them to their original sorted order.