The Josephus Problem: Filling in 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.