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(2^m) = 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: 2^m 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: 2^m 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 = 2^m + 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`	`2^m` `+ l`	`2l + 1`	`Survivor #`
3	2¹ + 1	2 × 1 + 1	3
5	2² + 1	2 × 1 + 1	3
6	2² + 2	2 × 2 + 1	5

Reviewing the small cases, we see that after l executions we are left with 2^m 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.