Let’s look at the problem quickly. In this problem we start with n people numbered 1 to n(with labels 1 to n) around a circle with the first person initially having a sword and the person who has the sword kills every adjacent (k=2) remaining person until only 1 survives for eg. 1 kills 2, then swords passes to 3 which then kills 4 then the sword passes to 5 which then kills 6 and so on…people on the round table keep killing adjacent person until the last 1 person remains i.e.
above is the starting configuration for n = 10. Here 2,4,6,8,10,3,7,1,9 will be killed and 5 will survive.
we have to find the person who survives(a person has the number as label which it had when the game(killing game) started i.e. in position 1 → person labeled is 1, in position 2 person labelled is 2 and so on…….)or we have to find the label of the surviving person.
Here we saw that after the first round all the even numbers were eliminated and the sword again came to 1(we can use this fact).
Finding a Recurrence
For a certain even number 2n, after the first round of killing the sword again comes to the first person and total n people remain(as half of the people on even numbers got killed) i.e.
If you observe, what happened is that the positions occupied are the same as the case for n = n, only the labels of the positions have been changed to 2*n-1 i.e. there is a one to one correspondence of the people here with the people in the case of n = n. 1 → 1, 2 → 3, 3 → 5 etc. So the answer to the problem of J(2n) is 2*J(n)-1(since all positions have a correspondence to 2*n -1, and our answer J(2n) is also a position here).
So we can say J(2n) = 2*J(n)-1.
Similarly for odd number 2n+1, the configuration after one round of killing comes out to be
here the one to one correspondence is for 2n+1 like before.
J(2n+1) = 2*J(n)+1.
For n = 1, J(1) = 1.
The Recursive solution can be given as:
J(1) = 1;
J(2n) = 2*J(n)-1;
J(2n+1) = 2*J(n)+1.
Using the above recurrence relation it is possible to find a closed form solution(direct formula).
It is easy to find a pattern in these initial values of J(n) found using the above relations. It seems when ever n equals a power of 2, the form of J(n) resets itself and every time in a group the values go up to a power of 2 with a difference of 2. So if we write n in the form n = 2^m + l, where 2^m is the largest power of 2 not exceeding n and l is what is left, then the closed form solution seems to be →J(2^m + l) = 2l + 1. We can apply induction to prove that it is correct, readers are encouraged do it themselves.
Changing the perspective a little
We know a binary number like for eg. (1011)₂ is calculated in base 10 as
(1*2³) + (0*2² + 1*2¹ + 1*2⁰) = 11, here notice that the highest power of 2 was 2³ = 2^m, and other terms can be interpreted as l(=(011)₂), and we know the answer for this n = (1011)₂ is 2l + 1, which is 2 multiplied by (011)₂ and adding 1 to it, we know for a fact that multiplying by 2 corresponds to shifting the bits to the left and adding a 0 to the end so (011)₂ → (110)₂, since we are adding 1 to it too(remember 2l + 1) (110)₂ + 1 = (111)₂, and voila! we got our answer J((1011)₂) = (111)₂. Just appreciate what we did here, we formalised a method of finding the answer by just looking at the bits of n and making one cyclic shift left!.
If n = (bₘbₘ₋₁bₘ₋₂….b₁b₀)₂ then J(n) = (bₘ₋₁bₘ₋₂….b₁b₀bₘ)₂.
The problem and it’s solution is embedded in the way a binary number system works!
If we were working in a base 2 system we would have spotted this pattern immediately!
Let that sink in. The fact that the solution of this problem is so elegant if we just change the base of our number system speaks volumes about the simplicity of solutions to different problems in different areas of mathematics if we just change the way we look at stuff.
We have solved the problem for k = 2 . We can also generalize this cyclic shift idea for k > 2. For now our exposition ends here.