Homework 6
Flavius Josephus was a Jewish historian living in the first century. According
to Josephus’ account of the siege of Yodfat, he and his 40 soldiers were trapped
in a cave by Roman soldiers. They chose suicide over capture, deciding to
form a circle and start killing every third person. Josephus states that by luck
or possibly by the hand of God, he and another man remained the last and
surrendered to the Romans (from Wikipedia).
The Josephus Problem, named for this apocryphal story, asks the question
of where to stand in a circle of n people in order to be the last person alive
when we kill every k
th person.
When n = 41 and k = 3, the solution to the Josephus Problem is 31. At the
beginning, all 41 rebels are alive:
r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12, r13, r14, r15, r16, r17, r18, r19, r20, r21,
r22, r23, r24, r25, r26, r27, r28, r29, r30, r31, r32, r33, r34, r35, r36, r37, r38, r39, r40, r41
After 13 killings, one “round” of the circle is completed, and 28 rebels remain
(the most recently dead rebel is marked by ?):
r1, r2, r4, r5, r7, r8, r10, r11, r13, r14, r16, r17, r19, r20, r22, r23, r25, r26, r28, r29,
r31, r32, r34, r35, r37, r38, ?, r40, r41
In the second round, 10 die and 18 remain:
r2, r4, r7, r8, r11, r13, r16, r17, r20, r22, r25, r26, r29, r31, r34, r35, r38, r40, ?
The remaining rounds appear in the following table (no one dies in round
8):
Round Rebels
3 r2, r4, r8, r11, r16, r17, r22, r25, r29, r31, r35, r38, ?
4 r2, r4, r11, r16, r22, r25, r31, r35, ?
5 r2, r4, r16, r22, ?, r31, r35
6 r4, r16, ?, r31, r35
7 r16, r31, ?
9 ?, r31
1
1. Design an algorithm that solves the Josephus Problem, using an appropriate data structure.
2. Prove that your algorithm takes O(kn) or O(n lg n) time. If your algorithm
takes longer than either of these, find a faster algorithm. Hint: if you are
using an appropriate data structure, this question should be very simple.
2
