April 15, 2021
И последнее — ещё пара картинок в заключение ко вчерашнему рассказу:
1) http://www.empiricalzeal.com/wp-content/uploads/2012/12/pinker-glow-worms-and-stars-plot.jpg : слева — случайно раскиданные точки, справа — положения светящихся glowworms на своде пещеры Waitomo в Новой Зеландии (источник — "What does randomness look like?", Wired). Последние светом приманивают пищу — так что им прямой резон располагаться подальше друг от друга, чтобы не мешать друг другу охотиться.
1) http://www.empiricalzeal.com/wp-content/uploads/2012/12/pinker-glow-worms-and-stars-plot.jpg : слева — случайно раскиданные точки, справа — положения светящихся glowworms на своде пещеры Waitomo в Новой Зеландии (источник — "What does randomness look like?", Wired). Последние светом приманивают пищу — так что им прямой резон располагаться подальше друг от друга, чтобы не мешать друг другу охотиться.
April 16, 2021
2) картинка из статьи "Determinantal Processes and Independence", J. Ben Hough, Manjunath Krishnapur, Yuval Peres, Bálint Virág: слева-сверху пуассоновский процесс ( = случайное распределение точек), справа-сверху — детерминантный (точки "отталкиваются" друг от друга), снизу в центре — перманентный (точки "комкуются"); спасибо @qtasep за ссылку!
April 16, 2021
Forwarded from Непрерывное математическое образование
На витрине ювелирного магазина лежат 15 бриллиантов. Рядом с ними стоят таблички с указанием масс, на которых написано 1, 2, ..., 15 карат. У продавца есть чашечные весы и четыре гирьки массами 1, 2, 4 и 8 карат. Покупателю разрешается только один тип взвешиваний: положить один из бриллиантов на одну чашу весов, а гирьки — на другую и убедиться, что масса на соответствующей табличке указана верно. Однако за каждую взятую гирьку нужно заплатить продавцу 100 монет. Если гирька снимается с весов и в следующем взвешивании не участвует, продавец забирает её. Какую наименьшую сумму придётся заплатить, чтобы проверить массы всех бриллиантов?
вот такую, например, задачу А.В.Грибалко с сегодняшнего МатПраздника предлагается решить
(потом можно также прочитать в брошюре небольшой комментарий про контекст)
вот такую, например, задачу А.В.Грибалко с сегодняшнего МатПраздника предлагается решить
(потом можно также прочитать в брошюре небольшой комментарий про контекст)
April 18, 2021
Математические байки
На витрине ювелирного магазина лежат 15 бриллиантов. Рядом с ними стоят таблички с указанием масс, на которых написано 1, 2, ..., 15 карат. У продавца есть чашечные весы и четыре гирьки массами 1, 2, 4 и 8 карат. Покупателю разрешается только один тип взвешиваний:…
Присоединюсь к коллегам: задача очень хорошая, а послесловие про контекст действительно стоит посмотреть!
April 18, 2021
Это, конечно, оффтопик для этого канала — но поздравляю всех с первым аппаратом тяжелее атмосферы, аэродинамически поднявшимся в воздух на другой планете!
Формулировка про "тяжелее воздуха" тут точная — в атмосфере Венеры летали (надувавшиеся прямо в атмосфере после торможения) аэростатные зонды советских АМС Вега-1 и Вега-2. А без слова "аэродинамически" формально-верно из-за слова "планета", но всё-таки тогда стоило было бы вспомнить про Луну (откуда взлетали как Apollo, так и советские Луна-16, Луна-20, Луна-24, недавний китайский Чанъэ-5), да и с астероидов тоже были взлёты — можно вспомнить японские Хаябусу и Хаябусу-2, летящий сейчас OSIRIS-REx...
А ещё этот вертолётик несёт на себе микроскопический кусочек ткани с того самого самолёта братьев Райт; жест совершенно символический — но очень красивый.
Кадр из только что закончившейся прямой трансляции NASA : показания альтиметра (взлёт, зависание, посадка) + см. новость N+1.
Момент полёта — https://youtu.be/p1KolyCqICI?t=2524
Формулировка про "тяжелее воздуха" тут точная — в атмосфере Венеры летали (надувавшиеся прямо в атмосфере после торможения) аэростатные зонды советских АМС Вега-1 и Вега-2. А без слова "аэродинамически" формально-верно из-за слова "планета", но всё-таки тогда стоило было бы вспомнить про Луну (откуда взлетали как Apollo, так и советские Луна-16, Луна-20, Луна-24, недавний китайский Чанъэ-5), да и с астероидов тоже были взлёты — можно вспомнить японские Хаябусу и Хаябусу-2, летящий сейчас OSIRIS-REx...
А ещё этот вертолётик несёт на себе микроскопический кусочек ткани с того самого самолёта братьев Райт; жест совершенно символический — но очень красивый.
Кадр из только что закончившейся прямой трансляции NASA : показания альтиметра (взлёт, зависание, посадка) + см. новость N+1.
Момент полёта — https://youtu.be/p1KolyCqICI?t=2524
April 19, 2021
Forwarded from Жалкие низкочастотники
Напишу немного про проклятье размерности. Это термин, которым, в частности, называют странности многомерных пространств, от которых человеческая интуиция начинает давать сбои.
Один популярный пример выглядит так: возьмём квадрат на плоскости и впишем в него круг. Ясно, что круг закроет большую часть площади квадрата. Дальше, возьмём куб и впишем в него шар. Опять же, шар займёт большую часть объёма куба. Но вот в четырёхмерном случае гиперсфера займёт меньше трети объёма гиперкуба, а при дальнейшем повышении размерности отношение их объёмов сходится к нулю. При этом евклидово расстояние от центра n-мерного куба до любого из его
Другой пример — гипотеза Борсука о возможности разбиения n-мерного тела диаметром 1 на n+1 тел диаметром меньше 1. Она доказана для
Всё это обычно выглядит как игры разума, не отягощённого бытовыми мелочами, однако бум нейросетей принес нам популярность всяких многомерных эмбеддингов и представлений — слов, текстов или картинок, и там такие пакости случаются регулярно. Недавно, в одной из задач мне пришлось столкнуться с такой штукой:
Возьмём, скажем, 100-мерное пространство и выберем в нём равномерно случайно из единичного гиперкуба 42 точки. Пронумеруем их в некотором случайном, но фиксированном порядке, от 1 до 42. Какова вероятность, что в нашем пространстве найдётся такая ось, в проекции на которую наши точки выстроятся в нужном порядке? Ответ: больше 99%. Кому интересно, можете посмотреть мой скрипт на питоне, которым это эмпирически можно проверить (работает довольно долго, решает системы линейных неравенств, пересекая полупространства для каждой пары точек).
Один популярный пример выглядит так: возьмём квадрат на плоскости и впишем в него круг. Ясно, что круг закроет большую часть площади квадрата. Дальше, возьмём куб и впишем в него шар. Опять же, шар займёт большую часть объёма куба. Но вот в четырёхмерном случае гиперсфера займёт меньше трети объёма гиперкуба, а при дальнейшем повышении размерности отношение их объёмов сходится к нулю. При этом евклидово расстояние от центра n-мерного куба до любого из его
2^n
углов растёт как sqrt(n)
, т.е. неограниченно; а основной объём пространства (т.е., например, основная часть равномерно случайно взятых точек) внутри такого куба оказывается на расстоянии от центра с матожиданием sqrt(n/3)
и с убывающей к нулю дисперсией. Короче, n-мерный куб — это очень странное место, с кучей углов и пустым центром.Другой пример — гипотеза Борсука о возможности разбиения n-мерного тела диаметром 1 на n+1 тел диаметром меньше 1. Она доказана для
n<=3
и опровергнута для n>=64
. Посредине — томящая неизвестность.Всё это обычно выглядит как игры разума, не отягощённого бытовыми мелочами, однако бум нейросетей принес нам популярность всяких многомерных эмбеддингов и представлений — слов, текстов или картинок, и там такие пакости случаются регулярно. Недавно, в одной из задач мне пришлось столкнуться с такой штукой:
Возьмём, скажем, 100-мерное пространство и выберем в нём равномерно случайно из единичного гиперкуба 42 точки. Пронумеруем их в некотором случайном, но фиксированном порядке, от 1 до 42. Какова вероятность, что в нашем пространстве найдётся такая ось, в проекции на которую наши точки выстроятся в нужном порядке? Ответ: больше 99%. Кому интересно, можете посмотреть мой скрипт на питоне, которым это эмпирически можно проверить (работает довольно долго, решает системы линейных неравенств, пересекая полупространства для каждой пары точек).
April 19, 2021
Математические байки
Photo
(+Иллюстрация к поведению куба)
April 19, 2021
Forwarded from Жалкие низкочастотники
В ответ на мой вчерашний пост в личку пришло сразу несколько бдительных математиков с разумными комментариями, которые я выношу в этот мини пост.
Конечно, число 42 я взял с потолка (ведь уже скоро день Полотенца), и вместо него могло быть другое число. И действительно, если немного подумать, то можно аналитически показать, что в n-мерном пространстве такую ось можно провести для любых n невырожденных точек (доказывается, например, построением базиса из векторов к этим точкам, а потом построением нужной оси в этом базисе).
Спасибо, Федя, Витя и все остальные, кто пишет мне уточнения и комментарии к моим постам :)
Конечно, число 42 я взял с потолка (ведь уже скоро день Полотенца), и вместо него могло быть другое число. И действительно, если немного подумать, то можно аналитически показать, что в n-мерном пространстве такую ось можно провести для любых n невырожденных точек (доказывается, например, построением базиса из векторов к этим точкам, а потом построением нужной оси в этом базисе).
Спасибо, Федя, Витя и все остальные, кто пишет мне уточнения и комментарии к моим постам :)
April 20, 2021
===
Один из самых классических объектов в комбинаторике — это число разбиений p(n): сколькими способами число n можно представить в виде суммы натуральных слагаемых, если мы не различаем способы, отличающиеся только порядком слагаемых (или, что то же самое, предполагаем, что слагаемые упорядочены по неубыванию).
Так,
p(1)=1,
p(2)=2 (потому что 2=1+1),
p(3)=3 (потому что 3=2+1=1+1+1),
p(4)=5 (потому что 4=3+1=2+2=2+1+1=1+1+1+1),
p(5)=7 (упражнение),
и так далее.
Разбиению числа n можно сопоставить диаграмму Юнга: фигуру из клеток в первом квадранте, у которой число клеток в k-й строке это k-е слагаемое. Например, вот диаграмма Юнга для разбиения 15=6+5+3+1:
Один из самых классических объектов в комбинаторике — это число разбиений p(n): сколькими способами число n можно представить в виде суммы натуральных слагаемых, если мы не различаем способы, отличающиеся только порядком слагаемых (или, что то же самое, предполагаем, что слагаемые упорядочены по неубыванию).
Так,
p(1)=1,
p(2)=2 (потому что 2=1+1),
p(3)=3 (потому что 3=2+1=1+1+1),
p(4)=5 (потому что 4=3+1=2+2=2+1+1=1+1+1+1),
p(5)=7 (упражнение),
и так далее.
Разбиению числа n можно сопоставить диаграмму Юнга: фигуру из клеток в первом квадранте, у которой число клеток в k-й строке это k-е слагаемое. Например, вот диаграмма Юнга для разбиения 15=6+5+3+1:
April 20, 2021
April 20, 2021
Хорошей замкнутой формулы (как формула Бине для чисел Фибоначчи) для чисел разбиения нет; интересно, что их количество растёт быстрее, чем любой полином, но медленнее, чем экспонента:
April 20, 2021
April 20, 2021
Но — если замкнутой формулы нет, то как можно (при желании) вычислять p(n) при большом n? Скажем, если перебор всех
p(100)=190569292
разбиений числа n=100 ещё можно поручить компьютеру, то перебирать все
p(1000)=24061467864032622473692149727991
разбиения числа n=1000 кажется не очень продуктивной идеей.
Один "технический" способ решения этого вопроса — это находить больше. А именно, пусть p_k(n) — число разбиений n в сумму (невозрастающих) слагаемых, которые все не превосходят данного k. Тогда, с одной стороны, p(n)=p_n(n), а с другой — числа p_k(n) уже несложно ищутся рекурсивно, когда мы перебираем варианты для самого большого слагаемого:
p_k(n) = \sum_{j=1}^k p_j(n-j).
p(100)=190569292
разбиений числа n=100 ещё можно поручить компьютеру, то перебирать все
p(1000)=24061467864032622473692149727991
разбиения числа n=1000 кажется не очень продуктивной идеей.
Один "технический" способ решения этого вопроса — это находить больше. А именно, пусть p_k(n) — число разбиений n в сумму (невозрастающих) слагаемых, которые все не превосходят данного k. Тогда, с одной стороны, p(n)=p_n(n), а с другой — числа p_k(n) уже несложно ищутся рекурсивно, когда мы перебираем варианты для самого большого слагаемого:
p_k(n) = \sum_{j=1}^k p_j(n-j).
April 20, 2021
April 20, 2021
Но нас будет интересовать другой способ — оказывается, на сами p(n) тоже есть рекуррентное соотношение, только чуть более сложное! Вот оно:
p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+p(n-15)-...
(Сумма обрывается, как только аргумент у p становится отрицательным.)
p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+p(n-15)-...
(Сумма обрывается, как только аргумент у p становится отрицательным.)
April 20, 2021
Применение этого равенства — кадр из великолепного видео Mathologer-а "The hardest "What comes next?" (Euler's pentagonal formula)" — которое я очень всем советую.
April 21, 2021
Как это соотношение можно получить? Беглый взгляд показывает, что это явно что-то нетривиальное.
Поэтому давайте его временно отложим в сторону, и применим к последовательности p(n) стандартный молоток (а точнее, кувалду) комбинаторики — рассмотрим производящую функцию этой последовательности:
P(q):=\sum_{n=0}^{\infty} p(n) q^n.
Поэтому давайте его временно отложим в сторону, и применим к последовательности p(n) стандартный молоток (а точнее, кувалду) комбинаторики — рассмотрим производящую функцию этой последовательности:
P(q):=\sum_{n=0}^{\infty} p(n) q^n.
April 21, 2021
Если бы мы работали не со всеми разбиениями n, а только с разбиениями в сумму слагаемых, не превосходящих k, то производящая функция развалилась бы в произведение k скобок-сомножителей:
April 21, 2021
April 21, 2021
Первая скобка отвечает за единицы, вторая за двойки, и так далее — так что (сгруппировав одинаковые слагаемые) разбиению n, в котором a_1 единиц, a_2 двоек,..., a_k слагаемых, равных k, мы сопоставляем произведение мономов из этих скобок, где q^{1*a_1} взят из первой скобки, q^{2*a_2} из второй, и т. д..
А дальше — каждая скобка "собирается", как сумма геометрической прогрессии.
А дальше — каждая скобка "собирается", как сумма геометрической прогрессии.
April 21, 2021