1

I am now trying to prove performing n perfect in-shuffle with 2^n deck of card, and then it will be resulting reverse order.

For example, Initial : [1, 2, 3, 4] 1st round : [3, 1, 4, 2] 2nd round : [4, 3, 2, 1] = reverse order!

Until now, I realized following some information.

  1. each k steps, card pair with 2^k cards are reverse order.

  2. card at kth, when next shuffle, it will be at 2k mod 2^(n-1)+1

I does not know how to prove when I do n perfect in-shuffle, then I get reverse order of original deck.

MarnixKlooster ReinstateMonica
  • 5,576
Tony_SSU
  • 21

1 Answers1

4

It is easy to verify (it looks like you almost had this) that this shuffle maps: $$\sigma: i \rightarrow 2i \mod (2^n + 1) \textrm{ for $i \in \{1,...,2^n\}$}$$

Take $a \in \{1,...,2^n\}$:

$$\sigma^n(a) = 2^n(a) \mod (2^n + 1)$$ $$= (2^n+1)(a) - a \mod (2^n+1)$$ $$= - a \mod (2^n+1)$$ $$= 2^n+1-a$$

As $2^n+1-a$ is the mirror of the initial position of $a$, we have shown that this deck will be reversed after performing $n$ shuffles.