A perfect shuffle is performed on a deck of cards by splitting the deck into two

Question

A perfect shuffle is performed on a deck of cards by splitting the deck into two halves (the top and the bottom half, we're assuming our deck has an even number of cards, then interweaving the two halves so that every-other card comes from the same half (and the order within the halves is preserved). There are two ways to do this: an out shuffle preserves the first and last cards, while an in shuffle does not. Show that after 8 perfect out shuffles, a deck of 52 cards is returned to its original position, but no fewer number of perfect out shuffles will do this. How many perfect in shuffles does it take to return a deck of 10 cards to its original position?

Explanation / Answer

A)

The out-shuffle is identical to an in-shuffle on two fewer cards.

Since the first and last cards are fixed, we will simply rename the deck to exclude those cards and focus on in-shuffling instead. To be perfectly clear, the 1st card is really the second card and so forth.....

The in-shuffle on 2n cards (which is an out-shuffling on 2n+2 cards) can be represented as a permutation S2n in two-line notation as follows:

= (1 2 3n n+1 n+2 n+32n)

      (2 4 6 ... 2n 1 3 5 ... 2n-1)

From here, imagine that we rewrite the two-line notation into disjoint cycle notation. Denote m as the length of the cycle to which 1 belongs.

Next, show that, for any arbitrary x{1,2,...,2n}, the length of the cycle to which x belongs divides m.

We know that (x)2x, then (2x)22x4x, then (4x)24x8x, and so forth working (mod2n+1).

From here, we can simply apply the fact that the order of a composition of disjoint cycles is the least common multiple of their respective lengths. Since all cycle lengths divide m

, then the order of the entire permutation is m. That is, the number of in-shuffles required to return a deck of 2n cards to its original position is equal to the order of 2 in the multiplicative group Z×2n+1. As discussed in the first paragraph, this will be equal to the number of out-shuffles required to return a deck of 2n+2 cards to their original position

Hence the perfect out shuffles for a deck of cards to return to its original position is 8

B)

Lets number the cards be from 0 to 9

by the fifth shuffle the entire deck has exactly reversed its order.

Hence 5 more in shuffles will bring the cards in to its original position.

Number of perfect in shuffles =   10

Shuffle 0 0 1 2 3 4 5 6 7 8 9 Shuffle 1 5 0 6 1 7 2 8 3 9 4 Shuffle 2 2 5 8 0 3 6 9 1 4 7 Shuffle 3 6 2 9 5 1 8 4 0 7 3 Shuffle 4 8 6 4 2 0 9 7 5 3 1 Shuffle 5 9 8 7 6 5 4 3 2 1 0

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.