Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/dubna/2013/courses/kanel.htm
Дата изменения: Sun Jul 28 10:48:11 2013
Дата индексирования: Sun Apr 10 10:11:08 2016
Кодировка: koi8-r
Поисковые слова: eta carinae
Dubna-2013: Belov
На главную страницу ЛШСМ-2013 К списку курсов ЛШСМ-2013

Алексей Яковлевич Белов

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

А.Я.Белов планирует провести 3-4 занятия

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

Например, известно, что следующие классы слов почти эквивалентны:

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

Обобщение этой теоремы дает задача Арнольда о перекладывания отрезков,

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