Почему математики ненавидят фильм «Умница Уилл Хантинг»

Эта классическая картина, удостоенная «Оскара», продемонстрировала зрителям удивительно простую математическую задачу

Я до сих пор помню тот вечер, когда впервые посмотрела фильм «Умница Уилл Хантинг» вместе с мамой. Мэтт Деймон играл уборщика в Массачусетском технологическом институте. Вытирая полы в коридоре, он прошёл мимо доски, на которой была написана сложная математическая задача. Остановился и начал решать её. Я заворожённо наблюдала, как он создавал, казалось бы, неразборчивые конструкции из точек и линий — пока внезапно из лекционного зала не вышел профессор математики и не прогнал его.

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

Но потом, когда я стала старше и стала лучше разбираться в математике, я списала всё это на голливудскую выдумку. Пусть фильм «Умница Уилл Хантинг» и рассказывает отличную историю, но он не очень реалистичен. На самом деле эта математическая задача не выдерживает тщательного анализа. В связи с недавней церемонией вручения премии «Оскар» многие вспоминают прошлых лауреатов — в том числе и фильм «Умница Уилл Хантинг». Стоит присмотреться к доске в фильме, который в 1997 году получил девять номинаций и выиграл в категориях «Лучший оригинальный сценарий» и «Лучшая мужская роль второго плана».

Основано на реальных событиях

Фильм был вдохновлён реальной историей — той, которую я лично нахожу гораздо более увлекательной, чем сказочная версия в «Умнице Уилле». В центре настоящей истории — Джордж Данциг, который однажды станет известен как «отец линейного программирования».

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

Данциг заметил, что задачи казались сложнее, чем обычно, но всё же решил обе и сдал свои решения Нейману. Как оказалось, он решил две из самых известных на тот момент нерешённых задач в статистике.

Это было действительно впечатляющим достижением. Напротив, математическая задача, представленная в голливудском фильме, решается очень легко, как только вы освоите терминологию. Я даже помогу вам её решить. Согласно фильму, задача заключается в следующем: нарисовать все гомеоморфно неприводимые деревья размера n = 10.

Прежде чем мы пойдём дальше, я хочу отметить две вещи. Во-первых, изложение этой задачи — это, по сути, самое сложное в ней. Совершенно нереалистично ожидать, что неспециалист — независимо от его математических способностей — будет знаком с техническим языком, использу��мым для формулировки задачи. Но это подводит меня ко второму моменту: после перевода технических терминов на нормальный язык сама задача оказывается простой. Набравшись терпения и дав несколько подсказок, её можно было бы поручить даже детям.

Решение задачи из фильма «Умница Уилл Хантинг»

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

Термин «гомеоморфный» в основном означает, что узлы в этой сети всегда располагаются в определённой последовательности; точная форма дерева не так важна, как последовательность связей. Когда я провожу связь между узлами A и B, я могу сделать эту связь длиннее, короче или слегка повернуть её, и это не будет иметь значения, пока общая структура сети остаётся прежней. Главное — это то, что A соединяется с B.

Чтобы посмотреть на это с другой стороны, представьте себе дерево в форме буквы X с пятью узлами и дерево в форме буквы K с пятью узлами. Эти деревья считаются одним и тем же деревом, поскольку количество узлов и последовательность связей остаются неизменными при смене формы.

А «неприводимый» в данном случае означает, что к каждому узлу графа должно вести либо одно, либо три и более рёбер (линий), так что ни один узел не соединяется только с двумя рёбрами: если к узлу ведут только два ребра, их можно свести (редуцировать) к одному.

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

Чтобы продемонстрировать это, сначала нарисуйте дерево, состоящее из одного центрального узла, от которого отходят девять связей, — в результате мы получим в общей сложности 10 узлов. Эта конструкция соответствует требуемым критериям — это одно из наших гомеоморфно неприводимых деревьев размера n = 10. Отлично!

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

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

Для этого подхода мы можем определить n_k как количество узлов n с k связями. Поскольку дерево должно быть неприводимым, не существует таких обстоятельств, при которых мог бы существовать n₂, поэтому n₂ = 0. Кроме того, мы знаем, что дерево должно иметь в общей сложности 10 узлов — это означает, что у вас никогда не будет n₁₀ или n₁₁ и так далее. Максимальное значение — n₉.

Тогда мы можем записать известные нам данные в виде математической формулы:
n₁ + n₃ + n₄ + n₅ + n₆ + n₇ + n₈ + n₉ = 10

Обратите внимание, что мы пропустили n₂, поскольку знаем, что оно равно 0.

Есть ещё одно ограничение, которое мы можем применить. Наше дерево с 10 узлами в конечном итоге будет иметь 18 линий, или соединений, между ними, если учесть, что связь между узлом A и узлом B считается дважды: одна — A-B, а другая — B-A. Мы можем использовать это для построения уравнения, в котором каждый узел и каждое соединение представлены отдельно. Например, если узел связан с одним другим узлом, это создаёт одно соединение: 1n₁. Если один узел связан с тремя другими узлами, будет создано три соединения, то есть 3n₃, и т. д. Это приводит нас к следующему уравнению:
n₁ + 3n₃ + 4n₄ + 5n₅ + 6n₆ + 7n₇ + 8n₈ + 9n₉ = 18

Теперь у нас есть два уравнения, которые ограничивают наши варианты рисования дерева. Но нам нужно объединить их, чтобы определить термины, наиболее релевантные для нашей задачи. Вы можете вычесть первое уравнение из второго, чтобы получить:
2n₃ + 3n₄ + 4n₅ + 5n₆ + 6n₇ + 7n₈ + 8n₉ = 8

Это уравнение служит ориентиром для рисования различных деревьев. Идея заключается в том, чтобы выбрать члены, которые в сумме дадут 8, если сложить их первые целые числа, или коэффициенты. Посмотрите, например, на 8n₉. Из него следует, что для построения нашего дерева нам нужно только одно n₉, что соответствует рисунку, на ко��ором один узел имеет девять связей.

Если вы попытаетесь нарисовать n₈, то попадёте в тупиковую ситуацию: не найдётся ни одного дерева, отвечающего нашим критериям. Если бы вы пользовались нашим уравнением в качестве ориентира, то даже не стали бы пытаться его рисовать, поскольку сразу поняли бы, что невозможно объединить 7n₈ с другим членом так, чтобы сумма первых цифр у них равнялась 8.

Но узел с семью связями, n₇, может подойти, если вы объедините его с n₃, то есть вы можете объединить дерево с семью связями (обозначенное в уравнении как 6n₇) и дерево с тремя связями (2n₃), чтобы найти другое решение задачи. И с этого момента вы можете продолжить процесс!

Существуют примеры получше

Я могу понять, почему создатели фильма «Умница Уилл Хантинг» не стали использовать реальную работу Данцига. Решение, которое он придумал, было не коротким — и деревья, вероятно, более привлекательны визуально для кадра.

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

Например, в области геометрии многие прорывные открытия, касающиеся мозаичного покрытия плоскости, были сделаны амбициозными людьми, которые не изучали математику или что-либо подобное ей. Одно из моих любимых открытий произошло в 2022 году, когда пенсионер, бывший печатник Дэвид Смит, наконец-то обнаружил «плитку Эйнштейна», которую математики очень долго искали, — многоугольник, способный полностью заполнить плоскость без каких-либо промежутков и без повторения образующегося узора.