Chapter 37
The Josephus problem and its
generalization
37.1 The Josephus problem
nprisoners are arranged in a circle. In succession, everysecondone is
removed from the circle and executed, and the last one is set free. Who
is the survivor?
Examples
1.n=10:
1
2
4 3
5
6
7
8 9
10
8
1
2 6
*
3
7
4 9
5
2.n=21. After the removal of the 10 even numbered ones and then
the first, there are the 10 odd numbers 3, 5,...,19,21. Thesurvivor
is the 5-th of this list, which is 11.