[Nik]

Помимо приятных задач про натуральные числа имеются весьма простые с виду задачи про последовательности символов какого-либо конечного алфавита (например, последовательности из «0» и «1»). Поскольку терминология и обозначения менее распространены, задачке будет предпослано некое вступление.
Определения и обозначения.
Рассматриваются (непустые) конечные и бесконечные последовательности из символов «0» и «1» (далее просто «последовательности»). Последовательности a1a2… и b1b2… считаем равными тогда и только тогда, когда a1 = b1, a2 = b2, …. Конечную последовательность будем называть словом. Последовательность, полученную из слова X и (возможно, бесконечной) последовательности Y путем приписывания последовательности Y справа к слову X, будем обозначать XY. Очевидно, если X, Y – слова и Z – последовательность, то (XY)Z = X(YZ), поэтому в подобных записях скобками будем пренебрегать. Слово Y называется подсловом последовательности A, если для некоторого слова X и последовательности Z последовательность A = XYZ, или A = YZ, или A = XY, или A = Y. Слово B назовем n-кратным повтором, если n – максимальное натуральное число, для которого слово B = CC...C (n раз), где С – некоторое слово. Для каждой последовательности A степенью периодичности p(A) назовем такое число, что последовательность A содержит в качестве подслова некоторый n-повтор и не содержит в качестве подслова никакого (n+1)-повтора. Если для последовательности A такого числа нет, считаем, что p(А) = бесконечность.
Неформально, последовательность имеет степень периодичности n, если в ней некоторый фрагмент повторен n раз подряд, но нет никакого фрагмента, который повторен подряд большее количество раз.
Задача.
Найти степень периодичности следующей последовательности:
an = 0, если в двоичной записи числа n содержится четное число нулей; иначе an = 1.
Интернет разрешен.

Это сообщение отредактировал Nik - 20/12/2006, 13:42

[Apri1]

Посмотрим для начала на эту последовательность. Вот первые знаки начиная с a1

0100110100101100110100110010110...

В глаза ничего не бросается Что бы бросилось поместим знаки отвечающие за числа между соседними степенями двойки в отдельные строки

В1 - 0
В2 - 10
В3 - 0110
В4 - 10010110
В5 - 0110100110010110...

Вот теперь некоторая регулярность в последовательности видна... В конце каждой строки стоит ровно предыдущая В начале предыдущая с единицами и нулями поменяными местами.

То есть наша последовательность строится таким образом
А = (В1)(В2)(В3)... Где В1 = 0 а В(n+1) = ~Bn(Bn)

При желании это наблюдение легко доказывается...

У меня такое ощущение что должно не сложно доказываться и то что р(А) = 2 но может быть это только ощущение

[Nik]

Гуд.
Ответ р(А) = 2 , конечно, напрашивается: меньше быть не может, а, если больше, то к чему такие задачки
Так что дело в доказательстве. Сложность - на "олимпиадном" уровне. Подсказка: найти в этой последовательности еще одну "регулярность".

Имеется более "фундаментальный" результат: в алфавите из трех (и более) букв существует бесконечная последовательность "без повторений" (т.е. с р = 1). Что само по себе любопытно.
"Доказательство предоставляется читателю"

Это сообщение отредактировал Nik - 21/12/2006, 17:11