Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

Josephus Problem

Puzzle

There are n persons in a circle, numbered 1 thru n. Going around the circle, every second person is removed from the circle, starting with person number 2, 4, and so on. Show that the number of the last person remaining in the circle can be obtained by writing n in binary, then moving the leftmost 1 to the right. So for example, with n = 13 persons (1101 in binary), the last person is number 11 (1011 in binary).

Source

Classic problem found in introductory books on combinatorics.

Solution

Explained quite well in an article by Rick Regan. Also see the Wikipedia article and Wolfram's page.

Sloane A032434 contains the list of survivors given by the formula $latex 1 + 2n - 2^{1 + \lfloor\lg n floor}$ where $latex \lfloor n floor$ is the floor function and $latex \lg$ is the logarithm in base 2. The first few members of the sequence are 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1.

Previous Puzzle: Six Colored Balls

We have two red, two green and two yellow balls. For each color, one ball is heavy and the other is light. All heavy balls weigh the same. All light balls weigh the same. How many weighings on a beam balance are necessary to identify the three heavy balls?

Next Puzzle: Forty-Five Minutes

How do we measure forty-five minutes using two identical wires, each of which takes an hour to burn. We have matchsticks with us. The wires burn non-uniformly. So, for example, the two halves of a wire might burn in 10 minute and 50 minutes respectively.

17 Aug 2011
© Copyright 2008—2017, Gurmeet Manku.