Проблема Иосифа

Проблема Иосифа Флавия или перестановка Иосифа Флавия - теоретическая проблема информатики или математики .

В схеме расположены пронумерованные объекты; затем, начиная с номера , удаляется каждый- й объект, круг снова и снова замыкается. Порядок удаленных объектов называется перестановкой Иосифа Флавия. ${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle k}$

Цель этой задачи - определить последний объект данной перестановки и . ${\ displaystyle n}$${\ displaystyle k}$

история

Проблема была названа в честь еврейского историка Флавия Иосифа , который спрятался от римлян в пещере с 40 другими мужчинами во время битвы за галилейский город Йотапата в 67 г. н.э. (всего 41 человек). Он сообщает об этом в своей книге « Еврейская война» (книга 3, глава 8). Когда убежище было предано, римляне попросили их сдаться в плен. Однако его последователи предпочли смерть и предпочли умереть коллективным самоубийством , порядок решал жребий. К счастью, Иосиф и еще один мужчина сдались последними. Позже это было превращено в головоломку, в которой каждый должен выстроиться в круг и каждый третий должен быть убит своим правым соседом. В этом особом случае Иосиф занял 16-е место, оставшись предпоследним и обогнав более слабого на 31-м месте. Оба сдались римлянам и выжили.

После Вильгельма Аренс , Кардано назвал проблему типа Иосифа игра (Ludus Josephi) в своей работе Practica arithmeticae (1539), но он был старше. После Морица Кантора его можно найти в рукописи Николя Шуке La triparty en la science des nombres (Лион, 1484 г.). Проблемой занимается также Клод Гаспар Баше де Мезириак (Problèmes plaisans et delectables, 1612), который также предлагает вариант: 15 турок и 15 христиан находятся на корабле в шторм. Капитан должен пожертвовать 15 из них, чтобы корабль не затонул, и выстроил их в ряд, причем каждый девятый был принесен в жертву.

решение

Проблема здесь решается в случае удаления каждого 2-го элемента ( ). Для общего случая решение следует ниже. Решение выводится с помощью рекурсии. обозначают последний элемент перестановки, если элементы присутствовали в начале (с ). На первом проходе удаляются все четные элементы. Во втором раунде элементы, которые находятся в новой позиции 2, 4 и т. Д., Удаляются, как если бы первого раунда не было. Если начальное количество элементов четное, то элемент из второго раунда был на позиции в первом раунде . Элемент изначально был на месте . Это приводит к следующей формуле рекурсии: ${\ displaystyle k = 2}$${\ Displaystyle к \ neq 2}$${\ displaystyle f (n)}$${\ displaystyle n}$${\ displaystyle k = 2}$${\ displaystyle x}$${\ displaystyle 2x-1}$${\ displaystyle f (2n)}$${\ displaystyle 2f (n) -1}$

${\ Displaystyle f (2n) = 2f (n) -1. \,}$

Если количество элементов вначале нечетное, то первоначальный первый элемент удаляется во втором раунде, но здесь также удаляется новый 2-й, 4-й и т. Д. Элемент. В этом случае оказывается, что Element был на позиции на первом круге . Отсюда следует формула рекурсии: ${\ displaystyle x}$${\ displaystyle 2x + 1}$

${\ Displaystyle f (2n + 1) = 2f (n) +1. \,}$

Если вы отобразите значения для и в таблице, вы увидите закономерность: ${\ displaystyle n}$${\ displaystyle f (n)}$

${\ displaystyle n}$	1	2	3	4-й	5	6-е	7-е	8-е	9	10	11	12-е	13-е	14-е	15-е	16
${\ displaystyle f (n)}$	1	1	3	1	3	5	7-е	1	3	5	7-е	9	11	13-е	15-е	1

Эта таблица предполагает, что существует возрастающая последовательность нечетных чисел, которая начинается снова, когда индекс равен степени двойки. Если кто-то выбирает и так то, а потом следует . Очевидно, что значения из таблицы удовлетворяют этому уравнению. Доказательство дается ниже по полной индукции . ${\ displaystyle f (n)}$${\ displaystyle f (n) = 1}$${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle l}$${\ displaystyle n = 2 ^ {m} + l}$${\ displaystyle 0 \ leq l <2 ^ {m}}$${\ Displaystyle F (N) = 2 \ CDOT L + 1}$

Утверждение: Если и , то следует . ${\ displaystyle n = 2 ^ {m} + l}$${\ displaystyle 0 \ leq l <2 ^ {m}}$${\ Displaystyle F (N) = 2l + 1}$

Доказательство: полная индукция окончена . Дело верно. Рассмотрим отдельно случаи для четного и нечетного . ${\ displaystyle n}$${\ Displaystyle п = 1}$${\ displaystyle n}$${\ displaystyle n}$

Если прям, то выбирайте и так, что и . Это применимо . Имеем место, где второе уравнение следует из предположения индукции. ${\ displaystyle n}$${\ displaystyle l_ {1}}$${\ displaystyle m_ {1}}$${\ Displaystyle п / 2 = 2 ^ {м_ {1}} + l_ {1}}$${\ displaystyle 0 \ leq l_ {1} <2 ^ {m_ {1}}}$${\ displaystyle l_ {1} = l / 2}$${\ Displaystyle f (n) = 2f (n / 2) -1 = 2 ((2l_ {1}) + 1) -1 = 2l + 1}$

Если нечетное, то выберите одно и такое, что и . Это применимо . Имеем место, где второе уравнение также следует из предположения индукции. Следовательно, утверждение доказано. ${\ displaystyle n}$${\ displaystyle l_ {1}}$${\ displaystyle m_ {1}}$${\ Displaystyle (п-1) / 2 = 2 ^ {м_ {1}} + l_ {1}}$${\ displaystyle 0 \ leq l_ {1} <2 ^ {m_ {1}}}$${\ displaystyle l_ {1} = (l-1) / 2}$${\ Displaystyle f (n) = 2f ((n-1) / 2) + 1 = 2 ((2l_ {1}) + 1) + 1 = 2l + 1}$

Наиболее элегантная форма решения следует из двоичного представления : может быть определена сама по себе 1-битным поворотом влево . Если один представлен в двоичном формате как , то решение задается как . Доказательство следует из представления as . ${\ displaystyle n}$${\ displaystyle f (n)}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle n = b_ {0} b_ {1} b_ {2} b_ {3} \ dots b_ {m}}$${\ displaystyle f (n) = b_ {1} b_ {2} b_ {3} \ dots b_ {m} b_ {0}}$${\ displaystyle n}$${\ displaystyle 2 ^ {m} + l}$

В закрытом виде решение для случая k = 2:

${\ Displaystyle е (п) = 1 + 2n-2 ^ {1+ \ lfloor \ ln n \ rfloor}}$

со скобкой Гаусса (функция округления)${\ displaystyle \ lfloor ... \ rfloor}$

Также существует решение в закрытой форме для случая k = 3.

Динамическое программирование является самым простым способом решить эту проблему в общем случае.

В этом методе используется формула рекурсии:

${\ Displaystyle е (п, к) = (е (п-1, к) + к-1) {\ bmod {п}}}$, С участием ${\ displaystyle f (1, k) = 0}$

что очевидно, если учесть, как изменяется номер последнего элемента при переходе от к . Этот метод имеет время выполнения , но существует другой подход как для малых, так и для крупных . Этот второй подход также использует динамическое программирование, но требует только времени выполнения . Снимает к ., 2 к ., ..., . Элементы за один шаг, а затем меняет нумерацию. ${\ displaystyle n-1}$${\ displaystyle n}$${\ Displaystyle О (п)}$${\ displaystyle k}$${\ displaystyle n}$${\ Displaystyle О (к \ журнал п)}$${\ Displaystyle \ lfloor п / к \ rfloor}$

выполнение

Следующий алгоритм рекурсивно реализует проблему в соответствии с приведенной выше формулой рекурсии для случая k = 2 и имеет время работы O (log (n)) .

int josephus(int n) 
{
    if(n == 1) 
        return 1;

    if((n%2) == 0) 
        return 2 * josephus(n / 2) - 1;

    if((n%2) == 1) 
        return 2 * josephus((n - 1) / 2) + 1;
}

Согласно закрытой формуле f (n) = 2 * l + 1 может быть указан следующий нерекурсивный алгоритм. Его время работы составляет O (1) .

int josephus(int n)
{
    m = floor( log2(n) );
    l = n - 2^m;
    j = 2*l + 1;

    return j;
}

литература

• Пол Ю: Развлекательная математика , Атлантический университет Флориды: факультет математики (доступен в формате PDF на английском языке; 868 kB)
• Уолтер Уильям Роуз Болл , Гарольд Скотт Макдональд Кокстер : Математические развлечения и эссе , Дувр, 1987. Страницы 32-36, ISBN 0-486-25357-0
• Рональд Л. Грэм , Дональд Э. Кнут и Орен Паташник : Конкретная математика: Фонд компьютерных наук , Массачусетс, 1994. Страницы 8-16, ISBN 978-0-201-55802-9
• Джеймс Дауди, Майкл Э. Мейс: перестановки Иосифа Флавия , Журнал комбинаторной математики и комбинаторных вычислений, том 6, 1989 г., стр. 125-130

веб ссылки

• Лоренц Дж. Хальбайзен: Проблема Иосифа Флавия .
• Игра Иосифа Флавия в Cut-the knot

Индивидуальные доказательства

1. ↑ Аренс, Mathematische Unterhaltungen und Spiele, Teubner 1901, глава 15, стр. 286ff
2. ^ Мориц Кантор, Лекции по истории математики, Том 2, стр. 332
3. ^ Проблема Флавий , MathWorld
4. ↑ Л. Хальбайзен, Н. Хунгербюлер: Проблема Иосифа Флавия , J. Théor. Nombres Bordeaux, Том 9, 1976, стр. 303-318.