Abstract
In the classic Josephus problem, elements 1,2,…,n are placed in order around a circle and a skip value k is chosen. The problem proceeds in n rounds, where each round consists of traveling around the circle from the current position, and selecting the kth remaining element to be eliminated from the circle. After n rounds, every element is eliminated. Special attention is given to the last surviving element, denote it by j. We generalize this popular problem by introducing a uniform number of lives ℓ, so that elements are not eliminated until they have been selected for the ℓth time. We prove two main results: 1) When n and k are fixed, then j is constant for all values of ℓ larger than the nth Fibonacci number. In other words, the last surviving element stabilizes with respect to increasing the number of lives. 2) When n and j are fixed, then there exists a value of k that allows j to be the last survivor simultaneously for all values of ℓ. In other words, certain skip values ensure that a given position is the last survivor, regardless of the number of lives. For the first result we give an algorithm for determining j (and the entire sequence of selections) that uses O(n 2) arithmetic operations.
“un gatto ha sette vite”
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Rouse Ball, W.W., Coxeter, H.S.M.: Mathematical Recreations and Essays. Dover, New York (1987)
Biggs, N.L.: The roots of combinatorics. Hist. Math. 6(2), 109–136 (1979)
Cardano, G.: Practica Arithmetice et Mensurandi Singularis (1539)
Dowdy, J., Mays, M.E.: Josephus permutations. J. Comb. Math. Comb. Comput. 6, 125–130 (1989)
Gardner, M.: Mathematical Puzzles of Sam Loyd, vol. 2. Dover, New York (1960)
Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics. Addison-Wesley, Reading (1994)
Halbeisen, L., Hungerbühler, N.: The Josephus problem. J. Théor. Nr. Bordx. 9, 303–318 (1997)
Herstein, I.N., Kaplansky, I.: Matters Mathematical. Harper & Row, New York (1974)
Jakobczyk, F.: On the generalized Josephus problem. Glasg. Math. J. 14, 168–173 (1973)
Josephus, T.F.: The Jewish War. 75 (1737), transl. by William Whiston. ISBN 0-14-044420-3
Lloyd, E.L.: An o(nlog m) algorithm for the Josephus problem. J. Algorithms 4(3), 262–270 (1983)
Odlyzko, A.M., Wilf, H.S.: Functional iteration and the Josephus problem. Glasg. Math. J. 33(2), 235–240 (1991)
Robinson, W.J.: The Josephus problem. Math. Gaz. 4, 47–52 (1960)
Ruskey, F., Williams, A.: The feline Josephus problem. In: Boldi, P., Gargano, L. (eds.) FUN 2010. LNCS, vol. 6099, pp. 343–354. Springer, Berlin (2010)
Sloane, N.J.A.: The on-line encyclopedia of integer sequences. http://www.research.att.com/~njas/sequences/A003418
Thérialut, N.: Generalizations of the Josephus problem. Util. Math. 58, 161–173 (2000)
Woodhouse, D.: The extended Josephus problem. Rev. Mat. Hisp.-Am. 4(33), 207–218 (1973)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ruskey, F., Williams, A. The Feline Josephus Problem. Theory Comput Syst 50, 20–34 (2012). https://doi.org/10.1007/s00224-011-9343-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-011-9343-6