0
$\begingroup$

A pack of 2n cards is shuffled by the "interlacing" method, in other words, if the original order is 1, 2, 3, 4,...,2n, the new order after the shuffle is 1, n+1, 2, n+2,... n, 2n. Work out how many times this shuffle must be repeated before the cards are again in the original order in the case of n = 10.

I know I have to use this proposition "The order of a permutation in cycle notation is equal to the least common multiple of the lengths of the cycles" but I can't find the order of the permutations.

$\endgroup$
-1
$\begingroup$

We will consider $2n$ and $1$ a combined fixed position and the position before $2n$ the position index $0$ and $2n,1$ is at position index $1$.

Then the shuffle is defined by sequence $a_{x+1}=2a_x-1\pmod{2n-1}$

Solve the recurrence we have $a_x=c\cdot2^{x-1}+1\pmod{2n-1}$ where $c$ depends on which initial number you choose.

The period of the sequence is the smallest $y$ such that $2n-1|c(2^y-1)$ for all $c$ including $c=1$ ($c=1$ for the initial number $2$ case.) Hence it is basically the smallest $y$ that $2n-1|2^y-1$.

When $n=10$, $2n-1=19$ and hence $y=18$ by fermat little theorem. (We might still need to manually check if divisors of $18$ works and none of them work so $18$ is the smallest)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.