## find a winner among n > 0 contestants by a game of elimination.

Consider a prize to be awarded to a winner among n > 0 contestants by a game of elimination. The n contestants first line up in a line and are assigned the numbers 1 to n one by one.

The host of the game then decides on an integer k > 1 and starting from contestant 1, the host counts k contestants down the line and eliminates the k^{th} contestants from the circle. He then continues to count for another k contestants and eliminates the k^{th} contestants from the line. When he counts to the end of the line, he will continue counting from the beginning of the line. This process repeats until there are only one contestant remains who will be the winner of the prize.

For example, if n = 7 and k = 3,

The initial line: 1234567, count to 3 and contestant 3 is eliminated

The line now becomes: 124567, continue counting from 4 and contestant 6 is eliminated

The line now becomes: 12457, continue counting from 7 and contestant 2 is eliminated

The line now becomes 1457, continue counting from 4 and contestant 7 is eliminated

The line now becomes 145, continue counting from 1 and contestant 5 is eliminated

The line now becomes 14, continue counting from 1 and contestant 1 is eliminated

The winner is contestant 4

## Login to view answer.