Недавно узнал о такой области математики, как "Оптимальный транспорт". Несмотря на довольно естественные задачи и немалую историю, в школе и университете я ничего о ней не слышал. Зато эта область сейчас крайне популярна в науке: постоянно выходят новые статьи, а компании наподобие Apple и Microsoft нанимают людей для разработки новых алгоритмов оптимального транспорта

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

Кстати, работает это и в другую сторону: если нужно что-то собрать и переместить в одну точку. Заметьте как естественно это выглядит. И неудивительно: в природе встречаются похожие формы. Примеры есть в комментариях

#математика

Сегодняшний опыт потребует самого простого и вкусного реквизита – мандаринки. Начните очищать фрукт с одного из полюсов, а затем убирайте кожуру, сохраняя толщину полосы постоянной (например, 1 сантиметр). В конце получится интересная кривая известная науке как клотоида, а также как спираль Эйлера или Корню. Чем тоньше будет полоса, тем более длинной и интересной получится спираль

Эта форма имеет важное практическое применение. Например, её используют при строительстве дороги для автомобилей или поездов. Если участок пути сделан в форме части клотоиды, водителю будет легче повернуть, плавно поворачивая руль. Кроме того, эта кривая применяется в оптике. Я немного писал о клотоиде раньше здесь

Вот так даже в обычной мандаринке скрывается много интересной математики

#математика #эээксперименты

Кубик Рубика появился по историческим меркам совсем недавно: в 1974 году и вскоре покорил мир. Помимо увлекательного способа провести досуг, пока ещё не изобрели тикток, и целого направления спорта, он также открыл потрясающий плацдарм для математиков. Такой небольшой разноцветный кусок пластика содержит целую вселенную, изучать которую отправились учёные со всего мира. Один из самых простых, но любопытных вопросов – сколько всего возможных состояний у кубика Рубика? Для начала – у самого обычного: 3 на 3

На оригинальной упаковке Ideal Toy Company гордо заявляла, что кубик может быть разобран в более, чем 3 миллиарда состояний. Однако, математики быстро поняли, что компания немного ошиблась. А именно – на 8 порядков, в 100 миллионов раз. На самом деле, у кубика Рубика порядка 43 квинтиллионов, а именно 43 252 003 274 489 856 000 возможных состояний

Как шутил про это заявление математик Джон Аллен Паулос – это всё равно, что МакДональдс хвастался бы, что они продали больше 120 бургеров

#математика

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

Но вот что интересно: решение состоит из 31 хода. В то же время кубик был разобран за 17 ходов, а „число Бога“ – максимальное число ходов, за которое кубик может быть собран из любого состояния – 20. То есть, решение могло бы быть быстрее ещё на треть! Но люди собирают кубики не самыми короткими алгоритмами, а послойно – так гораздо легче мыслить. Оптимальное „решение Бога“ вряд ли может быть найдено человеческим мозгом за короткое время, которое даётся на соревнованиях. Здесь компьютеры бесспорно лучше людей

#математика

Насколько сложно решать большие кубики Рубика? На удивление – немногим сложнее, чем обычный кубик 3 на 3

Может показаться, что чем больше сторона, тем сложнее решение. На самом деле, большие кубики решаются слой за слоем теми же алгоритмами, что и обычная головоломка. Чтобы научиться их собирать, нужно уметь справляться с кубиком 3 на 3 и запомнить пару специфичных деталей. В остальном это повторение одних и тех же действий. Долго, но не сложно. Есть даже пример решения гигантских кубов со стороной в 65365 деталей на компьютере

Гораздо интереснее после изучения обычного кубика решать головоломки других форм

#математика

Можно ли собрать кубик Рубика, если случайно крутить разные стороны?

У обычного кубика Рубика со стороной 3 на 3 есть 18 возможных движений. Если не уметь решать головоломку, может быть получится собрать её, просто вращая случайную сторону пока кубик не будет собран?

Из предыдущего поста вы знаете, что случайно блуждая в трёхмерном пространстве вероятность попасть в нужную точку равна примерно 34%. Здесь же пространство девятимерное (9 пар из 18 движений, потому что некоторые ходы „отменяют“ друг друга). Точно посчитать вероятность для высоких размерностей непросто, но она составляет меньше 8%. В 92% случаев кубик не получится собрать случайными движениями, даже если делать их бесконечно долго

Если не крутить центральные части, пространство становится шестимерным и вероятность случайно собрать кубик повышается почти до 10,5%. Но даже так сборка кубика – это довольно маловероятное событие

UPD: пост некорректен. Разбор читайте здесь и в комментариях. Кубик можно собрать случайными движениями

#математика

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

Сперва коллекция пополнялась быстро: до половины шанс получить новое животное выше, чем то, что уже есть. Но чем больше наклеек собрано, тем тяжелее получить ещё одну неповторяющуюся. Когда уже есть 11 животных, вероятность недостающего – 1/12 и в среднем придётся заказать роллы ещё 12 раз!

Математическая задачка в основе этой акции уже описана. В среднем для получения 12 наклеек придётся сделать 37 заказов. Я смоделировал 10 тысяч голодных студентов на Python. На графике видно, что части повезло собрать коллекцию быстро, в среднем нужно почти 40, а одному неудачнику пришлось делать 140 заказов

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

#математика

Готовим окрошку из кошки

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

Удивительно, что повторяя это действие дальше, набор пикселей снова превращается в исходное изображение. Так можно, например, засекретить картинку, отправить кому-нибудь, а получатель сможет разокрошить исходное сообщение

У этого преобразования много интересных свойств и применений, но самое шедевральное в нём – это название. Где ещё можно всерьёз прочитать заголовок наподобие „свойства окрошки из кошки“?

#математика

Продолжаю играться с графами после соревнования по сборке кубиков Рубика и других головоломок. Так выглядит граф группы перестановок последовательности из 8 элементов. Начинаем с упорядоченных цифр от 0 до 7 и переставляем пары соседних цифр (здесь выбраны только 3 возможных перестановки). Соединяем новую последовательность с предыдущей. Применяем такие перестановки несколько раз и визуализируем граф: получается такая красота

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

#математика

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

Блинные числа, кстати, исследовал Билл Гейтс. Вот его статья, опубликованная уже после покидания Гарварда

Спасибо Александру Червову за наводку

#математика

Когда свобода действий вредит ситуации

Однажды на олимпиаде по теории игр мне встретилась интересная задача. Прежде, чем к ней перейти, поговорим про упрощённый вариант. Муж и жена выбирают, как провести вечер. Из вариантов – пойти смотреть футбольный матч или посетить театр. Муж предпочитает спорт, а жена – искусство, но оба хотят провести вечер вместе. Если они пойдут на футбол, муж будет в восторге – вечер на 10 из 10, а жена насладится компанией супруга, но в целом оценит мероприятие на 5 баллов. В театре ситуация будет противоположной. Если же супруги пойдут в разные места, оба будут расстроены и оценят вечер на 0 баллов. Нужно сказать, как пара проведёт вечер

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

Теперь перейдём к олимпиадной формулировке. Ситуация будет такой же, но в обсуждении будет дополнительный шаг: после решения мужа жена может поменять своё. Для мужа в случае выбора им театра ничего не изменится. Однако, зная о том, что финальное слово за женой, он теперь может сказать „Ты как хочешь, а я пойду на футбол“. Тогда уже перед супругой окажется выбор: обрекать обоих на грустное одиночество или согласиться присоединиться и провести вечер на 5 баллов. Вот такой парадокс: у неё во второй ситуации большая свобода действий, но исход оказывается хуже, чем при первом раскладе

#математика

И раз уж у нас случилась внезапная серия постов про экономику, вот вам задача про деньги и распознавание мошенников

В одном из телеграм-чатов опубликовали сообщение с невероятно выгодным предложением. Обещают гарантированный доход – 6% прибыли в день – нужно лишь перевести инвестиции тюменскому Уоррену Баффету прямо сейчас. Звучит выгодно, надо брать!

Но вряд ли автор сообщения подозревал насколько это предложение выгодно. 6% в день при применении сложного процента даёт скромные 172441114627% годовых. Вложив одну копейку, можно через год забрать 17 миллионов рублей (и ещё немного на покушать останется). А чтобы догнать Илона Маска на пике его состояния с 350 миллиардами долларов, достаточно вложить 203 доллара на годик. Ну или вложить доллар и подождать 457 дней. Внимание, вопрос: стоит ли вкладывать в такое дело хоть одну копейку?

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

#математика

Продолжаем серию с подборкой старых статей списком удивительных математических явлений! И начнём с основ:

📝 Что такое математика
📝 Зачем нужна парабола
📝 Как решать квадратные уравнения

Освоили? Переходим к самому интересному:

📝 Геометрия футбольного мяча
📝 На Манхэттене π = 4
📝 Как связаны кролики и Парфенон?!

Если у вас закипели мозги, предлагаю дать им отдохнуть и прочитать эти статьи (отдых тоже должен быть созидательным, да-да):

📝 Забавные математические теоремы
📝 Самые интересные Шнобелевские премии
📝 Как вырастить величайшего хоккеиста 🔥

#математика #подборка_статей

Математическая задачка! В статье по изучению клеток при хронической обструктивной болезни лёгких учёные-медики собирали данные от нескольких групп пациентов, по 3 человека в каждой. Возраст людей в группах они указали в формате M ± S, где M – среднее, а S – стандартное отклонение. Зачем так делать, когда можно просто перечислить 3 числа, я не знаю, но это вопрос не по математике

Задача: укажите возраст пациентов в каждой группе, если данные для них такие:
1. 72 ± 2
2. 30 ± 4.36
3. 62 ± 11.53

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

Подсказка №1 (если забыли как считать M и S):
📝 Если возраст пациентов – X, Y и Z, то M = (X + Y + Z) / 3
📝 Удобнее работать не с S, а с дисперсией D = [(X - M)^2 + (Y - M)^2 + (Z - M)^2] / 2. Для того, чтобы получить стандартное отклонение, нужно взять из неё корень: S = √D

Подсказка №2:
📝 Возраст пациентов обычно указывается в годах. Это целые числа

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

#математика

Какие теоремы звучат как крутые фразы для татуировок?

#математика

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

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

Ещё более странный случай и больше информации – в треде

#математика #программирование

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

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

Если проблема кажется непонятной и неразрешимой, возможно стоит посмотреть на неё систематически. Или под непривычным углом

#математика@chelovek_nauk #программирование@chelovek_nauk