Комбинаторика слов и соотношения в кольцах. Лекция 3

Планируется рассказать про свойства символьных последовательностей, и замечательные теоремы с ними связанные и их обобщения.
Например, известно, что следующие классы слов почти эквивалентны:

• буквы $a$, $b$ самым тщательным образом перемешаны, т.е. в кусках одинаковой длинны количество символов каждого сорта отличается не более чем на $1$;
• количество различных подслов длины $n$ равно $n+1$, т.е. минимально возможное;
• слово получается из поворота окружности на величину $\alpha$ при фиксации буквой $a$ попадания на дугу длины $\alpha$.

Обобщение этой теоремы дает задача Арнольда о перекладывания отрезков.
Красивые элементарные факты о поведении слов в которые добавляется не слишком много запретов, отражаются на теореме Голода–Шафаревича. Наверное, стоит упомянуть также теорему Ширшова о высоте. На ленте напечатаны цифры, от $1$ до $9$. Тогда в ней можно вырезать $10$ стозначных чисел идущих в порядке убывания либо какая то комбинация цифр повторится много раз подряд.