ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 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 = (1bm - 1bm - 2...b1b0)2, то J(n) = (bm - 1bm - 2...b1b01)2.


Решение

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

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .