|
n человек выстраиваются по кругу и нумеруются числами от 1 до n. Затем из них исключается каждый второй до тех пор, пока не останется только один человек. Для данного n будем обозначать через J(n) номер последнего оставшегося человека. Докажите, что J(2n) = 2J(n) − 1; J(2n + 1) = 2J(n) + 1. задан 11 Июл '15 5:06 
sapere aude |
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
11 Июл '15 5:06
показан
1218 раз
обновлен
11 Июл '15 5:22
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Это сразу следует из общего факта: двоичная запись J(n) получается из двоичной записи n перестановкой самой первой единицы в конце числа. Доказательство несложное: если число равно $%2^n+k$%, то k первых удаляемых будут иметь номера 2, 4, ... , 2k. Останется степень двойки, а при ней всегда "выживает" первый. Он имеет номер 2k+1. Это и есть искомое правило, а из него оба факта прямо следуют.