Skip to content

Safe spot in a circle of 2000 with every second removed

Question

Two thousand people stand in a circle numbered 11 to 20002000. Person 11 eliminates person 22 and passes the sword to person 33, who eliminates person 44 and passes it on, and so on around the circle, each holder removing the next living person and handing the sword to the following survivor. Which numbered position is the last one remaining?

Short answer

Position 19531953. This is the Josephus problem with step 2: writing N=2m+rN=2^m+r with 0≤r<2m0\le r<2^m, the survivor is 2r+12r+1. Here 2000=1024+9762000=1024+976, so the survivor is 2⋅976+1=19532\cdot976+1=1953.

Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Probability Fundamentals is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free