Suppose you lay a string on the ground all around the earth right over the equator. The length of the string would be equal to the earth’s equatorial circumference—40,075.02 kilometers. Then, suppose you add 1 meter to the string, and suspend the string directly above the equator, with an even distance from the ground all the way around. Would a cat be able to pass from one hemisphere to another below the string?

Although this puzzle is quite simple, I like it because it’s so counterintuitive. It probably seems inconceivable that adding only 1 meter to such a large circumference would make any noticeable difference in the radius, let alone allow a cat to pass below the string in the space that was added. But if you do the math, you realize that the existing length of the circumference has no significance in determining how the radius would be affected when extending the length of the circumference. Instead, only the length of the addition is significant. The circumference can be expressed as P = 2πr (2 times Pi times the radius). Hence the original radius can be expressed as r = P/(2π). Adding 1 meter to the existing circumference would change the equation to: P + 1m = 2πr, where r represents the new radius. Isolating r, you get: r = (P + 1m)/(2π). Expanding the parentheses, you get: r = P/(2π) + 1m/(2π). Since the original length of the radius was P/(2π), the new radius is 1m/(2π) longer, which is about 16 centimeters (a bit more than 6 inches). That’s enough for a cat to go under and move from one hemisphere to the other.

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.

End of Article


You must log on before posting a comment.

If you don't have a username & password, please register now.

Reader Comments

I believe Josephus should be in position 19 if he wants to be the only man standing at the end. According to my findings, a formula could be:

Last Position = 1 + 2*(n - 2^(floor(log2 n)))

That is, first calculate the logarithm of n using base 2. Then obtain the floor of that number. Use this new number as the power and raise 2 to that power. Subtract the result from n, multiply it by 2 and add 1.

The way I got this was by manually obtaining the values for the first 15 possible numbers for n (1 - 15). I saw a pattern where for powers of 2 the position was always 1. And for the next consecutive numbers the value was 1 + 2, then 1 + 3, 1 + 5, etc., until it got to the next power of 2 and it went back to 1. So I knew that I needed to get the difference between the number n and the largest power of 2 smaller than or equal to n, multiply that by 2 and add it to 1. The difference is always zero for powers of 2 since you're subtracting the number from itself and then multiplying by two, and when you add 1 the result is, of course, 1.

A possible TSQL solution could be:

CREATE FUNCTION GetJosephusPosition(@N INT) RETURNS INT AS BEGIN DECLARE @POSITION INT

IF @N <= 0 SET @POSITION = 0 ELSE BEGIN DECLARE @LOG2 FLOAT DECLARE @POWER INT

SET @LOG2 = LOG10(@N)/LOG10(2) SET @POWER = POWER(2, FLOOR(@LOG2)) SET @POSITION = 1 + 2*(@N - @POWER) END

RETURN @POSITION END

cindyrod- June 13, 2008

Article Rating 5 out of 5

Let's see if it works better now. Here's the function I came up with again:

CREATE FUNCTION GetJosephusPosition(@N INT) RETURNS INT AS BEGIN DECLARE @POSITION INT

IF @N <= 0 SET @POSITION = 0 ELSE BEGIN DECLARE @LOG2 FLOAT DECLARE @POWER INT

SET @LOG2 = LOG10(@N)/LOG10(2) SET @POWER = POWER(2, FLOOR(@LOG2)) SET @POSITION = 1 + 2*(@N - @POWER) END

RETURN @POSITION END

cindyrod- June 13, 2008

Article Rating 5 out of 5