торта на куски
Математическое понятие: справедливый дележ
В следующий раз, когда вы окажетесь на чьем-либо дне рождения, подумайте, что такое простое действо, как разрезание торта, породило огромное количество математических мыслей. Как можно убедиться, что каждый гость был доволен куском, который ему отрезали, и, более того, не хотел ничей кусок больше, чем свой собственный? Задача становится сложнее, когда приходит понимание, что не всем может понравиться один и тот же кусок торта: некоторые любят больше крема; другие его вовсе не любят. Одни хотят цветочек на своем куске, другие хотят буквы. Математики попытались ответить на вопрос, есть ли способ разделить торт так, чтобы каждый человек остался доволен своим куском. На самом деле, идеальный метод разрезания торта между двумя людьми должен отвечать трем критериям:
1. Ни один уже получивший кусок торта человек не хочет вместо него кусок, принадлежащий другому человеку. Тогда такое разделение не будет вызывать зависти.
2. Будет невозможно сделать кого-то счастливее, чем они уже есть, и при этом не расстроить никого другого. Это условие называется результативностью.
3. Разделение должно быть справедливым, то есть каждый человек должен видеть, что все куски имеют одинаковую ценность. (Например, если торт делили три человека, и каждый из них любил цветы из крема, они бы увидели, что разделили справедливо, если бы на каждом куске был цветок.)
В 2014 году два исследователя, Джулиус Барбанель из Юнион-колледжа и Стивен Брамс из Нью-Йоркского университета, опубликовали алгоритм в журнале The Mathematical Intelligencer, который, по их утверждению, отвечает всем трем критериям, результатом чего является идеальное разрезание торта на доли. (Однако их метод предполагает, что торт делят всего лишь два человека.) Алгоритм берет во внимание тот факт, что торт «гетерогенный», то есть он имеет разные части, которые два человека ценят по-разному. Один человек, например, может любить большое количество крема на внешнем крае торта, а другому больше нравится тесто, нежели крем. Кроме того, этот метод зависит от третьей стороны, которая выступает в качестве судьи. Наконец, в алгоритме упоминается функция плотности вероятности, которая является просто математическим способом представления предпочтений людьми разных частей торта.
В первом шаге алгоритма каждый человек представляет свою функцию плотности вероятности, или ФПВ, судье. (Судья может принимать различные формы: компьютер, старшая сестра, прохожий на улице или родители.) Судья отмечает на торте все места, где ФПВ пересекаются; другими словами, где пересекаются предпочтения каждого человека. Судья назначает порции согласно этим предпочтениям, и если на этом этапе каждый человек получает куски одинакового размера, алгоритм останавливается, и все начинают есть. Например, скажем, что человек А любит шоколадный торт, а человек Б любит ванильный. Если торт поделен пополам двумя разными вкусами, то судья просто может разрезать торт по демаркационной линии и дать каждому человеку кусок, который ему больше нравится. Но если торт разделен не поровну, то человек с большим куском отдает часть своей доли другому человеку, начиная с того места, где степень его предпочтений является наименьшей. Этот процесс продолжается, пока объем порции каждого человека не станет одинаковым.
Помимо метода Брамса – Барбанеля, который помогает двум людям справедливо поделить торт, существует другой, более общий метод, который может помочь неограниченному количеству людей разделить торт на неограниченное количество кусков. Этот метод изобрели Брамс и другой математик, Алан Тейлор, он был опубликован в январе 1995 года в выпуске журнала American Mathematical Monthly. Этот общий метод несколько сложный, но суть в том, что после того, как торт был порезан человеком А, человек Б может обрезать некоторые куски, чтобы сделать их более одинаковыми, если он чувствует, что человек А несправедливо порезал торт. Затем человек В может обрезать куски, потом человек Г и так далее. Кроме того, этот метод обеспечивает наличие лишних кусков торта, поэтому если кто-то почувствует себя обманутым, они всегда смогут выбрать один из оставшихся кусков, который будет такого размера, каким бы его хотели видеть.
Справедливый дележ предполагает аддитивную полезность. Другими словами, если я люблю немного крема, тогда я полюблю и много крема; чем больше, тем лучше. С другой стороны, если удовольствие, которое я получил от поедания крема, было не аддитивным – другими словами, если бы оно было неаддитивной полезностью, – значит, после определенного количества сахарных вкусностей я не продолжу становиться счастливее. Исследования показали, что справедливый дележ не работает в ситуациях, связанных с неаддитивной полезностью.
2.10. Эффективная доставка посылок
Математическое понятие: задача коммивояжера
Когда вы получаете посылку от курьерской службы UPS, вы можете подумать, что математика не имеет никакого отношения в процессе ее доставки к вашей двери. Но на самом деле математика играет важную роль в том, как работники в грузовиках доставляют посылки.
В самом сердце операций UPS лежит процесс определения кратчайшего маршрута, который выберет водитель. У UPS есть примерно 96 000 транспортных средств, среди которых можно найти как машины, фургоны, мотоциклы, так и средства с альтернативными видами топлива, и каждый водитель посещает в среднем 150 пунктов назначений каждый день. Увеличение маршрута водителем хотя бы на одну милю будет стоить компании миллионы долларов в год. Поэтому у них есть огромный стимул сделать маршрут как можно короче и эффективнее.
Такая проблема – нахождение лучшего маршрута – хорошо известна математикам, которые называют ее задачей коммивояжера. Название было придумано, когда была распространена торговля «от двери до двери»; коммивояжер должен был посетить определенное количество домов за один день, поэтому ему было необходимо продумать маршрут, который позволит обойти их за наименьшее количество времени. Задача коммивояжера является сложной для решения, так как нужно принимать во внимание огромное количество факторов. Например, если водитель запланировал объехать 25 мест назначений в один день, то количество возможных маршрутов достигает 15 триллионов вариантов. Но благодаря компьютерным алгоритмам – набору инструкций, служащих определенной цели, – UPS может снизить число возможных маршрутов за короткий срок.
Усилия UPS в улучшении алгоритмов дали свои плоды в 2000-х, когда они создали компьютерную программу ORION (комплексная оптимизация и навигация на дороге). Математические вычисления программы ORION сэкономили их водителям миллионы миль в год. Вы можете сделать это и сами, если вам нужно выполнить ряд заданий, мысленно вы продумываете наиболее эффективный маршрут, чтобы минимизировать время и энергозатраты, например, чтобы дважды не возвращаться в одно и то же место или не попасть в пробку в час пик.
Эта проблема появилась и на больших экранах. В 2012 году вышел фильм, рассказывающий о четырех математиках, перед которыми стоит вопрос: давать ли военному ведомству США решение о равенстве классов сложности P и NP (см. главу 3.17), зная что обнародование их работы будет нести моральные последствия, как только военные получат решение, они смогут взломать любой код в мире и получат беспрецедентную власть.
2.11. Как алгоритмы влияют на ваш опыт работы в интернете?
Математическое понятие: алгоритмы
В сущности, алгоритм – это набор инструкций, который говорит вам, как достичь определенной цели за ограниченное число шагов. В теории алгоритмы не ограничены сферами математики и компьютеров. Если вы хотите смастерить скворечник, вам нужно следовать определенному набору инструкций. Если вы хотите сделать чашку на гончарном круге, вам опять же нужно будет следовать набору инструкций. Каждый из таких наборов инструкций является алгоритмом.
Вы наверняка знакомы с алгоритмами лучше, чем можете себе представить. В начальной школе, когда вы учились делить числа и складывать дроби, вы учились алгоритмам. Вы также учились алгоритмам, когда изучали последовательности действий при решении примеров (начать вычисления нужно всегда с того, что находится в скобках, а потом умножать, делить, прибавлять и вычитать). Другими словами, когда вы пытаетесь посчитать чаевые официанту в ресторане или сложить числа на салфетке, вы используете алгоритм.
Алгоритмы особенно важны в повседневном использовании Интернета. Если вы активный пользователь сети, вы сталкиваетесь с алгоритмами постоянно. Например, когда заказываете фильм, который вам порекомендовал Netflix, вы пользуетесь вычислительной мощностью алгоритма. Когда вы ищете слово в Google, определяете свои музыкальные предпочтения в Pandora, ставя лайки и дислайки песням, или ищете что-то на Amazon, алгоритмы обогащают ваш опыт в работе онлайн, соотнося то, что вам нравится и не нравится. С этой информацией сайты и программы могут предложить вам особые варианты, основываясь на ваших предпочтениях.
В 2006 году Netflix организовал соревнование, чтобы улучшить свой алгоритм по рекомендациям на 10 %, главный приз размером в 1 миллион долларов получила команда BellKor’sPragmatic Chaos. Ключом к победе стало то, что они предсказывали фильмы, которые понравятся людям, основываясь на разной информации, а потом сравнивали эти предсказания с оценками, которые зрители действительно в дальнейшем ставили фильмам. А рекомендации много значат для Netflix.
2.12. Объяснение парадокса Монти Холла
Математическое понятие: теория вероятности
Некоторые примеры математического мышления, такие, как парадокс дней рождения (см. главу 3.20), являются странными и нелогичными, но другие являются настолько ненормальными, что даже профессиональные математики с трудом верят в их подлинность. Одним из таких примеров является парадокс Монти Холла, названный в честь ведущего телешоу Let’s make a deal. Решение этой проблемы настолько удивительное, что даже после тщательного объяснения большинство людей будут чувствовать, что оно не может быть верным. В какой-то степени это математический эквивалент квантовой механики (область физики, которая изучает мельчайшие компоненты веществ): странный, в него трудно поверить, но он является верным.
В передаче ведущий предлагает игроку три двери. За одной из них находится новая машина; за двумя оставшимися – коза (или что-либо другое, не такое классное, как машина). Ведущий просит игрока выбрать дверь, за которой, по его мнению, находится машина. Потом, не открывая эту дверь, ведущий открывает другую дверь, показывая козу. Теперь игрок может изменить свой изначальный выбор. Вопрос состоит в том, стоит ли игроку придерживаться первоначального выбора или выбрать другую дверь.
Ответ: игрок всегда должен выбирать другую дверь. В начале игры вероятность выбора двери с машиной равна 1 к 3, но выбор другой двери на этом этапе удваивает шансы до 2 к 3. Как это возможно? Большинство людей считает, что изменение решения не имеет значения: после того, как ведущий открывает дверь, показывая одну из двух коз, шансы на выигрыш теперь составляют 1 к 2, так как одна дверь теперь прячет машину, а другая – вторую козу.
Но это убеждение не является правильным. Вы поймете почему, если возьмете лист бумаги и напишете все возможные варианты. Суть в том, что ведущий всегда открывает дверь, за которой находится коза. (Он никогда не откроет дверь, за которой прячется машина, иначе он испортит всю игру!) Теперь без опоры на нашу интуицию давайте выясним возможные перестановки:
• Вариант 1: Игрок выбирает дверь с козой № 1. Ведущий открывает дверь с козой № 2. Первоначальный выбор приведет к козе № 1, изменение решения приведет к машине.
• Вариант 2: Игрок выбирает дверь с козой № 2. Ведущий открывает дверь с козой № 1. Первоначальный выбор приведет к козе, изменение решения приведет к машине.
• Вариант 3: Игрок выбирает дверь с машиной. Ведущий открывает дверь с козой № 1 или козой № 2. Первоначальный выбор приведет к машине, изменение решения приведет к козе.
Итак, из этих трех вариантов можно сделать вывод, что в 2 из 3 случаев изменение решения ведет к машине. Результат абсолютно нелогичный, но абсолютно верный. Такова сила математики.
Похожей проблемой является коробка Бертрана, названная в честь Джозефа Бертрана, который написал о ней в книге, вышедшей в 1889 году. Представьте три коробки: одна с двумя золотыми монетами; одна с двумя серебряными монетами; и одна с одной золотой и одной серебряной монетами. Теперь выберите одну любую коробку и любую монету. Если она золотая, то какова вероятность того, что вторая монета тоже будет золотой? Вы можете подумать, что шансы составляют 1 к 2, но на самом деле 2 к 3.