RtW

12 April 2022


The Josephus Problem: Marginal Clarifications

The book's marginal markings for the closed-form proof required additional effort on my side to understand. This post explicates the ideas of that marginal note.

The key fact is that J(2m) = 1 for all m, and this follows immediately from our first equation, J(2n) = 2J(n) - 1.

By follows immediately the author of the note supposedly meant the following considerations.

Fact 1
2m is an even number (it can be divided by 2 for any integer m).
Fact 2
The meaning behind J(2n) = 2J(n) - 1 is that as long as we have an even number of people, the survivor is the same as in a twice smaller group minus one.
Fact 3
2m can be halved m times before reaching a value of 1.

Combining these facts, we can write that

\begin{align*}
J(2^m) &= 2 \times J(2^{m - 1}) - 1 \\
&= 2 \times (2 \times J(2^{m - 2}) - 1) - 1 \\
&= 2 \times [2 \times (2 \times J(2^{m - 3}) - 1) - 1] - 1 \\
&= 2 \times [2^2 \times J(2^{m - 3}) - 2 - 1] - 1 \\
&= 2^3 \times J(2^{m - 3}) - 2^2 - 2^1 - 1 \\
& \ \vdots \\
&= 2^m \times J(2^{m - m}) - 2^{m - 1} - 2^{m - 2} - \dots - 2^0 \\
&= 2^m \times J(1) - (2^{m - 1} + 2^{m - 2} + \dots + 2^0) \\
&= 2^m \times 1 - (2^{(m - 1) + 1} - 1) \\
&= 2^m - 2^m + 1 \\
&= 1 \ .
\end{align*}

So indeed, we have confirmed — based on the given facts — that the first person will survive whenever n is a power of 2.

Now we move to the second part of the note.

And in the general case, when n = 2m + l, the number of people is reduced to a power of 2 after there have been l executions. The first remaining person at this point, the survivor, is number 2l + 1.

To help us visualize what this text means, first we look at the small cases.

Three People

\begin{align*}
& \textbf{1} \\
& \bullet \\
\textbf{3} \ \circledast \qquad & \qquad \dagger \ \textbf{2} \\
\end{align*}

Five People

\begin{align*}
& \textbf{1} \\
& \bullet \\
\textbf{5} \ \bullet \qquad & \qquad \dagger \ \textbf{2} \\
\textbf{4} \ \bullet \qquad & \qquad \circledast \ \textbf{3} \\
\end{align*}

Six People

\begin{align*}
& \textbf{1} \\
& \bullet \\
\textbf{6} \ \bullet \qquad & \qquad \dagger \ \textbf{2} \\
\textbf{5} \ \circledast \qquad & \qquad \bullet \ \textbf{3} \\
& \dagger \\
& \textbf{4}
\end{align*}


n 2m + l 2l + 1 Survivor #
3 21 + 1 2 × 1 + 1 3
5 22 + 1 2 × 1 + 1 3
6 22 + 2 2 × 2 + 1 5

Reviewing the small cases, we see that after l executions we are left with 2m people. Hence — according to the considerations from the first part of this post — the survivor is the first person in this group.

The survivor's number can be calculated by the formula 2l + 1, because each of l executions affects 2 people (an executioner and an executed) and the next (plus one) person is the first one in a left group of people (hence the survivor, as was discussed above).

Phew! Such a small note and so much effort for its clarification.

In the next post we move on to the second part of the book and apply repertoire method for evaluation of a sum in a 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.