Задача Иосифа Флавия

1. Государственное учреждение образования «Гимназия №38 г. Минска»

Задача Иосифа Флавия
Авторы работы:
Рогова Валерия Владиславовна, ул. Шугаева, 19/2,
142, т.234-60-98;
Лебедева Виктория Алексеевна, д. Копище, ул.
Лопатина 2, 65, т.290-35-11,
Карамач Николай Александровия, ул.
Ф.Скорины, 41, 32
Научный руководитель работы:
Ларченко Андрей Николаевич
Учитель математики, гимназии 38.
Минск,2016

2. Цели:

3. Задачи:

4. Из истории…

Иосиф Флавий - известный историк
первого века - выжил и стал известным
благодаря математической одаренности.
В ходе иудейской войны он в составе
отряда из 41 иудейского воина был загнан
римлянами в пещеру. Предпочитая
самоубийство плену, воины решили
выстроиться в круг и последовательно
убивать каждого третьего из живых до
тех пор, пока не останется ни одного
человека. Однако Иосиф наряду с одним
из своих единомышленников счел
подобный конец бессмысленным - он
быстро вычислил спасительные места
в порочном круге, на которые поставил
себя и своего товарища.

5. Задача Иосифа Флавия

Условие
Расставим натуральные числа по кругу от 1 до 41 и
вычеркиваем каждое второе число до тех пор, пока не останется одно
число. Это и будет решение задачи.
4
1
3
9
3
8
3
3 7
3 6
3 5
4
1
4
0
2
3
4
5
6
7
8
9
3
3
1
0
3
2
1
1
19
3
1
3
0
2
9
1
2
1
3
1
4
2
8
1
5
1
6
2
7
1
7
2
6
2
5
1
8
2
4
2
3
2
2
2
1
2
0
1
9

6.

Четный случай. Выстроим в круг 10 чисел и будем исключать
каждое второе до тех пор, пока не останется только одно.
Следовательно выживет человек с
номером 5.
n
J ( 2n) 2 j ( n ) 1
n 0
1
3
2n-1
2n
2n-3
5
2n
7

7.

Нечётный случай. В случае 2n+1 чисел, 1 убирается за вторым
кругом.
1
2n+1
2n+1
2n-1
3
5
2n+1
7
Опять получаем первоначальную ситуацию с n числами, но на этот раз
номера удваиваются и увеличиваются на 1. Таким образом,
J (2n 1) 2 j (n) 1
n 0

8.

Рекуррентное соотношение дает возможность очень быстро
составить таблицу первых значений J(n).
1
2
3
4
5
6
7
8
9
10
11 12
13
14
15
16
J(n) 1
1
3
1
3
5
7
1
3
5
7
11
13
15
1
n
9
Если сгруппировать значения n по степеням 2 (в таблице эти
группы отделены вертикальными линиями), то в каждой группе J(n)
всегда будет начинаться с 1, а затем увеличиваться на 2.
J (2 k ) 2k 1
n
n 0,
k 0,2 n

9. Решим другую задачу:

Расставим натуральные числа по кругу от 1 до n. Вычеркиваем числа 2, 3,
пропускаем число 4, вычеркиваем два следующих числа и т.д. Вычеркиваем
до тех пор, пока не останется одно число. Это число и будет решением задачи.
J (41) j (1 33 2 7) 3 7 1 15
38
37
36
35
м
34
33
32
31
J (n) j (r 3s 2l ) 3l 1
41 1 2
39 40
3
4
5
к6
7
22
30
29
м
28
27
26
25
24 23
9
22 21 20 19
18
8
9
10
м
11
м
12
113
14
151
16
17

10.

Расставим в круге соответственно 6, 7, 8 чисел. Чтобы число n
осталось после первого круга, оно должно иметь вид n=3*k+1.
Мы делим n на тройки чисел, два из которых удаляем, значит после удаления
Остается k+1 число, т.к. удаляется 2*х чисел.
1
2
3
1
4
1
2
3
2
4
5
5
6
7
3
4
6
1
6
7
5
7
4
8

11.

Количество n=3k+1
чисел в круге
n=3(3l-1)+1 n=3*3(3
m-1)+1
...
Вычеркиваем
Осталось
2k
2l
2m
...
K+1
l
m
...
Количество 79=3*26+ 3(3*9-1)+1
чисел в круге +1
3(3*3*3- 3*3(3*3*1-1)+1
-1)+1
Вычеркиваем
осталось
52
18
6
2
27
9
3
1
n 3 (t 3s 1 1) 1 3 t s s 1 3 1 t 3s 2, t 3

12.

1
1
1
2
2
2
3
1
3
1
4
5
6
3
9
1
4
8
7
5
6

13.

1
17
16
J(17)
2
6
5
3
4
15
3
13
2
14
4
7
5
1
13
6
8
12
7
9
11
Вычер- Остакиваем лось
1*2
15
шаг 1
17
шаг 2
17
2*2
13
шаг 3
17
3*2
11
шаг 4
17
4*2
9
шаг 5
17
4*2
…
…
…
…
n
l*2
r*
8
0
10
9
j (n) j (2l r 3s ) 3l 1

14.

Рассмотрим табличные значения еще раз:
n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
j(n)
1
1
1
4
4
1
7
4
1
7
4
10
7
13
10
Пусть k=4
j(k)=j(4)=4
j(3k)=j(12)=10
j(3k+1)=j(13)=7
j(k-1)=j(3)=1
j(3k+2)=j(14)=13
Получаем рекурсивные формулы:
j(3k)=3j(k)-2
j(3k+1)=3j(k-1)+4
j(3k+2)=3j(k)+1

15.

Доказательство полученной формулы по индукции:
1. Верность формулы при малых n проверяется подстановкой:
J (1) j (1 30 2 0) 1 3 0 1
J (2) j (2 30 2 0) 1 3 0 1
J (3) j (1 31 2 0) 1 3 0 1
J (4) j (2 30 2 1) 1 3 1 4

16.

Пусть формула верна для всех целых чисел, меньших r 3
Покажем, что формула верна и для
s 1
j (r 3 2 (3k )) 3 j (3
s
s
2 l
.
n r 3s 2 l .
2k ) 2 3 (3k 1) 2 3l 1
j (r 3s 2 (3k 1)) j (r 3s 2 (3k ) 2) 3 j (r 3s 1 2k ) 1
3 (3k 1) 1 3l 1
j (r 3s 2 (3k 2)) j (r 3s 3 (2k 1) 1)
3 j (r 3s 1 (2k 1) 1) 4 3 (3k 1) 4 3 (3k 2) 3l 1