3

I am going through the Josephus problem and I am not able to understand the recurrence relation.

The solution says that for $2n$ people, the actual number of person in the $2n$-d round can be mapped using
$$J(2n)=2\cdot J(n)-1 \qquad\rm{eq.1}$$

and for 2n+1 people the numbering in the 2nd round can be mapped using
$$J(2n+1) = 2 \times J(n)+ 1 \qquad\rm{eq.2}$$

I understand the R.H.S of these $2$ equations.
In case of $2n$ people, after the first round the actual number of the person at position $1$ is $1 = 2 \times J(1)-1$, actual number of person $2$ is $3 =2 \times J(2)- 1$.

Same goes for the $2n+1$ equation too, actual number of person $1$ after round $1$ is $3 = 2 \times J(1)+ 1$.

What I do not understand is L.H.S, what does $J(2n)$ and $J(2n+1)$ mean here?
Why $2n$ and $2n+1$?
If I substitute '$1$' in eq.1, we get $J(2 \times 1)=2 \times J(1) - 1 \implies J(2)=1$; which is not correct.
What am I missing here?

Also how is it that using these equations I can calculate the position of the person that survives? Since these equations only represent the position of the person.

Thanks

Robert Lee
  • 7,233
Pharaoh
  • 233

1 Answers1

4

You’ve misunderstood the function $J$. $J(n)$ is the position number of the last survivor when we start with a circle of $n$ people. It is not the number of people left after the first round.

If $n=1$, the last survivor is of course person $1$, so $J(1)=1$. If $n=2$, the last survivor is again person $1$, so $J(2)=1=2J(1)-1$. If $n=4$, the first round kills off persons $2$ and $4$, and the second round kills off person $3$, so person $1$ is yet again the final survivor, and $J(4)=1=2J(2)-1$. If $n=3$, however, the first round kills off person $2$, the second round kills off person $1$, and person $3$ is the last survivor, so $J(3)=3=2J(1)+1$.

You can use the recurrences $J(2n)=2J(n)-1$ and $J(2n+1)=2J(n)+1$ and the initial condition $J(1)=1$ to calculate the final survivor for any $n$ simply by working backwards. If we start with $n=21$, for instance, we have

$$\begin{align*} J(21)&=J(2\cdot 10+1)\\ &=2J(10)+1\\ &=2J(2\cdot 5)+1\\ &=2\big(2J(5)-1\big)+1\\ &=4J(5)-1\\ &=4J(2\cdot 2+1)-1\\ &=4\big(2J(2)+1\big)-1\\ &=8J(2)+3\\ &=8J(2\cdot 1)+3\\ &=8\big(2J(1)-1\big)+3\\ &=16J(1)-5\\ &=16\cdot 1-5\\ &=11\,. \end{align*}$$

Brian M. Scott
  • 616,228
  • How did they make this connection with so few data points? I am referring to the proof here, https://en.wikipedia.org/wiki/Josephus_problem and the proof speaks about the place of the person in the 2nd round of slaying after all the even numbered persons are out by saying "If the initial number of people was even, then the person in position x during the second time around the circle was originally in position 2 x − 1", from here how do they make the jump to the general solution for even numbered person? what was the point behind discussing the place of persons in the 2nd round? – Pharaoh Mar 20 '21 at 21:00
  • @Pharaoh: First, do you understand why the person in position $x$ in the second round was originally in position $2x-1$? – Brian M. Scott Mar 20 '21 at 21:04
  • Yes, since all the even numbered person out in round 1, person at position 2 was originally at 3 and person at position 3 was originally at 5 and so on. so 3= 22-1; 5=23-1, hope that's right – Pharaoh Mar 20 '21 at 21:22
  • 2
    @Pharaoh: Okay. If you start with $2n$ people, you have $n$ people left after the first round. In the notation of the Wikipedia article, the final survivor will be the person who is now in position $f(n)$. Let $x=f(n)$. We just saw that the person in position $x$ now was at position $2x-1$ originally. That means that the final survivor must be the person who was at position $2x-1=2f(n)-1$ originally. By definition the final survivor when we start with $2n$ people is the one at position $f(2n)$, so $f(2n)=2f(n)-1$. – Brian M. Scott Mar 20 '21 at 21:27
  • I think I get it, Thanks – Pharaoh Mar 21 '21 at 10:36
  • @Pharaoh: You’re welcome. – Brian M. Scott Mar 21 '21 at 17:22