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" 1.
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
So let's suppose that we have . 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.
Generalized for 2n People
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.
This is just like starting out with
npeople 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|
|3||2||2 x 2 - 1 = 3|
|5||3||2 x 3 - 1 = 5|
|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|
It may help to understand the meaning behind the formula
all scientific models are just
metaphors 2 , 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
(Yeah, I'm almost citing the book.)
Namely, for a group of 10 people, the survived person number equals
[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.
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.