К счастью, есть методы получше, чем грубая сила. Иногда гораздо лучше. Наиболее быстро решаемые задачи, такие как перемножение чисел или сортировка множества объектов по размеру, относятся к категории P, то есть «полиномиальное время».
Более обширная категория задач – NP («недетерминированное полиномиальное время»). Проверить решение этих задач легко, но искать его можно довольно долго. Многие из наших любимых игр и головоломок попадают в эту категорию. Хороший пример – судоку. Решение неуловимо, оно требует незаурядных дедуктивных навыков, но его легче легкого проверить: требуется всего-навсего проинспектировать каждую строку, столбец и квадрат 3 × 3.
Здесь нельзя не упомянуть одну фундаментальную математическую задачу, решение которой оценивается в миллион долларов: эквивалентность классов P и NP. Они действительно различны или неявно совпадают? Большинство экспертов полагают, что они различны; зубодробительные задачи класса NP кажутся намного сложнее, чем задачи класса P, которые можно щелкать как орехи. Но это еще никто не доказал. Есть шансы, хотя и небольшие, что какой-нибудь неизвестный доселе алгоритм решит все эти NP-задачи одним махом.
Не будем забывать и про загадочное соответствие между сложностью и удовольствием. Почему-то наш мозг кайфует от NP-сложности, как от сахара, сплетен и сияющих экранов.
Взять хотя бы «пятнашки». В 1880 году, когда эту игру выпустили в широкую продажу, мир сразу на ней помешался. «Тысячи дотоле добропорядочных и трудолюбивых граждан, – сообщала газета The New York Times, – впали в пагубную страсть и, забыв о бизнесе и семьях, прожигают время с этой тлетворной коробочкой».
«Пятнашки» оставались самой популярной головоломкой всех времен и народов в течение столетия, пока в 1974 году не появилась новая комбинаторная игрушка: кубик Рубика. Вскоре книги о кубике Рубика заняли первое, второе и пятое места в списке бестселлеров The New York Times. Когда было продано 400 млн экземпляров кубика Рубика, он стал самой продаваемой игрушкой в истории человечества. Телеканал ABC даже стал крутить в утреннем эфире по субботам мультсериал под названием «Рубик, чудо-кубик»[55].
Как преподаватель алгебры, я знаю, насколько широкие массы обожают абстрактную математику. По популярности это развлечение уступает лишь параллельной парковке и таксидермии.
Чем же в целом здравомыслящих людей влекут эти зубодробительные головоломки?
Я восхищаюсь чарами NP-задач, подобных пению сирен: манящая сложность решения, которое ищется долго, а проверяется быстро. На подсознательном уровне наш игровой инстинкт – своего рода инстинкт математический, нюх на безумные комбинаторные задачи.
На определенном уровне каждая игра – это игра комбинаций.
А теперь приглашаю вас присоединиться к комбинаторному удовольствию. Если ваш противник победит, сделав непредвиденный блестящий ход, мужайтесь: это и есть познание NP-задач на собственном опыте.
СИМ
Игра Сим получила такое название в честь своего создателя Густавуса Симмонса, математика из Альбукерке. Кроме того, название намекает на слово simple (простой), скоро вы увидите почему.
Однако корни игры уходят в глубины теории Рамсея. Она названа в честь Фрэнка Рамсея, который родился в 1903 году и умер в 1930-м. Его творческий расцвет был короток, но он добился значительных результатов в экономической теории, теории вероятностей и в области логических парадоксов. Он даже сдружился с философом Людвигом Витгенштейном, которого историки считают «невыносимым». Тем не менее, несмотря на все эти достижения, имя Рамсея носит теория, посвященная изучению, казалось бы, тривиальной игры, в которой точки соединяют разноцветными линиями. Сколько точек мне понадобится, чтобы получить определенную фигуру? Такие вот вопросы ставит теория Рамсея.
Звучит глупо? Так оно и есть. Звучит просто? Осторожно: название обманчиво.
Сколько игроков? Двое.
Что потребуется? Бумага, карандаши разных цветов. Вначале по кругу ставят шесть точек (как на рисунке ниже).
В чем цель? Проигрывает тот, кто первым начертит треугольник из линий своего цвета.
Какие правила?
1. По очереди соединяйте по две точки.
Некоторые линии будут пересекаться. Ничего страшного. Обратите внимание, что из каждой точки можно провести пять линий, по одной ко всем другим точкам.
2. Когда ваш противник начертит треугольник из линий своего цвета, коснитесь трех точек и скажите: «С-И-М!» Поздравляю: вы победили!
3. Если вы начертили треугольник из линий своего цвета, еще не все потеряно. Вдруг противник его не заметит? Тогда у вас появляется возможность «похитить» победу, если треугольник начертит он.
4. Если вы говорите «Сим!», а треугольника на самом деле нет, то проигрываете.
Вначале все чудесно. Полным-полно возможностей для хода.
Но дальше сложность возрастает. Игровое поле загромождается треугольниками-«обманками» (или «приманками»). Они выглядят как треугольники (вернее, это и есть треугольники), однако их не надо брать в расчет, потому что в этой игре считаются только треугольники с вершинами в исходных точках.
Шесть точек позволяют построить 20 треугольников. Возникает немало ловушек. Нужно пристально всматриваться в игровое поле и разглядывать его как микроскопическое место преступления, пока… ага!
Заметили? Синие линии образуют треугольник. На рисунке ниже я выделил его.
Вот видите, а я предупреждал. Шесть точек – это довольно сложно.
Исток – теория Рамсея. Суть заключается в том, что простые исходные данные могут привести к пугающей сложности. Например, вот краткая выдержка из первого опубликованного анализа этой игры:
В этой статье, опубликованной в журнале Mathematics Magazine, излагается стратегия гарантированного выигрыша (оказывается, она есть у второго игрока). Тем не менее эта стратегия слишком сложна для запоминания.
Не переживайте. Теория Рамсея не ставит вопрос о том, как победить. Она посвящена тому, как создать игру, где невозможна ничья. Как гарантировать, что хотя бы кто-то выиграет.
В «Сим», например, мы хотим, чтобы кто-нибудь построил треугольник из линий одного цвета. Сколько точек для этого требуется? Шести достаточно (почему, обсудим позже), пяти – нет. «Сим» на пятиугольнике может окончиться ничьей.
«Сим» – не единственная игра на прилавке дядюшки Рамсея. Чтобы создать новую игру, можно просто поменять цель. Что, если проигрыш обеспечивают четыре попарно соединенные точки? (Четырехугольник с проведенными диагоналями.) Сколько точек гарантируют невозможность ничьей?
Если вам интересно, вот магическое число: 18 точек. Впрочем, если вам неинтересно, количество точек от этого не изменится.
Если «Сим» – источник головной боли, то вариант с четырехугольником – это томагавк для снятия скальпа. В нем 153 возможных хода, 3060 возможных комбинаций из четырех точек и слишком много скрещивающихся линий, чтобы сыграть в эту игру на бумаге.
Однако Рамсей может поддать газу. Что, если условие проигрыша – не четыре попарно соединенные точки, а пять? Другими словами, пятиугольник с проведенными диагоналями? Какое минимальное количество точек гарантирует невозможность ничьей?
Вопрос с подвохом! Анализировать эту игру настолько сложно, что после полувековых усилий ответ по-прежнему неизвестен. Мы знаем, что 42 точек недостаточно. И знаем, что 48 точно годится. А что с промежуточными значениями? Здесь математики зашли в тупик.
Этот вопрос не мог не возникнуть: слишком просто задать, но слишком сложно ответить.
«Я полагаю, что теория Рамсея появляется на большинстве планет, где возникают цивилизации, – размышляет математик Джим Пропп. – Действительно, испытываешь порыв создать эту теорию, когда смотришь на ночное небо, созерцаешь геометрию созвездий и задаешься вопросом: "Сколько этих узоров неизбежно возникает, когда на небе достаточно звезд?"».
Математик Пауль Эрдёш однажды вообразил, что эти самые инопланетяне прилетают на Землю и дают нам год на решение задачи с пятью точками, грозя уничтожить человечество, если мы не справимся. «Мы задействовали бы лучшие умы и быстрейшие компьютеры, – фантазировал Эрдёш, – и в течение года, скорее всего, решили бы задачу».
А как насчет следующего шага: шесть попарно соединенных точек? Если бы инопланетяне дали нам год, смогли бы мы произвести расчет? «У нас не осталось бы выбора, кроме как нанести упреждающий удар», – полагал Эрдёш.
Такова в общих чертах суть теории Рамсея. Легкомысленные игры ведут в бездонные кротовые норы, где всего шесть точек могут вызвать вселенскую мигрень.
Потому что все мы – точки.
В 1950-е годы венгерский социолог Шандор Салаи наблюдал за группами детей[56]. Он заметил странную закономерность: в классе из 20 человек всегда можно было найти группу из четырех, где все были друзьями, или группу из четырех человек, где никто ни с кем не дружил.
Чем объясняется такая закономерность? Откуда эти таинственные квартеты дружбы и отчуждения? От чего это зависит? От возраста детей? От атмосферы в школе? Или от того, есть ли в школах четырехугольные дворы?
И тут Салаи осенило. Может быть, это вообще не социологический факт? Может быть, это чисто математическая задача?
Сам того не подозревая, Салаи играл в версию «Сим» с четырьмя попарно соединенными точками. Дети вместо точек. Друзья вместо синих линий. Недрузья вместо красных.