The survivor in the circle

NN people stand in a circle labelled 11 through NN; let XX be the largest power of 22 that is N\le N. Starting at person 11, 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 aN+bX+ca\,N + b\,X + c for integers a,b,ca, b, c. Find a+2b+3ca + 2b + 3c.

Show hints (2)+
  1. Josephus, every-second elimination: survivor =2L+1= 2L+1 where L=NXL=N-X and XX is the top power of 22 N\le N.
  2. So W=2N2X+1W = 2N - 2X + 1: read off a=2,b=2,c=1a=2, b=-2, c=1.

Answer

Reveal answer →

1

Want the full step-by-step worked solution? It's part of Premium - along with a worked solution for every question in the bank.

Asked at: Jane Street, Citadel

Related questions