# Find the last member remained in game

Imagine a game like this, N man lined in circle, and numbered from 1 to N. Starting from the man with number one, he shout "in", the next one (man number two) shout "out", the next one (man number 3) shout "in", the next number 4 shout "out"..., and so on... The man shout "out" will get out of the circle immediately. The game runs till one member remained in circle. The question is which position (number) of the last one remained in circle.

if N = 2, the last one is 1
N = 3, the last one is 3
N = 6, the last one is 5
N = 20, the last one is 9

-
This is the Josephus problem with $k=2$. –  Chris Eagle Aug 23 '11 at 10:06
@Chris: I suggest you post that as an answer so it can be accepted and the question can be marked as answered. –  joriki Aug 23 '11 at 10:10
@joriki: I was hoping some more energetic person would write an answer that wasn't just a Wikipedia link. –  Chris Eagle Aug 23 '11 at 10:12
With all due respect: you're posting one well-known puzzle after the other. What is the point of this? –  t.b. Aug 23 '11 at 10:20
@Chris: I know what you mean, but in a case like this where the article already says it all and it's not very likely that someone will have something interesting to add to it, often the question remains in this state and never gets marked as answered. For this kind of question I think the Wikipedia link is the best answer; I don't think there's any point in someone spending time to write the same thing here. If you don't want to get "trivial" reputation points, you can always make your answer community wiki. –  joriki Aug 23 '11 at 10:25
show 1 more comment

## 1 Answer

This is the Josephus problem with $k=2$.

I might as well explain how I discovered this, since it's a fairly general technique: I solved the problem for $n=1$ to $10$ and typed the results into the On-Line Encyclopedia of Integer Sequences.

-
You proved me wrong and did add something useful to the mere Wikipedia link :-) –  joriki Aug 23 '11 at 10:43
The OEIS entry oeis.org/A006257 gives a neat algorithm. Write n in binary and rotate left one bit. –  Ross Millikan Aug 23 '11 at 13:18
See also Concrete Mathematics, Section 1.3, which is devoted to an explanation of the Josephus problem. –  Mike Spivey Aug 23 '11 at 16:18
In fact the CM book mentioned by Mike gives a speedy iterative algorithm to determine the number of the sole survivor. –  Ｊ. Ｍ. Aug 24 '11 at 3:32
add comment