В бесконечной последовательности натуральных чисел $%a_{1}; a_{2}; a_{3} ...$% число $%a_{1}$% равно 1, а каждое следующее число $%a_{n}$% строится из предыдущего $%a_{n-1}$% по правилу: если у числа n наибольший нечетный делитель имеет остаток 1 от деления на 4, то $%a_{n}= a_{n-1}+1$%, если же остаток равен 3, то $%a_{n}= a_{n-1}-1$%. Докажите, что в этой последовательности а) число 1 встречается бесконечно много раз; б) каждое натуральное число встречается бесконечно много раз. (Вот первые члены этой последовательности: 1; 2; 1; 2; 3; 2; 1; 2; 3; 4; 3; ...).

задан 9 Апр '14 16:46

изменен 26 Ноя '14 17:44

Хорошая задача!

(9 Апр '14 19:07) falcao
10|600 символов нужно символов осталось
1

Попробуем найти закономерность в строении данной последовательности. Значение $%a_n=1$% получается при $%n\in\{1;3;7;15;\ldots\}$% -- это наводит на мысль, что таковы числа вида $%2^k-1$% при $%k\ge1$%. Все они имеют двоичное представление вида $%11\ldots1_2$% из одних единиц.

Значение $%a_n=2$% получается при $%n\in\{2;4;6;8;12;14;16;\ldots\}$%. Двоичное представление этих чисел таково: $%10_2$%, $%100_2$%, $%110_2$%, $%1000_2$%, $%1100_2$%, $%1110_2$%, $%10000_2$% и так далее. Во всех случаях мы наблюдаем группу из одной или нескольких единиц, за которой следует группа из одного или нескольких нулей.

Значению $%a_n=3$% соответствуют $%n\in\{5;9;11;13;17;\ldots\}$%. Их двоичная запись: $%101_2$%, $%1001_2$%, $%1011_2$%, $%1101_2$%, $%10001_2$% -- налицо три группы "однородных" цифр. Проверим также число $%10$%, которое имеет вид $%1010_2$%. Значение $%a_{10}=4$%, и запись состоит из 4 групп "однородных" цифр.

Это позволяет сформулировать такую гипотезу: если записать число $%n$% в двоичной системе счисления и посмотреть на количество чередующихся групп из единиц и нулей, то их количество равно $%a_n$%. Доказать её можно методом математической индукции, где начальные значения уже проверены.

Рассмотрим число $%n > 1$%, для которого мы хотим проверить нашу гипотезу, считая, что для меньших значений она справедлива. Будем различать два случая: если "списать" в конце все нули, которыми оканчивается двоичная запись $%n$%, то на конце будет стоять либо 01, либо 11. Эти случаи в точности соответствуют тому, каков остаток при делении на 4 даёт наибольший нечётный делитель числа $%n$%: один или три.

В первом из случаев после вычитания единицы из числа $%n$%, равного $%\ldots010\ldots0_2$%, получается $%\ldots001\ldots1_2$%, откуда видно, что в записи числа $%n$% количество чередующихся групп на единицу больше, чем у числа $%n-1$%, причём независимо от того, были ли после 01 на конце нули, или их не было. Это соответствует определению, согласно которому должно быть $%a_n=a_{n-1}+1$%. Особо отметим случай, когда $%n$% является степенью двойки: двоичная запись имеет вид $%10\ldots0_2$%, где нули на конце имеются ввиду $%n > 1$%; при этом $%n-1$% записывается одними единицами, и закономерность соблюдается.

Во втором случае, когда после удаления нулей в конце остаётся 11, после вычитания единицы из $%n$%, записанного как $%\ldots110\ldots0_2$%, получается $%\ldots101\ldots1_2$%, и здесь происходит уменьшение на единицу количества чередующихся групп у $%n$% по сравнению с $%n-1$%. Это охватывает и случай, когда после 11 следовали нули, и случай, когда их не было. Описанный эффект соответствует равенству $%a_n=a_{n-1}-1$%, что завершает доказательство.

Ввиду того, что чисел с заданным количеством чередований единиц и нулей в двоичной записи бесконечно много, получаются все требуемые в условии выводы.

ссылка

отвечен 9 Апр '14 19:06

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×3,936

задан
9 Апр '14 16:46

показан
1562 раза

обновлен
26 Ноя '14 17:44

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

по почте:

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

по RSS:

Ответы

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

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