Circle Challenge

The Problem

Imagine you have a circle of people and you go around the circle removing every second person until one person is left.

If you have 3 people in the circle, then the 3rd person will be the last one remaining. If you have 4 people then the 1st person will be the last one remaining. If you have 11 people then the 7th person will be the one remaining.

If you have N people in the circle, who will be the last one remaining?

Please formulate your answer as a general solution and not as an algorithm that simulates the problem

Solution

Let N be the number of people in the circle and b_i...b₁b₀ its binary representation. The position (in binary representation) f_k...f₁f₀ of the last person remaining in the circle is expressed by the formula below:
......+----------------------------------------------------------------------------------------------
.......| 1, where k = 0
.......|
f_k = | if f_k-1 = b_k-1 then 1 , where k > 0 and k ≤ i and f_k...f₁f₀ ≤ b_i...b₁b₀
.......| else 0
......+----------------------------------------------------------------------------------------------

Examples:
N = 3 => b₁b₀ = 11
f₀ = 1
f₁ = f₀ (1) = b₀ (1) => 1
Result: f₁f₀ = 11 => 3

N = 4 => b₂b₁b₀ = 100
f₀ = 1
f₁ = f₀ (1) ≠ b₀ (0) => 0
f₂ = f₁ (0) = b₁ (0) => 0, but f₂f₁f₀ > b₂b₁b₀ => 101 > 100 then it is discarded
Result: f₁f₀ = 01 => 1

N = 11 => b₃b₂b₁b₀ = 1011
f₀ = 1
f₁ = f₀ (1) = b₀ (1) => 1
f₂ = f₁ (1) = b₁ (1) => 1
f₃ = f₂ (1) ≠ b₂ (0) => 0
Result: f₃f₂f₁f₀ = 0111 => 7

Built With

• text-description