0

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.

Maths123
  • 11

1 Answers1

-1

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)

cr001
  • 12,598