ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Задача 60913
Условие
Задача Иосифа Флавия.
n человек выстраиваются по кругу и
нумеруются числами от 1 до n. Затем из них исключается каждый
второй до тех пор, пока не останется только один человек.
Например, если n = 10, то порядок исключения таков: 2, 4,
6, 8, 10, 3, 7, 1, 9, так что остается номер 5.
Для данного n будем обозначать через J(n) номер последнего
оставшегося человека. Докажите, что
Решениеа) Если по кругу стоят числа 1, 2, ..., 2n,
то вначале вычеркиваются все четные числа. Оставшиеся числа 1,
3, 5, ..., 2n - 1 снова подвергаются процедуре
вычеркивания. k-ое число в этом списке имеет вид 2k - 1. После
того, как из этого списка будут вычеркнуты все числа кроме
одного, останется число с номером J(n), которое равно 2J(n) - 1.
Источники и прецеденты использования
|
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|
![]() |
Проект осуществляется при поддержке