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

Содержание

Слайд 2

Цели:

Цели:

Слайд 3

Задачи:

Задачи:

Слайд 4

Из истории…

Иосиф Флавий - известный историк первого века - выжил и

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

Слайд 5

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

Расставим натуральные числа по кругу от 1 до 41

Задача Иосифа Флавия Расставим натуральные числа по кругу от 1 до 41
и вычеркиваем каждое второе число до тех пор, пока не останется одно число. Это и будет решение задачи.

Условие

2

3

4

5

6

7

9

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

1

8

39

38

10

40

41

19

Слайд 6

Четный случай. Выстроим в круг 10 чисел и будем исключать каждое

Четный случай. Выстроим в круг 10 чисел и будем исключать каждое второе
второе до тех пор, пока не останется только одно.

Следовательно выживет человек с номером 5.

Слайд 7

Нечётный случай. В случае 2n+1 чисел, 1 убирается за вторым кругом.

2n+1

Опять получаем

Нечётный случай. В случае 2n+1 чисел, 1 убирается за вторым кругом. 2n+1
первоначальную ситуацию с n числами, но на этот раз
номера удваиваются и увеличиваются на 1. Таким образом,

Слайд 8

Рекуррентное соотношение дает возможность очень быстро составить таблицу первых значений J(n).

Если сгруппировать

Рекуррентное соотношение дает возможность очень быстро составить таблицу первых значений J(n). Если
значения n по степеням 2 (в таблице эти группы отделены вертикальными линиями), то в каждой группе J(n) всегда будет начинаться с 1, а затем увеличиваться на 2.



Слайд 9

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

Расставим натуральные числа по кругу от 1 до n. Вычеркиваем

Решим другую задачу: Расставим натуральные числа по кругу от 1 до n.
числа 2, 3,
пропускаем число 4, вычеркиваем два следующих числа и т.д. Вычеркиваем
до тех пор, пока не останется одно число. Это число и будет решением задачи.


22

Слайд 10

Расставим в круге соответственно 6, 7, 8 чисел. Чтобы число n
осталось

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

2

3

4

5

6

1

1

2

3

4

5

6

7

1

7

2

3

4

5

6

7

1

8

4

Слайд 12

3

2

1

1

1

3

2

4

5

6

1

1

2

3

4

5

6

7

8

9

1

3 2 1 1 1 3 2 4 5 6 1 1

Слайд 13

11

3

4

5

9

8

7

6

2

1

9

8

7

6

5

4

3

2

1

13

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

Слайд 14

Рассмотрим табличные значения еще раз:

Пусть 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

Получаем

Рассмотрим табличные значения еще раз: Пусть 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 проверяется подстановкой:

Доказательство полученной формулы по индукции: 1. Верность формулы при малых n проверяется подстановкой:

Имя файла: Задача-Иосифа-Флавия.pptx
Количество просмотров: 47
Количество скачиваний: 0