Майская проектная программа по математике и теоретической информатике

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

Детальное описание программы

Школьники отбирались на программу по результатам заочных частей проектов и собеседований.

Результатом работы являлся текст, написанный и защищенный школьником или командой школьников полностью самостоятельно. Самым важным требованием к тексту являлась корректность и верифицируемость. 

Программа не являлась соревновательной: были награждены все школьники, которые вовремя написали и отправили на рецензию текст, а также сделали доклад по результатам работы. Отдельно были награждены тексты, в корректности которых рецензенты смогли убедиться до обозначенных сроков.

Проекты

1. Как вода точит камень
2. Кусочно-евклидова динамика
3. Общение и информация

Подробное описание проектов
 

1. Как вода точит камень

Описание: Проект посвящен двум сюжетам из двумерной статистической физики, в которой около двадцати лет назад произошел настоящий прорыв, отголоски которого доносятся до сих пор: модели перколяции (протекания) и самоизбегающих блужданий (несамопересекающихся ломаных).

Для того, чтобы попасть на программу, участникам нужно было пройти тест и решить почти все задачи, предложенные на заочном этапе. В результате конкурса было приглашено 18 человек со всей России.

Задачи на программе были разделены на вводные (которые знакомят с основными понятиями проекта) и основные (которые раскрывают проблематику проекта). Для решения задач можно было объединяться в команды из двух-трёх человек.

По одной или нескольким из основных задач школьники писали учебно-исследовательские работы. Выбор задачи был предложен самим участникам, но предлагалось учитывать рекомендации руководителей (многие решили несколько основных задач). Основным требованием к тексту работы были корректность и верифицируемость (как в научных статьях), и в половине работ этого требования удалось достичь. Работа над текстом велась под руководством преподавателей проекта, но все тексты были написаны школьниками самостоятельно. На финальном этапе все работы были переданы на внешнее рецензирование (текст проверяли и оценивали математики, не имеющие отношение к программе). После получения рецензий у участников была возможность обсудить замечания рецензентов с преподавателями проекта и исправить работы.

По первому сюжету (модели протекания) работы написали две команды: Власов Алексей, Литвинов Марк и Волович Василий, Ефимов Артем, Карпов Александр. По второму сюжету (несамопересекающимся ломаным) работы написали также две команды: Васильев Иван, Ефремов Игорь, Янин Алексей и Сeвидов Артем, Журавлёв Дмитрий, Труфанова София. Ниже публикуем тексты работ с кратким описанием того, что в них сделано.

Участники проекта решили много интересных задач. Никита Ильин сделал доклад с решением сложной задачи об одновременном протекании. Браулов Григорий, Кирюшин Николай и Кузьмин Максим, Тармаев Александр исследовали наблюдаемую в модели несамопересекающихся ломаных, а Векшин Кирилл и Ерыкалкин Георгий — наблюдаемую в модели протекания.

Подготовленные участниками работы:

Теорема о количестве кракозябр фиксированной длины
Математическая публикация¹. Максимальное продвижение в задачах проекта про самоизбегающее блуждание.
Авторы: Васильев Иван, Ефремов Игорь, Янин Алексей

Как вода точит камень
Математический этюд¹. Доступное изложение доказательства основной теоремы проекта про перколяцию
Авторы: Власов Алексей, Литвинов Марк

Монотонные семейства бихроматических раскрасок
Математическая публикация¹. Результат о монотонных булевых функциях на многомерном кубе.
Авторы: Волович Василий, Ефимов Артем, Карпов Александр

Связь тождества треугольника и несамопересекающихся ломаных
Математический этюд¹. Доступное изложение идейной части доказательства основной теоремы проекта про самоизбегающее блуждание.
Авторы: Сeвидов Артем, Журавлёв Дмитрий, Труфанова София

Условия и решения задач (html-версия)

Результаты сдачи задач 

2. Кусочно-евклидова динамика

Описание: Проект рассматривал сохраняющие расстояния перекладывания отрезков или многоугольников как динамические системы. К очному участию в проекте были приглашены 15 человек из разных городов России — по результатам отборочного тура, включавшего изучение нового математического сюжета и решение серьезных задач. Очный этап состоял из трех треков.

В рассматриваемом разделе теории динамических систем основным модельным примером является вращение окружности (которое можно также представить как перекладывание двух отрезков). Итерируя апериодическое перекладывание двух отрезков, получаем (на n-ной итерации) перекладывание n+1 отрезков. Известная теорема о трех промежутках (решение гипотезы Штейнгауза) состоит в том, что длины этих отрезков могут принимать только 2 или 3 значения. Арина Смирнова усилила этот результат, получив выражение для трех длин промежутков в терминах цепных дробей.

Бесконечные апериодические последовательности из нулей и единиц, которые можно получить в качестве маршрутов при перекладывании двух отрезков, совпадают с последовательностями Штурма. Последние можно определить комбинаторно: Штурмова последовательность — это последовательность, в которой число подслов длины n равно n+1. А сколько слов длины n может встретиться хотя бы в одной из Штурмовых последовательностей? Ответ на этот вопрос намечен в работе Сергея Хейфеца, Ольги Кармановой и Владислава Гынгазова — предложенный подход опирается на интересную динамическую систему на торе.

В последовательностях Штурма встречаются палиндромы любой длины. Изящное геометрическое доказательство этого факта предложено в работе Андрея Черыдцева, Тимура Шамазова и Тагира Юсупова. Авторы также нашли число палиндромов данной длины — один или два в зависимости от четности длины.

Из равномерного распределения орбит при иррациональном повороте окружности можно вывести закон распределения для первой цифры числа 2^n (закон Бенфорда). Маргарита Шевцова задалась вопросом: сколько слов длины n, состоящих из ненулевых десятичных цифр, могут быть получены такой процедурой: рассматриваем конечную геометрическую прогрессию и от каждого члена прогрессии оставляем только первую цифру. Маргарита получила как верхнюю, так и нижнюю оценки. На самом деле, это только первый этап в решении более амбициозной задачи: для каждого n рассмотрим первую цифру числа n!; какие конечные подпоследовательности (из идущих подряд членов) и насколько часто встречаются в полученной последовательности цифр? Желаем Маргарите успеха в реализации этого далеко идущего проекта.

Наиболее амбициозный трек проекта был связан с внешними бильярдами. Елизавета Манжула, Валерий Самылкин и Александр Срибняк поставили компьютерные эксперименты и получили интересные гипотезы относительно внешних бильярдов вне рациональных трапеций. Андрей Дмитренко, Владислава Синицына и Маргарита Скачкова приблизились к полному описанию динамики внешнего бильярда вне правильного пятиугольника. Хотя этому сюжету посвящены престижные публикации, и качественное поведение системы считается в целом понятым, последнюю точку еще предстоит поставить, а у авторов есть новые — насколько мы можем судить — и интересные находки на этом классическом поле. Последние работы (касающиеся внешнего бильярда) не завершены, поскольку не хватило времени - глубина и техническая сложность задач не позволила представить окончательные результаты на смене. Но работа продолжается и должна привести к интересным публикациям.

Состоявшаяся смена положила начало научной коллаборации с долгосрочной и прорывной повесткой.

Подготовленные участниками работы:

О длинах интервалов между числами вида {k}_α
Математическая публикация¹. Доказано усиление известной теоремы о трех промежутках (=гипотезы Штейнгауза). А именно, вычислены длины этих промежутков.
Автор: Смирнова Арина

Оценка сверху на количество маршрутов при повороте окружности на произвольный угол
Математический этюд¹. Намечен интересный геометрический подход к оценке сверху на число подслов, встречающихся в хотя бы одной Штурмовой последовательности.
Авторы: Хейфец Сергей, Карманова Ольга, Гынгазов Владислав

Палиндромы в последовательностях Штурма
Математическая публикация¹. Приведено изящное геометрическое доказательство существования палиндромов в последовательностях Штурма
Авторы: Чердынцев Андрей, Шамазов Тимур, Юсупов Тагир

Исследование слов в последовательности первых цифр числа CAn
Математическая публикация¹. Получены и строго обоснованы верхние и нижние оценки на число слов в алфавите {1,...,9}, которые можно получить из геометрических прогрессий, взяв у каждого члена по первой цифре.
Автор: Шевцова Маргарита

Руководитель проекта, отмечая высокий уровень работ, принял решение также выдать сертификаты участникам, чьи работы не прошли рецензирования в рамках смены (см. правила программы)

Внешние бильярды вне рациональных трапеций
Авторы: Ярослав Орлов, Елизавета Манжула, Александр Срибняк

Исследование внешнего бильярда вне правильного пятиугольника*
*Авторы не дали согласия на выкладывание полного текста на сайте
Авторы: Андрей Дмитренко, Маргарита Скачкова,  Владислава Синицына

Ведение к очной части

Решаемые участниками задачи

3. Общение и информация

Описание: Участникам было предложенны задачи по коммуникационной сложности. В самой простой постановке коммуникационная сложности изучает игру для двух игроков, Ани и Бори, которые должны вычислить некоторую функцию f(x,y), если Аня знает только x, а Боря - только y. Для того, чтобы вычислить f(x,y) игрокам приходится общаться между собой посылая друг другу битовые сообщения. Коммуникационная сложность изучает минимальное количество сообщений, которого будет достаточно, чтобы оба игрока узнали f(x,y) для любых значений x и y. Более подробно об этом можно прочитать в тексте проекта.

Для того, чтобы попасть на смену, участникам нужно было пройти тест и решить почти все письменные задачи. В результате конкурса на смену было приглашено 18 человек со всей России.

На смене участникам было предложено заниматься полудуплексной коммуникационной сложность, в которой изучается количество сообщений Ани и Бори при использовании коммуникационного устройства напоминающего рацию. Более подробно об этом можно прочитать в тексте проекта. Задачи на смене были разделены на вводные (задачи, заведомо имеющие простое и понятное решение) и исследовательские (задачи, решение которых требует значительно больше усилий и времени, и в том числе открытые задачи, решение которых неизвестно). Для решения исследовательских задач можно было объединяться в команды из двух-трёх человек.

В результате смены участниками были решены две, насколько нам известно, открытые задачи: верхняя оценка на функцию внутреннего произведения в полудуплексной модели с тишиной (задача 39а, первое решение от Татьяны Гладыш) и верхняя оценка на функцию внутреннего произведения в полудуплексной модели с нулём (задача 39б, первое решение от команды в составе Анна Коган, Варвара Прозорова, Лев Шпрайдун).

В конце смены участникам было предложено записать решение одной из решённых ими исследовательских задач в виде теоремы с доказательством. Выбор задачи для записи (многие участники решили значительно больше одной исследовательской задачи) был предложен самим участникам, но предлагалось учитывать рекомендации руководителей. Текст должен был быть оформлен так, чтобы максимально приблизиться к текстам научных статей (строгое и подробное изложение, чёткие формулировки, корректность и завершённость доказательства). Работа над текстом велась под руководством преподавателей проекта, но все тексты были написаны школьниками самостоятельно. На финальном этапе все работы были переданы на внешнее рецензирование (текст проверяли и оценивали математики, не имеющие отношение к смене). После получения рецензий у участников была возможность обсудить замечания рецензентов с преподавателями проекта и исправить замечания.

​Подготовленные участниками работы:

Доказательство верхней оценки для функции ПЕРЕСЕЧЕНИЕ_n в полудуплексной модели с тишиной
Математическая публикация¹. Представлен коммуникационный протокол для функции пересечения множеств в полудуплексной модели с тишиной со сложностью. Полученная оценка совпадает с лучшей известной верхней оценкой с точностью до аддитивного члена меньшего порядка.
Автор: Анастасия Баркина

Верхняя оценка для функции РАВНО_n в модели с нулем
Математическая публикация¹. Представлен коммуникационный протокол для функции равенства в полудуплексной модели с нулём. Полученная оценка совпадает с известной нижней с точностью до аддитивного члена меньшего порядка.
Автор: Анастасия Гоге

Партия в строки
Математическая публикация¹. Доказана верхняя оценка на коммуникационную сложность игры Карчмера-Вигдерсона для функции чётности в полудуплексной модели с нулём.
Автор: Анастасия Мозголина

Верхние оценки на полудуплексные протоколы c нулем для функций РАВНО_n, БОЛЬШЕ_n
Математическая публикация¹. Доказана верхняя оценка на коммуникационную сложность функции БОЛЬШЕ в полудуплексной модели с нулём. Доказательство выполнено через сведение к задаче вычисления функции РАВНО. Полученная верхняя оценка совпадает с нижней с точностью до аддитивного члена меньшего порядка.
Автор: Алексей Волков

Верхняя оценка для сложности функции РАВНО_n в полудуплексной модели с тишиной
Математическая публикация¹. Доказана верхняя оценка на коммуникационную сложность функции равенства в полудуплексной модели с тишиной. Полученная верхняя оценка совпадает с нижней с точностью до аддитивного члена меньшего порядка.
Автор: Данила Расторгуев

Верхняя оценка для отношения R_{MOD_{(p,n)}} в полудуплексной модели с тишиной
Математическая публикация¹. Доказана верхняя оценка на коммуникационную сложность игры Карчмера-Вигдерсона дли функции сравнения по модулю p для произвольного p > 1 в полудуплексной модели с тишиной.
Автор: Иван Васильев

Upper bounds on half-duplex communication complexity of the function GT_n.
Математическая публикация¹. Доказана верхняя оценка на коммуникационную сложность функции БОЛЬШЕ в полудуплексных моделях с тишиной и с нулём. Доказательство выполнено через сведение к задаче вычисления функции РАВНО. Полученные верхние оценки совпадают с нижними с точностью до аддитивного члена меньшего порядка. Работа выполнена на английском языке по желанию авторов.
Авторы: Иван Лебедев, Лидия Симонова

Half duplex communication complexity of GREATER_n
Математическая публикация¹. Доказана верхняя оценка на коммуникационную сложность функции БОЛЬШЕ в полудуплексной модели с тишиной. Доказательство выполнено через сведение к задаче вычисления функции РАВНО. Полученная верхняя оценка совпадает с нижней с точностью до аддитивного члена меньшего порядка. Работа выполнена на английском языке по желанию авторов.
Авторы: Иван Лебедев, Лидия Симонова

Коммуникационная сложность
Математическая публикация¹. Доказана верхняя оценка на коммуникационную сложность функции равенства в полудуплексных моделях с тишиной и с нулём. Полученные верхние оценки совпадают с нижними с точностью до аддитивного члена меньшего порядка.
Автор: Кирилл Лебедев

Верхняя оценка для заданного отношения в классической модели
Математическая публикация¹. Доказана верхняя оценка на коммуникационную сложность игры Карчмера-Вигдерсона для пороговой функции Thr2 в классической коммуникационной модели.
Автор: Константин Жар

Верхняя оценка глубины полудуплексного протокола общения с нулём для функции ВП_n
Математическая публикация¹. Представлен коммуникационный протокол для функции внутреннего произведения в полудуплексной модели с нулём со сложностью 7n/8+O(1). Это является новым результатом, до этого лучшей известной оценкой была тривиальная оценка n+1.
Авторы: Лев Шпрайдун, Варвара Прозорова, Анна Коган

Верхняя оценка глубины полудуплексного протокола общения с нулём для функции ПЕРЕСЕЧЕНИЕ_n
Математическая публикация¹. Представлен коммуникационный протокол для функции пересечения множеств в полудуплексной модели с нулём со сложностью 5n/6+O(1).
Авторы: Лев Шпрайдун, Варвара Прозорова, Анна Коган

Общение и информация
Математическая публикация¹. Представлен коммуникационный протокол для функции внутреннего произведения в полудуплексной модели с тишиной со сложностью n/2+2. Это является новым результатом, до этого лучшей известной оценкой была оценка n/log_2(3). Полученная верхняя оценка совпадает с известной нижней оценкой с точностью до константы 2.
Автор: Татьяна Гладыш

Верхняя оценка для функции рекурсивного большинства
Математическая публикация¹. Доказана верхняя оценка на коммуникационную сложность игры Карчмера-Вигдерсона для функции рекурсивного большинства в полудуплексной модели с нулём.
Автор: Тимофей Москаленко

Коммуникационная сложность 2
Математическая публикация¹. Доказана верхняя оценка на коммуникационную сложность игры Карчмера-Вигдерсона для функции чётности в полудуплексной модели с нулём.
Автор: Филипп Молодцов

Верхняя оценка на полудуплексную коммуникационную сложность игры Карчмера-Вигдерсона для функции Threshold_2 с тишиной
Математическая публикация¹. Доказана верхняя оценка на коммуникационную сложность игры Карчмера-Вигдерсона для пороговой функции Thr2 в полудуплексной модели с тишиной.
Автор: Ренат Хатымов

Решаемые участниками задачи

Результаты сдачи задач

Подробнее о результатах программы

[1] Расшифровка номинаций (см. правила программы):

– математическая публикация: есть четкая формулировка результата и завершенное доказательство, т.е. работой можно пользоваться;
– математический этюд: есть набросок формулировки результата и идея доказательства, проверенные научным руководителем;
– математический эксперимент: есть четкая формулировка гипотезы, подтвержденной воспроизводимым компьютерным экспериментом.

Решение об отнесении работы к одной из номинаций принималось председателем комиссии Федором Петровым на основе предложений руководителей проектов и рецензий.

К участию в конкурсном отборе приглашаются учащиеся 10-х и 11-х классов образовательных организаций Российской Федерации.

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

Предлагаемые проекты:
Кусочно-евклидова динамика
Руководитель — Владлен Анатольевич Тиморин

Как вода точит камень
Руководитель — Станислав Константинович Смирнов

Общение и информация
Руководитель — Александр Владимирович Смаль

Доступ ко всем проектам появляется в течение суток после подачи заявки в системе Сириус. Курсы. Онлайн-тестирование по каждому проекту будет открыто в соответствующем курсе до 20 марта 2021 года. 

Письменные решения заданий проекта проверяются только у участников, успешно прошедших онлайн-тестирование. Проверяются решения, которые были загружены участниками до 30 марта 2021 года.

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

Список участников собеседований

На образовательную программу приглашаются школьники  в соответствии с рейтингом, составленным на основании оценки письменных решений участников и собеседования независимо в каждом из предложенных проектов. 

Список кандидатов, приглашенных к участию в образовательной программе, будет опубликован на официальном сайте Центра «Сириус» не позднее 10 апреля 2021 года.

Положение о Майской проектной программе по математике и теоретической информатике 
Образовательного центра «Сириус»

1. Общие положения
1.1. Настоящее Положение определяет порядок организации и проведения Майской проектной программы по математике и теоретической информатике Образовательного центра «Сириус» (далее — Образовательная программа), методическое и финансовое обеспечение Образовательной программы.

1.2. Образовательная программа по математике и информатике проводится в Образовательном центре «Сириус» (Образовательный Фонд «Талант и Успех») с 7 по 30 мая 2021 года.

1.3. В образовательной программе могут принять участие школьники 10–11 классов, успешно прошедшие конкурсный отбор.

1.4. К участию в образовательной программе допускаются школьники, обучающиеся в образовательных организациях Российской Федерации, реализующих программы общего и дополнительного образования, являющиеся гражданами Российской Федерации и стран СНГ.

1.5. Персональный состав участников образовательной программы утверждается Экспертным советом Образовательного Фонда «Талант и успех» по направлению «Наука».

1.6. Общее количество участников: от 40 до 70 человек.

1.7. Научно-методическое и кадровое сопровождение образовательной программы осуществляют факультет математики и компьютерных наук Санкт-Петербургского государственного университета и математический факультет Высшей школы экономики.

1.8. Допускается участие школьников в течение учебного года (с июля по июнь следующего календарного года) не более, чем в двух образовательных программах по направлению «Наука» (по любым профилям, включая проектные образовательные программы), не идущих подряд.

1.9. В связи с целостностью и содержательной логикой образовательной программы, интенсивным режимом занятий и объемом академической нагрузки, рассчитанной на весь период пребывания обучающихся в Образовательном центре «Сириус», не допускается участие школьников в отдельных мероприятиях или части образовательной программы: исключены заезды и выезды школьников вне сроков, установленных Экспертным советом Образовательного Фонда «Талант и успех».

1.10. В случае нарушений правил пребывания в Образовательном центре «Сириус» или требований настоящего Положения решением Координационного совета участник образовательной программы может быть отчислен с образовательной программы.

2. Цели и задачи образовательной программы
2.1. Цели образовательной программы: сформировать у участников комплексное представление о современных аспектах математики и компьютерных наук, дать практические навыки решения нестандартных задач.

2.2. Задачи образовательной программы:
– Обеспечить профессиональную ориентацию участников в различных областях современной математики и компьютерных наук.
– Дать участникам углубленные знания в избранных разделах высшей математики.
– Дать участникам углубленные знания в сложных алгоритмических вопросах.

3. Порядок отбора участников образовательной программы
3.1. Отбор участников образовательной программы осуществляется Координационным советом, формируемым руководителем Образовательного Фонда «Талант и успех», на основании требований, изложенных в настоящем Положении, а также общих критериев отбора в Образовательный центр «Сириус» (направление «Наука»).

3.2. К участию в конкурсном отборе приглашаются учащиеся 10-х и 11-х классов образовательных организаций, реализующих программы общего и дополнительного образования из всех регионов Российской Федерации (далее — кандидаты).

3.3. Для участия в конкурсном отборе школьнику необходимо подать заявку на официальном сайте Образовательного центра «Сириус».

Регистрация будет открыта до 19 марта 2021 года.

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

3.4.1. Предлагаемые проекты:

Кусочно-евклидова динамика
Руководитель — Владлен Анатольевич Тиморин

Как вода точит камень
Руководитель — Станислав Константинович Смирнов

Общение и информация
Руководитель — Александр Владимирович Смаль

3.4.2. Заочная часть каждого проекта состоит из двух частей: онлайн-курса с итоговым онлайн-тестированием и письменного решения задач из соответствующего проекта.

3.4.3. Доступ ко всем проектам появляется в течение суток после подачи заявки в системе «Сируис.Курсы», онлайн-тестирование по каждому проекту будет открыто в соответствующем курсе до 20 марта 2021 года. 

3.4.4. Письменные решения заданий проекта проверяются только у участников, успешно прошедших онлайн-тестирование. Проверяются решения, которые были загружены участниками до 30 марта 2021 года.

3.4.5. По итогам оценки письменных решений формируется список участников, прошедших на индивидуальное собеседование с преподавателями программы.

3.5. На образовательную программу приглашаются школьники  в соответствии с рейтингом, составленным на основании оценки письменных решений участников и собеседования независимо в каждом из предложенных проектов. Точное число школьников, приглашаемых на программу, определяется координационным советом с учетом квот п 1.6. в зависимости от результатов отбора.

3.6. В случае отказа кандидата от участия в образовательной программе или отклонения его кандидатуры Экспертным советом, приглашение переходит к следующему кандидату, строго в соответствии с рейтингом. Внесение изменений в список участников программы происходит до 26 апреля 2021 года.

3.7. Список кандидатов, приглашенных к участию в образовательной программе, будет опубликован на официальном сайте Центра «Сириус» не позднее 10 апреля 2021 года.

4. Аннотация образовательной программы
Образовательная программа ориентирована на погружение школьника в работу над проектом, с перспективой выхода на открытые вопросы. Программа существенно отличается от формата подготовки к олимпиадам и от режима работы большинства математических кружков, представляет из себя модель работы математика-исследователя. 
Детальное описание программы

5. Финансирование образовательной программы
5.1. Оплата проезда, пребывания и питания школьников — участников образовательной программы осуществляется за счет средств Образовательного Фонда «Талант и успех».