Structured Shuffles and the Josephus Problem

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.

KEYWORDS

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

S. Sullivan and T. Beatty, "Structured Shuffles and the Josephus Problem," Open Journal of Discrete Mathematics, Vol. 2 No. 4, 2012, pp. 138-141. doi: 10.4236/ojdm.2012.24027.

 [1] R. L. Graham, D. E. Knuth and O. Patashnik, “Concrete Mathematics: A Foundation for Computer Science,” Addison-Wesley Publishing Company, Boston, 1989. [2] F. Josephus and B. Radice, “The Jewish War,” Revised Edition, Penguin Books, New York 1985. [3] A. Shams-Baragh, “Formulation of the Extended Josephus Problem,” National Computer Conference 2002, Mashhad, December 2002. [4] M. Lerma, “Josephus Problem,” Northwestern University, Evanston, 2004. [5] T. Yamauchi, T. Inoue and S. Tatsumi, “Josephus Problem under Various Moduli,” Kwansei Gakuin University, Nishinomiya, 2009. [6] L. Casburn and T. Phan, “The Orthogonal Josephus Problem,” Journal of the Summer Undergraduate Mathematical Science Research Institute, 2001. [7] A. M. Odlyzko and H. S. Wilf, “Functional Iteration and the Josephus Problem,” Glasgow Mathematical Journal, Vol. 33, No. 2, 1991, pp. 235-240. doi:10.1017/S0017089500008272 [8] F. Ruskey and A. Williams, “The Feline Josephus Problem,” Theory of Computing Systems, Vol. 50, No. 1, 2012, pp. 20-34. doi:10.1007/s00224-011-9343-6