Josephus Problem

1234 people are standing in a circle and are numbered in the
clockwise order from 1 to 1234. Starting from person number 1, each time
we skip one person and eliminate the next person. We repeat this process
until only one person remains in the circle. Who will be the last
person?
What if instead of 1234, we have 12345678987654321 people around the
circle?
Explanation: In the version with 1234 people, first
person number 2 is eliminated then person number 4 and so on. This goes
on until person 1234 is eliminated. After going around the circle once,
we again skip person 1, but since we previously eliminated person number
2, this time we eliminate person number 3. We continue this process
until only one person remains.
The answer for the case of 1234 people is 421 and for the case of
12345678987654321 is 6676959465826659. More explanation is given
below:
This problem is known as the Josephus problem. Let
Theorem 1. [from https://en.wikipedia.org/wiki/Josephus_problem] Let
Proof. We prove the theorem using an induction on
For the induction step, we consider the two cases of odd
If
is even, then let be the largest power of two which not greater than and be . After going around the circle once, we eliminate all the people with even numbers and then start over with remaining people that only have odd labels. By the induction hypothesis, the answer for the remaining people would be ’th person whose label would be . Since then the label of the last remaining person would be equal to .If
is odd, then let be the largest power of two which not greater than and be . After going around the circle once, we eliminate all the people with even numbers and then start over with remaining people that only have odd labels. Also, since we eliminate the people with even labels, the last person is skipped and the next person to eliminate is person number 1. After eliminating person number 1, we are left with people with labels for in range . By the induction hypothesis, the last person who remains among these people would be the ’th person whose label is equal to . Note that and therefore which completes the proof.