Математические игры с дурацкими рисунками: 75¼ простых, но требующих сообразительности игр, в которые можно играть где угодно

Эту закономерность объясняет раздел информатики под названием «теория сложности». Она отвечает на простой вопрос: насколько усложняется задача, когда вы меняете ее масштаб? Возьмем для примера известную задачу коммивояжера. Ниже нарисована карта. Как посетить все четыре города и вернуться в исходную точку, пройдя наименьшее расстояние?

Если стартовать из Альбукерке, то есть три варианта маршрута: Санта-Фе, Розуэлл, Лас-Крусес, Альбукерке (663 мили); Санта-Фе, Лас-Крусес, Розуэлл, Альбукерке (734 мили); Розуэлл, Санта-Фе, Лас-Крусес, Альбукерке (901 миля). Хотите верьте, хотите нет, но это все возможные варианты. Вы можете записать еще 21 маршрут, но каждый из них будет эквивалентен одному из трех, перечисленных выше, просто будет начинаться в другой точке. Итак, наикратчайший путь – из Альбукерке в Санта-Фе, затем в Розуэлл, затем в Лас-Крусес, а затем обратно в Альбукерке. Задача решена.

Что, если я добавлю еще три города? Тогда придется сравнить 360 замкнутых маршрутов. Перебирать их вручную слишком долго, но компьютер справится мгновенно.

А что, если еще усложнить задачу? Скажем, учесть все 37 крупных городов в штате Нью-Мексико?

Теперь мы имеем 200 дуодециллионов возможных маршрутов, то есть 2 × 10⁴¹. Вы никогда не сможете перебрать все; даже хребет лос-аламосского суперкомпьютера сломается под тяжестью стольких соломинок. Такова суровая и фундаментальная математическая закономерность: комбинаторный взрыв. При добавлении лишь нескольких дополнительных объектов вы получаете миллионы новых комбинаций.

Из-за комбинаторного взрыва решение задач методом грубой силы, то есть путем перебора всех возможных вариантов, продвигается медленнее, чем ленивец в кандалах. Компьютер, который может решить перебором задачу с 10 городами за доли секунды, едва ли одолеет задачу с 20 городами за несколько столетий. Специалист в области теории сложности сказал бы, что алгоритм перебора вариантов «выполняется за экспоненциальное время», что означает «чрезвычайно медленно». Полезный жаргонизм, если хотите поддеть приятелей-айтишников, опаздывающих на обед.

К счастью, есть методы получше, чем грубая сила. Иногда гораздо лучше. Наиболее быстро решаемые задачи, такие как перемножение чисел или сортировка множества объектов по размеру, относятся к категории P, то есть «полиномиальное время».

Более обширная категория задач – NP («недетерминированное полиномиальное время»). Проверить решение этих задач легко, но искать его можно довольно долго. Многие из наших любимых игр и головоломок попадают в эту категорию. Хороший пример – судоку. Решение неуловимо, оно требует незаурядных дедуктивных навыков, но его легче легкого проверить: требуется всего-навсего проинспектировать каждую строку, столбец и квадрат 3 × 3.

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

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

Взять хотя бы «пятнашки». В 1880 году, когда эту игру выпустили в широкую продажу, мир сразу на ней помешался. «Тысячи дотоле добропорядочных и трудолюбивых граждан, – сообщала газета The New York Times, – впали в пагубную страсть и, забыв о бизнесе и семьях, прожигают время с этой тлетворной коробочкой».

«Пятнашки» оставались самой популярной головоломкой всех времен и народов в течение столетия, пока в 1974 году не появилась новая комбинаторная игрушка: кубик Рубика. Вскоре книги о кубике Рубика заняли первое, второе и пятое места в списке бестселлеров The New York Times. Когда было продано 400 млн экземпляров кубика Рубика, он стал самой продаваемой игрушкой в истории человечества. Телеканал ABC даже стал крутить в утреннем эфире по субботам мультсериал под названием «Рубик, чудо-кубик»[55].

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

Чем же в целом здравомыслящих людей влекут эти зубодробительные головоломки?

Я восхищаюсь чарами NP-задач, подобных пению сирен: манящая сложность решения, которое ищется долго, а проверяется быстро. На подсознательном уровне наш игровой инстинкт – своего рода инстинкт математический, нюх на безумные комбинаторные задачи.

На определенном уровне каждая игра – это игра комбинаций.