4247
Рассказы про разную математику. Архив: http://dev.mccme.ru/~merzon/mirror/mathtabletalks/
Давайте чуть-чуть продолжим про Кощея?
Так вот — похожее решение получается, если, уже придя к соотношению (*) выше,
L_{n+1} >= 2L_n - L_{n-4} - L_{n-5} - L_{n-6} -…,
начать доказывать нижнюю оценку на рост числа L_n разрешённых мелодий длины n, что
L_{n+1} >= L_n + L_{n-1}. (**)
(С той логикой, что последовательность явно будет расти медленнее, чем геометрическая со знаменателем 2, ну и Фибоначчи-подобный рост вполне хороший кандидат на попробовать…)
Доказывать — по индукции по всем меньшим значениям n. А именно: мы хотим проверить, что
L_{n+1} - L_n - L_{n-1} >=0.
А из (*) следует, что эта разность не меньше
L_n-L_{n-1}-L_{n-4}-L_{n-5}-L_{n-6}-….
Первая разность L_{n}-L_{n-1} не меньше L_{n-2} по предположению индукции. Осталось
L_{n-2}-L_{n-4}-L_{n-5}-L_{n-6}-… .
Теперь подчёркнутая разность L_{n-2}-L_{n-4} не меньше L_{n-3} по предположению индукции. Осталось
L_{n-3}-L_{n-5}-L_{n-6}-L_{n-7}… .
Теперь подчёркнутая разность L_{n-3}-L_{n-5} не меньше L_{n-4} по предположению индукции. Осталось
L_{n-4}-L_{n-6}-L_{n-7}-L_{n-8}… .
Теперь подчёркнутая разность L_{n-4}-L_{n-6} не меньше L_{n-5} по предположению индукции. Ну и так далее.
(Именно это решение рассказывали на видео-разборе; картинка-скриншот оттуда.)
Очень естественно такое искать, заменив конечную сумму (до r=29) на бесконечную (что соответствует тому, что запреты Кощея не останавливаются на 30 нотах). Понятно, что неравенство станет сильнее, поэтому то c, которое ему будет удовлетворять, подойдёт и для исходного.
Дальше — есть несколько путей. Можно просто угадать, что для золотого сечения
с=φ=(1+\sqrt{5})/2
неравенство обращается в равенство. Потому что сумма убывающей геометрической прогрессии со знаменателем 1/φ, начинающейся с 1, равна
1/(1- 1/φ) = 1/ (1/φ^2) = φ^2;
значит, в левой части получается
2- φ^{-4} * φ^2= 2- 1/φ^2 = 2 - (1-1/φ) = 1+ 1/φ = φ.
Второй путь — можно сказать, что сумма геометрической прогрессии равна
c^{-4} / (1-c^{-1}) = c^{-3} / (c-1);
так что мы ищем такое c, для которого
2 - с^{-3} / (c-1) >= c.
Если привести к общему знаменателю и перенести c в левую часть — получается полиномиальное неравенство
(2-c) c^3 (c-1) - 1 >=0.
Опять же, можно ещё раз увидеть, что на золотом сечении неравенство обращается в равенство ( 2-φ = 1/φ^2, φ-1 = 1/φ ), но можно и заметить, что какое-нибудь конкретное c этому неравенству удовлетворяет. И таких c есть целый интервал от золотого сечения φ=1.618… до чуть больше, чем 1.75. Достаточно проверить неравенство для любого из них.
Наконец, где золотое сечение — там и последовательность Фибоначчи. И отсюда и вариант решения, когда вместо чистого геометрического роста доказывается неравенство L_{n+1} >= L_n + L_{n-1}.
Если вернуться к исходному условию — то, как и положено, Иван-дурак может выиграть. И тут есть разные решения.
Способ 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, удовлетворяющая неравенству (*), остаётся положительной — а, на самом деле, экспоненциально растёт.
Друзья! Мы забыли про ММО в воскресенье) Так что доклад переносится на субботу, 9 марта, на то же самое время!
Читать полностью…
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»
https://www.mathnet.ru/present231
А.М.Вершик. «A что будет, если n очень большое?» (ЛШСМ-2008)
Анатолий Моисеевич Вершик (28.12.1933–14.02.2024)
Читать полностью…
Давайте я чуть-чуть добавлю к тому, что пишут коллеги.
Все знают, что планеты движутся вокруг звезды по эллипсам. И навскидку не очень ясно, как это утверждение доказывать, не закапываясь в какие-нибудь жуткие выкладки.
Лет пять назад появилось выложил замечательное видео (на канале minutephysics с 3blue1brown) про лекцию Фейнмана об этом, « Feynman’s Lost Lecture ».
Я его очень рекомендую посмотреть — но если коротко, есть совершенно замечательный промежуточный шаг, который, услышав однажды, забыть нельзя.
Отложим скорости планеты в разные моменты времени от начала координат. Оказывается, что концы этих векторов образуют окружность — просто с центром не в начале координат!
(«Годограф скоростей — круглый»)
Чтобы вывести это утверждение, нужны и закон всемирного тяготения, и закон сохранения момента импульса (а точнее, следующий из него второй закон Кеплера — правило площадей). А вывод из него эллиптичности орбиты связан как раз с картинкой с эллипсом-огибающей!
(Я немного об этом когда-то писал — см. тут и ниже — но очень советую посмотреть и видео, и страницы/миниатюры Мат. Этюдов про огибающие.)
появление эллипса на круглом листе бумаги ( via vk.com/thebeautyoftruth )
Читать полностью…
Ответ:
Луна в первой четверти означает, что направление на неё почти под прямым углом к направлению на Солнце. А Венера — внутренняя планета, так что на 90 градусов выйти не может.
Если говорить более аккуратно, то радиус орбиты у неё — чуть больше 0.7 радиуса орбиты Земли (точнее, большая полуось 0.723 а.е., но я наизусть только 0.7 помню — одну цифру помнить проще 🙂 ; ну и на уровне прикидки в уме эллиптичностью пренебрегаем, всё-таки там эксцентриситеты порядка процента)
Значит, Венера не может быть от Солнца на угловом расстоянии, большем, чем (примерно) arcsin 0.7.
Ну а sqrt{2}/2=0.707..., так что этот угол это с отличной точностью 45 градусов.
Итак, максимальный угол между направлениями на Венеру и Солнце это чуть больше, чем 45 градусов (на самом деле 47, но это я уже потом посмотрел — а тут прикидывал на ходу, и кажется, неплохо получилось).
Итого:
*) угол Солнце-Земля-Луна в этот момент примерно равен 90 градусам (потому что от Луны освещена половина),
*) угол Солнце-Земля-Венера никогда не больше 47 градусов.
Значит, в момент наблюдения угол Венера-Земля-Луна был не меньше 43 градусов. А не единицы градусов, которые « рядом » на небе! Так что Венеру исключаем.
St. Petersburg mathematicians and their discoveries
Книжка про математиков Петербурга и их открытия — завершена.
Теперь напечатаем малым тиражом и разошлём авторам и всем причастным.
Кому интересно иметь её в бумажном виде — печатайте сами себе в каком-нибудь самиздате (вроде есть сайты, куда можно pdf загрузить, и потом в мягком переплёте получить по почте).
Женя Кац напомнила про видео — мыльные пузыри в сильный мороз можно заморозить(!). Я вот вживую такого никогда не видел…
Читать полностью…
https://mccme.ru/free-books/
Дед Мороз напоминает про страницу, на которой бесплатно доступны файлы множества книг (в основном издательства МЦНМО)
брошюры библиотеки «Математическое просвещение» и Летней школы «Современная математика», доклады семинара «Глобус» и материалы выездного семинара учителей, книги Арнольда и Гельфанда, Прасолова и Шеня и многое другое.
новогодние каникулы — как раз хорошая возможность спокойно почитать
Так вот — на самом деле, то, что мы тут исследовали ним на двух кучках, совершенно неважно! То же самое правило наименьшего исключенного (mex-rule) строит соответствующее *n (ним на одной кучке из n камней) и для любой равноправной игры. А именно: пусть у нас есть какая-то равноправная игра, будем сопоставлять ей ним-игру *n по индукции. Если уже построены сопоставления для всего, что можно из данной позиции получить за один ход, и это *n_1,…,*n_m, то самой позиции сопоставляем *n, где n — наименьшее неотрицательное целое число, не встречающееся среди n_1,…,n_m.
Доказательство теоремы Шпрага-Гранди. Построить-то соответствующие ним-игры мы построили, но остаётся проверить, что построенная игра действительно равна исходной — то есть что их сумма нулевая. А для этого в их сумме мы предъявим выигрышную стратегию для второго игрока.
Пусть из исходной позиции A нашей игры можно пойти в A_1,…,A_m — которым соответствуют ним-игры *n_1,…,*n_m, и мы уже знаем, что
A_j + *n_j =0.
Мы взяли n = mex(n_1,…,n_m), и рассматриваем сумму A+*n. Докажем, что в ней выигрывает второй игрок.
Действительно, что может сделать первый игрок? Он может сделать ход со стороны A, переведя её в одну из A_j с n_j<n. Тогда мы отвечаем, оставляя *n_j из n камней в *n — и тем самым отдаём противнику позицию A_j + *n_j, проигрышную по предположению.
Он может сделать ход со стороны ним-кучки, перейдя от *n к какому-то *n’. Но раз n было наименьшим исключённым из n_1,…,n_m, значит, найдётся j такое, что n’=n_j. И тут уже мы отвечаем, переходя из A в A_j и опять приводя игру в проигрышную позицию A_j + *n_j.
Наконец, первый игрок мог сделать ход со стороны A, переведя её в одну из A_j, но с n_j>n. Тогда мы ответим ходом из A_j. А именно — n<n_j, поэтому найдётся позиция A_j’, куда мы из A_j можем пойти, которой сопоставлена *n (потому что n_j — наименьшее исключённое). Вот туда мы и пойдём — приведя игру к
A_j’+*n=0.
На самом деле, разбора вариантов n_j<n и n_j>n можно было и не делать, ограничившись замечанием, что *A_j + *n = *n_j + *n; в игре в правой части очевидно выигрывает начинающий (т.е. мы — ход сейчас наш), а у нас есть теорема, что замена игры на равную не изменяет победителя. Но так у нас есть не только теорема, но и явная конструкция стратегии.
С днём Пи (14 марта, 3/14)!
https://youtu.be/d-o3eB9sfls?si=hJrUVLxXrgUiUfIu
Очень логично было бы доказывать, например, неравенство экспоненциального роста:
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.
Если такое есть — всё доказано.
Давайте я напишу пару слов про задачу 11-6 с сегодняшней ММО:
Кощей придумал для Ивана-дурака испытание. Он дал Ивану волшебную дудочку, на которой можно играть только две ноты — до и си. Для прохождения испытания Ивану нужно сыграть какую-нибудь мелодию из 300 нот на свой выбор. Но до того, как он начнёт играть, Кощей выбирает и объявляет запретными одну мелодию из пяти нот, одну — из шести нот, …, одну — из 30 нот. Если в какой-то момент последние сыгранные ноты образуют одну из запретных мелодий, дудочка перестаёт звучать. Сможет ли Иван пройти испытание, какие бы мелодии Кощей ни объявил запретными?
📢 Лекция Владимира ФОКА в это воскресенье, 10 марта 12:00 МСК
🎤 Возобновляется наш онлайн семинар для старшеклассников и студентов.
📘 Всю осень на matklassonline выходил курс по комбинаторике (а мы с Максом Карсаковым вели по нему кружок). Вместо последнего занятия была обещана лекция – и вот наконец она состоится!
Владимир Фок — математик, профессор университета Страсбурга, специалист по матфизике.
🔍 Теорема Эйлера и бозоны-фермионы
Пентагональная формула Эйлера даёт разложение бесконечного произведения ∏(1 - q^n) в сумму
∑ (-1^k)q^(3k^2 - k)/2 = 1 - q - q^2 + q^5 + q^7 - q^12 - ...
Доказательство этой формулы, вернее её обобщения — тройного произведения Якоби, предложенное Борхердсом, использует соответствие между диаграммами Юнга и диаграммами майя — бесконечными последовательностями крестиков и ноликов, а также понятие моря Дирака из физики. Идеи этого доказательства можно также использовать для решения многих других комбинаторных задач.
Доклад рассчитан на матшкольников начиная с 9 класса. Достаточно владения перечислительной комбинаторикой в объёме нашего курса.
Для меня этот курс Вершика стал первым знакомством с асимптотической комбинаторикой. И с идеей, что очень часто число [комбинаторных] объектов большого размера N примерно данной формы оказывается ведущим себя, как экспонента от фиксированной степени N, умноженной на («энтропийный») функционал от формы — после чего предельная форма оказывается максимизирующей этот функционал.
(По ссылке на mathnet-е лежат и рабочие материалы/записки курса — https://www.mathnet.ru/PresentFiles/231/v231.pdf )
https://www.kommersant.ru/doc/3200633
к юбилею Анатолия Моисеевича Вершика — напомним относительно недавнюю “математическую прогулку” с ним
Любую гладкую кривую можно увидеть, нарисовав не саму кривую, а множество касательных к ней. Понятие огибающей подробно описано в сюжете «Парабола: изонить», в котором в качестве огибающей семейства прямых возникает парабола.
Но построение касательных не такое простое дело. Продемонстрируем, как увидеть конические сечения — эллипс, гиперболу, параболу — ничего не считая и не рисуя, а просто складывая листок бумаги. Сюжет сегодняшнего Математического вторника: «Эллипс, гипербола, парабола: складывание листа бумаги» https://etudes.ru/models/conic-sections-paper-folding/ . Для эллипса и гиперболы понадобится вырезать кружок из бумаги, для параболы – просто прямоугольный лист.
Похожие картинки можно уже было видеть в миниатюрах Эллипс как огибающая, Гипербола как огибающая, Парабола как огибающая. Но в них надо уметь строить перпендикуляр к отрезку, а в указанном сегодня способе складывания листочка эта операция «зашита» в сам способ складывания.
Три дня назад на небе можно было увидеть аккуратную половинку Луны (почти точно в фазе первой четверти) — и очень яркую «звёздочку» рядом. Первое, что приходит в голову при виде чего-то столь яркого, это Венера и Юпитер. (Вообще, Марс иногда бывает очень ярким, но не так часто; есть ещё Сириус, но давайте мы его временно заметём под ковёр).
Так вот: допустим, мы ограничили выбор Венерой и Юпитером. Интересно, что написанного выше достаточно, чтобы один из этих вариантов исключить! Как думаете, какой?
(image credit: NASA, вырезано из What’s Up video)
https://mccme.ru/nir/seminar/
в четверг (11.01) продолжится семинар учителей математики:
А.Д.Блинков будет рассказывать про книжку «Площади без формул», которая скоро выйдет в серии «Школьные математические кружки»
как обычно: 19:00, столовая МЦНМО, приглашаются все желающие
Нерегулярная рубрика «рабочие картинки» (они красивые, хочется поделиться): часть поверхности Маркова
x^2+y^2+z^2-xyz = D
и некоторые слоения на ней.
Давайте посмотрим на один пример применения этой науки.
Есть такая стандартная кружковская задача:
Есть ромашка с n лепестками, и двое по очереди отрывают либо один лепесток, либо два соседних. Кто не может сделать ход — проиграл. Кто выигрывает при правильной игре?
Решение: при n>2 выигрывает второй игрок. После первого хода первого игрока второй отрывает лепестки строго напротив — разбивая окружность лепестков на два одинаковых участка, и остаётся применить симметричную стратегию.
Это, конечно, решает исходную задачу. Но представим себе, что нам досталась позиция после нескольких ходов. Например, пусть нам достался набор лепестков, образующий отрезки длиной 4, 5, 9 и 20. Кто выигрывает при правильной игре? А если (допустим, ромашка была очень большая) нам достались отрезки длиной 12, 70 и 180?
Попытка исследовать эти игры «от начальной позиции», исследуя дерево вариантов сверху, приводит к не очень подъёмному перебору. (Навскидку, первый вариант вручную и без оптимизации уже неподъёмный, но ещё должен перебираться на компьютере; а второй даже и компьютер не потянет.)
А вот применение конструкции из теоремы Шпрага-Гранди позволяет справиться даже и вручную! А именно — мы хотим для любого n узнать, какому числу камней a_n соответствует игра для одного отрезка из n последовательных лепестков. За один ход мы можем получить из него два отрезка длин s и t, где либо s+t=n-1, либо s+t=n-2.
(Если отрываем лепестки с края, то кто-нибудь из s и t будет нулём.)
Двум отрезкам соответствует сумма игр, и ним-сумма (a.k.a. XOR) соответствующих количеств камней. Соответственно, получаем рекуррентное соотношение
a_n = mex ( XOR(a_s,a_t) | s+t = n-1 или s+t = n-2 ).
Во-первых, при необходимости его и до 180 можно дотащить «вручную». Да, априори это могло бы быть оочень занудно, но это явно посильная задача даже без компьютера.
Во-вторых: давайте посчитаем первые несколько членов последовательности.
n=0 -> пустая игра, ходов нет,
a_0=0.
n=1 -> единственный ход приводит к 0, значит,
a_1=1.
n=2 -> можно получить либо пустую позицию, либо один лепесток, значит,
a_2=mex(0,1) = 2.
n=3 -> можно получить конфигурации (1), (2), (1,1), которым соответствуют ним-значения 1, 2 и 0 соответственно. Значит,
a_3=mex(0,1,2)=3.
n=4 -> можно получить конфигурации (2), (1,1), (3), (1,2), которым соответствуют ним-значения 2, 0, 3 и 3 соответственно. Значит,
a_4= mex(0,2,3)=1.
n=5 -> можно получить конфигурации (3), (2,1), (4), (1,3), (2,2) которым соответствуют ним-значения 3, 3, 1, 2 и 0 соответственно. Значит,
a_5= mex(0,1,2,3)=4.
После чего можно ввести начало найденной последовательности — 0,1,2,3,1,4 — в OEIS, онлайн-энциклопедию целочисленных последовательностей (коллеги цитировали текст к 50-летию энциклопедии — начинавшейся ещё не как онлайн!).
И первой ссылкой этот поиск выдаст последовательность A002186 — после чего, посмотрев на то, что такое упоминаемая там game of Kayles, становится понятно, что это буквально то, что нам нужно. И кстати — начиная с n=71 последовательность становится периодичной с периодом 12.
(For the record: подумав, что я хочу привести тут пример с игрой с ромашкой, я ещё не знал названия Kayles — выше описан буквально тот путь, которым я прошёл.)
Если возвращаться именно к нашим позициям из примеров выше — наборам (4,5,9,20) и (12,70,180) — то первому из них соответствует ним-сумма 1, 4, 4 и 1, и выигрывает второй игрок. А второму — ним-сумма 4, 4 и 6, так что выигрывает первый. Один из выигрышных ходов — превратить третий отрезок в 180 лепестков с ним-значением 6 во что-то с нулевым ним-значением, вырвав два лепестка посередине: мы получим позицию (12,70,89,89) с нулевым суммарным ним-значением.
А как эта проигрышная позиция находится? В столбце будут выигрышные позиции, приходящие из проигрышных клеток в столбцах ниже (в смысле плоскости — если хотите, севернее) или левее (западнее). И первая из клеток, которая таким образом « выбита » не будет, и будет проигрышной.
Если заполнять таблицу «какой игре *n равняется сумма *k+*m» (как мы уже знаем, на самом деле это таблица значений XOR двоичных записей), то правило выше превращается в правило наименьшего исключенного:
в клетке (k,m) стоит первое из неотрицательных целых чисел, которое не появляется ни в одной из клеток (k’,m’), которые из неё можно получить за один ход.