2

In a game, $N$ people are lined up in a circle and numbered from $0$ to $N-1$. At each turn, the next $K$th person, starting with the last eliminated person, is eliminated from the game. The first person to be eliminated is the $K$th. Find the last remaining person in the game. Example:

$N$ = 5, $K$ = 3

0 1 2 3 4

0 1 3 4

1 3 4

1 3

3

The last person is the 3rd one.

Peter
  • 84,454
M3601
  • 21
  • Welcome to MSE. Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or closed. To prevent that, please [edit] the question. This will help you recognise and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. – José Carlos Santos Feb 14 '21 at 12:21
  • 1
    Very nice problem – alien2003 Feb 14 '21 at 12:25
  • 5
    Unless I am misreading, this is the classic Josephus Problem – lulu Feb 14 '21 at 12:27
  • I tried to solve this problem long time ago (with the only difference that I numbered from $1$ to $N$), but all I could find out was a recursion for the next eliminated person, no fast way to find out the last person if $N$ is extremely large. – Peter Feb 14 '21 at 12:28
  • 1
    I think that this might be very difficult or maybe impossible to calculate only based on N and K,pretty much like Ramsey's numbers for which,a formula doesn't exist yet.Unfortunatly I think that the recursion is the only way to find the number of the last person – alien2003 Feb 14 '21 at 12:36

0 Answers0