Blog Post 6

\(1\) \(\underline{\text{Card Shuffling}}\)

In discrete mathematics, a riffle shuffle is a shuffling of cards in which the top half is placed in one hand and the other half lies in the opposite hand. The cards are then alternatively interlaced with one another. There are two different types of riffle shuffles that will be the topic of discussion: the out-shuffle and the in-shuffle. An out-shuffle keeps the top card on top and the bottom card on bottom. When the top card is, instead, placed in the second position we have an in-shuffle.

Consider a typical \(52\) card deck. If we name and order the cards \(0,1,2,3,4...\), then after an out-shuffle we receive the order \(0,26,1,27,2,28...\). After an in-shuffle, the cards appear as \(26,0,27,1,28,2...\). Note that the first card is in the \(0\) position. To return to the original order, we must make \(8\) out-shuffles. Interestingly enough, however, it takes \(52\) in-shuffles.

In general, if we wish to know the position that the card currently at position \(x\) will be sent to, we can follow a formula based on the concept of modular arithmetic. For out-shuffles we use \(2x \pmod{n-1}\) (with the exception that \(51\) lies in position \(51\)) and for in-shuffles we use \(2x+1 \pmod{n+1}\), where \(n\) is the number of cards in the deck and \(x\) is the position.

As an example with a \(12\) card deck, the card in position \(2\) in an out-shuffle would be moved to position \(4\) because we would take \(4 \pmod{11}\). Likewise, the card in position \(4\) would be moved to position \(8\) because we would take \(8 \pmod{11}\). If we continue this process, we can write the results as such:

\((0)\)

\((1 \hspace{2mm} 2 \hspace{2mm} 4 \hspace{2mm} 8 \hspace{2mm} 5 \hspace{2mm} 10 \hspace{2mm} 9 \hspace{2mm} 7 \hspace{2mm} 3 \hspace{2mm} 6)\)

\((11)\)

Each number that follows describes what position that card will be moved to and it ends when the cycle would repeat. For whatever size deck, every card needs to be represented. If one value has not made an appearance in the previous sets, you must start a new set. Notice that the first card, \(0\), and the last card \(11\) do not move. This should be expected as this is what characterizes an out-shuffle.

Through this, you can also find the number of out-shuffles it will take to return to the original order. Notice that there are three sets of patterns above with deck size \(12\). In the first, there is one value, in the second there are ten values, and in the last there is one value. The least common multiple of the sizes/lengths of each set will describe the number of shuffles needed. In this case, we have lcm(\(1,10,1\))=\(10\). So it takes ten out-shuffles to return a deck of size \(12\) back to the original order.

\(2\) \(\underline{\text{Suggested Exam Problem}}\)

How many out-shuffles does it take to return a deck of size \(20\) to its original order?

## Share on Social Media