Forwarded from Непрерывное математическое образование
Анатолий Моисеевич Вершик (28.12.1933–14.02.2024)
Forwarded from Непрерывное математическое образование
https://www.kommersant.ru/doc/3200633
к юбилею Анатолия Моисеевича Вершика — напомним относительно недавнюю “математическую прогулку” с ним
к юбилею Анатолия Моисеевича Вершика — напомним относительно недавнюю “математическую прогулку” с ним
Коммерсантъ
«Эстетика в математике очень важная вещь»
Елена Кудрявцева поговорила с Анатолием Вершиком — одним из самых цитируемых российских ученых
Forwarded from Непрерывное математическое образование
Непрерывное математическое образование
https://www.mathnet.ru/present231 А.М.Вершик. «A что будет, если n очень большое?» (ЛШСМ-2008)
Для меня этот курс Вершика стал первым знакомством с асимптотической комбинаторикой. И с идеей, что очень часто число [комбинаторных] объектов большого размера N примерно данной формы оказывается ведущим себя, как экспонента от фиксированной степени N, умноженной на («энтропийный») функционал от формы — после чего предельная форма оказывается максимизирующей этот функционал.
(По ссылке на mathnet-е лежат и рабочие материалы/записки курса — https://www.mathnet.ru/PresentFiles/231/v231.pdf )
(По ссылке на mathnet-е лежат и рабочие материалы/записки курса — https://www.mathnet.ru/PresentFiles/231/v231.pdf )
Forwarded from Математические этюды
Forwarded from Математические этюды
Фотографии Антона Фонарёва
Forwarded from Непрерывное математическое образование
https://www.quantamagazine.org/elliptic-curve-murmurations-found-with-ai-take-flight-20240305/
знаете, что такое мурмурации? а для эллиптических кривых?
«when a transatlantic collaboration used statistical techniques and artificial intelligence to discover completely unexpected patterns in elliptic curves, it was a welcome, if unexpected, contribution. (…) Since then, in a series of recent papers, mathematicians have begun to unlock the reasons behind the patterns, dubbed “murmurations” for their resemblance to the fluid shapes of flocking starlings»
знаете, что такое мурмурации? а для эллиптических кривых?
«when a transatlantic collaboration used statistical techniques and artificial intelligence to discover completely unexpected patterns in elliptic curves, it was a welcome, if unexpected, contribution. (…) Since then, in a series of recent papers, mathematicians have begun to unlock the reasons behind the patterns, dubbed “murmurations” for their resemblance to the fluid shapes of flocking starlings»
Forwarded from Кроссворд Тьюринга (Vanya Yakovlev)
📢 Лекция Владимира ФОКА в это воскресенье, 10 марта 12:00 МСК
🎤 Возобновляется наш онлайн семинар для старшеклассников и студентов.
📘 Всю осень на matklassonline выходил курс по комбинаторике (а мы с Максом Карсаковым вели по нему кружок). Вместо последнего занятия была обещана лекция – и вот наконец она состоится!
Владимир Фок — математик, профессор университета Страсбурга, специалист по матфизике.
🔍 Теорема Эйлера и бозоны-фермионы
⏰ Начало в 12:00 МСК. Обратите внимание на необычное время
📌 Ссылка на Zoom.
#открытые_лекции #анонс
🎤 Возобновляется наш онлайн семинар для старшеклассников и студентов.
📘 Всю осень на matklassonline выходил курс по комбинаторике (а мы с Максом Карсаковым вели по нему кружок). Вместо последнего занятия была обещана лекция – и вот наконец она состоится!
Владимир Фок — математик, профессор университета Страсбурга, специалист по матфизике.
🔍 Теорема Эйлера и бозоны-фермионы
Пентагональная формула Эйлера даёт разложение бесконечного произведения ∏(1 - q^n) в сумму
∑ (-1^k)q^(3k^2 - k)/2 = 1 - q - q^2 + q^5 + q^7 - q^12 - ...
Доказательство этой формулы, вернее её обобщения — тройного произведения Якоби, предложенное Борхердсом, использует соответствие между диаграммами Юнга и диаграммами майя — бесконечными последовательностями крестиков и ноликов, а также понятие моря Дирака из физики. Идеи этого доказательства можно также использовать для решения многих других комбинаторных задач.
Доклад рассчитан на матшкольников начиная с 9 класса. Достаточно владения перечислительной комбинаторикой в объёме нашего курса.
⏰ Начало в 12:00 МСК. Обратите внимание на необычное время
📌 Ссылка на Zoom.
#открытые_лекции #анонс
Forwarded from Кроссворд Тьюринга (Vanya Yakovlev)
Друзья! Мы забыли про ММО в воскресенье) Так что доклад переносится на субботу, 9 марта, на то же самое время!
Давайте я напишу пару слов про задачу 11-6 с сегодняшней ММО:
Понятно, что вместо мелодий можно говорить про слова из двух символов — например (чтобы не говорить « до » и « си »), из 0 и 1.
Для начала — а что, если Кощей начинает запрещать не с длины 5, а с длины 3? Оказывается, что тогда он может выиграть!
Действительно: пусть он сначала запретит слово 001. Тогда за двумя нулями может идти только третий — и значит, только последовательность из одних нулей. Так что пара запретов 001 + 000000000000 практически равносильна запрету просто на два нуля. (Практически — потому что если мы говорим о словах конечной длины, то там незадолго до конца написать короткий хвост из нулей будет можно, но 300 это достаточно большая длина, чтобы всё закончилось до того.)
Пусть Кощей эти два запрета (001 + 000000000000) и наложит.
Итак, два нуля запрещены, значит, за каждым нулём следует единица. Отлично!
Теперь Кощей запрещает 1101. Поскольку за нулём должна следовать единица — это более-менее то же самое, что запретить просто 110. И поэтому за двумя единицами будет следовать третья — так что, добавив к этому запрету 1111111111, Кощей добивается того, что и две единицы подряд запрещены.
За 0 следует 1, за 1 следует 0, теперь Кощей запрещает 01010 — и испытание становится непроходимым.
(Кстати, последовательности из 0 и 1 выше можно сократить до длин 6 и 7 соответственно — там они длинные, чтобы показать, что в этом месте можно обойтись и очень длинным запретом.)
Кощей придумал для Ивана-дурака испытание. Он дал Ивану волшебную дудочку, на которой можно играть только две ноты — до и си. Для прохождения испытания Ивану нужно сыграть какую-нибудь мелодию из 300 нот на свой выбор. Но до того, как он начнёт играть, Кощей выбирает и объявляет запретными одну мелодию из пяти нот, одну — из шести нот, …, одну — из 30 нот. Если в какой-то момент последние сыгранные ноты образуют одну из запретных мелодий, дудочка перестаёт звучать. Сможет ли Иван пройти испытание, какие бы мелодии Кощей ни объявил запретными?
Понятно, что вместо мелодий можно говорить про слова из двух символов — например (чтобы не говорить « до » и « си »), из 0 и 1.
Для начала — а что, если Кощей начинает запрещать не с длины 5, а с длины 3? Оказывается, что тогда он может выиграть!
Пусть Кощей эти два запрета (001 + 000000000000) и наложит.
Итак, два нуля запрещены, значит, за каждым нулём следует единица. Отлично!
Теперь Кощей запрещает 1101. Поскольку за нулём должна следовать единица — это более-менее то же самое, что запретить просто 110. И поэтому за двумя единицами будет следовать третья — так что, добавив к этому запрету 1111111111, Кощей добивается того, что и две единицы подряд запрещены.
За 0 следует 1, за 1 следует 0, теперь Кощей запрещает 01010 — и испытание становится непроходимым.
(Кстати, последовательности из 0 и 1 выше можно сократить до длин 6 и 7 соответственно — там они длинные, чтобы показать, что в этом месте можно обойтись и очень длинным запретом.)
Если вернуться к исходному условию — то, как и положено, Иван-дурак может выиграть. И тут есть разные решения.
Способ 1, неконструктивный. Можно для каждого n задаться вопросом — а сколько вообще мелодий длины n (без запрещённых подслов) он может сыграть? Обозначим это количество через L_n (и удобно считать, что L_0=1).
Тогда значения последовательности L_n для n<=5 это 1, 2, 4, 8, 16 и 31 (первый раз срабатывает запрет). Пока что она растёт довольно быстро — и вопрос в том, успеет ли Кощей её рост как-то «сбить».
Понятно, что последовательность длины n+1 продолжает последовательность длины n — так что для начала можно дописать к каждой мелодии длины n оба возможных продолжения. Получится 2L_n. Но при этом последние несколько нот могут образовать только что появившуюся запретную мелодию какой-то длины k. Так что для каждой запретной мелодии длины k нужно выкинуть из нашего подсчёта те, которые на неё заканчиваются. А их не больше, чем L_{n+1-k}, потому что если этот кусочек убрать — то получится разрешённая мелодия длины n+1-k.
Значит,
L_{n+1} >= 2 L_n - \sum_{k>=5} L_{n+1-k}. (*)
Важное замечание: рассуждения тут довольно универсальные. Если дудочка играет не две ноты, а d, то в формуле выше будет не 2L_n, а d*L_n. Если запрещённых подслов не по одному на длину, а какой-то список E, то будет
L_{n+1} >= d L_n - \sum_{w\in E} L_{n+1-|w|},
где |w| это длина слова w.
И теперь достаточно доказать, что последовательность L_n, удовлетворяющая неравенству (*), остаётся положительной — а, на самом деле, экспоненциально растёт.
Способ 1, неконструктивный. Можно для каждого n задаться вопросом — а сколько вообще мелодий длины n (без запрещённых подслов) он может сыграть? Обозначим это количество через L_n (и удобно считать, что L_0=1).
Тогда значения последовательности L_n для n<=5 это 1, 2, 4, 8, 16 и 31 (первый раз срабатывает запрет). Пока что она растёт довольно быстро — и вопрос в том, успеет ли Кощей её рост как-то «сбить».
Значит,
L_{n+1} >= 2 L_n - \sum_{k>=5} L_{n+1-k}. (*)
Важное замечание: рассуждения тут довольно универсальные. Если дудочка играет не две ноты, а d, то в формуле выше будет не 2L_n, а d*L_n. Если запрещённых подслов не по одному на длину, а какой-то список E, то будет
L_{n+1} >= d L_n - \sum_{w\in E} L_{n+1-|w|},
где |w| это длина слова w.
И теперь достаточно доказать, что последовательность L_n, удовлетворяющая неравенству (*), остаётся положительной — а, на самом деле, экспоненциально растёт.
L_{n+1} >= c*L_n,
где c>1 — какая-то (хорошо выбранная) константа. Разумеется, доказывать — по индукции.
Потому что если L_n экспоненциально растёт, то вычитаемые L_{n+1-k} должны оказываться «маленькими» по сравнению с уже имеющимся L_n.
И действительно: если у нас L_m >= c L_{m-1} при m<=n, то
L_{n+1-k} <= L_n / c^{k-1}, откуда
L_{n+1} >= 2 L_n - \sum_{k>=5} L_{n+1-k}
>= 2 L_n - \sum_{k>=5} L_n /c^{k-1} =
(2- \sum_{r>=4} c^{-r} ) L_n.
Значит, для доказательства остаётся найти такое c на отрезке от 1 до 2, что
2- \sum_{r>=4} c^{-r} >= c.
Если такое есть — всё доказано.