RtW

2 February 2022


The Josephus Problem: Filling the Gaps for Odds

As was promised earlier, in this post we're going to review The Josephus Problem for an odd number of people. This time we assume the last person is assigned the number 2n + 1 (since this expression can represent any odd integer, for an arbitrary integer n).

Three People

\begin{align*}
& \textbf{1} \ \textit{\scriptsize 2n - 1} \\
& \dagger \\
\textit{\scriptsize 2n + 1} \ \textbf{3} \ \bullet \qquad & \qquad \dagger \ \textbf{2} \ \textit{\scriptsize 2n} \\
\end{align*}

Five People

\begin{align*}
& \textbf{1} \ \textit{\scriptsize 2n - 3} \\
& \dagger \\
\textit{\scriptsize 2n + 1} \ \textbf{5} \ \bullet \qquad & \qquad \dagger \ \textbf{2} \  \textit{\scriptsize 2n - 2} \\
\textit{\scriptsize 2n} \ \textbf{4} \ \dagger \qquad & \qquad \bullet \ \textbf{3} \  \textit{\scriptsize 2n - 1} \\
\end{align*}

Seven People

\begin{align*}
& \textbf{1} \ \textit{\scriptsize 2n - 5} \\
& \dagger \\
\textit{\scriptsize 2n + 1} \ \textbf{7} \ \bullet \qquad & \qquad \dagger \ \textbf{2} \ \textit{\scriptsize 2n - 4} \\
\textit{\scriptsize 2n} \ \textbf{6} \ \dagger \qquad & \qquad \bullet \ \textbf{3} \ \textit{\scriptsize 2n - 2} \\
\textit{\scriptsize 2n - 1} \ \textbf{5} \ \bullet \qquad & \qquad \dagger \ \textbf{4} \ \textit{\scriptsize 2n - 3} \\
\end{align*}

Generalized

\begin{alignat*}{4}
&& && & \textbf{1} \quad & && \\
&& && & \dagger \\
&& \textit{\scriptsize 2n + 1} \ & \bullet \quad \quad & && & \ \dagger \ \\
&& \dagger \ \ && && && & \bullet \ \textbf{3} \\
&& \textit{\scriptsize 2n - 1} \ \bullet \ \ && && && & \ \dagger \ \\
&& \dagger \ \ && && && & \bullet \ \textbf{5} \\
&& \textit{\scriptsize 2n - 3} \ & \bullet \quad \quad & && & \ \dagger \\
&& && & \ldots \quad
\end{alignat*}


Once again, here's a table that summarizes how "re-numbering" can be performed and verifies that the formula 2n + 1 calculates initial person's number, when n is the person's number after the 1st round.

Initial Person's Number After the 1st Round Verify 2n + 1
1 Dead -
2 Dead -
3 1 2 x 1 + 1 = 3
4 Dead -
5 2 2 x 2 + 1 = 5
6 Dead -
7 3 2 x 3 + 1 = 7
2n - 3 n - 2 2(n - 2) + 1 = 2n - 3
2n - 2 Dead -
2n - 1 n - 1 2(n - 1) + 1 = 2n - 1
2n Dead -
2n + 1 n 2(n + 1) + 1 = 2n

These considerations help us to establish, that in a group of the odd number of people 2n + 1, the survived person number is the same as the survived person number in a group of n people, but doubled and increased by 1.

\begin{equation*}
J(2n + 1) = 2J(n) + 1 \ , \qquad \text{for } n \ge 1.
\end{equation*}

The next post is devoted to the proof of the Josephus problem closed form.

Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Created by Y.E.T.If you see an error, please report it.