В оскароносном кинохите «Умница Уилл Хантинг» зрителям предложили на удивление элементарную математическую головоломку
Многие до сих пор отчетливо помнят сцену из культовой драмы, где Мэтт Деймон в роли неприметного уборщика из Массачусетского технологического института замирает перед грифельной доской. Пока в коридорах МТИ кипит студенческая жизнь, герой вдумчиво наносит на поверхность хаотичное, на первый взгляд, нагромождение точек и линий. Это зрелище завораживало: казалось, на наших глазах рождается истина, пока строгий профессор не прерывал этот процесс, прогоняя юношу.
Согласно сюжету, перед нами была задача колоссальной сложности, над которой ведущие эксперты бились десятилетиями. Уилл Хантинг же справлялся с ней за считанные мгновения. В юности эта концепция скрытого гения, способного посрамить академическое сообщество, казалась вдохновляющей. Однако профессиональный взгляд на математику заставляет признать: перед нами классическая голливудская условность. На поверку задача с доски не выдерживает серьезной критики. Сегодня, когда фильм 1997 года, собравший россыпь наград и девять номинаций на «Оскар», снова оказывается в центре внимания, стоит разобраться, что же на самом деле было написано на той знаменитой доске.
Подлинная история за кадром
Хотя сценарий кажется сказочным, у него есть реальный прототип, чья судьба куда более примечательна. Речь идет о Джордже Данциге, будущем «патриархе линейного программирования».
Путь Данцига не был усыпан розами: в школе он даже испытывал определенные трудности с алгеброй. К моменту судьбоносного события он был уже не просто любителем, а аспирантом. В 1939 году Джордж опоздал на лекцию выдающегося статистика Ежи Неймана в Беркли. Увидев на доске условия двух задач, он принял их за домашнее задание.
Данциг позже вспоминал, что примеры показались ему непривычно трудоемкими, но он все же подготовил решение. Как выяснилось позже, он мимоходом нашел ответы на две фундаментальные, считавшиеся на тот момент нерешаемыми проблемы статистики.
Это было поистине грандиозное достижение. В сравнении с ним математический ребус из фильма выглядит весьма скромно — его решение становится очевидным сразу после расшифровки терминологии. В «Умнице Уилле Хантинге» персонажам предлагается построить все возможные гомеоморфно неприводимые деревья десятого порядка (n = 10).
Стоит оговориться: основная трудность здесь заключается исключительно в формулировке. Маловероятно, что человек без профильного образования будет знаком с подобным профессиональным жаргоном. Однако, как только мы переведем эти термины на общедоступный язык, задача превратится в увлекательное упражнение, доступное даже школьнику.
Алгоритм решения задачи Уилла Хантинга
Для начала разберемся с определениями. В математической теории граф в виде «дерева» — это структура из точек (узлов), соединенных линиями, где полностью отсутствуют замкнутые контуры (циклы). Размер дерева определяется количеством его вершин. Нам необходимо изобразить все вариации таких структур с десятью узлами.
Понятие «гомеоморфности» в данном контексте указывает на то, что важна лишь топологическая последовательность соединений, а не визуальная форма. Мы можем изгибать линии или менять их длину, но если иерархия связей между узлами А и Б сохраняется, то дерево считается идентичным. Представьте буквы Х и К, состоящие из пяти узлов — с точки зрения этой задачи они могут рассматриваться как одна и та же структура, если логика связей не меняется.
Требование «неприводимости» означает, что каждый узел должен иметь либо одну связь (быть «листом»), либо три и более. Узлы с ровно двумя связями исключаются, так как их можно «схлопнуть», превратив две линии в одну прямую.
Таким образом, цель — нарисовать все возможные конфигурации деревьев из 10 точек, соблюдая эти нехитрые правила. Простейший перебор вручную займет всего несколько минут. Например, можно начать с «звезды»: один центральный узел, от которого расходятся девять лучей. Это идеальное соответствие условиям.
Дальнейший поиск вариантов — это вопрос терпения. Можно пробовать схемы с семью или шестью ответвлениями от главного узла, постепенно распределяя оставшиеся точки и следя за тем, чтобы не возникало «запрещенных» узлов с двумя связями.
Для тех, кто ценит академическую строгость, существует метод уравнений теории графов. Обозначив через nk количество узлов с k связями, мы можем составить систему ограничений. Учитывая, что общее число узлов равно 10, а n2 должно быть равно нулю, мы получаем формулу:
n1 + n3 + n4 + n5 + n6 + n7 + n8 + n9 = 10
Второе важное условие для любого дерева с 10 вершинами — сумма всех связей должна равняться 18 (удвоенное количество ребер, так как каждая линия считается для обоих узлов, которые она соединяет):
n1 + 3n3 + 4n4 + 5n5 + 6n6 + 7n7 + 8n8 + 9n9 = 18
Комбинируя эти уравнения, мы получаем изящный фильтр для поиска решений:
2n3 + 3n4 + 4n5 + 5n6 + 6n7 + 7n8 + 8n9 = 8
Теперь достаточно подбирать целые коэффициенты, сумма которых дает 8. Например, 8n9 сразу указывает на нашу «звезду». Сочетание 6n7 и 2n3 дает другой вариант, и так далее. Весь процесс логического перебора оказывается быстрым и интуитивно понятным.
Наука богаче вымысла
Понятно, почему кинематографисты предпочли теорию графов реальным работам Данцига: графические схемы выглядят на экране эффектнее, чем многостраничные статистические выкладки. Тем не менее выбор этой задачи кажется несколько поверхностным.
Мировая наука знает немало подлинных историй, где энтузиасты совершали открытия, менявшие парадигму. К примеру, в геометрии значительные прорывы в области апериодических мозаик часто совершались людьми без ученых степеней. Одно из самых ярких событий последних лет произошло в 2022 году: бывший печатник и пенсионер Дэвид Смит обнаружил «плитку Эйнштейна». Он нашел многоугольник, способный замостить плоскость без промежутков и повторений узора — загадку, которую профессиональное сообщество не могло разгадать десятилетиями. Именно такие реальные триумфы человеческого разума заслуживают того, чтобы о них снимали кино.
