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.
Ken's Solution:

1. From the binary total, move the leading one to the end to get the final person. For 1000 (1111101000), move the leading one to the end to get 977 (1111010001).
2. From (1), subtract (the highest power of two less than the total). If negative, add the next lowest power of two instead (977-512=465).
Another Solution, from Bill Beall :
977th position would be best.
The binary value of 1000 is '1111101000'.
Inverting the bits, you get a binary value of '10111' or 23 decimal.
Subtract 23 from the total (1000-23 = 977).
This method works for small values, (which is how I found it).

Thanks for the "Hint".
And from Chris Woodward (chris.n.lisa@beloved.com), a base 10 implementation of the first above:
Take the number of people in the contest minus the next lower power of 2. 
Multiply the result by 2 and add one.

( 1000 - 512 ) * 2 + 1 = 977
And from Wilfred Theunissen :
1000 = '1111101000' binary.

As you and many others stated, my position has to be 

        '1111010001' = 977

For the position of my friend I just have to change the leading number:
I change 'x' into '1-x'; So his place is '0111010001' = 465.

In general:

Let x be the total of all prisoners;
Write x = a(n) * 2^n + a(n-1) * 2^(n-1) + .... + a(1)*2 + a(0);
so x = 'a(n)a(n-1)a(n-2).....a(1)a(0)' binary.
Then my position has to be 'a(n-1)a(n-2)....a(1)a(0)a(n)' binary and my
friends position has to be 'Aa(n-2)a(n-3)...a(1)a(0)a(n)' binary, where
A=1-a(n-1).
Mail to Ken