Недавно узнал о такой области математики, как "Оптимальный транспорт". Несмотря на довольно естественные задачи и немалую историю, в школе и университете я ничего о ней не слышал. Зато эта область сейчас крайне популярна в науке: постоянно выходят новые статьи, а компании наподобие 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. Если у вас есть бизнес, берите акцию на вооружение: она завлекает людей, но требует больше усилий, чем кажется

#математика

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

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

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

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

#математика