Математическое отражение реальности О честном делении пирогов, числах Мерсенна и подтасовке выборов

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

Для теоретиков

В этом разделе мы приводим самые интересные абстрактные (и даже немного серьезные) новости, с которыми нашим читателям удалось познакомиться на страницах Ленты.Ру за 2009 год.

Начнем, пожалуй, с того, что в октябре 2009 года состоялось знаменательное событие: интернет-проект GIMPS (Great Internet Meresenne Prime Search) получил-таки свои премиальные 100 тысяч долларов. Эта сумма стала наградой за обнаружение простого числа (то есть числа, среди делителей которого имеется только единица и оно само), длина десятичной записи которого составляет более 10 миллионов знаков. Если быть точным, то само открытие состоялось еще в 2008 году, когда ученые из Калифорнийского университета обнаружили число Мерсенна (простое число вида 2ⁿ — 1), в записи которого присутствует 12 миллионов 978 тысяч 189 знаков. Однако деньги организаторы получили почти на год позже.

Отличились в 2009 году японцы. Они смогли посчитать число Пи с точностью до 2 триллионов 576 миллиардов 980 миллионов 377 тысяч 524 знаков, что в два раза больше предыдущего рекорда (первые миллион цифр после запятой у числа Пи можно посмотреть здесь). Подобные масштабные вычисления делаются не просто "на интерес", а позволяют исследователям проверять различные гипотезы, имеющие существенное значение для приложений. Вот, например, до сих пор неизвестно, все ли цифры от 0 до 9 встречаются в записи этого числа бесконечное число раз. Гипотеза, разумеется, утверждает, что это так, однако доказать ее пока не представляется возможным.

Также в прошедшем году американцы посчитали все конгруэнтные числа до триллиона. Конгруэнтными называют натуральные числа, выражающие площадь прямоугольного треугольника с рациональными сторонами. Наименьшим подобным объектом является 5 - это площадь треугольника со сторонами 3/2, 20/3 и 41/6. Изучение этих чисел вплотную связано со знаменитой гипотезой Берча и Свиннертон-Дайера, за решение которой полагается награда в миллион долларов от Математического института Клэя. Конгруэнтные числа — настолько сложный объект, что еще в 80-х годах прошлого века относительно чисел меньше 1000 оставались некоторые неясности. Таким образом, достижение американцев действительно достойно быть упомянутым в нашем списке.

Не обошли в этом году и геометрию. Например, некоторых успехов удалось добиться в вопросе плотных упаковок. Эта задача представляет собой всего лишь строгую математическую формализацию трудностей, с которыми мы сталкиваемся в обычной жизни, когда, например, собираем чемодан в поездку и хотим впихнуть в него как можно больше вещей. Задача звучит так: в замкнутой области пространства (чемодане) необходимо разместить геометрические фигуры (вещи) так, чтобы отношение их объема к объему области было максимальным. Традиционно эту задачу решают для простейших геометрических фигур — тетраэдров. В этом году сразу два коллектива математиков установили рекорды на этом поприще.

Сначала исследователи из Принстонского университета добились плотности упаковки в 0,782. Данный результат был не сильным продвижением вперед по сравнению с предыдущим рекордом, который составлял 0,778 и был установлен в 2006 году в том же университете. Спустя несколько месяцев ученые из университета Кента перекрыли это достижение, добившись плотности упаковки более чем в 0,85. Отдельно необходимо заметить, что в первом случае упаковки получались сложными и «скучными» — тетраэдры не соприкасались гранями и вообще выглядели достаточно хаотично, в то время как во втором случае ученым удалось получить квазикристаллическую структуру, то есть материал, обладающий решеткой с симметрическими ячейками, в то время как общей периодичности в материале не наблюдается. Разумеется, у второй упаковки больше возможностей найти применение.

В связи с плотной упаковкой хочется вспомнить и новость про гипотезу Кельвина. Формулировка задачи, относительно которой Кельвин высказал свою гипотезу, немного напоминает формулировку задачи о плотной упаковке: необходимо предъявить такую схему распределения многогранников одинакового объема в пространстве, чтобы площадь стенок разбиения была минимальной. Гипотеза, в свою очередь, утверждает, что решением будут слепленные урезанные октаэдры (многогранники, строение которых напоминает «разлиновку» обычного футбольного мяча). Контрпримеров к этой гипотезе достаточно много (например здесь представлена конструкция, в которую входят многогранники с 12 и 14 гранями), однако в 2009 году ученым из Университета Бата удалось построить целую серию контрпримеров. Внимания этот факт заслуживает из-за метода, который применили ученые — им удалось приспособить для работы трехмерную версию уравнения Свифта-Хоенберга, которое использовалось для анализа периодических структур на плоскости.

Еще одним интересным результатом, достигнутым в прошлом году, стало создание алгоритма подсчета всевозможных раскрасок графов. Графами в математике называют объекты, которые можно представлять себе как множество точек на плоскости, соединенное ребрами. Они полезны в самых разнообразных областях человеческой деятельности. Например вершины могут представлять собой сайты — а ребра будут соединять только те сайты, между которыми существует прямая гиперссылка. В качестве подобного графа, теоретически, можно представить всю глобальную сеть (как выглядит интернет в таком представлении, можно посмотреть тут).

Теперь представим, что в этом графе нам требуется разбить все сайты на фиксированное число групп. Чтобы определять принадлежность к той или иной группе, мы будем просто раскрашивать ту или иную вершину в один из фиксированного набора цветов. Сколько существует вариантов таких раскрасок? В 2009 году ученым удалось предложить новый алгоритм решения этой задачи, который работает в несколько раз быстрее предыдущих. Суть алгоритма заключается в особом кодировании состояний при помощи подходящего многочлена.

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

Для практиков

В этом разделе мы поговорим о том, как мощные математические идеи применялись на практике.

Помните, мы в начале упомянули о зомби? Так вот, в прошедшем году появилось сразу два исследования, посвященных этим созданиям. Правда, если быть точным, речь в работах идет о математических моделях процессов распространения информации, диффузии в разломах кристаллов и прочих, а зомби появились просто как забавный способ привлечь внимание к результатам. Однако это не отменяет полезности проведенных исследований на тот случай, если какой-нибудь из фильмов Джорджа Ромеро вдруг начнет воплощаться в жизнь.

В рамках первой статьи ученые пытались разобраться в том, что делать людям в ситуации, когда зомби-вирус неожиданно вырвался на свободу. Оказалось, что единственное спасение заключается в тотальном истреблении нежити - на разработку вакцины или изоляцию зараженных просто не останется времени. Дело в том, что вирус способен захватить целый город в 500 тысяч жителей всего за трое суток. Впрочем, повод для оптимизма в данном случае есть: зомби у исследователей были бессмертные, а согласно каноническим представлениям, обезглавливание живого мертвеца приводит к его окончательной гибели.

Целью другого исследования стала стратегия, которой следует придерживаться, если вдруг недалеко от вас оказалась толпа голодных зомби. Как оказалось, самый надежный способ спастись — спрятаться в каком-нибудь подходящем лабиринте (на роль оного прекрасно подойдет супермаркет с его бесчисленными полками, холодильниками и стойками). Впрочем, в отличие от предыдущего исследования, ситуация, изучавшаяся учеными, была, возможно, излишне оптимистична. В работе предполагалось, что зомби бродят случайно, в то время как канонические живые мертвецы традиционно могут ориентироваться, например, на запах жертвы.

Удалось в 2009 году математикам изучить и такое загадочное понятие, как счастье. Если быть точным, то ученые решили измерить, насколько общество является счастливым. Для этого они прибегли к помощи блогов (на взгляд автора этих строк, не самый удачный выбор из соображений репрезентативности). Чтобы оценить коллективное самочувствие людей, ученые отбирали записи, в которых присутствовали слова "I feel", а также анализировали музыку, которую слушали авторы блогов. Оказалось, что с 2005 года уровень счастья вырос примерно на 4 процента. Кроме этого удалось определить, что самые счастливые дни - праздники, например Рождество и День Святого Валентина, а наибольшую грусть навевают годовщины различных драматических событий, например 11 сентября 2001 года. После появления этого исследования коллеги предложили ученым ответить при помощи собранных данных на извечный вопрос современной музыки: какие исполнители продают больше дисков — веселые или грустные?

Другой важной проблемой, к решению которой ученые приблизились в 2009 году, стала задача честного деления пирога на троих, которая заключается в следующем. Предположим, что необходимо поделить пирог на N человек. При этом нам известно, что у каждого из них имеются собственные критерии сравнения различных кусков пирога. Например, кому-то больше нравится кусок с украшениями, а кто-то не любит, когда слишком много начинки. Возникает вопрос, всегда ли можно разрезать пирог так, чтобы каждый из N человек остался доволен, то есть, сравнив свой кусок с остальными, пришел бы к выводу, что его не обделили. В прошлом году ученые научились делить пирог почти честно на трех человек.

А еще мы обещали рассказать про парадокс двух конвертов. Его суть заключается в следующем: предположим, что у нас имеется пара конвертов. В обоих деньги, причем в одном в два раза больше, чем в другом. Мы случайно берем один из конвертов, заглядываем в него и считаем деньги. После этого у нас появляется выбор: оставить деньги себе или поменять конверты. Вопрос: что делать? Оказывается, что простые рассуждения способны завести нас в совершенно безвыходную ситуацию.

Действительно, пусть игрок обнаружил в конверте x рублей. Тогда с вероятностью 0,5 в другом конверте 2x или 0,5x. В результате среднее взвешенное ожидаемое значение составляет 1,25x, что уж точно больше имеющейся на руках у игрока суммы, и поэтому игроку выгоднее сделать обмен. Однако те же самые рассуждения, примененные к другому конверту, утверждают, что игроку снова выгоднее будет поменять конверты. Разумеется, эти рассуждения совершенно неверны с точки зрения теории вероятности, однако наличия подобной проблемы в действительности это не отменяет.

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

Наконец в завершение хотелось бы поговорить о спорте. В 2009 году на эту тему было много интересных новостей. Например, математики доказали, что футбол — это не только самая популярная в мире спортивная игра, сколько плохо организованный эксперимент по сравнению физической формы команд. Или экономисты предложили свой способ оценки рейтинга баскетболистов. Однако самыми интересными, на наш взгляд, стали достижения ученых в области заплывов.

Исследователей заинтересовал вопрос, который уже достаточно давно мучает спортсменов-гребцов. Предположим, мы рассадили их в длинную гребную лодку и дали каждому по веслу. Спортсмен может грести либо с одного борта лодки, либо с другого. При этом, разумеется, каждый его гребок сообщает лодке ускорение, поперечное направлению движения. Возникает вопрос, как рассадить людей так, чтобы в результате лодка в перпендикулярном направлении не колебалась. Как оказалось, это равносильно следующей задаче: в наборе подряд идущих целых чисел 1, 2, ..., N необходимо расставить знаки так, чтобы сумма чисел оказалась равна нулю.

В рамках исследования, помимо теоретических результатов, касающихся данной задачи (например, оказывается, это можно сделать только в том случае, если N кратно четырем, то есть 4, 8, 16 и так далее) исследователи сделали неожиданное практическое открытие: им удалось обнаружить рассадку восьмерки (лодки, в которой восемь гребцов и рулевой), которая ранее никому не была известна.

Пожелания

На этом разрешите закончить. В 2009 году было много чего замечательного и интересного, однако все охватить в узких рамках одной заметки не представляется возможным. От нового года мы, однако, ждем большего. Вот, например, математики научили нас защищаться от зомби, однако живыми мертвецами ужасы, подстерегающие нас, далеко не исчерпываются. Хотелось бы узнать, существуют ли какие-то математически обоснованные советы на случай вторжения на Землю инопланетян или полчищ вампиров. Или, например, какие есть проверенные способы упаковки невыпуклых многогранников в замкнутом объеме (этими объектами удобно представлять, например, носки). Но что бы там ни было, с Новым годом вас и побольше математики!