Задача 60913

Темы:    [ Рекуррентные соотношения (прочее) ] [ Двоичная система счисления ]

Сложность: 4 Классы: 8,9,10,11

Условие

Задача Иосифа Флавия. n человек выстраиваются по кругу и нумеруются числами от 1 до n. Затем из них исключается каждый второй до тех пор, пока не останется только один человек. Например, если n = 10, то порядок исключения таков: 2, 4, 6, 8, 10, 3, 7, 1, 9, так что остается номер 5. Для данного n будем обозначать через J(n) номер последнего оставшегося человека. Докажите, что
а) J(2n) = 2J(n) - 1;
б) J(2n + 1) = 2J(n) + 1;
в) если n = (1b_{m - 1}b_{m - 2}...b₁b₀)₂, то J(n) = (b_{m - 1}b_{m - 2}...b₁b₀1)₂.

Решение

а) Если по кругу стоят числа 1, 2, ..., 2n, то вначале вычеркиваются все четные числа. Оставшиеся числа 1, 3, 5, ..., 2n - 1 снова подвергаются процедуре вычеркивания. k-ое число в этом списке имеет вид 2k - 1. После того, как из этого списка будут вычеркнуты все числа кроме одного, останется число с номером J(n), которое равно 2J(n) - 1.

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	5
Название	Числа, дроби, системы счисления
Тема	Системы счисления
параграф
Номер	3
Название	Двоичная и троичная системы счисления
Тема	Двоичная система счисления
задача
Номер	05.075