Day 22: CM, Page 9

Day 22: The authors examine the Josephus problem. They start by looking at small examples. When they fail to find a pattern, they try to find a recurrence. Rather than finding a single equation, they break the problem into even and odd numbers of people.

Starting with an even number of people, after the first round we're left with exactly half as many people.

1 2 3 4 5 6 7 8 9 10
1 3 5 7 9

1 3 5 7 9 is the same as 1 2 3 4 5 except that each person's number is double and decreased by 1. So:

J(2n) = 2(J(n)) - 1

In other words 1 2 3 4 5 6 7 8 9 10 will have the same solution as 1 2 3 4 5 where each number is doubled (2 4 6 8 10) and decreased by 1 (1 3 5 7 9) since we know all the even numbers in the first sequence will be eliminated. The key here is that the authors have found a notation that allows the problem to be expressed as a sub-problem of itself. Pretty ingenious!

We'll take a look at odd numbers tomorrow.