Математические байки


Гео и язык канала: не указан, Русский
Категория: Образование


Рассказы про разную математику.
Архив: http://dev.mccme.ru/~merzon/mirror/mathtabletalks/

Связанные каналы

Гео и язык канала
не указан, Русский
Категория
Образование
Статистика
Фильтр публикаций




Репост из: Непрерывное математическое образование
какими формулами задаются «Вавилонские» итерации?

если одна сторона прямоугольника площади 2 равна x, то вторая равна 2/x

дальше мы заменяем x на среднее арифметическое двух сторон, x→x/2+1/x (и прямоугольники становятся все ближе к квадратам, а x все ближе к √2)

сравним это с методом Ньютона: чтобы найти корень уравнения f(x_0)=0, мы начинаем с какого-то x и представляем себе, что f примерно линейная — если f(x+t)≈f(x)+tf'(x), то f≈0 при t=-f(x)/f'(x), т.е. новое приближение получается заменой x→x-f(x)/f'(x)

в частности, для функции x²-2 мы получаем те же самые итерации: x-(x²-2)/(2x)=x/2+1/x


Репост из: GetAClass - физика и здравый смысл
#математика

В ролике «Как вавилоняне извлекали квадратные корни» мы рассказываем о том, как древневавилонские математики извлекали квадратные корни, а делали они это с удивительной точностью и происходило это почти 4000 лет назад во времена царя Хаммурапи.

Для этого они использовали геометрические соображения и находили сторону квадрата заданной площади, рассуждая приблизительно следующим образом…

Пусть нам нужно найти сторону квадрата, площадь которого равна 2. В качестве нулевого приближения к такому квадрату выберем прямоугольник со сторонами 2 и 1.

Для построения следующего приближения возьмем прямоугольник, одна сторона которого равна среднему арифметическому сторон прямоугольника из предыдущего приближения, то есть 3/2. Чтобы площадь такого прямоугольника оставалась равной 2, его вторая сторона должна быть равной 4/3. Так мы получим второй прямоугольник, площадью 2, но уже больше похожий на квадрат.

Идем дальше. Для следующего приближения опять возьмем прямоугольник, одна сторона которого равна среднему арифметическому сторон предыдущего, то есть 17/12. И опять определим вторую сторону, сохраняя площадь равной 2. Получим 24/17.

На следующем (третьем) шаге получим стороны прямоугольника 577/408 и 816/577.

На четвертом шаге получим 665867/470832 и 941664/665867.

А теперь давайте сравним точное значение √2 с приближением, полученном на четвертом шаге:

√2 =
1,414213562373095...

665867/470832 =
1,41421356237468...

То есть уже на четвертом шаге мы (а, вернее, они — древние вавилоняне) правильно определили 12 значащих цифр √2. При этом с каждым следующим шагом число правильных знаков удваивается!

Невероятный результат, особенно с учетом того, что получен он почти 4000 лет назад!


Репост из: Кроссворд Тьюринга
📢 Лекция Виктора КЛЕПЦЫНА в это воскресенье, 24 марта 15:00 МСК

🔍 Складывая игры: ним, хакенбуш и сюрреальные числа Конвея.

Многим известна игра «ним» — и описание выигрышных и проигрышных позиций в ней. Но как до него можно дойти? Мы придём к этому ответу, обсудим сложение игр (не чисел — игр!), теорему Шпрага-Гранди (Sprague-Grundy) — а потом перейдём к неравноправным (пристрастным) играм и сюрреальным числам Конвея.

Доклад рассчитан на матшкольников начиная с 8 класса. Знать заранее ничего не нужно.


⏰ Начало в 15:00 МСК.
Обратите внимание на необычное время


📌 Ссылка на Zoom.

#открытые_лекции #анонс


Ещё другой способ рассуждать — удивительным образом, приводящий к такому же неравенству (и у меня нет этому хорошего объяснения).

Прошлое решение было неконструктивным — мы посчитали разрешённые последовательности длины n, и выяснили, что их число всегда положительно (и даже быстро растёт). Но это не позволяет ответить на вопрос «а как же Ивану играть» (ну, если исключить рекомендации вида «ну, обходи дерево мелодий, рано или поздно на разрешённую наткнёшься»).

Давайте представим себе Ивана, играющего мелодию ноту за нотой. Ему нужно решить — какую ноту играть следующей?

Логично, что Иван не хочет проиграть, сыграв одну из запретных мелодий. И логично, что он следит за тем, какие ноты ему сейчас опасно играть: если последние сыгранные 13 нот это первые 13 из запретной мелодии длины 15 — то ему, конечно, было бы логично следующей нотой сыграть не ту, которая идёт 14-й в запретной мелодии. А как бы это устроить?

Давайте измерять «опасность», происходящую от ситуации «ещё вот эти k нот сыграть приводит к проигрышу», величиной a^k, где a — некоторая константа, 0


Давайте чуть-чуть продолжим про Кощея?

Так вот — похожее решение получается, если, уже придя к соотношению (*) выше,
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}.


Очень логично было бы доказывать, например, неравенство экспоненциального роста:
L_{n+1} >= c*L_n,
где c>1 — какая-то (хорошо выбранная) константа. Разумеется, доказывать — по индукции.

Потому что если L_n экспоненциально растёт, то вычитаемые L_{n+1-k} должны оказываться «маленькими» по сравнению с уже имеющимся L_n.

И действительно: если у нас L_m >= c L_{m-1} при m=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.

Если такое есть — всё доказано.


Если вернуться к исходному условию — то, как и положено, Иван-дурак может выиграть. И тут есть разные решения.

Способ 1, неконструктивный. Можно для каждого n задаться вопросом — а сколько вообще мелодий длины n (без запрещённых подслов) он может сыграть? Обозначим это количество через L_n (и удобно считать, что L_0=1).

Тогда значения последовательности L_n для n= 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, удовлетворяющая неравенству (*), остаётся положительной — а, на самом деле, экспоненциально растёт.


Давайте я напишу пару слов про задачу 11-6 с сегодняшней ММО:

Кощей придумал для Ивана-дурака испытание. Он дал Ивану волшебную дудочку, на которой можно играть только две ноты — до и си. Для прохождения испытания Ивану нужно сыграть какую-нибудь мелодию из 300 нот на свой выбор. Но до того, как он начнёт играть, Кощей выбирает и объявляет запретными одну мелодию из пяти нот, одну — из шести нот, …, одну — из 30 нот. Если в какой-то момент последние сыгранные ноты образуют одну из запретных мелодий, дудочка перестаёт звучать. Сможет ли Иван пройти испытание, какие бы мелодии Кощей ни объявил запретными?


Понятно, что вместо мелодий можно говорить про слова из двух символов — например (чтобы не говорить « до » и « си »), из 0 и 1.

Для начала — а что, если Кощей начинает запрещать не с длины 5, а с длины 3? Оказывается, что тогда он может выиграть!

Действительно: пусть он сначала запретит слово 001. Тогда за двумя нулями может идти только третий — и значит, только последовательность из одних нулей. Так что пара запретов 001 + 000000000000 практически равносильна запрету просто на два нуля. (Практически — потому что если мы говорим о словах конечной длины, то там незадолго до конца написать короткий хвост из нулей будет можно, но 300 это достаточно большая длина, чтобы всё закончилось до того.)
Пусть Кощей эти два запрета (001 + 000000000000) и наложит.

Итак, два нуля запрещены, значит, за каждым нулём следует единица. Отлично!

Теперь Кощей запрещает 1101. Поскольку за нулём должна следовать единица — это более-менее то же самое, что запретить просто 110. И поэтому за двумя единицами будет следовать третья — так что, добавив к этому запрету 1111111111, Кощей добивается того, что и две единицы подряд запрещены.

За 0 следует 1, за 1 следует 0, теперь Кощей запрещает 01010 — и испытание становится непроходимым.
(Кстати, последовательности из 0 и 1 выше можно сократить до длин 6 и 7 соответственно — там они длинные, чтобы показать, что в этом месте можно обойтись и очень длинным запретом.)


Репост из: Кроссворд Тьюринга
Друзья! Мы забыли про ММО в воскресенье) Так что доклад переносится на субботу, 9 марта, на то же самое время!


Репост из: Кроссворд Тьюринга
📢 Лекция Владимира ФОКА в это воскресенье, 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 класса. Достаточно владения перечислительной комбинаторикой в объёме нашего курса.


⏰ Начало в 12:00 МСК. Обратите внимание на необычное время

📌 Ссылка на Zoom.

#открытые_лекции #анонс


Репост из: Непрерывное математическое образование
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»


Репост из: Математические этюды
Фотографии Антона Фонарёва




Для меня этот курс Вершика стал первым знакомством с асимптотической комбинаторикой. И с идеей, что очень часто число [комбинаторных] объектов большого размера N примерно данной формы оказывается ведущим себя, как экспонента от фиксированной степени N, умноженной на («энтропийный») функционал от формы — после чего предельная форма оказывается максимизирующей этот функционал.

(По ссылке на mathnet-е лежат и рабочие материалы/записки курса — https://www.mathnet.ru/PresentFiles/231/v231.pdf )


Репост из: Непрерывное математическое образование
https://www.mathnet.ru/present231

А.М.Вершик. «A что будет, если n очень большое?» (ЛШСМ-2008)




Репост из: Непрерывное математическое образование
Анатолий Моисеевич Вершик (28.12.1933–14.02.2024)

Показано 20 последних публикаций.