The Josephus Problem: Filling in the Gaps for Evens

I'm back to solving The Josephus Problem after a break. During the break, I had finished reading A Mind for Numbers by Barbara Oakley. In the book, she confirms that my choice to put away a "not solvable" task for some time — after thoroughly focusing on it — was a fine choice. This way I was letting my brain continue solving the task "in the background" ¹.

And yes, I must say this approach did work. First of all, I've figured out starting which part of the chapter I had lost the thread of thought. This was the sentence So let's suppose that we have 2n people originally. This sentence sounded incomprehensible to me. But now I have cracked it by looking at the small cases again: substituting 2n for the initial number of people each time. The following diagrams help visualizing this idea for an even number of people. They show the moment after the first round.

Two People

$\begin{align*} \textbf{1} & \ \textit{\scriptsize 2n - 1} \\ \bullet \\ \quad \\ \dagger \\ \textbf{2} & \ \textit{\scriptsize 2n} \\ \end{align*}$

Four People

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

Six People

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

Eight People

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

Generalized for 2n People

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

Well, now indeed I see that

After the first go-round, we're left with [the diagram, see it in the book. YE] and 3 will be the next to go.

and

This is just like starting out with n people except that each person's number has been doubled and decreased by 1.

The "re-numbering" is summarized in the following table. Data in the third column allows us to verify that the formula 2n - 1 (where n is the person's number after the 1st round) calculates the initial person's number.

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

It may help to understand the meaning behind the formula

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

Since all scientific models are just metaphors ² , here's how it can be explained in plain English:

The survived person number in a group of 2n people is the same as the survived person number in a group of n people, but doubled and decreased by 1. (Yeah, I'm almost citing the book.)

Namely, for a group of 10 people, the survived person number equals 2 x [survivor number in a group of 5 people] - 1. That is, 2 x 3 - 1 = 5.
(We know that the survivor in a group of 5 people is the person number 3 from the consideration of the small cases.)

That's it, we've filled in the gaps for an even number of people.

In the next post, we're going to review the case of an odd number of people in a similar manner.

Footnotes:

A quote from the book A Mind for Numbers:

If you are trying to understand or figure out something new, your best bet is to turn off your precision-focused thinking and turn on your "big picture" diffuse mode.

Oakley, B. (2014). A Mind for Numbers: How to Excel at Math and Science (Even If You Flunked Algebra). TarcherPerigee.