Задача
Задача Иосифа Флавия.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.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь