ПРЕДИСЛОВИЕ РЕДАКТОРА РУССКОГО ИЗДАНИЯ

Автор этой книги С. В. Голомб — известный ученый, профессор отделений математики и электронной вычислительной техники небольшого, но весьма известного в США университета Южной Калифорнии (к слову сказать, там же сотрудничают видный геометр Герберт Буземан и один из крупнейших специалистов по современной прикладной математике Ричард Беллман — их имена знакомы советскому читателю по переводам многих книг). Научные труды Голомба, посвященные теории информации, теории кодирования и математической статистике, а также разнообразным применениям этих дисциплин — вопросам хранения и передачи информации в живой природе и в технике, — хорошо известны специалистам*. Но вовсе не эти тонкие и глубокие работы сделали его имя широко популярным во всем мире — своей известностью он в первую очередь обязан придуманной им в часы досуга игре (точнее, серии игр), связанной с ПОЛИМИНО.

В 1953 году, будучи аспирантом отделения математики Гарвардского университета в Бостоне, Голомб выступил с докладом о полимино в Гарвардском математическом клубе. Собственно, с этого доклада и повторяющей его статьи «Шахматные доски и полимино» [7 ] и ведет свое начало история полимино. Можно только поражаться, какое распространение получили впоследствии связанные с полимино игры и задачи и как быстро захватили они обширнейшую аудиторию — от школьников младших и средних классов и домашних хозяек до профессоров математики.

В США, Англии и ряде других стран начали продавать в качестве детских (и не только детских) игр различные наборы полимино с подробными инструкциями о правилах игры. Многочисленные статьи о полимино стали появлять

* Сошлюсь на перевод написанной совместно с выдающимся генетиком М. Дельбрюком и математиком Л. Р. Велчем статьи Голомба «Строение и свойства кодов без запятой» [Математика, 4, вып. 5, 137—160 (I960)], посвященной обсуждению некоторых априорно возможных систем передачи генетической информации от хромосом ядра клетки к телу (цитоплазме) клетки и тем самым ко всему живому организму.

ся в самых разнообразных журналах: научных (Journal of Combinatorial Theory или Canadian Mathematical Journal), научно-педагогических (American Mathematical Monthly или Mathematical Gazette), научно-популярных (в двух самых распространенных из них — в американском Scientific Americana советском «Наука и жизнь»—тема полимино одно время получила чуть ли не «постоянную прописку»), в журналах для школьников (советский журнал «Квант») или изданиях, посвященных «развлекательной математике» (Recreational Mathematics Magazine или Fairy Chess Review). Широкой известностью во всем мире пользуется книга G. Голомба «Полимино», русский перевод которой ныне предлагается вниманию читателя. Столь бурный интерес к, казалось бы, непритязательной теме из области математических развлечений, не претендующей на особое внимание, на первых порах может показаться несколько неожиданным; попытаемся по возможности его пояснить.

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

Дальнейшая проблематика связана со складыванием новых фигур из заданного набора полимино или с доказательствами невозможности тех или иных расположений полимино. Так, например, достаточно типичными следует считать открывающие книгу результаты о невозможности покрытия обыкновенной шахматной доски с двумя вырезанными противоположными угловыми клетками 31 домино (составленным из двух примыкающих квадратов, равных полям доски) или о возможности покрытия доски с одним удаленным полем 21 угловым тримино независимо от того, где расположено вырезанное поле (первая из упомянутых задач весьма популярна среди школьников всего мира, интересующихся математикой). Новые мотивы появляются

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

Связанные с полимино игры и задачи достаточно просты по формулировкам и не особенно оригинальны. На первый взгляд, они очень близки к старинной китайской головоломке «танграм» (или «чи-чао-тю»), состоящей в складывании фигурок из разрезанной определенным образом на семь частей квадратной деревянной или металлической пластинки*, а также к близкой танграму древнегреческой головоломке «стомахион», в которой число частей квадратной пластинки увеличено до 14 (эту последнюю головоломку принято приписывать Архимеду). И тем не менее интерес, который в наши дни вызывает эта проблематика, вполне закономерен и объясним.

Чтобы вскрыть его причины (которые, разумеется, отнюдь не обязаны осознавать неспециалисты), следует вкратце остановиться на некоторых общих тенденциях современной математики. Начиная с XVII века, эпохи Ньютона и Лейбница, центральным разделом математики считался математический анализ (дифференциальное и интегральное исчисление), изучающий непрерывно развивающиеся во времени и пространстве процессы, а также непрерывные функции (графиками которых служат непрерывные линии), используемые для математического описания этих процессов. Поскольку множество значений таких функций, как правило, является бесконечным, то вплоть до второй половины XX века математики пренебрежительно относились к задачам, связанным с так называемой «конечной» математикой, в частности с комбинаторикой, в которой требуется разобраться в конечном числе возможных вариантов: все подобные задачи относились к «низшей» математике, противопоставляемой так называемой «высшей математике», то есть математическому анализу. Однако с появлени-

* См., например, гл. 33 книги [34] или: Д. И. Перепелкин, Курс элементарной геометрии, ч. I, М.—Л., Гостехиздат, 1948, стр. 208—209.

ем ЭВМ (в названии которых обычно неправомерно опускается весьма важное прилагательное «цифровая», так что здесь точнее было бы говорить ЭЦВМ—электронная цифровая вычислительная машина} картина полностью изменилась. Современная электронная вычислительная техника базируется на вводимых в машину в качестве исходных данных и получаемых в виде результата цифровых записях, позволяющих охватить необычайно широкий круг явлений — универсальность (конечного!) алфавита ЭЦВМ родственна, скажем, универсальности русского алфавита, с помощью конечных комбинаций 32 символов (букв) которого удается выразить самые тонкие и глубокие оттенки мысли или чувства.

Появление ЭЦВМ заставило ученых по-новому взглянуть на окружающий нас мир. При этом обнаружилось, что явления, имеющие «дискретный», или «конечный», характер, встречаются весьма часто и играют большую роль. Достаточно сказать, что органическая жизнь, как мы теперь знаем, тесно связана со знаменитым четырехбуквенным алфавитом дезоксирибонуклеиновой кислоты (ДНК), на языке которой составляются хранимые в хромосомах живой клетки «команды». Именно они дают указания об общем плане строения организма и о его индивидуальных особенностях наследственного характера. И хотя сегодня мы по-прежнему нередко употребляем выражение «высшая математика» как синоним термина «математический анализ», но уже не вкладываем в него никакой оценки сравнительного значения разных разделов математической науки.

Пересмотр позиций способствовал, в частности, расцвету комбинаторики, которую еще совсем недавно не относили к разряду особо уважаемых математических дисциплин. Это нашло свое отражение не только в появлении ряда книг, посвященных комбинаторике (см. монографии [41] — [43—47]), но и в создании специальных периодических изданий (к их числу принадлежит Journal of Combinatorial Theory, в котором было опубликовано немало научных статей, связанных с полимино). Интерес к комбинаторике, стимулируемый существованием ЭВМ, объясняется двояко: с одной стороны, многие связанные с конструированием и эксплуатацией ЭВМ задачи имеют чисто комбинаторный характер, с другой —решение многих комбинаторных проблем оказывается удобным поручать нашим, электронным «помощникам», для которых стандартными явля- 9

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

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

Все сказанное выше проливает достаточный свет на ту почву, на которой вырос интерес к полимино. Человеческое существование нельзя разделить на отдельные неперекры- вающиеся компоненты: быт, труд, отдых — все они тесно переплетены между собой. «Модная» в тот или иной период времени «развлекательная математика» всегда оказывается

* С этой точки зрения наиболее естественным является сопоставление содержания настоящей книги с тем течением комбинаторной геометрии, которое начинается с известной задачи о разрезании квадрата на попарно неравные квадраты", большое внимание, которое уделяется этой достаточно частной задаче, ее вариантам и обобщениям (см. [52]), также кажется необъяснимым в отрыве от охарактеризованных выше общенаучных тенденций.

тесно связанной с магистральной линией развития науки. Так, первая в Европе книга по математическим развлечениям — знаменитый сборник «Приятных и занимательных задач» литератора и любителя математики Баше де Мезириака (1612) — весьма естественно укладывается в общую схему математики XVII века. Ее влияние на научные интересы Блеза Паскаля или Пьера Ферма не вызывает сомнения. Именно научная актуальность определила огромный успех сочинения Баше, выдержавшего в короткий срок множество переизданий и постоянно перепечатываемого вплоть до наших дней. Из книги Баше черпали проблемы многие видные математики того времени. Аналогично этому научные интересы С. В. Голомба, в значительной степени концентрирующиеся вокруг чисто комбинаторных проблем, бесспорно, сыграли роль в «открытии» им полимино, и именно они обеспечили успех его книге.

Выше уже упоминалось о том, что в ряде стран наборы полимино продаются в качестве игр. Читатель легко сможет самостоятельно изготовить набор 12 пентамино, основываясь на приведенном на стр. 11 рисунке. Делать полимино лучше всего из плотного картона; полученные фигурки желательно оклеить цветной бумагой. Не советуем вырезать полимино просто из бумаги: при складывании узоров бумажные полимино будут мяться. Помимо пентамино, из картона и цветной бумаги можно изготовить и иные п-мино (скажем, отвечающие значениям п — 1, 2, 3, 4 и 6; см. рис. 1 и 20 в книге) или треугольные или шестиугольные монстры (см. рис. 134, 137 или 139, 141 и 143). При этом ребро «образующих квадратов», таких, что n-мино является объединением п подобных квадратов, лучше всего принять равным 2 см или близким к этой величине. Сторону порождающих треугольные монстры правильных треугольников также можно считать равной 2 см, а сторону правильных шестиугольников, объединением которых получаются шестиугольные монстры, — такой же или несколько меньшей. «Пространственные полимино», в частности изображенные на рис. 112 пространственные мономино, домино, тримино и тетрамино, а также пентакубики, о которых говорится на стр. 128, можно склеить из детских кубиков. Автор книги описывает некоторые связанные с полимино игры; другие такие игры читатели смогут придумать самостоятельно или найти их описания в указанной в конце книги литературе.

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

И. Яглом