Алекс в стране чисел. Необычайное путешествие в волшебный мир математики - Алекс Беллос Страница 55

Комбинаторика — это область математики, которая имеет дело с исключительно большими числами. Как мы видели на примере магических квадратов, уже небольшое количество чисел можно расположить на удивление большим количеством способов. Хотя и латинские, и магические квадраты образуют квадратные таблицы, при их одинаковом размере латинских квадратов меньше, чем магических, однако латинских квадратов все равно очень много. Например, количество латинских квадратов размером 9 × 9 выражается числом из 28 цифр. Сколько среди них различных судоку? Число латинских квадратов, представляющих собой судоку, — то есть таблиц размером 9 × 9, в которых 9 подквадратов содержат все цифры, — меньше полного числа примерно в сто тысяч раз и равно 6 670 903 752 021 072 936 960. Впрочем, многие из этих таблиц представляют собой различные варианты одного и того же квадрата, получаемые отражением или вращением (что мы видели выше для магического квадрата 3 × 3). Если не считать квадраты, получаемые вращениями и отражениями, то искомое количество заметно уменьшается: общее число различных возможностей для целиком заполненных таблиц судоку оказывается равным примерно 5,5 миллиарда.

Это, впрочем, не равно полному числу возможных судоку, которое намного больше данного числа, потому что каждая заполненная сетка будет решением многих разных судоку. Скажем, напечатанное в газете судоку имеет одно-единственное решение. Но как только вы заполните один из квадратов, вы немедленно тем самым создадите новую таблицу с новым набором данных, другими словами — новое судоку с тем же единственным решением, и т. д. для каждого из квадратов, которые вы будете заполнять. Так что если в данном судоку имеется, скажем, 30 исходно заданных чисел, то у вас есть возможность создать еще 50 других судоку с тем же единственным решением — до тех пор, пока не будет заполнена вся таблица. (Это означает новое судоку для каждого дополнительного числа, до тех пор пока в таблице из 81 квадрата не окажется 80 заполненных.) Нахождение полного числа судоку не слишком интересно, поскольку большинство таблиц для них имеют лишь очень небольшое число незаполненных клеток, что не отвечает духу этих головоломок. Математиков гораздо более привлекает задача нахождения минимального числа цифр, исходно расставленных по таблице. Самый главный комбинаторный вопрос касательно судоку звучит так: каково наименьшее количество чисел, которые можно оставить, чтобы имелся только один способ заполнения всей таблицы?

Те судоку, которые печатают в газетах, обычно содержат около 25 заданных чисел. К настоящему моменту никому не удалось найти судоку, которая имела бы единственное решение при менее чем 17 заданных числах. На самом деле судоку с 17 подсказками привели к появлению некоторого комбинаторного культа. Гордон Ройл из Университета Западной Австралии поддерживает базу данных по судоку с 17 подсказками, и от создателей головоломок по всему миру ему ежедневно приходят три или четыре новые. К настоящему моменту он собрал их почти 50 000 штук. Но несмотря на то, что он — признанный во всем мире специалист по судоку с 17 подсказками, он говорит, что не знает, сколь близко подошел к нахождению полного числа возможных головоломок. «Некоторое время назад я бы сказал, что дело близится к концу, но потом один анонимный участник прислал мне почти 5000 новых, — говорит он. — Мы так толком и не поняли, как же этот человек под ником „anon17“ смог их найти, но несомненно, он использовал какой-то хитрый алгоритм».

По мнению Ройла, барьер из 17 заданных чисел пока не преодолен, потому что «или мы недостаточно умные, или наши компьютеры недостаточно мощные». Скорее всего, участник «anon17» не обнародовал свой метод потому, что тайком использовал чей-то очень большой компьютер. Ответы на комбинаторные задачи нередко опираются на серьезную работу компьютера по перебору чисел. «Полное возможное пространство допустимых головоломок с 16 подсказками настолько обширно, что нам остается лишь исследовать его маленький уголок, если мы не будем привлекать какие-то новые теоретические идеи», — утверждает Ройл. Однако чутье подсказывает ему, что судоку с 16 под сказками никогда не будут найдены. Он добавляет: «Сейчас имеется так много головоломок с 17 подсказками, что было бы крайне странно, если бы вдруг нашлась какая-нибудь с 16-ю, на которую мы до сих пор случайно не наткнулись».

* * *

Мне всегда казалось, что одна из причин успеха судоку — это экзотическое название, апеллирующее к романтическому увлечению высшей восточной мудростью, несмотря на то что эту идею предложил американский архитектор Говард Гарнс. На самом деле существует традиция головоломок, имеющая свои корни на Востоке. Самый первый международный бум головоломок относится к началу XIX века, когда европейские и американские моряки, вернувшиеся из Китая, привезли наборы геометрических фигур из семи элементов, как правило изготовленных из дерева или слоновой кости, — двух больших и двух маленьких треугольников, треугольника среднего размера, ромба и квадрата. Сложенные вместе, эти кусочки образовывали большой квадрат. К фигурам прилагались буклеты, изображавшие десятки вариантов различных геометрических или человеческих фигур и других объектов. В головоломке требовалось сложить каждую из них, используя все семь деталей.

Эта головоломка ведет свое происхождение из китайской традиции расстановки столов на званых обедах в виде различных фигур. В одной китайской книге XII века показаны 76 вариантов расположения столов, причем многие из этих вариантов были задуманы так, чтобы напоминать различные объекты, к примеру развевающийся флаг, горный хребет и цветы. В начале XIX столетия китайский писатель с забавным прозвищем Отупелый Отшельник приспособил эту церемониальную хореографию к миниатюрным геометрическим фигурам (размером с палец), которые поместил в книгу под названием «Картинки, составленные из семи дощечек мастерства».

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

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

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