What would happen in the variant of the Josephus problem in which people in odd-numbered positions are killed in each round? What would happen in the variant of the Josephus problem in which people in odd-numbered positions are killed in each round?
For example, with $N=10$ people:
$$
1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \to 2, 4, 6, 8, 10 \to 4 ,8 \to 8.
$$
As you can see in the above example the killing starts from position $1$.
I was just curious to find out what would be the solution to this variant. I tried out different values of $n$ but could not find a proper algorithm.
Position $2^{\lfloor \log_2 N \rfloor}$ is always safe since it is the position that maximizes the number of trailing zeros in its binary representation.
Claim: The person originally sitting in position $n$ is killed in the $i$-th round iff the binary representation of $n$ has exactly $i-1$ trailing zeroes.
Proof: By strong induction on $i$. If $i=1$ the claim is trivially true since $n$ has $0$ trailing zeroes iff $n$ is odd.
If $i &gt; 1$, by induction hypothesis we have that all remaining people were originally sitting in positions whose binary representation has $i$ or more trailing zeros, i.e, those positions are exactly the integers in $S = \{1, \dots, N\}$ that are multiples of $2^i$.
If $n=2^i k$ then there are exactly $k$ positions in $S$ smaller than or equal to $n$, i.e., $n$ is killed iff $k$ is odd.