: Recursive relations and some : The Josephus Problem in : The Josephus Problem in

Introduction and an example.

We are going to study a variant of the Josephus problem in this article. In this variant of the Josephus problem two numbers are to be eliminated at the same time, but two processes of elimination go for different directions. Let $n$ and $k$ be natural numbers such that $k \geq 2$. Suppose that there are $n$-numbers. Then the first process of elimination starts with the 1 st number and the $k$-th, $2k$-th, $3k$-th number, ... are to be eliminated. The second process starts with the $n$-th number, and the $(n-k+1)$-th, $(n-2k+1)$-th, $(n-3k+1)$-th number, ... are to be eliminated. We suppose that the first process comes first and the second process second at every stage. We denote the number that remains by $JI(n,k)$.

The function $JI(n,2)$ has very interesting properties. It has fractal-like graphs. See Example 3.4. The sequence $\{ JI(n,2), n = 1, 2, ... \}$ has a remarkable property when divided by 2. See Example 3.1. We denote $JI(n,2)$ by $JI(n)$.

As to the author's other researches of the variant of the Josephus problem, see [1], [2] , [3] and [4].

Example 1.1   Suppose that there are $n = 8$ numbers and $k = 2$. Then the 2nd and 4th number will be eliminated by the first process. Similarly 7th and 5th number will be eliminated by the second process. Then we have the following Figure. 1.1.
Here we covered eliminated numbers by the first process and the second process with gray color disks and gray color rectangles respectively, and the number with a underline was eliminated for the last time, and the number with a double underline was eliminated just before it. In Figure 1.1 the last number eliminated is 5 and 4 was eliminated before it. Now two directions are going to overlap. The first process will eliminate the 8,6 and the second process will eliminate 1. The number that remains is 3. See Figure 1.2.

Figure (1.1)　　　　　　　　　　　　　　Figure (1.2)

Example 1.2   We are going to study another example. Suppose that there are $n = 33$ numbers and $k = 2$. This time we calculate $JI(33)$ using a recursive relation. The 2nd, 4th, ...16th number will be eliminated by the first process. Similarly the 32th, 30th,...18th number will be eliminated by the second process. Then we have the following Figure 1.3.
In Figure 1.3 the last number eliminated is 18, and 16 was eliminated before it. Now two directions are going to overlap. The first process will eliminate the 19th, 23th, 27th, 31th and 1st, and the second process will eliminate the 15th, 11th, 7th, 3th.
Now we have 8 numbers that remain. See Figure 1.4

Figure (1.3) 　　　　　　　　　　　　　　　　　　　Figure (1.4)
We are going to use a recursive relation to calculate $JI(33)$. We have numbers {33,29,25,21,17,13,9,5}, and the next number to be eliminated is 29 and after that 9 will be eliminated. Suppose that we do not know the result of Example 1.1. If $JI(8)$ = 1 or 2 or 3 ... or 8, then $JI(33)$ = 33 or 29 or 25 or ...or 5 respectively. By comparing the values of $JI(8)$ and $JI(33)$ we can make a recursive relation
$JI(33) = 37 - 4JI(8)$.
By the result of Example 1.1 we know that $JI(8) = 3$. This means that the third number of the list {33,29,25,21,17,13,9,5} will remain, and hence $JI(33) = 37 - 4\times 3 = 25$.

: Recursive relations and some : The Josephus Problem in : The Josephus Problem in