2
$\begingroup$

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

enter image description here

  • 3
    This is the [Josephus problem](http://en.wikipedia.org/wiki/Josephus_problem) with $k=2$.2011-08-23
  • 1
    @Chris: I suggest you post that as an answer so it can be accepted and the question can be marked as answered.2011-08-23
  • 0
    @joriki: I was hoping some more energetic person would write an answer that wasn't just a Wikipedia link.2011-08-23
  • 4
    With all due respect: you're posting one well-known puzzle after the other. What is the point of this?2011-08-23
  • 1
    @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.2011-08-23
  • 0
    Sorry guy, Math is not my major, so I'm not aware of this is well-know puzzle. Thanks.2011-08-23

1 Answers 1

5

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.

  • 2
    You proved me wrong and did add something useful to the mere Wikipedia link :-)2011-08-23
  • 3
    The OEIS entry http://oeis.org/A006257 gives a neat algorithm. Write n in binary and rotate left one bit.2011-08-23
  • 1
    See also *Concrete Mathematics*, Section 1.3, which is devoted to an explanation of the Josephus problem.2011-08-23
  • 0
    In fact the CM book mentioned by Mike gives a speedy iterative algorithm to determine the number of the sole survivor.2011-08-24