Day 21: CM, Page 8

Day 21: The authors find a cleaner solution to zig problem. Rather than derive the closed form by expanding a recurrent form, they notice a relationship between zigs and lines in a plane. A zig is the same as two intersecting lines except that the lines don't continue after they meet. Since the lines in both problem only intersect one another once, we don't need to worry about intersection after the zig if we always ensure the lines intersect before the zig. And if the lines intersect before the zig, we'll have the same number of regions as lines in plane minus the regions after the zig. For each zig, we only loose two regions (one for each line that is lost). So zigs are related to lines in a plane as follows:

Z(n) = 2(L(n)) - 2n

If we expand that we have:

2(n(n+1))/2 + 1 - 2n =
n^2 + n + 1 - 2n =
n^2 -n + 1

Which matches what we found yesterday.

Next the author introduces the Josephus problem. There is a story behind this problem. Josephus was a famous historian of the first century. During the Jewish-Roman war, Josephus was trapped in a cave with 40 other Jewish rebels. They decided to kill themselves rather than surrender. They got in a circle and had every third person kill himself. Josephus and a conspriator decided they didn't want to kill themselves and quickly calculated where to position themselves in the circle so that they were the last ones standing. How did Josephus perform the calculation?

Reading ahead a little authors begin by looking at the same problem, but hop two people instead of three. Lets look at some small examples where every second person is killed.
J(1) = 1
J(2) = 1
J(3) = 3
J(4) = 1
J(5) = 3
J(6) = 5
J(7) = 7
J(8) = 1
J(9) = 3
J(10) = 5
J(11) = 7
J(12) = 9
J(13) = 11
J(14) = 13
J(15) = 15
J(16) = 1

So it appears that the solution depends on n's position relative to the most recent power of 2. It looks like J(n) = 1 + 2(n - "last power of 2")

J(3) = 1 + 2(3-2) = 3
J(4) = 1 + 2(4-4) = 1
J(11) = 1 + 2(11 - 8) = 7
J(15) = 1 + 2(15 - 8) = 15

Tomorrow, we'll see how the authors approach the problem. Here's a statue of Josephus: