6

A perfect riffle shuffle, also known as a Faro shuffle, is performed by cutting a deck of cards exactly in half and then perfectly interleaving the two halves. There are two different types of perfect shuffles, depending on whether the top card of the resulting deck comes from the top half or the bottom half of the original deck.

An out-shuffle leaves the top card of the deck unchanged. After an in-shuffle, the original top card becomes the second card from the top. For example:

OutShuffle(A♠2♠3♠4♠5♥6♥7♥8♥) = A♠5♥2♠6♥3♠7♥4♠8♥

InShuffle(A♠2♠3♠4♠5♥6♥7♥8♥) = 5♥A♠6♥2♠7♥3♠8♥4♠

Consider a deck of $2^n$ distinct cards, for some non-negative integer $n$ . What is the effect of performing exactly $n$ perfect in-shuffles on this deck?

What is the answer and How can i prove that?

Teru
  • 95
  • 1
    You've written a great example with $8 = 2^3$ cards. What happens if you do two more inshuffles? (Meaning two more than the one you've written) – Michael Harrison Mar 04 '16 at 06:20
  • 1
    if i do two more inshuffles, then 5♥A♠6♥2♠7♥3♠8♥4♠ -> 7♥5♥3♠A♠8♥6♥4♠2♠ 7♥5♥3♠A♠8♥6♥4♠2♠ -> 8♥7♥6♥5♥4♠3♠2♠A♠ – Teru Mar 04 '16 at 06:22

1 Answers1

5

Now that you know the answer (it reverses the deck), here's how you can prove it. The shuffle can be written as a cyclic permutation. If I write $$( 1 \ 2 \ 4 \ 8 \ 7 \ 5 )(3 \ 6),$$ this is a way of writing the permutation in which the first card goes to the second place, the second goes to the fourth place, the fourth goes to the eighth place, etc. This is just a different way of writing the result of one inshuffle. Now iterating this permutation three times looks like this: $$( 1 \ 2 \ 4 \ 8 \ 7 \ 5 )(3 \ 6)( 1 \ 2 \ 4 \ 8 \ 7 \ 5 )(3 \ 6)( 1 \ 2 \ 4 \ 8 \ 7 \ 5 )(3 \ 6),$$ which reduces to the cycle $$(1 \ 8)(2 \ 7)(3 \ 6)(4 \ 5),$$ which is exactly the permutation which reverses the order.

Maybe you can try it for 16 and observe if there is a nice pattern which works for all $2^n$.

Michael Harrison
  • 1,932