ИСТИНА |
Войти в систему Регистрация |
|
ИСТИНА ЦЭМИ РАН |
||
Планируется рассказать про свойства символьных последовательностей, и замечательные теоремы с ними связанные и их обобщения. Например, известно, что следующие классы слов почти эквивалентны: буквы a,b самым тщательным образом перемешаны, т.е. в кусках одинаковой длины количество символов каждого сорта отличается не более чем на 1; количество различных подслов длины n равно n+1, т.е. минимально возможное; слово получается из поворота окружности на величину α при фиксации буквой a попадания на дугу длины α. Обобщение этой теоремы дает задача Арнольда о перекладывания отрезков, Красивые элементарные факты о поведении слов, в которые добавляется не слишком много запретов, отражаются на теореме Голода-Шафаревича. Наверное, стоит упомянуть также теорему Ширшова о высоте. На ленте напечатаны цифры от 1 до 9. Тогда в ней можно вырезать 10 стозначных чисел, идущих в порядке убывания, либо какая-то комбинация цифр повторится много раз подряд.