next up previous
: An interesting fact about : The Josephus Problem in : Introduction and an example.

Recursive relations and some formulas for JI(n).

Theorem 2.1 (1)   $ JI(8n) = 4JI(2n) - 1 - \lfloor JI(2n)/(n+1) \rfloor $.
(2) $ JI(8n+1) = 8n+5-4JI(2n).$
(3) $ JI(8n+2) = 4JI(2n)-3- \lfloor JI(2 n)/(n + 2) \rfloor $.
(4) $ JI(8n+3) = 8n+7-4JI(2n).$
(5) $ JI(8n+4) = 8n+8-4JI(2n+1)+ \lfloor JI(2n+1)/(n+2) \rfloor.$
(6) $ JI(8n+5) = 4JI(2n+1)-1.$
(7) $ JI(8n+6) = 8n+10-4JI(2n+1)+ \lfloor(JI(2n+1)/(n+2)\rfloor.$
(8) $ JI(8n+7) = 4JI(2n+1)-3,$
where $ \lfloor \ \rfloor$ is the floor function.

Proof (1)   We suppose that there are $ 8n$ numbers. The first process begins to eliminate them, starting with the 2nd number, while the second process starts with the $ (8n-1)$-th number. When the two processes have eliminated $ 4n$ numbers, $ 4n$ numbers remain. See Figure 2.1.
After this, the two processes are going to intersect each other.
When $ 6n$ numbers are eliminated, $ 2n$ numbers remain. See Figure 2.2.
Here the number with an underline was eliminated for the last time, and the number with a double underline was eliminated just before it.
Since there are $ 2n$ numbers remaining, $ JI(8n)$ depends on $ JI(2n).$
If $ JI(2n) = 1, 2, ...,n$, then by Figure 2.2 we have $ JI(8n) = 3, 7, ..., 4n-1$.
Therefore If $ JI(2n) \leq n$, then
$ JI(8n) = 4JI(2n) - 1 $.
If $ JI(2n) = n+1, ...,2n$, then by Figure 2.2 $ JI(8n) = 4n+2, ...,8n-2$.
Therefore if $ JI(2n) \geq n+1$, then
$ JI(8n) = 4JI(2n) - 2$.
By using the floor function we can express these two equations of $ JI(8n)$ by one equation $ JI(8n) = 4JI(2n) - 1 - \lfloor JI(2n)/(n+1) \rfloor $. We have proved (1) of Theorem 2.1.
% latex2html id marker 1298\includegraphics[height=6cm,clip]{proof8n.eps}

Figure (2.1.)               Figure (2.2)
(2) We suppose that there are $ 8n+1$ numbers. When $ 6n+1$ numbers are eliminated, $ 2n$ numbers remain. See Figure 2.3.
Here the number with an underline was eliminated for the last time, and the number with a double underline was eliminated just before it.
Since $ 2n$ numbers remain, $ JI(8n+1)$ depends $ JI(2n).$
When we begin to eliminate $ 2n$ numbers that remain, the second process will eliminate $ 8n-3$, and after that the first process will eliminate 9.
Therefore we can assume that we have the Josephus problem with the list
{ 8n+1, 8n-3, ..., 9, 5 }, where the first number to be eliminated is $ 8n-3$, and the second number is $ 9$. Therefore if $ JI(2n) = 1,2,...,2n$, then $ JI(8n) = 8n+1, 8n-3,...,5$, and hence
$ JI(8n+1) = 8n+5-4JI(2n)$.
We have proved (2) of Theorem 2.1.
(3) We suppose that there are $ 8n+2 $ numbers. When 6n+2 numbers are eliminated, 2n numbers remain. See Figure 2.4. By the method that is similar to the one we used in (1) we can prove (3).
% latex2html id marker 1299\includegraphics[height=6cm,clip]{proof8n12.eps}
Figure (2.3.)
                 Figure (2.4)
(4) We suppose that there are $ 8n+3$ numbers. When $ 6n+3$ numbers are eliminated, $ 2n$ numbers remain. See Figure 2.5. By the method that is similar to the one we used in (2) we can prove (4).
(5) We suppose that there are $ 8n+4$ numbers. The situation of (5) is different from these of (1), (2), (3) and (4). When $ 6n+3$ numbers are eliminated, $ 2n+1$ numbers remain. When there are $ 2n+1$ numbers remain, there is not any number left between the number with an underline and the number with a double underline. See Figure 2.6. By the method that is similar to the one we used in (2) we can prove (5).
% latex2html id marker 1300\includegraphics[height=6cm,clip]{proof8n34.eps}
Figure (2.5.)
             Figure (2.6)
(6) We suppose that there are $ 8n+5$ numbers. When $ 6n+4$ numbers are eliminated, $ 2n+1$ numbers remain. See Figure 2.7. Similarly we can prove (6).
(7) We suppose that there are $ 8n+6$ numbers. When $ 6n+5$ numbers are eliminated, 2n+1 numbers remain. See Figure 2.8. Similarly we can prove (7).
% latex2html id marker 1301\includegraphics[height=6cm,clip]{proof8n56.eps}

Figure (2.7.)                  Figure (2.8)
(8) We suppose that there are $ 8n+7$ numbers. When $ 6n+6$ numbers are eliminated, $ 2n+1$ numbers remain. See Figure 2.9. Similarly we can prove (8).
% latex2html id marker 1302\includegraphics[height=6cm,clip]{proof8n7.eps} Figure (2.9.)

Lemma 2.1   $ J(2n) \neq n + 1$ for any natural number $ n$.

Proof   By Theorem 2.1 we have $ JI(8n) = 4JI(2n) - 1 - \lfloor JI(2n)/(n+1) \rfloor $,
and hence $ JI(8n) = 3, ..., 4n-1, 4n+2, ...$ for $ JI(2n)= 1, ...,n, n+1, ...$. Clearly we have $ J(8n) \neq 4n + 1.$
Similarly we can prove that
$ J(8n+2) \neq 4n + 2$, $ J(8n+4) \neq 4n + 3$ and $ J(8n+6) \neq 4n + 4$.


next up previous
: An interesting fact about : The Josephus Problem in : Introduction and an example.