The survivor in the circle

HardBrainteasers~8m

$N$ people stand in a circle labelled $1$ through $N$ ; let $X$ be the largest power of $2$ that is $\le N$ . Starting at person $1$ , each living person kills the next living person clockwise and passes the sword on, until one survives. The survivor's label can be written as $a\,N + b\,X + c$ for integers $a, b, c$ . Find $a + 2b + 3c$ .

Show hints (2)+

Josephus, every-second elimination: survivor $= 2L+1$ where $L=N-X$ and $X$ is the top power of $2$ $\le N$ .
So $W = 2N - 2X + 1$ : read off $a=2, b=-2, c=1$ .

Answer

Reveal answer →

Create a free account to see the full worked solution and track your progress.

Create a free account

Interview format: Market Maker, Hedge Fund Quant

The survivor in the circle

Answer

Related questions