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.