Find a shuffle of 13 cards that requires 42 repeats to return to the original order

Question

I don't know how to approach this problem at all. Should I find a set of disjoint cycles such that the lcm of their orders is 42? For example

(1 2 3 4 5 6)(7 8 9 10 11 12 13)

Answer 1

Let me generelize your question:

For given $n, k \in \mathbb N$ find $\sigma \in S_n: ord(\sigma) = k.$

Let us compose $k = p_1^{m_1}\ldots p_l^{m_l},$ where $p_i$ are distinct primes.

If $p_1^{m_1} + \cdots + p_l^{m_l} > n,$ then there is no such $\sigma$. Otherwise $$\sigma := \sigma_1\ldots \sigma_l := $$$$(1 \ldots p_1^{m_1}) ((p_1^{m_1} + 1) \ldots (p_1^{m_1} + p_2^{m_2})) \ldots ((p_1^{m_1} + \ldots + p_{l-1}^{m_{l-1}} + 1)\ldots(p_1^{m_1} + \ldots + p_{l}^{m_{l}}))$$

Let us show that $ord(\sigma) = k$. As disjoint cycles commute $$\sigma^a = (\sigma_1)^a\ldots(\sigma_l)^a.$$ So if $\sigma^a = id,$ then $ord(\sigma_i) | a,$ so $k | a$. Thus $ord(\sigma) = k$.

In your paticular example: $n = 13, k = 2 \times 3 \times 7,$ so for $$\sigma = (1\,2) (3\,4\,5) (6\,7\,8\,9\,10\,11\,12)$$ we have $ord(\sigma) = 42.$

By the way your example is also correct. If by "shuffle" you ment that $\forall j: \sigma(j) \neq j,$ the promblem is similar rucksack problem, thus it is solvable only via an exhaustive search, as it will require to find such $n_1, \ldots, n_l$ that $$n_1 + \ldots + n_l = n,$$ $$lcm(n_1,\ldots, n_l) = k.$$