n человек выстраиваются по кругу и нумеруются числами от 1 до n. Затем из них исключается каждый второй до тех пор, пока не останется только один человек. Для данного n будем обозначать через J(n) номер последнего оставшегося человека. Докажите, что J(2n) = 2J(n) − 1; J(2n + 1) = 2J(n) + 1.

задан 11 Июл '15 5:06

3

Это сразу следует из общего факта: двоичная запись J(n) получается из двоичной записи n перестановкой самой первой единицы в конце числа. Доказательство несложное: если число равно $%2^n+k$%, то k первых удаляемых будут иметь номера 2, 4, ... , 2k. Останется степень двойки, а при ней всегда "выживает" первый. Он имеет номер 2k+1. Это и есть искомое правило, а из него оба факта прямо следуют.

(11 Июл '15 5:22) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×979
×896
×121
×30

задан
11 Июл '15 5:06

показан
464 раза

обновлен
11 Июл '15 5:22

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru