Generalizations of the Feline and Texas Chainsaw Josephus Problems ()

David Ariyibi^{*}, Kevin Chang^{}, Pamela E. Harris^{}

Department of Mathematics and Statistics, Williams College, Williamstown, MA, USA.

**DOI: **10.4236/ojdm.2019.94011
PDF
HTML XML
460
Downloads
1,395
Views
Citations

Department of Mathematics and Statistics, Williams College, Williamstown, MA, USA.

We define and study the Extended Feline Josephus Game, a game in which *n* players, each with* ℓ* 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 *ℓ*, the goal of the game is to identify the surviving player. In this paper, we show how the defining parameters *n*, *k*, *s*, and *ℓ *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.

Share and Cite:

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.

1. Introduction

The origins of the Josephus problem and its corresponding game can be traced back to 1st century AD. Named after Jewish historian and military commander, Flavius Josephus, the game is based on his accounts of the Siege of Jotapata. Long into the siege, Josephus and 40 of his soldiers were cornered into a cave surrounded by Roman soldiers. Rather than face capture at the hands of the enemy, Josephus convinced his men to choose suicide by means of a game of “chance”. He and his men would stand in a circle. Then starting at a particular person, each would kill the neighbor to his left. Allegedly, predicting the outcome of the game, Josephus and one other man remained until the final round of the game, at which point the two decided to surrender to the Roman forces [1] [2] .

This historical account led mathematicians to define and study variations of the counting-out game, named the Josephus Game, which is described as follows: Given an ordered set of n players standing in a circle, the game begins by determining an initial player from which we alternate between skipping and killing a player in a clockwise direction. The Josephus Problem is to identify the position of the surviving player in this game. Although the problem has been solved in various ways [3] [4] [5] [6] , many variations and generalizations of the game have since been introduced.

Two of these generalizations are the Generalized Josephus Game, a variant that allows the number of consecutively skipped players to equal some fixed positive integer [2] [4] [5] [7] , and the Feline Josephus Game [2] [8] , which adds the rule that each player now has a positive integer number of lives. In the Feline Josephus Game, each time a player is hit; their number of lives decreases by 1. If a player’s number of lives reaches 0, that player is removed from the game, and the game continues until all but one player remains. Other variants of the game include the Texas Chainsaw and Feline Texas Chainsaw Josephus Games. In these variants, the rules of the original Josephus Game still apply; however the number of players killed in a row varies instead of the number of players skipped. As the name implies, the latter includes the varying lives aspect from the Feline variant [2] [9] .

In this work, we introduce the Extended Feline Josephus Game with the goal of identifying the survivor when the number of players, consecutive hits, consecutive skips, and initial lives, are greater than or equal to 1. We remark that this new variant recovers the Feline variant when setting the hit parameter to 1, the Feline Texas Chainsaw variant when setting the skip parameter to 1, the Texas Chainsaw variant when setting both the skip and lives parameters to 1, and the original Josephus Game when setting the hit, skip, and lives parameters to 1. Thus the Extended Feline Josephus Game we present provides a generalization to much of the previous work in this area.

The main results in this paper determine closed formulas and recurrence relations for the survivor of an Extended Feline Josephus Game when the defining parameters satisfy certain relations. In what follows, we let $J{\left(n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\right)}_{K\mathrm{/}S}$ denote the surviving player of the Extended Josephus Game given n people, k hits, s skips, ℓ lives, and where the subscript denotes whether the game begins by hitting or skipping first. If both of the subscripts K and S are present, this means that the result works for each of these cases. Lastly, we remark that our games always label players 0 through n and they begin at player 0.

Our first main result presents the case where $\mathcal{l}=1$ and provides closed formulas to determine the survivor of the games considered.

Main Theorem 1. Let $n,k,s\in \mathbb{N}:=\left\{1,2,3,\cdots \right\}$ and $\mathcal{l}=1$.

1) If $n=a{\left(\frac{k+s}{s}\right)}^{b}+km$ and $s\mathrm{|}k$, the

$J{\left(n,k,s,1\right)}_{S}=(\begin{array}{ll}\left(k+s\mathrm{mod}n\right)+\left(s-1\mathrm{mod}\left(n-k\right)\right)\hfill & \text{if}\text{\hspace{0.17em}}\text{\hspace{0.05em}}k<n<k+s\hfill \\ \left(k+s\right)m+s-1\mathrm{mod}n\hfill & \text{if}\text{\hspace{0.17em}}\text{\hspace{0.05em}}n\le k\text{\hspace{0.05em}}\text{\hspace{0.17em}}\text{or}\text{\hspace{0.17em}}\text{\hspace{0.05em}}n\ge k+s.\hfill \end{array}$

2) If $n=a{\left(k+s\right)}^{b}+km$ and $\left(k+s\right)m<n\le k\left(m+1\right)$, then

$J{\left(n,k,s,1\right)}_{S}=\left(k+s\right)m+s-1\mathrm{mod}n.$

Our second main result considers the case where $\mathcal{l}\ge 1$ and provides recursive formulas to determine the survivor of the games considered.

Main Theorem 2. Let $n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\in \mathbb{N}$.

1) If $\mathrm{gcd}\left(n,k+s\right)=1$ and $\mathcal{l}>k$, such that ${\mathcal{l}}^{\prime}\equiv \mathcal{l}\mathrm{mod}k$ and ${\mathcal{l}}^{\prime}>0$, then

$J{\left(n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\right)}_{K\mathrm{/}S}=J{\left(n\mathrm{,}k\mathrm{,}s\mathrm{,}{\mathcal{l}}^{\prime}\right)}_{K\mathrm{/}S}\mathrm{.}$

2) If $n\mathrm{|}s$ and $k\mathrm{|}n$, then

$J{\left(n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\right)}_{K\mathrm{/}S}=J{\left(n\mathrm{,}k\mathrm{,}s\mathrm{,1}\right)}_{K\mathrm{/}S}\mathrm{.}$

3) If $n\mathrm{|}\left(k+s\right)$ and $\lceil \frac{k}{n}\rceil \mathrm{|}\mathcal{l}$ where $a=k\mathrm{mod}n$, then

$J{\left(n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\right)}_{S}=J{\left(s\mathrm{mod}n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}-\frac{\left(k-a\right)\mathcal{l}}{n\lceil \frac{k}{n}\rceil}\right)}_{S}\mathrm{.}$

4) If $n=a\left(k+s\right)$, where $a\in \mathbb{N}$, then

$J{\left(n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\right)}_{S}=\left(k+s\right)\lfloor \frac{J{\left(as\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\right)}_{S}}{s}\rfloor +\left(J{\left(as\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\right)}_{S}\mathrm{mod}s\right)\mathrm{.}$

5) Let $a=\mathrm{gcd}\left(n,k,s\right)$, then

$J{\left(n,k,s,\mathcal{l}\right)}_{K/S}=a\cdot J{\left(\frac{n}{a},\frac{k}{a},\frac{s}{a},\mathcal{l}\right)}_{K/S}+a-1.$

The paper is organized as follows. In Section 2, we give the necessary background and notation to concretely define the Extended Feline Josephus Game. In Section 3, we consider explicit solutions for games where the lives parameter is 1, and present a proof of Main Theorem 1. In Section 4, we consider closed formulas to games where the lives parameter varies. In Section 5, we consider recursive solutions for reducing games to other games with smaller defining parameters thereby establishing Main Theorem 2. Lastly, Section 6 communicates ideas and areas for future work.

2. Background

To understand the Extended Feline Josephus Game, we begin by defining the variables and notations used to describe the layout for any particular game. We label the n players 0 through $n-1$. As stated before, each player has $\mathcal{l}$ lives at the beginning of the game. Each time a player is hit, their number of lives decreases by 1, and a player is removed from the game once their number of lives reaches 0. In these games, k consecutive players are hit in a row, and then s consecutive players are skipped. The last variable, p, denotes the player whom the game begins with. Whether the game starts by skipping or by killing players first is referred to as either a skip-first or kill-first game, and this is denoted through the use of subscripts S or K, respectively. Thus for a specific game ${\left(n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\mathrm{,}p\right)}_{K\mathrm{/}S}$, the surviving player is denoted as $J{\left(n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\mathrm{,}p\right)}_{K\mathrm{/}S}$.

We also define a round as one set of k hits and s skips (or vice versa) and a cycle as a traversal through all (remaining) players in a game regardless of whether the action on any specific player is a hit or a skip.

We illustrate these definitions through the following example^{1}.

Example 1. We want to determine the survivor of a kill-first game where $n=10$, $k=3$, $s=3$, $\mathcal{l}=2$, and $p=0$. We run through the game in Figure 1, by denoting a hit with an X and a skip with an O. Whenever a player has lost all of their lives we remove them from the game, in which case they receive neither an X nor an O for the remaining rounds. This allows us to determine that $J{\left(10,3,3,2,0\right)}_{K}=1$.

The following remark and result demonstrate that any game can be translated into another with a different starting player or to a kill-first/skip-first order while preserving the final position of the survivor.

Remark 1. Notice that $J{\left(n,k,s,\mathcal{l},p\right)}_{K/S}=\left(J{\left(n,k,s,\mathcal{l},0\right)}_{K/S}+p\right)\mathrm{mod}n$ since the results of any game starting at player p can be shifted back by the same amount to recover the results starting at player 0.

Lemma 1. If ${p}^{\prime}=\left(p+s\right)\mathrm{mod}n$, then $J{\left(n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\mathrm{,}p\right)}_{S}=J{\left(n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\mathrm{,}{p}^{\prime}\right)}_{K}$.

Proof. Let A be a skip-first game where the survivor is $J{\left(n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\mathrm{,}p\right)}_{S}$, and let B be a kill-first game where the survivor is $J{\left(n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\mathrm{,}{p}^{\prime}\right)}_{K}$. Game A begins at player p and initially skips s players. Game A now proceeds to hit or kill k people starting at the player in position $\left(p+s\right)\mathrm{mod}n$. Since the number of lives of all the players have not changed after the initial skips, at this point in the game, the games A and B are equivalent and will have the same surviving player. $\square $

Figure 1. Game ${\left(\mathrm{10,3,3,2,0}\right)}_{K}$ progresses from left to right, beginning at player 0. In this table “X” represents a hit while “O” represents a skip. The game consists of 6 rounds, 7 cycles, and $J{\left(10,3,3,2,0\right)}_{K}=1$.

As a result of Remark 1, all following results utilize games beginning at player 0. Therefore, for the sake of simplicity, from now on we denote the survivor of the game as $J{\left(n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\right)}_{K\mathrm{/}S}$, eliminating the need for the p parameter. Also, the use of kill-first or skip-first games in describing specific results depending on which is more intuitive to understand.

3. Games Where Players Have One Life

We begin our analysis by establishing results for the Extended Feline Josephus Game in cases where $\mathcal{l}=1$. We will use these results to extend to more general cases where $\mathcal{l}\ge 1$. The following result provides an initial identification of the survivor of a game under these parameters.

Proposition 1. If $n\le k$, then $J{\left(n,k,s,1\right)}_{K}=n-1$.

Proof. Since $n\le k$, the life of every player is decreased by 1 in the first round. Since $\mathcal{l}=1$, each player’s life is decreased to 0, and each player is removed from the game. Therefore, the survivor is the last player to be removed, player $n-1$. $\square $

Note that if the players only have one life, the more interesting games are where there are less players killed at a time than there are players total. The following results consider such cases.

Proposition 2. If $n=k+s$ and $k\ge s$, then $J{\left(k+s,k,s,1\right)}_{K}=n-1$.

Proof. Consider a kill-first game where $n=k+s$. At the end of the first round, players 0 through $k-1$ are eliminated, and players k through $n-1$ are skipped. A total of s players remain. The second round begins with the player k. Since $k\ge s$, the number of kills is greater than the number of players remaining. Therefore, by Proposition 1, the last player is the survivor, player $n-1$. $\square $

Proposition 3. If $n\ne k+s$ and $\lceil \frac{n}{2}\rceil \le k<n$, such that $s\equiv a\mathrm{mod}\left(n-k\right)$, then

$J{\left(n\mathrm{,}k\mathrm{,}s\mathrm{,1}\right)}_{K}=k+a-1\mathrm{mod}n\mathrm{.}$

Proof. Consider the case where $n\ne k+s$. In the first round, players 0 through $k-1$ are removed. Players k through $n-1$ remain, with a total of $n-k$ players left. We then shift the positions of each player back by k, such that the player at position k is now at position 0, and generally the player at position x is now at position $x-k$. Therefore, the position of the last player skipped in the round, of the remaining players, is given by $a-1$ where $s\equiv a\mathrm{mod}\left(n-k\right)$. We then shift the players positions forward by k to return to the original game layout. Thus, at the end of the first round, the last player skipped is at position $k+a-1\mathrm{mod}n$. Since $\lceil \frac{n}{2}\rceil \le k<n$, the number of remaining players is strictly less than half of the initial number of players at the beginning of the game and thus less than or equal to k. By Proposition 1, the second round proceeds by removing all the remaining players starting at the player $k+a\mathrm{mod}n$ and ending at position $k+a-1\mathrm{mod}n$. Therefore, the survivor is player $k+a-1\mathrm{mod}n$. $\square $

Having established the prior results, we now use a proof technique similar to that of Sullivan, Beatty, and Insko’s for the Texas Chainsaw Josephus Problem [2] [10] to establish a proof for Main Theorem 1 Part 1, which we restate for ease of reference.

Theorem 3. If $n=a{\left(\frac{k+s}{s}\right)}^{b}+km$ and $s\mathrm{|}k$, then

$J{\left(n,k,s,1\right)}_{S}=(\begin{array}{ll}\left(k+s\mathrm{mod}n\right)+\left(s-1\mathrm{mod}\left(n-k\right)\right)\hfill & \text{if}\text{\hspace{0.17em}}\text{\hspace{0.05em}}k<n<k+s\hfill \\ \left(k+s\right)m+s-1\mathrm{mod}n\hfill & \text{if}\text{\hspace{0.17em}}\text{\hspace{0.05em}}n\le k\text{\hspace{0.05em}}\text{\hspace{0.17em}}\text{or}\text{\hspace{0.17em}}\text{\hspace{0.05em}}n\ge k+s\hfill \end{array}$

where $n\equiv a\mathrm{mod}k$, b is as large as possible, $m\in {\mathbb{Z}}_{\ge 0}$, and $\left(k+s\right)\mathrm{|}a{\left(\frac{k+s}{s}\right)}^{b}$ if $k+s\le a{\left(\frac{k+s}{s}\right)}^{b}$.

Proof. The proof consists of three cases based on the value of n. We first consider case 1 where $n\le k$. Note that $a\equiv n$, so $b=0$ and $m=0$. Thus by Proposition 1 and Lemma 1, the survivor is player $\left(s-1\right)\mathrm{mod}n$.

Next, we consider case 2 where $n>k$ and $n=a{\left(\frac{k+s}{s}\right)}^{b}$. Therefore, $b>0$ and $m=0$. If $n=k+s$, then by Proposition 2 and Lemma 1, the survivor is player $\left(s-1\right)\mathrm{mod}n$. If $n<k+s$, then since $s\mathrm{|}k$, we know that $k\ge s$, $n<2k$, and thus $\lceil \frac{n}{2}\rceil \le k$. Therefore by Proposition 3 and Lemma 1, the survivor is player $\left(k+s\mathrm{mod}n\right)+\left(s-1\mathrm{mod}\left(n-k\right)\right)$. Lastly, if $n>k+s$, since $\left(k+s\right)\mathrm{|}n$, we know that there are exactly $\frac{n}{k+s}$ rounds in a cycle through all of the players. Since in each round, we skip s out of the $k+s$ players in the round, it follows that at the end of the first cycle, there are

$s\left(\frac{n}{k+s}\right)=a{\left(\frac{k+s}{s}\right)}^{b}\left(\frac{s}{k+s}\right)=a{\left(\frac{k+s}{s}\right)}^{b-1}$

players remaining, the next round starting at player 0. Similarly, after a total of b cycles, there are only a players remaining since b is reduced to 0. Note that in each cycle, players 0 through $s-1$ are skipped and are thus part of the remaining a players. Since $a\le k$, and the next round starts at player 0, this case reduces back to case 1. Thus, the survivor is player $\left(s-1\right)\mathrm{mod}n$.

Finally, we consider case 3 where $n>k$ and $n=a{\left(\frac{k+s}{s}\right)}^{b}+km$. Thus $b\ge 0$ and $m>0$. We use induction to establish the result for $n\ge k$. The base cases are shown in cases 1 and 2. In the general case, after the first round, players 0 through $s-1$ are skipped and players s through $k+s-1$ are killed. Note that players $k+s$ through $k+2s-1$ are the next to be skipped, so we shift all of the currently living players’ positions back by $k+s$. Thus player $k+s$ is now at position 0 and player 0 is now at position $n-k-s$. Note that there are now $n-k$ players. Since $n-k\equiv a\mathrm{mod}k$, we have

$n-k=a{\left(\frac{k+s}{s}\right)}^{b}+km-k=a{\left(\frac{k+s}{s}\right)}^{b}+k\left(m-1\right)$

keeping b and m fixed. By induction,

$J{\left(n-k\mathrm{,}k\mathrm{,}s\mathrm{,1}\right)}_{S}=\left(k+s\right)\left(m-1\right)+s-1\mathrm{mod}n$.

By shifting the positions forward to their original indices, we get

$J{\left(n\mathrm{,}k\mathrm{,}s\mathrm{,1}\right)}_{S}=\left(k+s\right)m+s-1\mathrm{mod}n$,

the desired solution. Note that this process of shifting positions occurs m times, reducing m to 0 and reducing back to case 2 beginning at player $\left(k+s\right)m\mathrm{mod}n$. $\square $

We illustrate Theorem 3 with the following.

Example 2. We want to know the survivor of a skip-first game where $n=485$, $k=12$, $s=3$, and $\mathcal{l}=1$. Since $n>k+s$, we first calculate that $485\equiv a\mathrm{mod}12$, which implies that $a=5$. The largest value of b such that $485-5{\left(\frac{12+3}{3}\right)}^{b}\ge 0$ is 2. It follows that $m=\frac{485-5{\left(5\right)}^{2}}{12}=30$. Thus

$J\left(485,12,3,1\right)=\left(12+3\right)30+3-1=452.$

while Theorem 3 places strong restrictions on the parameters n, k, and s, the following results introduces a solution which loosens some of these requirements and establishes Main Theorem 1 Part 2.

Theorem 4. If $n=a{\left(k+s\right)}^{b}+km$ and $\left(k+s\right)m<n\le k\left(m+1\right)$, then

$J{\left(n\mathrm{,}k\mathrm{,}s\mathrm{,1}\right)}_{S}=\left(k+s\right)m+s-1\mathrm{mod}n$

where $n\equiv a\mathrm{mod}k$, b is as large as possible, and $m\in {\mathbb{Z}}_{\ge 0}$.

Proof. Similar to Theorem 3, the proof consists of 3 cases based on the value of n. We first consider case 1 where $n\le k$. This parallels case 1 from Theorem 3. Thus the survivor is player $\left(s-1\right)\mathrm{mod}n$. Next, we consider case 2 where $n=a{\left(k+s\right)}^{b}$. Thus $b\ge 0$ and $m=0$. Note that $\left(k+s\right)m<n\le k\left(m+1\right)$ implies that $n\le k$, so this case reduces back to case 1 beginning at player 0. Thus the survivor is player $\left(s-1\right)\mathrm{mod}n$. For the last case, we consider where $n=a{\left(k+s\right)}^{b}+km$, with $m\ge 1$. The proof is similar to that of case 3 in Theorem 3, so we omit it. $\square $

4. Games Where Players Have Multiple Lives

In order to find the surviving player in games where $\mathcal{l}\ge 1$, we first consider closed formulas of special cases with respect to n.

Proposition 4. If $n\mathcal{l}\le k$, then $J{\left(n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\right)}_{K}=n-1$.

Proof. Since $n\mathcal{l}\le k$, the lives of every player is decreased to 0 in the first round, removing every player. The survivor is player $n-1$, the last to be removed. $\square $

Similarly to Proposition 1, the more interesting cases are where $n\mathcal{l}>k$, which the following formulas explore. The results are derived from attempts to find solutions to the cases where $n=k$ and $n=s$, respectively.

Proposition 5. If $n\mathrm{|}k$, then $J{\left(n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\right)}_{S}=s\lceil \frac{n\mathcal{l}}{k}\rceil -1\mathrm{mod}n$.

Proof. In the first round, since $n\mathrm{|}k$, all n players have lost $\frac{k}{n}$ lives. The round ends on player $k+s-1\mathrm{mod}n$, which simplifies to $s-1\mathrm{mod}n$. The game continues but now starting at player $s\mathrm{mod}n$. Thus with each round i, the player ending the round is player $si-1\mathrm{mod}n$ and all players have lost a total of $\frac{k}{n}i$ lives. Therefore after round $\frac{\mathcal{l}}{\left(\frac{k}{n}\right)}$, all players have lost their lives, and the last player skipped in the previous round is player $s\lceil \frac{n\mathcal{l}}{k}\rceil -1\mathrm{mod}n$, the survivor. $\square $

Proposition 6. If $n\mathrm{|}s$ and $k\ge n$, then

$J{\left(n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\right)}_{K\mathrm{/}S}=(\begin{array}{ll}\left(s\mathrm{mod}\left(n\mathcal{l}-a\right)+a-1\right)\mathrm{mod}n\hfill & \text{if}\text{\hspace{0.17em}}\text{\hspace{0.05em}}n\left(\mathcal{l}-1\right)<a<n\mathcal{l}\hfill \\ n-1\hfill & \text{if}\text{\hspace{0.17em}}\text{\hspace{0.05em}}a\le n\left(\mathcal{l}-1\right)\text{\hspace{0.05em}}\text{\hspace{0.17em}}\text{or}\text{\hspace{0.17em}}\text{\hspace{0.05em}}a\mathrm{=}n\mathcal{l}\hfill \end{array}$

where $a=\lfloor \frac{n\mathcal{l}}{k}\rfloor k$.

Proof. Since $n\mathrm{|}s$, by Lemma 1, the surviving player of a skip-first game of this form is the same as its kill-first counterpart. It suffices to only consider the skip-first game.

We first look at the case where $a=n\mathcal{l}$. Since $a=n\mathcal{l}$, we know that $k\mathrm{|}n\mathcal{l}$ and that $\frac{n\mathcal{l}}{k}$ is an integer. It follows that $\frac{n\mathcal{l}}{k}$ is the total number rounds in the game, and since s is a multiple of n, every player is hit in order and thus also removed in order in the last round. Therefore, the survivor is player $n-1$.

For all other cases, it must be that $k\overline{)|}n\mathcal{l}$. Note that $\frac{n\mathcal{l}}{k}$ is thus not an integer, so $\lfloor \frac{n\mathcal{l}}{k}\rfloor $ is the number of rounds needed for at least one but not all players to be removed. It follows that $\lfloor \frac{n\mathcal{l}}{k}\rfloor k$ is the total number of lives lost after those rounds. Since $n\mathrm{|}s$, all n players are initially skipped in the first round before the k hits. At the end of the round, since $k\ge n$, all players have lost at least 1 life. The new round starts on player $k+s\mathrm{mod}n$ which simplifies to $k\mathrm{mod}n$. Thus, players are being hit in order. Since this pattern can only continue while there are all n players, after $\lfloor \frac{n\mathcal{l}}{k}\rfloor $ rounds, the pattern ends on the player at position $\lfloor \frac{n\mathcal{l}}{k}\rfloor k-1\mathrm{mod}n$, denoted as $a-1\mathrm{mod}n$. Note that at this point in the game, there are $nl-a$ players left, which we know is a nonzero amount. Since a lives have also been removed at this point, we know that there are $n\mathcal{l}-a<k$ players remaining. Thus, by Proposition 4, the player at the end of the next round of skips is the survivor, player $\left(s\mathrm{mod}\left(n\mathcal{l}-a\right)+a-1\right)\mathrm{mod}n$.

However, if $a\le n\left(\mathcal{l}-1\right)$, it must be the case that after $\lfloor \frac{n\mathcal{l}}{k}\rfloor $ rounds, there are still at least n lives, so all players must still be in the game with at least 1 life each. Since after $\lfloor \frac{n\mathcal{l}}{k}\rfloor $ rounds, it must be that there are $nl-a$ players remaining. it must be the case that $k>n\mathcal{l}$ thus $\lfloor \frac{n\mathcal{l}}{k}\rfloor =0$ and $a=0\le n\left(\mathcal{l}-1\right)$. Since $k>n\mathcal{l}$, by Proposition 4, the survivor is at position $n-1$. $\square $

To better illustrate the proof of Proposition 6, we provide the following.

Example 3. We want to know the survivor of a skip-first game where $n=5$, $k=6$, $s=5$, and $\mathcal{l}=3$. We run the game in Figure 2.

Using Proposition 6, we calculate that $n\mathcal{l}=15$, $n\left(\mathcal{l}-1\right)=10$, and $a=\lfloor \frac{5\times 3}{6}\rfloor 6=12$. Note that after $\lfloor \frac{5\times 3}{6}\rfloor =2$ rounds, the first two players are removed, the next round starting on player 2. Since $10<a<15$, then

$J{\left(5,6,5,3\right)}_{S}=\left(5\mathrm{mod}\left(15-12\right)+12-1\right)\mathrm{mod}5=3.$

5. Reducing Parameter Values of Games

If the problem does not fall into one of the cases where there is a known closed formula for identifying the survivor, the best alternative is to reduce the amount of time it takes to identify the survivor iteratively. We do this by reducing the parameters involved with a particular game.

Note that for certain games where parameters n, k, and s are fixed, we see a repeating sequence of numbers for the survivor as ℓ increases. In order to more clearly illustrate, we define an step as any act occurring in the game, whether it be a skip, hit, or kill. Additionally we define a reset as a point in a game where after a number of rounds, the next round begins at the initial player, and every player in the game has had their lives decreased by the same amount. The game has effectively been simplified to a game starting at the same player with the same layout, only with fewer lives.

Example 4. Given a kill-first game where $n=5$, $k=2$, $s=2$, and ℓ is sufficiently large, resets happen after the lives of all players are decreased by 2. Specifically, this game resets after 5 rounds (or 4 cycles). We run the game in Figure 3.

Figure 2. Game ${\left(\mathrm{5,6,5,3}\right)}_{S}$ consists of 2 rounds, 7 cycles, and $J{\left(5,6,5,3\right)}_{S}=3$.

Figure 3. For game ${\left(\mathrm{5,2,2,}\mathcal{l}\right)}_{K}$, if $\mathcal{l}>2$, then $J{\left(5,2,2,\mathcal{l}\right)}_{K}=J{\left(5,2,2,\mathcal{l}-2\right)}_{K}$.

The following results provide insight into what constraints need to be satisfied to reduce the value of ℓ and specify how small the lives parameter can be reduced to while keeping the rest of the game’s parameters fixed. The results that follow establish each part of Main Theorem 2 individually.

Theorem 5. If $\mathrm{gcd}\left(n,k+s\right)=1$ and $\mathcal{l}>k$, such that ${\mathcal{l}}^{\prime}\equiv \mathcal{l}\mathrm{mod}k$ and ${\mathcal{l}}^{\prime}>0$, then

$J{\left(n,k,s,\mathcal{l}\right)}_{K/S}=J{\left(n,k,s,{\mathcal{l}}^{\prime}\right)}_{K/S}.$

Proof. Since $\mathrm{gcd}\left(n,k+s\right)=1$, the number of steps until a reset is $n\left(k+s\right)$. Therefore, there are $k+s$ cycles until a reset. Using ( [2] , Lemma 6), it suffices to show that after $k+s$ cycles, each player has been skipped exactly s times, and thus each player has been hit exactly k times. The next cycle starts with player 0, resetting the game with the new number of lives, $\mathcal{l}-k$. This reset pattern continues while $\mathcal{l}-ik>0$ for $0\le i\le \lfloor \frac{\mathcal{l}}{k}\rfloor $. After this point, another reset is impossible since by ( [2] , Lemma 6), at least one player will be removed during a cycle, thereby changing n. Thus we set ${\mathcal{l}}^{\prime}=\mathcal{l}-\lfloor \frac{\mathcal{l}}{k}\rfloor k$ which simplifies to $\mathcal{l}\mathrm{mod}k$. $\square $

While Theorem 5 reduces ℓ, we are particularly interested in solutions which would reduce ℓ to one, so that we can utilize the results from Section 3. The following result provides such a solution, establishing Part 2 of Main Theorem 2.

Theorem 6. If $n\mathrm{|}s$ and $k\mathrm{|}n$, then $J{\left(n,k,s,\mathcal{l}\right)}_{K/S}=J{\left(n,k,s,1\right)}_{K/S}.$

Proof. Since $n\mathrm{|}s$, by Lemma 1, the surviving player of a skip-first game of this form is the same as its kill-first counterpart. In each round, the skip of s players starts the next round at the same point as where the last hit left off. Thus, the immediate next group of k players get their lives reduced by one. Since $k\mathrm{|}n$, after $\frac{n}{k}$ rounds, the game resets with every player’s life reduced by 1. This continues until the game resets with every player’s life reduced to 1. $\square $

The following results, establishing Parts 3 and 4 of Main Theorem 2, focus on reducing n as opposed to ℓ.

Theorem 7. If $n\mathrm{|}\left(k+s\right)$ and $\lceil \frac{k}{n}\rceil \mathrm{|}\mathcal{l}$, then

$J{\left(n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\right)}_{S}=J{\left(s\mathrm{mod}n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}-\frac{\left(k-a\right)\mathcal{l}}{n\lceil \frac{k}{n}\rceil}\right)}_{S}$

where $a=k\mathrm{mod}n$.

Proof. Since $n\mathrm{|}\left(k+s\right)$, it follows that until a player is removed from the game, each round starts at player 0. For the first round, the skipping ends with player $s-1\mathrm{mod}n$. Then, the next k players are hit, ending on player $n-1$. Note that players 0 through $s-1\mathrm{mod}n$ are hit $\frac{k-a}{n}$ times each, and players s through $n-1$ are hit $\frac{k-a}{n}+1$ times each, which simplifies to $\lceil \frac{k}{n}\rceil $. Thus, after $\frac{\mathcal{l}}{\lceil \frac{k}{n}\rceil}$ rounds, players $s\mathrm{mod}n$ through $n-1$ are removed, leaving players 0 through $s-1$ remaining. The next round starts at player 0. Note that the surviving players have lost $\frac{k-a}{n}\cdot \frac{\mathcal{l}}{\lceil \frac{k}{n}\rceil}$ lives each, and the survivor of the game is now $J{\left(s\mathrm{mod}n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}-\frac{k-a}{n}\cdot \frac{\mathcal{l}}{\lceil \frac{k}{n}\rceil}\right)}_{S}$. $\square $

Example 5. We want to know the survivor of a skip-first game where $n=11$, $k=6$, $s=5$, and $\mathcal{l}=3$. We run the game in Figure 4.

Corollary 1. If $n=k+s$ and $k\ge s$, then

$J{\left(n,k,s,\mathcal{l}\right)}_{S}=(\begin{array}{ll}\left(s\mathrm{mod}\left(s\mathcal{l}-a\right)+a-1\right)\mathrm{mod}s\hfill & \text{if}\text{\hspace{0.17em}}\text{\hspace{0.05em}}s\left(\mathcal{l}-1\right)<a<s\mathcal{l}\hfill \\ s-1\hfill & \text{if}\text{\hspace{0.17em}}\text{\hspace{0.05em}}a\le s\left(\mathcal{l}-1\right)\text{\hspace{0.05em}}\text{\hspace{0.17em}}\text{or}\text{\hspace{0.17em}}\text{\hspace{0.05em}}a=s\mathcal{l}\hfill \end{array}$

where $a=\lfloor \frac{s\mathcal{l}}{k}\rfloor k$.

Proof. Since $n\mathrm{|}\left(k+s\right)$ and $\lceil \frac{k}{n}\rceil \mathrm{|}\mathcal{l}$ trivially, by Theorem 7,

$J{\left(k+s,k,s,\mathcal{l}\right)}_{S}=J{\left(s,k,s,\mathcal{l}\right)}_{S}$.

Note that the layout of the game now has s players. Since $k\ge s$, by Proposition 6, the survivor is the same. $\square $

Example 6. We want to know the survivor of a skip-first game where $n=11$, $k=6$, $s=5$, and $\mathcal{l}=3$. Doing so will require the use of Example 3. We run the game in Figure 5.

Theorem 8. If $n=a\left(k+s\right)$, where $a\in \mathbb{N}$, then

$J{\left(n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\right)}_{S}=\left(k+s\right)\lfloor \frac{J{\left(as\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\right)}_{S}}{s}\rfloor +\left(J{\left(as\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\right)}_{S}\mathrm{mod}s\right)\mathrm{.}$

Proof. Note that in the first round, we skip players 0 through $s-1$ and

Figure 4. Game ${\left(\mathrm{8,13,11,4}\right)}_{S}$ consisting of 3 rounds, 12 cycles, and $J{\left(8,13,11,4\right)}_{S}=J{\left(3,13,11,2\right)}_{S}=1$.

Figure 5. Game ${\left(\mathrm{11,6,5,3}\right)}_{S}$ consists of 7 rounds, 10 cycles, and $J{\left(11,6,5,3\right)}_{S}=J{\left(5,6,5,3\right)}_{S}=3$.

reduce the lives of players s through $k+s-1$ players. The next round begins on player $k+s$. Since $a=\frac{n}{k+s}$, it follows that it takes a rounds to complete a cycle while no players have been removed. Note that after a rounds, the players $i\left(k+s\right)$ through $i\left(k+s\right)+s-1$ where $0\le i<a$ have all been skipped and the players $i\left(k+s\right)+s$ through $\left(i+1\right)\left(k+s\right)-1$ have had their lives decreased by 1. Thus, after ℓ cycles, these players have been removed, leaving as players remaining. Note that this method of removal has segmented the remaining players into groupings of s players distance k apart from another neighboring grouping. Therefore the survivor of the initial game is contained within the players of this now smaller game. Assuming we know the position of the survivor in the smaller game, denoted $J{\left(as\mathrm{,}k\mathrm{,}s\mathrm{,}l\right)}_{S}$, we derive which grouping of players $J\left(as\mathrm{,}k\mathrm{,}s\mathrm{,}l\right)$ belongs to in the initial game by $\left(k+s\right)\lfloor \frac{J\left(as\mathrm{,}k\mathrm{,}s\mathrm{,}l\right)}{s}\rfloor $. We also derive the position for which $J\left(as\mathrm{,}k\mathrm{,}s\mathrm{,}l\right)$ stands within its grouping of players by $J\left(as\mathrm{,}k\mathrm{,}s\mathrm{,}l\right)\mathrm{mod}s$. Thus, the survivor of the initial game is player

$\left(k+s\right)\lfloor \frac{J{\left(as\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\right)}_{S}}{s}\rfloor +\left(J{\left(as\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\right)}_{S}\mathrm{mod}s\right)$.

The following example illustrates the proof of Theorem 8. $\square $

Example 7. We want to know the survivor of the skip-first game with $n=15$, $k=2$, $s=3$, and $\mathcal{l}=2$. We run the example in Figure 6.

Using Theorem 8, we calculate that $a=3$ and find that $J{\left(3\times 3,2,3,2\right)}_{S}=7$. Therefore

$J{\left(15,2,3,2\right)}_{S}=\left(2+3\right)\lfloor \frac{7}{3}\rfloor +\left(7\mathrm{mod}3\right)=11.$

Note that while k and s are fixed parameters, there values can still be reduced. In particular, their values can be reduced as long as they retain the same proportions relative to n. The following result, offers an equation to recover the initial game’s survivor using this method of reduction. This is also the content of Part 5 of Main Theorem 2.

Theorem 9. If $a=\mathrm{gcd}\left(n,k,s\right)$, then

$J{\left(n,k,s,\mathcal{l}\right)}_{K/S}=a\cdot J{\left(\frac{n}{a},\frac{k}{a},\frac{s}{a},\mathcal{l}\right)}_{K/S}+a-1.$

Proof. The proof consists of two cases based on the value of a. For the first case, let $a=\mathrm{gcd}\left(n,k,s\right)=1$. Trivially, $J{\left(n,k,s,\mathcal{l}\right)}_{K/S}=J{\left(n,k,s,\mathcal{l}\right)}_{K/S}+1-1$.

We now consider the case where $a>1$. Let A be game ${\left(n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\right)}_{K\mathrm{/}S}$ where $a=\mathrm{gcd}\left(n,k,s\right)>1$, and let B be game ${\left(\frac{n}{a}\mathrm{,}\frac{k}{a}\mathrm{,}\frac{s}{a}\mathrm{,}\mathcal{l}\right)}_{K\mathrm{/}S}$. Note that

$\mathrm{gcd}\left(\frac{n}{a},\frac{k}{a},\frac{s}{a}\right)=1$,

therefore by the first case, B can only be reduced by this theorem trivially. Note that each of the n players of A can be surjectively mapped onto one of the $\frac{n}{a}$ players of B using the function $f\left(i\right)=\lfloor \frac{i}{a}\rfloor $ to provide their position. Note that when mapping all of the players, there are a consecutive players in A mapped to each player in B. It follows that in a round, the hits and skips also are mapped from A to B. For instance, in a round, k hits in A are mapped to $\frac{k}{a}$ hits in B on the corresponding mapped players. Therefore, given the survivor of game B, we know the corresponding remaining players in game A; the first of the remaining a players is player $a\cdot J{\left(\frac{n}{a}\mathrm{,}\frac{k}{a}\mathrm{,}\frac{s}{a}\mathrm{,}\mathcal{l}\right)}_{K\mathrm{/}S}$. Note that in this point of game A, each player has one life. Since $a\mathrm{|}s$ and $a\mathrm{|}k$, by Proposition 1 and Lemma 1, the last of the remaining players, player $a\cdot J{\left(\frac{n}{a},\frac{k}{a},\frac{s}{a},\mathcal{l}\right)}_{K/S}+a-1$ is the survivor. $\square $

Example 8. We want to know the survivor of a skip-first game where $n=8$, $k=2$, $s=4$, and $\mathcal{l}=2$. We run the game in Figure 7(a).

Since $a=\mathrm{gcd}\left(8,2,4\right)=2$, by Theorem 9 we find that $J{\left(4,1,2,2\right)}_{S}=0$, as illustrated in Figure 7(b). Therefore

Figure 6. ${\left(\mathrm{15,2,3,2}\right)}_{S}$ consists of 15 rounds, 10 cycles, and $J{\left(15,2,3,2\right)}_{S}=11$.

Figure 7. (a) Game ${\left(\mathrm{8,2,4,2}\right)}_{S}$ consists of 8 rounds, 9 cycles, and $J{\left(8,2,4,2\right)}_{S}=1$. (b) Game ${\left(\mathrm{4,1,2,2}\right)}_{S}$ consists of 8 rounds, 9 cycles, and $J{\left(4,1,2,2\right)}_{S}=0$.

$J{\left(8,2,4,2\right)}_{S}=2\left(0\right)+2-1=1.$

6. Future Work

In this paper, we showed how parameters $n\mathrm{,}k\mathrm{,}s$, and ℓ affect the survivor of games with specific constraints on those parameters. However, the general problem of identifying the survivor with any set of parameters has not yet been solved. Similar to Sullivan and Inkso’s variant, it is of note that since ℓ can be reduced to less than or equal to k in any game where n and $k+s$ are relatively prime, any direct solution for this case would only need to consider $\mathcal{l}\le k$. Other questions include but are not limited to: Are there other relationships between n, k, and s which produce similar reduction patterns? For many of the results in this paper, $k\ge s$. Through working with this problem, we noticed that the survivor becomes harder to identify as k becomes smaller, relative to s or n. Is there a recursive solution for cases when k is relatively close to either s or n?

Another direction for further research includes exploring other Josephus game variants. For example, S. Sharma, Tripathi, Bagai, Saini, and N. Sharma explore a variant in which the number of people hit at a time varies with each round [11] . One could then study a game variant in which the number of skips and hits vary within the game. Lastly, in the game studied here, the n players are listed in a line/circle. A further extension can be considering them lying on a general graph. Therefore, one could apply the techniques of random walks to study such games. For relevant work we refer the reader to [12] .

NOTES

^{1}For those interested in creating more examples, we provide a command-line Python program that computes the survivor of the Josephus game with defining parameters
$n\mathrm{,}k\mathrm{,}s\mathrm{,}\mathcal{l}\mathrm{,}p$, see https://github.com/davariyibi/Josephus-Simulator.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

[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 |

Journals Menu

Contact us

+1 323-425-8868 | |

customer@scirp.org | |

+86 18163351462(WhatsApp) | |

1655362766 | |

Paper Publishing WeChat |

Copyright © 2024 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.