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;
End of Article
