A pack of 13 distinct cards is shuffled in some particular manner and then repeatedly in exactly the same manner. What is the maximum number of shuffles required for cards to return to their original position.
I don't know how to start with this problem. I've never come across such problems in past. Any hint will be appreciated.
This problem is in the book Pathfinder for Olympiad Mathematics
Given Answer : 60
Put in mathematical terms, the shuffle is basically a permutation. And a permutation consists of disjoint cycles. So all the problem is asking is the maximum lowest common multiple of the lengths of the cycles, where the sum of the lengths is $13$.
(e.g. a permutation sending $123456$ to $364512$ has cycles: $(1, 3, 4, 5), (2, 6)$)
When there are $2$ cycles, the greatest LCM can be $6*7 = 42$
When there are $3$ cycles, let the minimum length be $a$. Then $a \leq 4$. Take cases and check that the maximum is achieved when the lengths are $1, 5, 7$ and the LCM is $35$.
When there are $4$ cycles, the maximum is achieved when the lengths are $1, 3, 4, 5$ and the LCM is $60$.
Beyond 4 cycles, it is easy to see that no permutation gives LCM more than $60$. Thus $60$ is the answer.