ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 60911
Темы:    [ Периодичность и непериодичность ]
[ Итерации ]
[ Двоичная система счисления ]
Сложность: 5
Классы: 8,9,10,11
Название задачи: Последовательность Морса.
В корзину
Прислать комментарий

Условие

Последовательность Морса. Бесконечная последовательность из нулей и единиц

0110 1001 1001 0110 1001...

построена по следующему правилу. Сначала написан нуль. Затем делается бесконечное количество шагов. На каждом шаге к уже написанному куску последовательности приписывается новый кусок той же длины, получаемый из него заменой всех нулей единицами, а единиц — нулями.
а) Какая цифра стоит на 2001 месте?
б) Будет ли эта последовательность, начиная с некоторого места, периодической?
в) Докажите, что данная последовательность переходит в себя при замене каждого нуля на комбинацию 01, а каждой единицы — на комбинацию 10.
г) Докажите, что ни одно конечно слово из нулей и единиц не встречается в последовательности Морса три раза подряд.
д) Как, зная представление числа n в двоичной системе счисления, найти n-й элемент данной последовательности?


Ответ

а) 1; б) нет; д) n-й элемент данной последовательности совпадает по модулю 2 с $ \nu$(n) (суммой двоичных цифр числа n).

Источники и прецеденты использования

книга
Автор Алфутова Н.Б., Устинов А.В.
Год издания 2002
Название Алгебра и теория чисел
Издательство МЦНМО
Издание 1
глава
Номер 5
Название Числа, дроби, системы счисления
Тема Системы счисления
параграф
Номер 3
Название Двоичная и троичная системы счисления
Тема Двоичная система счисления
задача
Номер 05.073

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .