Generalizations of the Feline and Texas Chainsaw Josephus Problems
Abstract: We define and study the Extended Feline Josephus Game, a game in which n players, each with &#8467; lives, stand in a circle. The game proceeds by alternating between hitting k consecutive players—each of whom will consequently lose a life—and skipping s consecutive players. This cycle continues until every player except one loses all of their lives. Given the nonnegative integer parameters n, k, s and &#8467;, the goal of the game is to identify the surviving player. In this paper, we show how the defining parameters n, k, s, and &#8467; affect the survivor of games with specific constraints on those parameters and our main results provide new closed formulas to determine the survivor of these Extended Feline Josephus Games. Moreover, for cases where these formulas do not apply, we provide recursive formulas for reducing the initial game to other games with smaller parameter values. For the interested reader, we present a variety of directions for future work in this area, including an extension which considers players lying on a general graph, rather than on a circle.
Cite this paper: Ariyibi, D. , Chang, K. and Harris, P. (2019) Generalizations of the Feline and Texas Chainsaw Josephus Problems. Open Journal of Discrete Mathematics, 9, 144-158. doi: 10.4236/ojdm.2019.94011.
References

[1]   Sullivan, S. and Insko, E. (2018) A Variant on the Feline Josephus Problem. arXiv preprint arXiv:1803.11340.

[2]   Lloyd, E.L. (1983) An O(n log m) Algorithm for the Josephus Problem. Journal of Algorithms, 4, 262-270.
https://doi.org/10.1016/0196-6774(83)90025-1

[3]   Theriault, N. (2000) Generalizations of the Josephus Problem. Utilitas Mathematica, 58, 161-174.

[4]   Halbeisen, L. and Hungerbühler, N. (1997) The Josephus Problem. Journal de theorie des nombres de Bordeaux, 9, 303-318.
https://doi.org/10.5802/jtnb.204

[5]   Shams-Baragh, A. (2002) Formulating the Extended Josephus Problem. National Computer Conference, December 2002, Mashhad, 1-5.

[6]   Uchiyama, S. (2003) On the Generalized Josephus Problem. Tsukuba Journal of Mathematics, 27, 319-339.
https://doi.org/10.21099/tkbjm/1496164652

[7]   Ruskey, F. and Williams, A. (2012) The Feline Josephus Problem. Theory of Computing Systems, 50, 20-34.
https://doi.org/10.1007/s00224-011-9343-6

[8]   Park, J.-W. and Teixeira, R. (2018) Serial Execution Josephus Problem. The Korean Journal of Mathematics, 26, 1-7.

[9]   Josephus, F. (2018) The Wars of the Jews or History of the Destruction of Jerusalem. BoD-Books on Demand.

[10]   Sullivan, S. and Beatty, T. (2012) Structured Shuffles and the Josephus Problem. Open Journal of Discrete Mathematics, 2, 138-141.
https://doi.org/10.4236/ojdm.2012.24027

[11]   Sharma, S., Tripathi, R., Bagai, S., Saini, R. and Sharma, N. (2015) Extension of the Josephus Problem with Varying Elimination Steps. The Delhi University Journal of Undergraduate Research and Innovation, 1, 211-218.

[12]   Shang, Y.L. (2017) Consensus in Averager-Copier-Voter Networks of Moving Dynamical Agents. Chaos, 27, 023116.
https://doi.org/10.1063/1.4976959

Top