Городская научно-практическая конференция юных исследователей

«Будущее Петрозаводска»

Секция (юниор) математика

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

МОУ «Гимназия №30 имени »,

7Б класс, г. Петрозаводск

Руководитель

учитель математики МОУ «Гимназия №30 имени »

E-mail: *****@***ru,  тел.+79212269676

Петрозаводск, 2017

Введение

Меня заинтересовала данная тема, потому что мне нравятся задачи на поиск закономерности, а также задачи, которые связаны с какими-то историческими событиями. К тому же часто при выборе ведущего в игре используются различные считалочки, и решение данной задачи позволит мне занять правильную позицию.

Цель исследования: решить задачу Иосифа Флавия, немного изменив условие задачи.

Задачи исследования:

    Изучить литературу по данной теме Узнать исторические сведения об Иосифе Флавии и его легенде Провести эксперимент с помощью одноклассников Найти закономерность в решении данной задачи Познакомиться с системами счисление и решить задачу в двоичной системе

Объект исследования: задачи на закономерности.

Предмет исследования: задача Иосифа Флавия.

Гипотеза исследования: Закономерность для решения задачи Иосифа Флавия существует.

Методы исследования:

    Поиск информации в Интернет-ресурсах. Эксперимент Обработка и анализ информации Выявление формул и закономерностей путём опытов.

В задаче Иосифа Флавия выбывал каждый третий, но я думаю, что мне будет сложно пока найти эту закономерность, поэтому немного изменю условие. В своей работе я буду искать победителя, если каждый второй участник будет выбывать из круга.

НЕ нашли? Не то? Что вы ищете?

Таким образом, формулировка задачи будет следующая:

Несколько человек стоят по кругу и играют в считалочку. Требуется узнать, каким по счету нужно встать, чтобы при выбывании каждого второго, остаться в кругу.

Теоретическая часть

Исторические факты

Задача Иосифа Флавия или, по-другому, эту задачу называют считалка Джозефуса - известная математическая задача с историческим подтекстом

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

Справочный материал

Для решения данной задачи мне понадобятся сведения о четности и нечетности чисел, понятии степени числа и системах счисления.

Четные и нечетные числа

Чётное число — целое число, которое делится на 2 без остатка:

Пример: 0, 2, 4, 6, 8, …

Нечётное число — целое число, которое не делится на 2 без остатка:

Пример: 1, 3, 5, 7, 9, …

Если n чётно, то оно представимо в виде n=2k, а если n нечётно, то в виде n=2k+1 или n=2k-1, где k – целое число.

Степень числа

Степенью числа а с натуральным показателем n большим 1, называется произведение n множителей, каждый из которых равен а.

Для степени числа а с показателем n принято обозначение: аn.

По определению аn = а · а · а · а… а. (n раз)

Таблица степеней числа 2

n

1

2

3

4

5

6

7

8

9

10

2n

2

4

8

16

32

64

128

256

512

1024

Системы счисления

Десятичная система счисления  -  одна из наиболее распространённых систем счисления. В ней используются арабские цифры 0;1;2;3;4;5;6;7;8;9. Предполагается, что количество символов 10 связано с количеством пальцев рук у человека.

Двоичная система счисления -  в современном мире одна из самых распространённых систем счисления. Она используется практически во всех современных компьютерах и прочих вычислительных электронных устройствах.

В двоичной системе счисления используются всего две цифры 0 и 1. Другими словами, двойка является основанием двоичной системы счисления. (Аналогично у десятичной системы основание 10).

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

В десятичной системе счисления мы располагаем десятью знаками-цифрами (от 0 до 9). Когда счет достигает 9, то вводится новый разряд (десятки), а единицы обнуляются и счет начинается снова. После 19 разряд десятков увеличивается на 1, а единицы снова обнуляются. И так далее. Когда десятки доходят до 9, то потом появляется третий разряд – сотни.

Двоичная система счисления аналогична десятичной за исключением того, что в формировании числа участвуют всего лишь две знака-цифры: 0 и 1. Как только разряд достигает своего предела (т. е. единицы), появляется новый разряд, а старый обнуляется.

Попробуем считать в двоичной системе:

0 – это ноль

1 – это один (и это предел разряда)

10 – это два

11 – это три (и это снова предел)

100 – это четыре

101 – пять

110 – шесть

111 – семь и т. д. [3]

Чтобы представить число в двоичной системе, нужно разложить его по степеням числа 2.  Пример: 18 = 24 + 21, значит 1810 = 100102

Практическая часть

Эксперимент

В своём классе я провела эксперимент. Я попросила одну из одноклассниц выбрать себе место, на котором, как она считает не выйдет из круга. Результаты эксперимента представляю в виде таблицы.

Количество участников

4

5

6

7

8

9

10

19

Выбранное место

3

2

5

7

3

1

6

3

Победитель

1

3

5

7

1

3

5

7

         Как видно из таблицы, 2 раза из 8 она угадала. Когда я проводила эксперимент, я называла победителя, и к концу 3-его и 4-ого раза вроде бы появилась закономерность, но как только количество участников стало равным степени двойки, закономерность сбилась и догадаться снова, куда нужно встать у нее не получилось.

Вывод: пользуясь интуицией или методом подбора очень сложно понять, где нужное место.

Поиск закономерности в десятичной системе

Далее я решила с помощью ручки и листа бумаги посчитать для первых 40 участников, какое место должно быть выигрышным (приложение 1)

Данные я собрала в таблицу:

n

1

2

3

4

5

6

7

8

9

f(n)

1

1

3

1

3

5

7

1

3

10

11

12

13

14

15

16

17

18

19

5

7

9

11

13

15

1

3

5

7

20

21

22

23

24

25

26

27

28

29

9

11

13

15

17

19

21

23

25

27

30

31

32

33

34

35

36

37

38

39

40

29

31

1

3

5

7

9

11

13

15

17

n – это количество человек, стоящих в круге.

f(n) - это значение, которое соответствует победителю при данном количестве человек.

Анализируя данные из таблицы, можно заметить, что все победители стоят на нечётных местах. Это можно объяснить тем, что все четные номера выходят при первом же круге.

Далее обратим внимание на выигрышную позицию под №1. Она повторяется при количестве человек  равных: 1; 2; 4; 8; 16; 32 и т. д. Если этот ряд продолжить, то можно заметить, что все числа являются  степенями двойки. Таким образом , где i – 0, 1, 2, 3, … (1)

       Все попытки вывести зависимость выигрышного положения от количества участников приводили меня в тупик, поэтому я решила вывести закономерность не от n, а от числа, показывающего, на сколько данное количество человек отличается от ближайшей степени 2. Назовем это число k. Например, при n = 25 получим k = 9 (25=24+9).

Составим таблицу зависимости выигрышного положения от k.

k

1

2

3

4

5

6

7

8

9

10

f(n)

3

5

7

9

11

13

15

17

19

21

Получаем ряд последовательных нечетных чисел, который можно задать формулой (2)

Пользуясь формулами (1) и (2) и таблицей зависимости f(n) от n, можно вывести следующую формулу: , где k = 0, 1, 2, 3, …

Пример: . Сверяем с таблицей, ответ верный.

;

 

В случае с историей Иосифа Флавия n = 40. Ближайшая степень 2 это 32, т. е. 40 = 32 + 8. Значит k = 8. Пользуясь формулой, можно вычислить выигрышную позицию равную 17, что подтверждается и опытным путем.

Вывод правила в двоичной системе

Так как при выводе закономерности я встретилась со степенями двойки, поэтому я решила попробовать изучить эту закономерность в двоичной системе счисления. Для начала я перевела данные моей таблицы в двоичную систему счисления:

n

1

10

11

100

101

110

111

1000

1001

1010

f(n)

1

1

11

1

11

101

111

1

11

101

1011

1100

1101

1110

1111

10000

10001

10010

10011

10100

111

1001

1011

1101

1111

1

11

101

111

1001

10101

10110

10111

11000

11001

11010

11011

11100

11101

11110

1011

1101

1111

10001

10011

10101

10111

11001

11011

11101

11111

100000

100001

100010

100011

100100

100101

100110

100111

101000

11111

1

11

101

111

1001

1011

1101

1111

10001

n – это количество участников в двоичной системе счисления.

f(n) – это номер победителя в двоичной системе счисления.

Анализируя данные из таблицы, можно заметить, что, во-первых, количество 1 и в первом и во втором числе совпадает, а во-вторых, число во второй строке можно получить, если первую единицу числа n переместить в конец и убрать лишние 0.

Например: при n = 100011  f(n)=111

       Попробуем объяснить это при помощи ранее выведенной закономерности. Рассмотрим наш пример 1000112 = 3510. Первая единица показывает ближайшую степень числа 2. В нашем примере это 32 = 25, значит, остальные цифры в записи составляют число k. Так как при записи число не может начинаться с 0, то получаем k = 11. Добавив в конце 1, мы увеличим число разрядов, значит, увеличим число k в 2 раза, а сама 1, стоящая в последнем разряде добавляет к числу 1. Получаем . Эту же закономерность мы получили и в десятичной системе.

Пример:

 

Таким образом, доказано, что данная закономерность может быть применена и в двоичной системе счисления.

Заключение

Выполнив данную исследовательскую работу, я сделала вывод, что задача Иосифа Флавия имеет решение. Закономерность, которая показывает выигрышную позицию при выбывании каждого второго, может быть описана следующей формулой . При данном условии Иосифу Флавию нужно  было вставать на место №17. Эта задача очень интересная, для её решения мне пришлось познакомиться с новой информацией. Гипотеза, выдвинутая в начале работы, полностью доказана.  В дальнейшем я бы хотела решить эту задачу, не меняя условия и попробовать вывести закономерность, когда выбывает каждый третий. 

Источники информации

Задача Иосифа Флавия -  материал из Википедии

https://ru. wikipedia. org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%98%D0%BE%D1%81%D0%B8%D1%84%D0%B0_%D0%A4%D0%BB%D0%B0%D0%B2%D0%B8%D1%8F#cite_note-1

Флавий Иосиф — биография, факты из жизни, фотографии, справочная информация http://www. piplz. ru/page. php? id=1791 Двоичная система счисления http://www. inf1.info/binarynotation

Приложение