Период бесконечной последовательности

mushroom

Известно, что бесконечная последовательность из 0 и 1 имеет период длины не больше чем n и не имеет предпериода. Каково минимальное число первых символов, которое нужно знать, чтобы определить период последовательности? Заранее спасибо.

margo11

предлагаю гипотезу: ответ 2n-2

Gennadi23

n-2 --- необходимый минимум!
Пример:
последовательность периода n-1
(n-2) единиц, 0, (n-2) единицы, 0, ...
и последовательность периода n
(n-2) единицы, 0, (n-1) единица, 0, ...
Отличаются только в (2n-2)-ом знаке
Достаточность пока не доказана.

jasmin030185

и не имеет предпериода

?

dimaxd

Это значит, что период начинается с начала последовательности.

jasmin030185

И я о том же. Пример Барса не подходит.

jasmin030185

Упсс, дошло.

afony

n-2 достаточно. Сейчас пишу решение. Надеюсь, что не ошибся

a-knyazev

Пишу еще раз:
Первая последовательность суть n-2) единицы и один 0) в периоде
Вторая последовательность суть n-2) единицы, один 0 и одна 1) в периоде

Gennadi23

Это был я

afony

) Если 1 - период, то 2n-2 очевидно достаточно.
2) Пусть известно, что из того, что число m<= k<=n-3 является периодом (а 1...m-1 - нет) для первых 2n-2 чисел следует, что m - период для всей последовательности.
3) Докажем, что и для m=k+1 верно 2). Предположим, что помимо m существует другой период p>m; p<=n, который является периодом для всей последовательности. Если p делится на m, то m - период. Пусть p на m не делится. Поскольку p+m<=2n-2, то p(mod m) - тоже период для первых 2n-2 чисел, но 0<p(mod m)<m, противоречие (т.к. мы предполагали, что 1...m-1 - не периоды для 2n-2 чисел).
Т.е. для m<=n-2 достаточно проверить первые 2n-2 числа.
Предположим, что и n, и n-1 - периоды для первых 2n-2 чисел, но тогда первое равно второму, второе - третьему и т.д., т.е. период = 1.
Таким образом если n-1 - период для первых 2n-2 чисел, а все меньшие m нет, то n-1 - период для всей последовательности. Если же ни одно m<=n-1 не подходит, то период n.

Gennadi23

В целом, согласен. Более того, если m является периодом для первых n+m-1 элемента, то m является периодом и для всей последовательности.
Тонким местом доказательства является
то p(mod m) - тоже период для первых 2n-2 чисел

Это верно, но требует неких усилий для доказательства.

afony

Ну так надо же оставить кому-нибудь сладкое

Gennadi23

Но вообще-то это следует из того, что если слово b неразложимо, и bd=db, то d = b^k

afony

Как-то умно ты излагаешь, я не врубаюсь. Чтобы доказать, что a_l=a_{l+p(mod m)} возьмем
a_{l(mod m)}. Тогда l(mod m)+p<=2n-2, т.е. a_l=a_{l(mod m)}=a_{l(mod m)+p}=a_{l+p(mod m)} , т.к.
l+p(mod m)-(l(mod m)+p) делится на m.

Gennadi23

Излагаю я в теминах дискретной математики (кодирование там все такое, автоматы....)
А приведенное тобой доказательство --- оно и есть д-во. Вобщем, никто и не говорил, что тут надо расписываться на ... листов.

afony

А никто и не просит, чтобы ты расписывал на ... листов. Просто если хочешь, чтобы тебя понимали, пиши простым языком. Я учил дискру в рамках университетского курса, но с используемой тобой терминологией не встречался. Конечно приятно щегольнуть знанием математических терминов, но дискуссия должна вестись на понятном всем языке.

Gennadi23

Извини, но я уже не помню, что в курсе было в основном курсе, а что нет Давно это было
Следующий раз постараюсь выражаться понятнее.
Спасибо за замечание.

mushroom

Спасибо Огромное за подробное решение!
Интересна еще такая постановка:
Если рассмотреть все множество последовательностей с
периодом не большим n и не имеющих предпериода.
Мощность этого множества асимптотически равна 2^{n+1}
Есть и точная формула, если интересует.
Рассмотреть также функцию f на этом множестве,
определяюмую так:
f(a) = минимальное количество начальных символов последовательности a
по которым можно определить период(т.е. однозначно восстановить
последовательность)
Вопрос:
какова асимптотика мат.ожидания f
(т.е. среднего арифметического по всему множеству)?
Программа вычисляет для n <= 12.
Резулттат получается примерно такой:
n+1 <= Mf <= n+2
Было бы здорово, если бы кто-нибуюь подсказал,
как подступиться к решению.
Заранее спасибо,
искренне ваш Anonymous

afony

Пожалуйста (надеюсь, спасибо было не только у ) . несколькими сообщениями выше давал значение f(a)=n-m+1, где m - период a. Т.е. зная точное кол-во последовательностей периода строго m можно все посчитать. Или вопрос в том, как получить простую формулу?
2: Пожалуйста. Я и сам толком не помню, что было в основном курсе . Рад выслушать встречные замечания, если они по существу.

mushroom

Я наверное плохо сформулировал.
Точные оценки для f(a как мы знаем такие:
n <= f(a) <= 2n-2
Таких а, что f(a) = 2n-2 всего 4 для любого n.
Имменно:
(0..001)^{\infty} - длина периода = n
(0..01)^{\infty} - длина периода = n-1
(1..110)^{\infty} - длина периода = n
(1..10)^{\infty} - длина периода = n-1
Количество a таких, что f(a) = n можно получить
по формуле включений-исключений.
Так как f(a) = n <=>
1) у на чала a длины n префиксы и суффиксы одинаковой длины не равны.
2) a = 0000.... или a=1111.....
Как искать количство a, таких что f(a) = n+m пока не понятно...
Пока вроде все...:)

afony

Нет, сформулировал ты нормально, просто я немного стормозил . Спасибо за разъяснения.
Похоже, точное значение f(a) проще всего считать так: брать первые ее M членов, и смотреть, какие возможные значения периода<=n у этих первых M членов. Наименьшее M, для которого возможное значение периода всего одно, и есть f(a). Это, наверное, и так было известно. Но думаю, что для конкретного a проще способа нет.
Могу предложить точную на классе всех последовательностей a с периодом m оценку f(a). Именно, f(a)<=max_{k: m<k<=n}(m+k-НОД(m,k. Доказательство:
Пусть задана некоторая последовательность a с периодом m<=n. Пусть есть число k, m<k<=n, зададимся вопросом: Какое наименьшее количество M ее первых членов нужно взять, чтобы
k и m не могли быть одновременно периодами? Ответ: M=m+k-НОД(m,k). Действительно, пусть k и m - периоды среди первых M=m+k-НОД(m,k) членов последовательности. Тогда a_{k mod(m)}=a_1, a_{(k+1) mod(m)}=a_2, ... , a_{(k+m-НОД(m,k mod(m)}=a_{(1+m-НОД(m,k mod(m) } (*). Из этих равенств вытекает, что НОД(m,k) - тоже период. Это тонкое место док-ва и требует дополнительных мыслительных усилий ( ). Проще всего это понять, расставив числа a_1, ... , a_m по кругу и соединять отрезком те из них, которые находятся на расстоянии k(mod m тогда получим НОД(k,m) групп ломаных, соединяющих наборы точек (a_j,a_{j+НОД(m,k)},...,a_{m-НОД(m,k)+j}).
Если же M меньше m+k-НОД(m,k число a_{(m+k-НОД(m,k mod(m)} в равенствах (*) фигурировать не будет. Тогда положим все числа a_j (0<j<=m кроме него равными 0, а его - равным 1, получим пример M чисел, у которых по крайней мере два периода: m и k.
Оставить комментарий
Имя или ник:
Комментарий: