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.
Share and Cite:
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.
Conflicts of Interest
The authors declare no conflicts of interest.
References
|
[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
|