The Logical Puzzle - 27 Jun 2008

Solution to June’s Puzzle: Josephus Problem

The Josephus problem is an ancient puzzle that involves a group of 41 men standing in a circle. Going around the circle, every second standing man is executed (one skipped, one executed) until only one man is left standing. Assuming that the positions are numbered 1 through 41, which position should Josephus (one of the men) choose if he could, so that he would be the only one to remain standing? Can you generalize the solution for n men? Write a T-SQL solution that returns the position based on the input number of men @n.

An easy way to find a generic solution to this puzzle with any number of men is to first solve it with very small numbers of men (1, 2, 3, and so on), and to look for a pattern in the results. If you solve the puzzle for small numbers, you get the results shown in Web Table A (www.sqlmag.com, InstantDoc ID 99039), where n is the number of men, and p is the position of the only man left.

The pattern you can identify is that p is an increasing sequence of odd integers that restarts from 1 when n is a power of 2. You express n as 2^a + b, where b >= 0 and b < 2^a. That is, a is the highest power of 2 such that 2^a is smaller than n, and b is n minus 2^a. Then, p can be expressed as 2b + 1. For example, for n = 41, you express n as 2^5 + 9. Since b = 9 and p = 2b + 1, you get p = 19.

Of course, this is just an observation of a pattern based on the cases that were tested. To ensure that the pattern holds for all cases, you need a mathematical proof. You can find such a proof at en.wikipedia.org/wiki/Josephus_problem. The following T-SQL expression calculates p for a given @n:

DECLARE @n AS INT;SET @n = 41;SELECT 2 * (@n - POWER(2, CAST(LOG(@n)/LOG(2) AS   INT))) + 1 AS p;