148
правок
Изменения
→Свойства периода
|statement= Если у строки есть [[Основные определения, связанные со строками#Отношения между строками|период]] длины <tex>k</tex>, то у нее есть период длины <tex>kx</tex>, где <tex> x \in N</tex>.
|proof=
Пусть <b>длина</b> строки равна <tex>n</tex>, сама <b>строка</b> {{---}} <tex>\alpha</tex>.<br/>Доказательство будем вести по <b>индукции по числу</b> <tex>x</tex>.<br/>
<ol>
<li>Для <tex> x = 1 </tex> утверждение очевидно.</li>
<li>Пусть верно для <tex>x \leqslant m</tex>.</li>
<li>Докажем, что верно для <tex>x = m + 1</tex>.<br/>
Из <b>определения периода</b> имеем, что<br/> <ul><tex>\forall i = 1 \ldots n - k</tex>, <tex>\alpha [i] = \alpha[i + k]</tex>,<br/ul>а из <b>предположения</b> индукции, что<br/> <ul><tex>\forall i = 1 \ldots n - km</tex>, <tex>\alpha [i] = \alpha[i + mk]</tex><br/ul>
Значит получаем, что<br/>
следовательно<br/>
</ol>
Утверждение доказано.
|statement= Если у строки есть периоды длины <tex>p</tex> и <tex>q</tex>, то НОД<tex>(p, q)</tex> также является периодом этой строки.
|proof=
Пусть <b>строка</b> равна <tex> \alpha </tex>.<br/>Доказательство будем вести <b>по индукции по парам</b> <tex>(p, q)</tex>, где <tex> p \geqslant q </tex>, а <tex>(p, q) + 1 = \begin{cases} (p, q + 1), & q < p;\\
(p + 1, 1), & q = p.\end{cases}</tex><br/>
<ol>
<li>Для <tex> (1, 1) </tex> утверждение очевидно.</li>
<li>Пусть верно для всех <b>пар меньших</b> <tex>(p, q)</tex>.</li>
<li>Докажем, что верно для <tex>(p, q)</tex>.<br/>
Из <b>определения периода</b>:<br/><ul><tex>\forall i = 1 \ldots n - p</tex>, <tex>\alpha [i] = \alpha[i + p] = \alpha[i + q]</tex>.<br/ul>Значит <ul><tex>\forall i = q \ldots n - p</tex>, <tex>\alpha [i + q] = \alpha[i + p]</tex><br/ul>
Сделаем замену <tex>j = i + q</tex> и получим, что<br/>
<ul><tex>\forall j = 1 \ldots n - (p - q)</tex>, <tex>\alpha [j] = \alpha[j + (p - q)]</tex><br/ul>Получили новый <b>период длины</b> <tex>p - q</tex>. Из предположения известно, что НОД<tex>(p - q, q)</tex> {{---}} период строки, но НОД<tex>(p - q, q)</tex><tex>=</tex>НОД<tex>(p, q)</tex>.</li>
</ol>
Следовательно утверждение доказано.
