Structured Shuffles and the Josephus Problem

Abstract

The Australian Shuffle consists of placing a deck of cards onto a table according to this rule: put the top card on the table, the next card on the bottom of the deck, and repeat until all the cards have been placed on the table. A natural question is “Where was the very last card placed located in the original deck?” Card trick magicians have known empirically for years that the fortieth card from the top of a standard fifty-two card deck is the final card placed by this shuffle. The moniker “Australian” comes from putting every other card “Down Under”. We develop a formula for the general case of N cards, and then extend that generalization further to cases involving the discard of k cards before or after putting one on the bottom of the deck. Finally, we discuss the connection of the Australian Shuffle and its generalizations to the famous Josephus problem.