The Last One Standing

Question

One hundred people stand in a circle, numbered 1 to 100 clockwise. Starting with person 1, every second person is eliminated: person 2 goes first, then person 4, and so on around and around, closing the circle as people leave. Which position survives?

Accepted Answer

The power-of-two anchor First the clean case. If n is a power of two, one full lap eliminates every even position and returns the turn to person 1, leaving n/2 people in a circle with person 1 again going first. The structure repeats exactly, so person 1 survives whenever n = 2^m. Reducing the general case to that anchor For general n, write n = 2^m + ell, qquad 0 le ell < 2^m, so 2^m is the largest power of two not exceeding n. Eliminate the first ell people to go, which takes ell eliminations and leaves exactly 2^m people. Crucially, the turn now sits with the person immediately after the last one eliminated, and that person is in position 2ell + 1. From this moment the situation is the clean power-of-two case with 2ell + 1 playing the role of person 1, so that position survives: J(n) = 2ell + 1 = 2(n - 2^m) + 1. The answer for 100 The largest power of two at most 100 is 64, so ell = 100 - 64 = 36 and J(100) = 2(36) + 1 = 73. The one-line binary version The formula has a neat restatement: write n in binary and move the leading 1 to the end. Here 100 = 1100100_2, and rotating gives 1001001_2 = 73. Interviewers who know the problem often ask for this form, because reproducing it sh

The Last One Standing

Problem

Your answer

Hints

More Brainteasers & Logic to train on