The Josephus Problem

###
1. In Massada, in ancient Greece, it was decided that there were too many
prisoners and many should be executed. One prisoner was given a sword
and all 1000 prisoners were instructed to stand in a circle. The one with the
sword was instructed to kill the man on his left and then pass the sword to
the next man on the left, who would then do the same. The circle would
continue to get smaller as this continued, and the last man left would be set
free. Josephus, one of the prisoners, placed himself at the correct position
in the lineup to be the one remaining man at the end of this elimination. At
what position did he place himself on the circle?

2. If the last two will be set free, where should Josephus direct his
friend to stand?

To attack this problem, try it for smaller numbers of prisoners first, less than
20 or so.

####
Source: Martin Gardner, Dick McFarland, and the Stanford EE Ph.D.
qualifying exam.

[Taken from "Ken's Puzzle of the Day" March 14, 1994]

Here is a hint that may help.

Examine the binary values for the starting total and the end position.

Solution

Mail to Ken