Задача 60911

Темы:    [ Периодичность и непериодичность ] [ Итерации ] [ Двоичная система счисления ]

Сложность: 5 Классы: 8,9,10,11 Название задачи: Последовательность Морса.

Условие

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

0110 1001 1001 0110 1001...

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

Ответ

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

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

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