In Concrete Mathematics, Chapter 3, Section 3, an interesting method to solve the Josephus problem is discussed. The paragraphs below depict the method, which are extracted from the book:
(Initially, the people waiting to be executed are labeled from $ 1 $ to $ n $, and stand in a circle. Every third person is executed.)
Whenever a person is passed over, we can assign a new number. Thus, $ 1 $ and $ 2 $ become $ n + 1 $ and $ n + 2 $; then $ 3 $ is executed; $ 4 $ and $ 5 $ become $ n + 3 $ and $ n + 4 $, then $ 6 $ is executed; ...; $ 3k + 1 $ and $ 3k + 2 $ become $ n + 2k + 1 $ and $ n + 2k + 2 $, then $ 3k + 3 $ is executed; then $ 3n $ is executed (or left to survive).
The $ k $th person eliminated ends up with number $ 3k $. So we can figure out who the survivor is if we can figure out the original number of person number $ 3n $.
If $ N > n $, person number $ N $ must have had a previous number, and we can find it as follows. We have $ N = n + 2k + 1 $ or $ N = n + 2k + 2 $, hence $ k = \lfloor (N - n - 1) / 2 \rfloor $; the previous number was $ 3k + 1 $ or $ 3k + 2 $, respectively. That is, it was $ 3k + (N - n - 2k) = k + N - n $. Hence we can calculate the survivor's number $ J_3(n) $ as follows:
$ N := 3n $;
while $ N > n $ do $ N := \lfloor \frac { N - n - 1 } { 2 } \rfloor + N - n $;
$ J_3(n) := N $;
I understand how the process goes. What I really can't get is why the renumbering scheme is true. Let's consider the example below, which is also from the book.
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22
23 24 25
26 27
28
29
30
In the first round of execution, 3, 6 and 9 got killed; the remaining people are labeled from 11 to 17. It's easy to figure out why the renumbering scheme (in which $ 3k + j $ becomes $ n + 2k + j $) is true in this round. For example, $ 1 = 3 \times 0 + 1 $, $ 11 = 10 + 2 \times 0 + 1 $; this is how 1 becomes 11. In the second round, according to the scheme, $ 11 = 3 \times 3 + 2 $, and $ 18 = 10 + 2 \times 3 + 2 $. This result agrees with the example above, but I cannot understand it, since the number has changed twice after the second round and the new number has no direct connection with 10, but the formula is still 10 plus something, rather than 17 plus something.
I would like a clear explanation on why the renumbering scheme ($ 3k + j \to n + 2k + j $) is true, even after the first round.
I think about it a little differently; perhaps this approach will make more sense.
Suppose that some person $P$ stays alive long enough to acquire the number $N>n$. That person must have had a previous number, say $M$. If $M$ were a multiple of $3$, the person would have been killed at that point, so $M=3k+1$ or $M=3k+2$ for some $k$. Since the person who at some point is numbered $3k$ is the $k$-th person killed, $k$ people are killed before we call out $M$ and point at $P$. Thus, at that point $n-k$ people remain in the circle. Now we count around these $n-k$ people, and when we get back to $P$, we find that he now has the number $N$. That can only happen if $N=M+n-k$, i.e., $M=k+N-n$.
If $M=3k+1$, this means that $3k+1=k+N-n$, so $2k=N-n-1$, and
$$k=\frac{N-n-1}2=\left\lfloor\frac{N-n-1}2\right\rfloor\;.$$
If $M=3k+2$, it means similarly that $k=\frac{N-n-2}2$. In the latter case $N-n-1$ must be odd, so
$$k=\frac{N-n-2}2=\left\lfloor\frac{N-n-1}2\right\rfloor\;.$$
Thus, in all cases
$$k=\left\lfloor\frac{N-n-1}2\right\rfloor\;,$$
and $M=k+N-n$.