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

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

Five People

Six People

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.