Математика для гиков

В 1999 году Френсис Су, профессор математики из колледжа Харви Мадд, опубликовал исследование, в котором объяснил, как решить проблему справедливого дележа, используя лемму Шпернера, теорему, затрагивающую раздел математики, известный как комбинаторика (см. главу 1.26). Изначально лемма затрагивает треугольники. Возьмите треугольник и разделите его внутри на маленькие треугольники. Вы можете разделить его на любое количество треугольников; просто убедитесь, что они плотно прилегают друг к другу и между ними нет свободного пространства. Дальше обозначьте вершины большого треугольника цифрами 1, 2 и 3 так, чтобы каждая вершина была обозначена разными цифрами. На этом этапе заметьте, что углы некоторых треугольников меньшего размера касаются как минимум одной стороны большого треугольника. На каждом угле напишите цифру. На стороне между вершинами 1 и 2 отметьте каждый угол меньших треугольников 1 или 2. (Какую цифру вы поставите, зависит только от вас.) На стороне между вершинами 2 и 3 отметьте каждый угол 2 или 3, а на стороне между углами 3 и 1 отметьте каждый угол 3 или 1. Что касается углов внутри большого треугольника, вы можете отметить их цифрами 1, 2 и 3 в любом порядке. Лемма Шпернера утверждает, что там должен быть хотя бы один маленький треугольник с вершинами 1, 2 и 3. Их может быть больше чем один, но их всегда будет нечетное число.

Когда лемму Шпернера применяют при дележе аренды, цифры заменяются буквами, которые обозначают имя каждого арендатора, а каждый треугольник, большой и маленький, представляет разное распределение аренды. Согласно лемме, существует такое распределение аренды, которое удовлетворит каждого жильца настолько, что он не будет завидовать ничьей комнате или доле аренды. Другими словами, так как в большом треугольнике есть маленький треугольник с вершинами 1, 2 и 3, то есть и способ распределить комнаты и аренду так, чтобы все были счастливы.

Лемма Шпернера – это пример математической находки, которая может показаться абстрактной и неприменимой в повседневной жизни, но на самом деле может помочь людям решить проблему быстро и эффективно.

Справедливый дележ после Второй мировой войны

Особый пример справедливого дележа возник после Второй мировой войны, когда члены антифашистской коалиции пытались выяснить, что делать с Берлином. В итоге они поделили город на четыре секции. Секции США, Великобритании и Франции сформировали Западный Берлин, а секция СССР сформировала Восточный Берлин.

2.9. Справедливое разрезание торта на куски

Математическое понятие: справедливый дележ

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

1. Ни один уже получивший кусок торта человек не хочет вместо него кусок, принадлежащий другому человеку. Тогда такое разделение не будет вызывать зависти.

2. Будет невозможно сделать кого-то счастливее, чем они уже есть, и при этом не расстроить никого другого. Это условие называется результативностью.

3. Разделение должно быть справедливым, то есть каждый человек должен видеть, что все куски имеют одинаковую ценность. (Например, если торт делили три человека, и каждый из них любил цветы из крема, они бы увидели, что разделили справедливо, если бы на каждом куске был цветок.)

В 2014 году два исследователя, Джулиус Барбанель из Юнион-колледжа и Стивен Брамс из Нью-Йоркского университета, опубликовали алгоритм в журнале The Mathematical Intelligencer, который, по их утверждению, отвечает всем трем критериям, результатом чего является идеальное разрезание торта на доли. (Однако их метод предполагает, что торт делят всего лишь два человека.) Алгоритм берет во внимание тот факт, что торт «гетерогенный», то есть он имеет разные части, которые два человека ценят по-разному. Один человек, например, может любить большое количество крема на внешнем крае торта, а другому больше нравится тесто, нежели крем. Кроме того, этот метод зависит от третьей стороны, которая выступает в качестве судьи. Наконец, в алгоритме упоминается функция плотности вероятности, которая является просто математическим способом представления предпочтений людьми разных частей торта.