ЛАТИНСКИЙ КВАДРАТ

Латинский квадрат – разновидность неправильных математических квадратов, заполненная n различными символами таким образом, чтобы в каждой строке и в каждом столбце встречались все n символов (каждый по одному разу).

Латинские квадраты существуют для любого n. Любой латинский квадрат является таблицей умножения (таблицей Кэли) квазигруппы. Название «латинский квадрат» берет начало от Леонарда Эйлера, который использовал латинские буквы вместо цифр в таблице.

Два латинских квадрата называются ортогональными, если различны все упорядоченные пары символов (a,b), где a – символ в некоторой клетке первого латинского квадрата, а b – символ в той же клетке второго латинского квадрата.

Ортогональные латинские квадраты существуют для любого порядка, кроме 2 и 6. Для n являющихся степенью простого числа есть набор n–1 попарно ортогональных латинских квадратов. Если в каждой диагонали латинского квадрата все элементы различны, такой латинский квадрат называется диагональным. Пары ортогональных диагональных латинских квадратов существуют для всех порядков, кроме 2, 3 и 6. Латинский квадрат часто встречается в задачах составления расписания, поскольку в строках и столбцах числа не повторяются.

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

Занимаясь греко-латинскими квадратами Эйлер доказал, что квадратов второго порядка не существует, зато были найдены квадраты 3, 4, и 5 порядков. Ни одного квадрата 6 порядка он не нашел. Им была высказана гипотеза, что не существует квадратов четных порядков, не делящееся на 4 (то есть 6, 10, 14 и т. д.). В 1901 Гастон Терри перебором подтвердил гипотезу для 6 порядка. Но в 1959 году гипотеза была опровергнута Э. Т. Паркером, Р. К. Боусом и С. С. Шрикхердом, обнаружившими греко-латинский квадрат порядка 10.

ПОЛИМИНО АРТУРА КЛАРКА

Полимино – по сложности его, безусловно, относится к категории труднейших математических квадратов. Вот как о нем пишет писатель-фантаст А. Кларк – ниже размещен отрывок из книги "Земная Империя". Очевидно, что Кларк, проживая на своем острове, он жил на Цейлоне – и его философия отрыва от социума интересна сама по себе, увлекся развлечением, которому учит бабушка мальчика, и передал его нам. Предпочтем это живое описание имеющимся систематизациям, которые передают, возможно, суть, но не дух игры.

– Ты уже достаточно большой мальчик, Дункан, и сумеешь понять эту игру… впрочем, она куда больше, чем игра. Вопреки словам бабушки, игра не впечатлила Дункана. Ну что можно сделать из пяти белых пластмассовых квадратиков?

– Прежде всего,– продолжала бабушка,– тебе нужно проверить, сколько различных узоров ты сумеешь сложить из квадратиков.

– А они при этом должны лежать на столе? – спросил Дункан.

– Да, они должны лежать, соприкасаясь. Перекрывать один квадратик другим нельзя.

Дункан принялся раскладывать квадратики.

– Ну, я могу выложить их все в прямую линию,– начал он.– Вот так… А потом могу переложить две штуки и получить букву L… А если я возьмусь за другой край, то получится буква U…

Мальчик быстро составил полдюжины сочетаний, потом еще и вдруг обнаружил, что они повторяют уже имеющиеся.

– Может, я тупой, но это все.

Дункан упустил самую простую из фигур – крест, для создания которой достаточно было выложить четыре квадратика по сторонам пятого, центрального.

– Большинство людей начинают как раз с креста,– улыбнулась бабушка.– По-моему, ты поторопился объявить себя тупым. Лучше подумай: могут ли быть еще какие-нибудь фигуры?

Сосредоточенно двигая квадратики, Дункан нашел еще три фигуры, после чего прекратил поиски.

– Теперь уже точно все, – уверенно заявил он.

– А что ты скажешь про такую фигуру?

Слегка передвинув квадратики, бабушка сложила из них подобие горбатой буквы F.

– Ого!

– И вот еще одна.

Дункан чувствовал себя последним идиотом, и бабушкины слова легли бальзамом на его смущенную душу:

– Ты просто молодец. Подумаешь, упустил всего две фигуры. А общее число фигур равно двенадцати. Не больше и не меньше. Теперь ты знаешь их все. Ищи хоть целую вечность – больше не найдешь ни одной.

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

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

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

– Мм…да.

– Слушай дальше. Шестьдесят – замечательное круглое число, которое можно составить несколькими способами. Самый легкий – умножить десять на шесть. Такую площадь имеет эта коробочка: по горизонтали в ней умещается десять квадратиков, а по вертикали – шесть. Стало быть, в ней должны уместиться все двенадцать фигур. Просто, как составная картинка-загадка.

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

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

Вскоре Дункан начал крепко сомневаться в бабушкиных словах. Ему с легкостью удавалось уложить в коробку десять фигур, а один раз он ухитрился втиснуть и одиннадцатую. Но очертания незаполненного пространства не совпадали с очертаниями двенадцатой фигуры, которую мальчик вертел в руках. Там был крест, а оставшаяся фигура напоминала букву Z…

Еще через полчаса Дункан уже находился на грани отчаяния. Бабушка погрузилась в диалог со своим компьютером, но время от времени заинтересованно поглядывала на него, словно говоря: «Это не так легко, как ты думал».

В свои десять лет Дункан отличался заметным упрямством. Большинство его сверстников давным-давно оставили бы всякие попытки. (Только через несколько лет он понял, что бабушка изящно проводила с ним психологический тест.) Дункан продержался без посторонней помощи почти сорок минут…

Тогда бабушка встала от компьютера и склонилась над головоломкой. Ее пальцы передвинули фигуры U, X и L…

Дно коробки оказалось целиком заполненным! Все куски головоломки заняли нужные места.

– Конечно, ты заранее знала ответ! – обиженно протянул Дункан.

– Ответ? – переспросила бабушка.– А как ты думаешь, сколькими способами можно уложить пентамино в эту коробку?

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

– Так сколько, по-твоему, может быть способов? – снова спросила бабушка.

– Двадцать,– выпалил Дункан, думая, что уж теперь бабушка не будет возражать.

– Попробуй снова.

Дункан почуял опасность. Забава оказалась куда хитрее, чем он думал, и мальчик благоразумно решил не рисковать.

– Вообще-то, я не знаю,– сказал он, мотая головой.

– А ты восприимчивый мальчик,– снова улыбнулась бабушка.– Интуиция – опасный проводник, но порою другого у нас нет. Могу тебя обрадовать: угадать правильный ответ здесь невозможно. Существует более двух тысяч различных способов укладки пентамино в эту коробку. Точнее, две тысячи триста тридцать девять. И что ты на это скажешь?

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

– Не верю!

Элен редко выказывала раздражение. Когда Дункан чем-то обижал ее, она просто становилась холодной и отрешенной. Однако сейчас бабушка лишь усмехнулась и что-то выстучала на клавиатуре компьютера.

– Взгляни сюда,– предложила она.

На экране появился набор из двенадцати разноцветных пентамино, заполняющих прямоугольник размером десять на шесть. Через несколько секунд его сменило другое изображение, где фигуры, скорее всего, располагались уже по-другому (точно сказать Дункан не мог, поскольку не запомнил первую комбинацию). Вскоре изображение опять поменялось, потом еще и еще… Так продолжалось, пока бабушка не остановила программу.

– Даже при большой скорости компьютеру понадобится пять часов, чтобы перебрать все способы,– пояснила бабушка.– Можешь поверить мне на слово: все они разные. Если бы не компьютеры, сомневаюсь, что люди нашли бы все способы обычным перебором вариантов.

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

Но тогда восторг и благоговение Дункана были пассивными. Настоящий взрыв интеллектуального наслаждения случился позже, когда он самостоятельно отыскал свой первый способ укладки пентамино. Несколько недель Дункан везде таскал с собой пластмассовую коробочку. Все свободное время он тратил только на пентамино. Фигуры превратитесь в личных друзей Дункана. Он называл их по буквам, которые те напоминали, хотя в ряде случае сходство было более чем отдаленным. Пять фигур – F, I, L, Р, N шли вразнобой, зaто остальные семь повторяли последовательность латинского алфавита: Т, U, V, W, X, Y, Z.

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

Вскоре он сообразил, причем сам, без бабушкиных подсказок, что пентамино можно уложить в прямоугольник с другими размерами сторон. Довольно легко Дункан нашел несколько вариантов для прямоугольников 5 на 12 и 4 на 15. Затем он целую неделю мучился, пытаясь загнать двенадцать фигур в более длинный и узкий прямоугольник 3 на 20. Снова и снова он начинал заполнять коварное пространство и… получат дыры в прямоугольнике и «лишние» фигуры.

Сокрушенный, Дункан наведался к бабушке, где его ждал новый сюрприз.

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

Окрыленный бабушкиной похвалой, Дункан с новыми силами продолжил «охоту на пентамино». Еще через неделю он начал понимать, какой непосильный груз взвалил на свои плечи. Количество способов, которым можно расположить двенадцать фигур, просто ошеломляло Дункана. Более того, ведь каждая фигура имела четыре положения!

И вновь он явился к бабушке, выложив ей все свои затруднения. Если для прямоугольника 3 на 20 существовало только два варианта, сколько же времени понадобится, чтобы их найти?

– Изволь, я тебе отвечу,– сказала бабушка.– Если бы ты действовал как безмозглый компьютер, занимаясь простым перебором комбинаций и тратя на каждую по одной секунде, тебе понадобилось бы…– Здесь она намеренно сделала паузу.– Тебе понадобилось бы более шести миллионов… да, более шести миллионов лет.

Земных или титанских? Этот вопрос мгновенно возник в мозгу Дункана. Впрочем, какая разница?

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

Дункан повиновался, уже без энтузиазма и веры в успех. А потом ему в голову пришла блестящая идея.

Карл сразу же заинтересовался пентамино и принял вызов. Он взял у Дункана коробочку с фигурами и исчез на несколько часов.

Когда Карл позвонил ему, вид у друга был несколько расстроенный.

– А ты уверен, что эта задача действительно имеет решение? – спросил он.

– Абсолютно уверен. Их целых два. Неужели ты так и не нашел хотя бы одно? Я-то думал, ты здорово соображаешь в математике.

– Представь себе, соображаю, потому и знаю, каких трудов стоит твоя задачка. Нужно проверить… миллион миллиардов возможных комбинаций.

– А откуда ты узнал, что их столько? – спросил Дункан, довольный тем, что хоть чем-то сумел заставить друга растерянно чесать в затылке.

Карл скосил глаза на лист бумаги, заполненный какими-то схемами и цифрами.

– Если исключить недопустимые комбинации и учесть симметрию и возможность поворота… получается факториал… суммарное число перестановок… ты все равно не поймешь. Я тебе лучше покажу само число.

Он поднес к камере другой лист, на котором была крупно изображена внушительная вереница цифр:

1 004 539 160 000 000.

Дункан ничего не смыслил в факториалах, однако в точности подсчетов Карла не сомневался. Длиннющее число ему очень понравилось.

– Так ты собрался бросить эту задачу? – осторожно спросил Дункан.

– Еще чего! Я просто хотел тебе показать, насколько она трудна.

Лицо Карла выражало мрачную решимость. Произнеся эти слова, он отключился.

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

– Ну вот и все,– усталым, но торжествующим голосом возвестил он.

Дункан едва верил своим глазам. Ему казалось, что шансы на успех ничтожно малы. Он даже убедил себя в этом. И вдруг… Перед ним лежал прямоугольник три на двадцать, заполненный всеми двенадцатью фигурами пентамино.

Потом Карл поменял местами и перевернул фигуры на концах, оставив центральную часть нетронутой. От усталости у него слегка дрожали пальцы.

– Это второе решение,– пояснил он.– А теперь я отправляюсь спать. Так что спокойной ночи или доброго утра – это уж как тебе угодно.

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

Он не завидовал победе друга. Дункан слишком любил Карла и всегда радовался его успехам, хотя нередко сам оказывался побежденной стороной. Но в сегодняшнем триумфе друга было что-то иное, что-то почти магическое.

Дункан впервые увидел, какой силой обладает интуиция. Он столкнулся с загадочной способностью разума вырываться за пределы фактов и отбрасывать в сторону мешающую логику. За считаные часы Карл выполнил колоссальную работу, превзойдя самый быстродействующий компьютер.

Впоследствии Дункан узнал, что подобными способностями обладают все люди, но используют они их крайне редко – возможно, один раз в жизни. У Карла этот дар получил исключительное развитие… С того момента Дункан стал серьезно относиться к рассуждениям друга, даже самым нелепым и возмутительным с точки зрения здравого смысла.

Это было двадцать лет назад. Дункан не помнил, куда делись пластмассовые фигуры пентамино. Возможно, так и остались у Карла.

Бабушкин подарок стал их новым воплощением, теперь уже в виде кусочков разноцветного камня. Удивительный, нежно-розового оттенка гранит был с холмов Галилея, обсидиан – с плато Гюйгенса, а псевдомрамор – с гряды Гершеля. И среди них… сначала Дункан подумал, что ошибся. Нет, так оно и есть: то был самый редкий и загадочный минерал Титана. Крест каменного пентамино бабушка сделала из титанита. Этот иссиня-черный, с золотистыми вкраплениями минерал не спутаешь ни с чем. Таких крупных кусков Дункан еще не видел и мог только догадываться, какова его стоимость.

– Не знаю, что и сказать,– пробормотал он.– Какая красота. Такое я вижу в первый раз.

Он обнял худенькие бабушкины плечи и вдруг почувствовал, что они дрожат и ей никак не унять эту дрожь. Дункан бережно держал ее в своих объятиях, пока плечи не перестали дрожать. В такие мгновения слова не нужны. Отчетливее, чем прежде, Дункан понимал: он последняя любовь в опустошенной жизни Элен Макензи. И теперь он улетает, оставляя ее наедине с воспоминаниями.