Josephus Flavius Problem
A recent letter from a math teacher reminded my that the recursive solution I have been planning to describe for a while now is long overdue.
This solution applies to the case where every other person is executed
After the first go-round we essentially come up with the same problem but for a different number of individuals. We have to distinguish between two cases: n is even and n is odd. When n is even,
|J(2k) = 2J(k) - 1, and|
|J(2k + 1) = 2J(k) + 1.|
There is a way to solve these recursive formulas but the result is simple enough for us just to guess the right expression. The formulas are very easy to apply. Let's build a table for the first few values of n:
We may now notice that J(n) is always odd and starts anew from 1 with every power of 2. It increases through all successive odd numbers until it is about to reach the next power of 2 when it again drops to 1. For every number n, there exists an integer a such that
J(2a + t) = 2t + 1.
We prove the formula by induction on a. For
J(2a + t) = 2J(2a -1 + t/2) - 1 = 2(2t/2 + 1) - 1 = 2t + 1
by the inductive assumption. Similarly, if 2a + t = 2k + 1, then
J(2a + t) = 2J(2a -1 + (t-1)/2) + 1 = 2(2(t-1)/2 + 1) + 1 = 2t + 1
This completes the induction step.
- R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
- Josephus Flavius problem
- Two ancient variants
- A simple solution
- Partial recursive solution
- A problem from USAMTS