**:**
An interesting fact about
**:** The
Josephus Problem in **:**
Introduction and an example.

**Theorem
2.1** (1)
*.
(2)
(3)
.
(4)
(5)
(6)
(7)
(8)
where
is the floor function.*

**Proof
** (1) *We suppose
that there are
numbers. The first process begins to eliminate them, starting with
the 2nd number, while the second process starts with the
-th
number. When the two processes have eliminated
numbers,
numbers remain. See Figure 2.1. After this, the two processes are
going to intersect each other. When
numbers are eliminated,
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
numbers remaining,
depends on
If
,
then by Figure 2.2 we have
.
Therefore If
,
then .
If
,
then by Figure 2.2
.
Therefore if
,
then .
By using the floor function we can express these two equations of
by one equation
.
We have proved (1) of Theorem 2.1.
*

*Figure
(2.1.) * *Figure
(2.2) (2) We suppose that there are
numbers. When
numbers are eliminated,
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
numbers remain,
depends
When we begin to eliminate
numbers that remain, the second process will eliminate
,
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
,
and the second number is
.
Therefore if
,
then
,
and hence .
We have proved (2) of Theorem 2.1.
(3) We suppose that there are
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).
Figure (2.3.)*

(4) We suppose that there are numbers. When numbers are eliminated, 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 numbers. The situation of (5) is different from these of (1), (2), (3) and (4). When numbers are eliminated, numbers remain. When there are 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).

Figure (2.5.)

(6) We suppose that there are numbers. When numbers are eliminated, numbers remain. See Figure 2.7. Similarly we can prove (6).

(7) We suppose that there are numbers. When numbers are eliminated, 2n+1 numbers remain. See Figure 2.8. Similarly we can prove (7).

*Figure
(2.7.) * *Figure
(2.8) (8) We suppose that there are
numbers. When
numbers are eliminated,
numbers remain. See Figure 2.9. Similarly we can prove (8).
Figure (2.9.)*

**Lemma
2.1**
*for any natural number
.*

**Proof
** *By Theorem 2.1
we have
,
and hence
for
.
Clearly we have
Similarly we can prove that ,
and
.*

**:**
An interesting fact about
**:** The
Josephus Problem in **:**
Introduction and an example.