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

  • 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.

  • 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