МАТЕМАТИКА
Глава 9
Дракула готовит мартини
Эта глава открывается классической головоломкой; далее показано, как на ее основе проделать два таинственных карточных фокуса. В наше время существует обширнейшая литература по математическим (или «самосрабатывающим», как их называют фокусники) карточным трюкам. Если хотите побольше узнать о математической магии, хорошим введением в нее может стать моя книга «Математика, магия и мистика», выпущенная издательством «Dover» в мягкой обложке. Нижеследующий текст впервые вышел в «Isaac Azimov's Science Fiction Magazine» (сентябрь 1979).
— Время коктейлей, дорогая, — объявил граф Дракула своей супруге. — Тебе как обычно? — Да, милый, — подтвердила миссис Дракула. Граф извлек из бара одну бутылку, содержащую кварту водки, и другую, поменьше, содержащую пинту[51] «человеческой крови». Влив немного крови в водку, он как следует встряхнул бутылку, а затем перелил в точности такой же объем обратно в емкость с кровью. Таким образом, в большой бутылке снова оказалась кварта жидкости, а в маленькой — пинта.
Миссис Дракула сидела спиной к мужу, но, глядя в зеркало на стене гостиной, она видела, что он делает. Граф выполнял стандартную трансильванскую процедуру по приготовлению вампирического мартини.
Допустим, что при смешивании водки с кровью объем компонентов не меняется. Если провести вышеописанную операцию дважды, водки в пинте крови окажется больше, чем крови в кварте водки? или меньше? или их будет поровну?
Возможно, вам уже попадалась такая загадка, и речь в ней шла об одинаковых стаканах с вином и водой. Однако в нашем случае содержимое двух сосудов не столь сходно, к тому же нам не сообщают, какой объем жидкости переливают туда и обратно.
Ответ
Если вы попытаетесь решить эту задачку алгебраически, введя точные количества, то вы, скорее всего, запутаетесь. Между тем существует до смешного простое доказательство того, что количество крови в водке должно оказаться в точности равным количеству водки в крови.
Нам говорят, что в конце всех операций, как и в самом начале, большая бутылка содержала 1 кварту жидкости, а малая — 1 пинту. Рассмотрим большую бутылку. В ней не хватает некоторого количества водки, обозначим его как х. Но поскольку суммарный объем жидкости в ней по-прежнему равен 1 кварте, значит, недостающее количество замещено равным объемом крови — тем же х! Конечно, такое же рассуждение применимо и к маленькой бутылке. Если в ней не хватает количества крови, равного х, но суммарный объем по-прежнему составляет 1 пинту, то, следовательно, недостающую кровь замещает количество водки, равное х. Вообще-то совершенно не важно, сколько раз произвольные объемы жидкости переливают туда-сюда, главное, чтобы в результате одна бутылка содержала ровно кварту, а другая — ровно пинту. Даже размеры емкостей несущественны. Объем водки в крови просто обязан равняться объему крови в водке!
Сумеете ли вы придумать простенький карточный фокус, основанный на этом забавном принципе?
Выньте из колоды двадцать шесть черных карт и сложите их одной стопкой. Рядом положите, скажем, тринадцать красных. Повернитесь спиной и попросите кого-нибудь вынуть из черной стопки столько карт, сколько ему вздумается, а затем положить их в красную стопку и перетасовать. После этого он должен вынуть такое же количество карт из бывшей красной стопки, поместить их в черную и тоже перемешать.
Вы оборачиваетесь, с важным видом трете виски и объявляете, что благодаря ясновидению открыли: число красных карт среди черных в точности равно количеству черных карт среди красных.
Так будет всегда — по той же причине, что описана в разгадке истории с мартини. Если хотите, можете позволить зрителю объединить две стопки в одну, перетасовать и затем отложить двадцать шесть карт из нее в одну кучку, а тринадцать — в другую. Результат будет тем же, что и раньше.
А теперь предлагаю вам вернуться к первой части этого рассказа и перечитать ее. Какую вопиющую ошибку я допустил, описывая, как граф Дракула делает коктейли?
В моем описании сказано, что миссис Дракула видела мужа в зеркале. Но, как известно (или должно быть известно) каждому читателю, вампиры в зеркале не отражаются.
Постскриптум
Сотни математических карточных фокусов используют, по сути, тот же принцип. Вот хороший пример, можете испробовать его на приятелях.
Перед тем как показать трюк, разделите стандартную колоду из пятидесяти двух карт на две равные части. Переверните одну половину и перемешайте двадцать шесть карт, лежащих рубашкой вниз, с двадцатью шестью, лежащими рубашкой вверх. Приступая к фокусу, продемонстрируйте всем, что получившаяся колода представляет собой смесь карт, обращенных рубашкой вверх и вниз, но не говорите, сколько из них перевернуто. Пусть кто-нибудь перетасует колоду и под столом передаст ее вам. Через несколько мгновений вы достаете карты, держа по полколоды в каждой руке, и объявляете, что в каждой из этих половинок — одно и то же число карт, лежащих рубашкой вниз! Выяснится, что так оно и есть.
Секрет фокуса. Под столом быстро отсчитайте двадцать шесть карт. Переверните любую из двух полуколод, прежде чем выложить все карты на стол. Понимаете, каков здесь механизм? Перед тем как вы перевернули полуколоду, количество карт, лежащих рубашкой вниз в одной полуколоде, равно числу карт, лежащих рубашкой вверх, в другой. Переверните полуколоду — и те карты, что лежали рубашкой вниз, будут лежать рубашкой вверх (и наоборот). В результате в каждой полуколоде окажется равное число карт, повернутых рубашкой в одну сторону.
Глава 10
Ряд Фибоначчи
Классический ряд Фибоначчи начинается так: 1, 1, 2, 3, 5, 8, 13, 21… Каждый член последовательности (кроме первых двух) — сумма двух предыдущих. Обобщенный случай ряда Фибоначчи — последовательность, в начале которой могут стоять два любых целых числа.
Числам Фибоначчи посвящено необозримое количество литературы. Существует даже периодическое издание — «Fibonacci Quarterly» («Ежеквартальник Фибоначчи»). Хорошим введением в эту тему может стать книга Альфреда Позантье и Ингмара Лемана «Феноменальные числа Фибоначчи» (Амхерст, штат Нью-Йорк: «Prometheus», 2007).
Моя статья о некоторых малоизвестных свойствах чисел Фибоначчи вышла в «Journal of Recreational Mathematics» («Журнале развлекательной математики») (№ 34, 2005–2006, с. 183–190).
Ряд Фибоначчи — слыхали? —
1 да 1 — в начале,
потом — 2, 3, 5, 8,
отложите вопросы,
веселье мы вам обещали!
Прошло почти два десятка лет со времени моего последнего интервью с доктором Матриксом, которое я взял у него на математической конференции в Лиссабоне. (Это интервью завершает подборку моих колонок из журнала «Scientific American», составившую книгу «Использование покрытий Пенроуза для разгадки шифров»[52].) С тех пор я совершенно потерял след старого хрыча и его дочери Ивы, наполовину японки. Так что я с огромным удивлением и удовольствием повстречался с ним на конференции по теории чисел, проходившей в Стэнфордском университете. В программе значился его доклад «Некоторые малоизвестные факты о рядах Фибоначчи».
Ивы в Стэнфорде не было — теперь она уже не сопровождала отца в его вояжах, поскольку в 1991 году вышла замуж за одного японского фокусника. Ныне она живет в Токио вместе с мужем и двумя сыновьями-подростками — Ирвингом и Джошуа.
Сам доктор Матрикс заметно постарел. Волосы у него стали снежно-белыми, однако изумрудно-зеленые глаза сохранили всегдашнюю живость и пронзительность, а вышагивал он по-прежнему ровно и уверенно. Он передал мне текст своей лекции. Из нее, а также из наших дальнейших бесед я почерпнул необыкновенные сведения.
Пусть А, В, С, D — четыре любых последовательных члена обобщенного ряда Фибоначчи. Тогда произведение А и D даст одно число из пифагоровой тройки[53], а удвоенное произведение В и С — другое число из той же тройки! Рассмотрим, к примеру, четыре первых члена простейшего ряда Фибоначчи — 1, 1, 2, 3. Подстановка этих чисел в наши формулы даст знакомые длины сторон прямоугольного пифагорова треугольника — 3, 4, 5. С помощью такой процедуры можно, разумеется, создать бесконечное количество пифагоровых троек, хотя, к сожалению, не все такие триады.
Вот уравнение для четырех последовательных элементов ряда Фибоначчи:
(А × D)2 + (2 × В × С)2 = (В2 + С2)2
Это равенство легко доказать. Доктор Матрикс не дал ссылки на эту диковинку, однако я связался с редактором «Fibonacci Quarterly» и установил, что ее некогда опубликовал А. Хорадам в «American Mathematical Monthly»[54].
В ходе своего выступления доктор Матрикс продемонстрировал на экране старый парадокс с изменением площади (рис. 1). Перед нами квадрат площадью 64 «квадратные единицы». Если переложить четыре его части так, чтобы те составили прямоугольник, площадь неожиданно вырастет до 65 единиц! А если куски вновь переложить, как показано на рис. 2, общая площадь съежится до 63!
Отметьте, что длины в этом классическом парадоксе — 3, 5, 8 и 13, а это четыре члена ряда Фибоначчи. У этой последовательности есть известное свойство: если возвести в квадрат ее элемент, имеющий номер n, полученная величина будет равна произведению предшествующего и последующего члена ряда ±1 (т. е. членов с номерами n–1 и n+1).
В данном случае сторона квадрата — 8, площадь — 64. В ряду Фибоначчи 8 находится между 5 и 13. Следовательно, 5 и 13 автоматически становятся сторонами прямоугольника, площадь которого должна составлять 65: отсюда выигрыш в одну квадратную единицу.
Благодаря этому свойству нашего ряда мы можем построить квадрат со стороной, длина которой представляет любое число из этого ряда (больше 1), а затем разрезать фигуру в соотношении, определяемом двумя предшествующими членами ряда. Так, выбрав квадрат со стороной 13, можно разделить три из его сторон на сегменты с длинами 5 и 8, а затем провести линии разреза, как показано на рис. 3. Площадь этого квадрата — 169. Из его фрагментов можно сложить прямоугольник с длинами сторон 21 и 8, а площадь этого прямоугольника будет равна 168. Из-за своего рода «перекрывания», происходящего вдоль диагонали прямоугольника, здесь мы теряем, а не приобретаем одну квадратную единицу.
Потеря одной квадратной единицы происходит, если взять квадрат со стороной 5. И это подводит нас к забавному правилу. Каждый второй элемент ряда Фибоначчи, если принять его за длину стороны квадрата, создает «дополнительную площадь» вдоль диагонали прямоугольника и зримую прибавку одной квадратной единицы. Все остальные элементы ряда (если их также брать через один) дают перекрывание частей прямоугольника и потерю одной квадратной единицы. Чем дальше по ряду мы продвигаемся, тем менее заметна площадь такого перекрывания. И соответственно, чем ниже номера членов ряда, тем перекрывание виднее. Можно даже построить своего рода парадокс с квадратом, имеющим сторону всего в две единицы, но в таком случае полученный из него прямоугольник 3 на 1 потребует столь явного перекрывания, что пропадет весь эффект от парадокса.
По всей видимости, первую попытку обобщить этот парадокс квадрата и прямоугольника с помощью упомянутого ряда Фибоначчи предпринял В. Шлегель (см. его статью в «Zeitschrift fur Mathematik und Physik»[55]). Э.Б. Эскотт опубликовал похожий анализ в «Open Court»[56], описав несколько иной метод разрезания квадрата. Льюис Кэрролл интересовался этим парадоксом и оставил ряд незавершенных заметок, где он приводит формулы для расчета других сторон фрагментов[57].
Бесконечное количество других вариантов получим, если положим в основу этого парадокса другие ряды Фибоначчи. Так, квадраты, построенные на основе ряда 2, 4, 6, 10, 16, 26…, дают прибавку или потерю в 4 квадратные единицы. Величину этой прибавки-потери легко можно вычислить: это разность между квадратом любого элемента последовательности и произведением соседних с ним элементов. Ряд 3, 4, 7, 11, 18… дает прибавку или потерю в 5 квадратных единиц. Т. де Молидар[58] в своей «Grande Encyclopedie des Jeux»[59] изображает квадрат, основанный на ряде 1, 4, 5, 9, 14… Длина стороны квадрата равна 9, a при превращении в прямоугольник он теряет и квадратных единиц. Ряд 2, 5, 7, 12, 19… также дает потери и прибавки, равные 11. Однако в обоих случаях перекрывание («добавочная площадь») вдоль диагонали прямоугольника достаточно велико, и его можно заметить. Пусть А, В и С — три последовательных члена какого-нибудь ряда Фибоначчи, а X — потеря или прибавка площади. Тогда получим две следующие формулы:
А + В = С
В2 = АС ± X
Можно заменить X любой потерей или прибавкой, которую мы хотим получить, а вместо В подставить любую длину квадрата, которая нам нравится. Затем можно составить квадратные уравнения, а решив их, узнать два других элемента нашего ряда Фибоначчи, хотя, конечно, это не обязательно будут рациональные числа. Поэтому, к примеру, невозможно получить потери или прибавки в 2 или 3 квадратные единицы, деля квадрат на куски с рациональными длинами. Но если длины составят иррациональные числа, то, конечно, результата достичь удастся. Таким образом, ряд Фибоначчи √2, 2√2, 3√2, 5√2… даст прибавку или потерю, равную 2, а ряд √3, 2√3, 3√3, 5√3… даст прибавку или потерю в 3 квадратные единицы.
Доктор Матрикс великодушно сослался в своей лекции на главы 8 и 9 моей книги, вышедшей в мягкой обложке и называющейся «Математика, магия и мистика» (издательство «Dover»)[60]. Эти главы посвящены всевозможным удивительным геометрическим исчезновениям, в том числе таинственной пропаже лиц и людей! Там описано, в частности, блистательное открытие мага-любителя Пола Карри: путем простой перестановки кусков некой фигуры получается фигура, казалось бы, той же площади, но с большой дырой внутри!
Доктор завершил свой доклад кратким рассказом о числах трибоначчи. Ряд трибоначчи получают, всякий раз суммируя три предыдущих члена: 1, 1, 2, 4, 7, 13, 24, 44, 81… В обобщенной последовательности Фибоначчи отношение соседних членов А и В (т. е. результат деления А на В) стремится к 0,618… — величине, обратной прославленному «золотому сечению». В последовательности трибоначчи такое отношение стремится к 0,543… Числа тетраначчи получают путем суммирования четырех предшествующих элементов ряда. Разумеется, можно обобщить этот случай, приняв за n количество суммируемых элементов. Тогда при стремлении n кбесконечности отношение соседних членов будет по мере увеличения их номеров стремиться к 0,5.
Как я позже узнал от Дональда Кнута, известного ученого-компьютерщика из Стэнфордского университета, подобные ряды впервые были предложены Нараяной Пандитой в 1356 году, в главе 13 его замечательной работы, написанной на санскрите и озаглавленной «Ганита каумуди» («Услады лотосовых вычислений»)[61]. Кнут обсуждает ее и дает ссылки на другие работы в четвертом томе своего классического труда «Искусство компьютерного программирования»[62]. Позже эту последовательность заново открыл» четырнадцатилетний Марк Фейнберг. Он написал об этом в «Fibonacci Quarterly»[63]. В 1967 году Марк, уже второкурсник Пенсильванского университета, разбился на мотоцикле.
Доктор Матрикс, когда мы обедали с ним и с Дональдом Кнутом, сообщил нам еще об одной неправдоподобной диковинке, не связанной с числами Фибоначчи. Расположите десять цифр в алфавитном порядке, и они образуют случайное и весьма скучное с виду число 8 549 176 320. Разделите его на 5. Получится 1 709 835 264 — еще одно десятизначное число, где представлены все десять цифр! Разделите и его на 5. Получится 341 967 052,8 — третье число, где каждая из десяти цифр встречается по одному разу[64]!
Теперь разделим это число на 4. Окажется, что вы снова вернулись к самому первому — «алфавитному» — числу, только в нем теперь появилась десятичная запятая. Понимаете, отчего это произошло? Дважды разделив на 5 и один раз на 4, вы тем самым разделили первое число на 100[65].
Я послал эту диковинку, обнаруженную доктором Матриксом, своему другу Оуэну О'Ши, который родом из ирландского города Cobh (произносится «Коув»). Он — автор недавно вышедших «Магических чисел Профессора»[66]. В ответ Оуэн написал мне о множестве других удивительных свойств этого якобы «неинтересного» алфавитного числа. Например, оно раскладывается по степеням простых чисел как произведение 210, 33,5 и 61843. Это означает, что 8 549 176 320 без остатка делится на все числа от 1 до 9, исключая 7. Множитель 61 843 (тоже простое число) возникает довольно неожиданно.
О'Ши двумя способами делит число 8 549 176 320 по разрядам, получив следующее уравнение:
854 + 917 + 632 + 0 = 8 · 5 · 49 + (1 · 7 · 63) + 2 + 0
Каждая часть равна 2403.
Затем О'Ши составил число, воспользовавшись обратным алфавитным порядком, и получил 0 236 719 458. Представив разряды этого числа в виде слагаемых: 0 + 2367 + 19 + 4 + 5 + 8, — он снова пришел к сумме 2403.
Два американских математика, Джеймс Смоук и Томас Дж. Ослер, в своей книге «Волшебный трюк Фибоначчи»[67] сообщают еще об одном удивительном фокусе. Возьмем дробь 100/89. В десятичном виде она равна 1,123 595 505 61… Первые пять цифр в ней — это первые пять чисел Фибоначчи[68].
Добавьте два нуля в числитель и по девятке в начало и конец знаменателя, и у вас получится дробь 10000/9899, то есть
1,0102030508132134559046368…
Заметьте: первая единица, а затем девять следующих пар цифр представляют собой десять первых чисел в ряду Фибоначчи!
Авторы приводят доказательство, что если такую процедуру повторять бесконечно, то можно получить все числа Фибоначчи из этого ряда! Каждый следующий шаг увеличивает количество получаемых чисел Фибоначчи на пять. Таким образом, если представить дробь 1000000/998999 в десятичном виде и объединить составляющие ее цифры в триады, мы увидим, что перед нами первые пятнадцать чисел Фибоначчи; следующий шаг даст нам первые двадцать пять элементов ряда, и так до бесконечности!
Этот забавный случай рассмотрен в упражнении G43 «Конкретной математики» Грэхема, Кнута и Паташника[69], заметивших, что данное явление впервые обнаружили Брук и Уолл (дается ссылка на их статью в «Fibonacci Quarterly»)[70]. Кнут сообщил мне, что похожие дроби, такие как 1000000/989899 и 1000000000/898998999, сходным образом порождают числа трибоначчи!
Полагаю, мало кто из математиков догадывается, что ряд Фибоначчи может служить основой для арифметической записи. Каждое целое положительное число можно уникальным способом выразить как сумму некоторого набора чисел Фибоначчи, не следующих одно за другим. Знаете ли вы, что двенадцатое число Фибоначчи — квадрат двенадцати, 144? Это единственное число Фибоначчи, являющееся полным квадратом, если не считать 1. А «кубы Фибоначчи» — только 1 и 8. Другие забавные подробности см. в главе 13 моего «Математического цирка»[71].
А существует ли простой способ проверить, принадлежит ли какое-нибудь число к ряду Фибоначчи? Да, такой способ есть. Целое положительное число n является числом Фибоначчи, если (и только если) 5n2 + 4 или 5n2 — 4 представляет собой полный квадрат! Можете развлечься, проверяя какие-нибудь целые положительные числа на калькуляторе. 666 — число Фибоначчи? Нет! А 123? A 987?
И наконец — странное уравнение, объединяющее ряд Фибоначчи с последовательностью факториалов и дающее в пределе значение числа е. Подобно π, это трансцендентное число так и норовит появиться в самых неожиданных местах. Загадочную дробь мне прислал О'Ши, добавив, что нашел ее в Интернете.
Глава 11
Покрытие «изуродованных» шахматных досок с помощью L-тримино
Среди современных математиков приобрела большую популярность так называемая теория покрытий. Нижеследующий текст первоначально был опубликован в «College Mathematical Journal» (май 2009).
Введение
Пусть стандартную шахматную доску «изуродовали», удалив два крайних угловых поля, расположенных по диагонали друг напротив друга. Можно ли оставшиеся 62 квадрата покрыть с помощью 31 прямоугольной костяшки домино? Ответ — нет, потому что убранные квадраты — одного цвета. Допустим, их цвет — белый. Тогда среди оставшихся 62 полей окажутся два «лишних» черных квадрата. Между тем каждая костяшка домино покрывает одну черную и одну белую клетку. После того как мы поместим на доску 30 костяшек, две черные клетки останутся свободными. Они не могут примыкать друг к другу (иметь общую сторону), а следовательно, их невозможно покрыть при помощи костяшек домино. Эта широко известная задача, которая решается элементарной проверкой равенства, являет собой простой пример задачи покрытия изуродованной шахматной доски.
Менее известна связанная с ней другая задача. Предположим, доску изуродовали, удалив две клетки разного цвета из любых мест доски. Всегда ли можно будет покрыть при помощи костяшек домино оставшиеся 62 клетки? Ответ — да, и существует прелестное доказательство, полученное Ральфом Гомори[72].
Проведем по доске жирные линии, как показано на рис. 1. Получим замкнутую дорожку, вдоль которой клетки лежат, словно камешки чередующегося цвета в ожерелье. Если с этой дорожки убрать две любые клетки противоположного цвета, получится два незамкнутых сегмента — или один, если удаленные клетки находились рядом (имели общую сторону).
В каждом сегменте будет поровну черных и белых клеток, а следовательно, его можно будет покрыть с помощью костяшек домино. Остроумное доказательство Гомори легко обобщить, применив его ко всем квадратным доскам с четным числом полей.
Если вместо пластинок домино покрывать доску с помощью L-тримино (называемых также косыми, или V-тримино, или угловыми тримино), тогда все квадратные доски, у которых число клеток без остатка делится на 3, можно будет покрыть такими фигурами (кроме доски 3×3). Среди них мы не будем рассматривать «неповрежденные», а возьмем лишь такие изуродованные доски, где число клеток кратно 3 после того, как из произвольного места доски удалили одну клетку. Будем называть такие доски дефицитными. Иными словами, доска со стороной n является дефицитной, если n2–1 кратно 3; т. е. само n не кратно 3. Длины сторон таких досок образуют ряд (1):
2, 4, 5, 7, 8, 10, 11, 13, 14… (1)
Каждое из этих чисел будем называть порядком доски. И еще: здесь и далее слово «тримино» будет означать исключительно L-тримино.
Основной вопрос: какие дефицитные доски (полученные после того, как из произвольного места обычной доски убрано одно поле) со сторонами из ряда (1) можно покрыть (без разрывов и наложений) с помощью L-тримино? Мы будем рассматривать эти доски, грубо говоря, по возрастанию их порядка, кульминацией же станет полное и универсальное решение задачи.
Степени двойки
Рассмотрим доску второго порядка. Ее можно покрыть, какую бы клетку мы ни удалили (см. рис. 2, слева). На рис. 2, справа, показано, как можно покрыть доску 4-го порядка. Вырезанная клетка неизбежно оказывается в квадрате 2×2, в каком-то из его четырех углов. Остальная часть доски покрывается благодаря приему, который Соломон Голомб окрестил rep-tile («рептилия»): элемент покрытия (tile) как бы воспроизводит увеличенную копию (replica) самого себя. Левый верхний квадрат 2×2 можно поворачивать, чтобы недостающая клетка оказывалась в четырех разных местах, и весь квадрат 4-го порядка можно при этом поворачивать так, чтобы эта клетка попадала на любое из его шестнадцати полей.
А 1953 году Голомб, «отец» полимино (он придумал для них название и первым начал изучать их), вывел индуктивное доказательство, продемонстрировав, что все доски со сторонами, отвечающими прогрессии 2, 4, 8, 16…) можно покрыть с помощью тримино, когда отсутствует произвольная клетка доски. Впервые доказательство было опубликовано в 1938 году[73]. Позже его повторил Э.Б. Эскотт (см. статью в журнале «Open Court»[74]). С тех пор математики включают это доказательство в свои книги, часто без ссылки на Голомба. Роджер Нельсен приводит Голомбово доказательство в виде единственной диаграммы, без всяких словесных пояснений[75]. Знаменитое доказательство Голомба начинается с рассмотрения квадрата 2×2 (рис. 3, слева). Этот квадрат затем помещается в угол квадрата 4—го порядка (рис. 3, в центре). А уже этот квадрат 4×4 располагается в углу квадрата 8-го порядка (рис. 3, справа), после чего рядом с углом зачерненного квадрата 4-го порядка укладывают одно тримино. Мы уже знаем, что зачерненный квадрат можно покрыть при отсутствии в нем любой клетки, и мы знаем, что три незачерненных области (примыкающих к нашему одиночному тримино) можно покрыть с помощью тримино, так как в каждой из них отсутствует одна клетка (угловая). Поворачивая доску[76], можно добиться того, чтобы любая клетка в зачерненном квадрате приходилась на любое место доски 8-го порядка.
Порядки 5 и 7
Далее нас ждет доска 5-го порядка, поскольку 5 — следующее число в последовательности (1), для которого мы пока не вывели доказательства. Если убрать центральную клетку, полученную фигуру можно покрыть очень аккуратно и симметрично (как показано на рис. 4. слева). Я покрыл эту доску четырьмя элементами 2×3. Каждый из них можно в свою очередь двумя различными способами покрыть двумя тримино. Покрытия 2×3 — очень полезный инструмент при решении задач с тримино. Когда недостающая клетка расположена, как показано черным на рис. 4 (средний квадрат), клетку над ней, как нетрудно убедиться, приходится покрывать с помощью тримино, примыкающего слева или справа. В любом случае у нас появятся две свободное клетки (они обозначены как 1 и 2), которые нельзя покрыть тримино. И в самом деле, квадрат 5-го порядка можно покрыть тримино, только если недостающая клетка находится в одной из позиций, обозначенных черным на рис. 4. справа. Вот вам приятное упражнение: посмотрите, удастся ли вам покрыть доску, если вырезанная клетка находится в углу.
Доску 7-го порядка анализировать гораздо труднее. Я не сумел придумать одиночную диаграмму, которая доказывала бы, что такую доску можно покрыть тримино, однако Голомб прислал мне свое неопубликованное доказательство, где он использует три диаграммы.
Его доказательство развивается так. На рис. 5 показаны три способа покрытия доски 7-го порядка. Очевидно, что при каждом таком покрытии квадрат 2×2 можно покрыть с помощью тримино, если недостающая клетка находится в любом из его четырех углов. Поворачивая эти три фигуры, можно добиться того, чтобы недостающая клетка приходилась на любое место доски.
Несколько труднее придумать, как покрыть доски с помощью максимального количества элементов 2×3. Вот вам задачка: сможете ли вы покрыть доску 7×7 с помощью шести элементов 2×3 и четырех тримино (рис. 6)? Решение — единственное (если не считать его зеркального отражения). (Это решение приводится на с. 204).
Посмотрев на рис. 5, можно отметить, что для каждого приведенного разбиения количество свободных тримино (не входящих в элементы 2×3) оказывается четным. И это не совпадение. Мне удалось вывести следующий тривиальный закончик. Когда порядок доски — четный, количество свободных тримино при покрытии — нечетное, и наоборот: когда порядок доски — нечетный, число свободных тримино должно быть четным.
Доказать эти равенства просто. Если доска имеет четный порядок, то после удаления одной клетки количество тримино при любом способе покрытия составит величину, равную (n2–1)/3, т. е. нечетное число. В каждом элементе 2×3 содержится два тримино, а значит, общее количество тримино, входящих в состав элементов 2×3, неминуемо окажется четным. Если вычесть это четное число из общего числа тримино (а оно — нечетное), мы получим нечетное число тримино, не входящих ни в один элемент 2×3.
Пусть доска имеет нечетный порядок. После удаления одной клетки на доске останется четное число клеток. «Вычтем» из него четное число тримино, входящих в элементы 2×3, и получим четное число тримино, в такие элементы не входящих.
Выше 7-го порядка
Индуктивное доказательство Голомба применимо к бесконечному числу рядов, чьи элементы удваиваются. В частности, после того как мы успешно покрыли доску 7×7, можно понять, как покрываются доски размером n×n, где n = 2k·7. К примеру, возьмем доску 14-го порядка. Разобьем ее на области, расположив зачерненную доску 7-го порядка в левом верхнем углу и положив одно тримино у нижнего правого угла этой зачерненной доски, подобно тому, как мы проделывали раньше (см. рис. 3, справа). Поскольку доску 7-го порядка можно покрыть, из этого с очевидностью вытекает доказательство для доски 14-го порядка, а далее, по индукции, доказательства для порядков 28, 56, 112…
Подобное доказательство нельзя вывести для доски 10-го порядка, расположив в ее углу квадрат 5-го порядка, поскольку его не всегда удается покрыть (см. рис. 4). Однако с этой сложностью легко справиться, применив несколько иной подход. Разместим в левом верхнем углу квадрат 8-го порядка — его, как нам известно, можно покрыть. Остается угловая область, имеющая ширину 2 и занимающая низ и правую часть большого квадрата (см. рис. 7). Путем поворотов и отражений любую недостающую клетку в квадрате 8-го порядка удается расположить в любом месте этой доски. Таким же образом получаем доказательство для порядков 20, 40, 80 и т. д. Сходное доказательство существует для доски 11-го порядка: квадрат 7-го порядка располагаем в ее углу, и тогда угловая область, занимающая нижнюю и боковую часть большого квадрата, будет иметь ширину 4. Индукция позволяет вывести доказательства и для порядков 22, 44, 88… Понятно, что эта методика дает нам бесконечное количество покрываемых досок, длина сторон которых удваивается (это своего рода удваивающийся ряд). Просто располагайте в левом верхнем углу любой доски заведомо покрываемый квадрат со стороной, которая меньше стороны исходной доски либо равна ей. Если оставшуюся снизу и сбоку область большой доски вам удастся покрыть — значит, и большая доска покрываема.
Обычно труднее всего покрыть доски, у которых длина сторон — простое число. Проблему доски 17-го порядка удается решить, поместив в ее угол квадрат со стороной 13 и оставив внизу и сбоку область шириной 4. Проблему доски 19-го порядка — поместив в ее угол квадрат 14-го порядка (доказательство его покрываемости основано, в свою очередь, на таком же свойстве квадрата 7-го порядка) и получив угловую область шириной 5 (см. рис. 8).
ПОЛНЫЙ И УНИВЕРСАЛЬНЫЙ РЕЗУЛЬТАТ
Занимаясь разбиением этих фигур, я подобрался (но пока недостаточно близко) к тому, чтобы вывести индуктивное доказательство того, что все дефицитные квадраты покрываемы, за исключением квадрата 5-го порядка. Это доказательство в конце концов получили И. Пинг Чу и Ричард Джонсонбау[77]. Чу и Джонсонбау позаботились не только обо всех дефицитных квадратах, но и обо всех дефицитных прямоугольниках! Их индуктивное доказательство — слишком специальное, чтобы его здесь приводить. Коротко говоря, они продемонстрировали покрываемость для всех прямоугольников m×n (включая и квадраты — случай, когда m=n) с числом клеток, кратным 3 после удаления одного поля. Подобные доски покрываемы, если выполняются все четыре необходимых и достаточных условия:
1) m ≥ 2,
2) n ≥ m,
3) если m=2, n должно тоже равняться 2,
4) m ≠ 5.
Прямоугольник 4×7 — самый маленький дефицитный прямоугольник (не квадрат), который можно покрыть с помощью L-тримино. Вот еще одно упражнение: много ли у вас уйдет времени на то, чтобы покрыть такую фигуру с помощью тримино и двух элементов 2×3, если недостающая клетка у этой фигуры располагается в углу?
Кристофер Йенсен показал в своей неопубликованной статье, что если в углу любой доски убрать две клетки, как показано на рис. 9. получившуюся доску нельзя будет покрыть с помощью тримино. Однако, если исключить приведенные пять случаев, доску с длинами сторон 3m–1 и 3n+1 и с любыми двумя недостающими клетками окажется возможным покрыть при следующем необходимом и достаточном условии: либо если n=1, либо если m ≥ 3 и n ≥ 3.
Заключение
Кейт Джонс, основавшая и возглавляющая фирму «Kadon Enterprises», которая выпускает и продает разные симпатичные механические головоломки и другие забавные математические предметы, выпустила на рынок игру под названием «V-21»[78]. Буква V здесь — от «V-тримино», а 21 — число тримино в наборе, где кроме ярко раскрашенных фишек имеется также доска 8-го порядка, на которую их можно класть. Первое задание — положить мономино (квадрат 1-го порядка) в произвольное место доски, а затем покрыть оставшуюся площадь с помощью тримино (т. е. решить задачу для доски 8-го порядка). К игре прилагается сорокастраничное руководство. В нем напечатана короткая статья Нортона Старра «Дефицитная шахматная доска» и приводятся изображения прямоугольных досок и задачи к ним.
Завершим наш рассказ красивейшим симметричным покрытием стандартной шахматной доски (рис. 10).
А вот и ответ на задачу, которую я предложил вам на с. 197:
Глава 12
Ay, мистер Херш, вы «здесь»?
Рубен Херш принадлежит к небольшой группе математиков, убежденных, что математика реальна лишь в контексте человеческой цивилизации. А я — бесстыжий платоник и предпочитаю иной язык мышления, предполагающий, что если из Вселенной исчезнут все разумные существа, то математические объекты и теоремы в каком-то смысле никуда не денутся — даже если не останется никого, кто смог бы писать или говорить о них. Гигантские простые числа продолжают быть простыми, хоть никто и не доказывал, что они являются таковыми. Как выразился однажды Бертран Рассел, даже в центре Солнца дважды два — четыре.
Более ранние мои замечания по этой теме см. под заголовком «В защиту платоновского реализма» — так называется глава у моей книги «Джинн из гиперпространства» (Амхерст, штат Нью-Йорк: «Prometheus Books», 2008).
Брайан Дэвис в своей статье «Дайте платонизму умереть» («IMS Newsletter»[79], июнь 2007) определяет математический платонизм как убежденность в том, что математические объекты существуют «в некоем математическом царстве, за пределами времени и пространства». Но у меня (как, полагаю, и у большинства математических платоников) — иные убеждения. Аристотель, математический реалист, с радостью ухватился за платоновские универсалии трансцендентального царства («оранжевость», «коровность», «двоечность» и т. п.), приспособив их к объектам, существующим во времени и пространстве. Так, геометрическая форма вазы находится «здесь», в данной вазе, эта форма не плавает где-то возле платоновской «пещеры».
В качестве примера можно рассмотреть камешки. Пусть каждый из них — модель числа 1. В таком случае очевидно, что все теоремы арифметики можно доказать, перекладывая камешки. В принципе таким путем можно даже доказать, что произвольно выбранное число (не важно, насколько большое) является простым или составным.
Рубен Херш, мой давний оппонент, в своей статье «О платонизме» пишет:
На мой взгляд, платонизм (имея в виду обычный, бытовой платонизм типичного практикующего математика) справедливо признаёт существование математических фактов и объектов, не управляемых волей или прихотью конкретного математика, но обрушиваемых на него как объективные факты и сущности, о которых он должен узнавать и чье независимое существование и чьи качества он стремится обнаруживать и исследовать.
Что ж, профессор Херш, добро пожаловать в Платоновский клуб! Любой платоник всецело согласится с вашими словами. Но затем Херш делает невероятное заявление: «Ошибка платонизма — в неверной интерпретации этой объективной реальности, в выведении ее за рамки человеческой культуры и сознания».
Математические теоремы и объекты, продолжает Херш, подобно «многим другим реалиям культуры» являются «внешними и объективными с точки зрения любой отдельной личности (курсив Херша), но при этом внутренними, историчными и социально обусловленными с точки зрения данного социума или данной культуры в целом (по-прежнему курсив Херша)».
Получается, Херш все-таки не платоник! Неужели он вправду отрицает, что перекладывание камешков с целью доказать, скажем, что число 17 является простым, — это процесс, протекающий «здесь» независимо отданной культуры? Разумеется, манипулирование камешками является культурно обусловленным — в том тривиальном смысле, что вообще всякая человеческая деятельность так или иначе обусловлена культурой. Но не более того. Тот факт, что число 17 — простое, очевидным образом реализуется «здесь», в поведении камешков: по сути, аналогичным образом присутствует «здесь» эллиптическая орбита Марса или спиральная форма нашей галактики.
Херш буквально помешан на втискивании математики в социальность; в своей книге «Что же такое математика?» («Oxford University Press», 1997) пишет даже (крепитесь!), что 8+5 не обязательно равняется 13, ибо у отдельных небоскребов нет тринадцатого этажа. Стало быть, если вы доедете на лифте до восьмого этажа, а потом подниметесь еще на пять этажей, вы окажетесь на четырнадцатом этаже. Вероятно, Херш предполагает тем самым, что в субкультуре некоторых высотных зданий законы арифметики постоянно нарушаются?
Надо ли мне отмечать здесь, что с тех пор, как Декарт арифметизировал геометрию, ее модели тоже в принципе возможно строить с помощью камешков? И в самом деле, Вселенная заполнена моделями почти всех математических областей, объектов и теорий. Любой тополог сумеет доказать, построив грубую модель из конверта и затем разрезав ее пополам, что рассечение бутылки Клейна на две равные части даст две зеркальные ленты Мёбиуса[80].
Для комплексных чисел и производных функций, возможно, не существует материальных моделей, однако и эти объекты вкраплениями испещряют Вселенную. Ньютон и Лейбниц, если выражаться обиходным языком, изобрели дифференциальное и интегральное исчисление, но в более глубинном смысле они открыли законы, согласно которым живет Вселенная. Множество Мандельброта не находится вне пространства и времени[81]. Оно существует на компьютерных экранах. Неужели антиреалисты считают, что математик, занимающийся свойствами Мандельбротова множества, на самом деле изучает структуры внутри собственного мозга, так как его глаза и мозг воспринимают экран, или что он исследует часть человеческой цивилизации и культуры, к которой он принадлежит, — потому что именно эта цивилизация создала его компьютер?
Подобные рассуждения грешат таким же искажением научного языка, как и заявления, что астрономы, мол, изучают «нездешние» образования, поскольку телескопы — часть человеческой культуры, не говоря уж о том, что и вся астрономия тоже является ее частью. Отсюда недалеко до утверждений, что и вся Вселенная существует лишь потому, что ее наблюдают человеческие цивилизации (а не наоборот — мы существуем, потому что нас создала Вселенная).
Возможно, кардинальные числа, введенные Кантором[82], не находятся «здесь», но кто знает?.. Не исключено, что они скрываются где-нибудь в космосе. Подобно физикам, математики часто совершают открытия, исследуя материальные модели. Классический пример: Фрэнк Морли вывел свою «теорему Морли», изучая углы бумажных моделей произвольных треугольников — моделей таких же «здешних», как камни или звезды. Никоим образом нельзя сказать, будто Морли изобрел свою теорему или нашел ее где-то внутри своего черепа или культуры, к которой принадлежал.
В своей статье Херш справедливо называет меня теистом. И добавляет, что я верю в действенность молитвы. Атеисту Хершу это кажется оскорблением. Что ж, все зависит от значения слова «действенность». Я не верю, что если кто-нибудь помолится о победе футбольной команды или о выздоровлении любимого человека, больного раком, то Господь приложит десницу к Вселенной и тут же ее изменит. Я могу допустить, что Бог вполне способен менять вероятности исхода событий на квантовом уровне, — в наши дни эта догадка популярна среди теистов, — но все же я склонен сомневаться и в этом.
Однако я в самом деле считаю, что молитвы о прощении оправданны, а молитвы о даровании мудрости помогают принимать верные решения. Гилберт Честертон замечает где-то, что для атеиста настанет грустный день, когда с ним произойдет что-то чудесное, а ему будет некого за это поблагодарить.
Херш пишет также, что как-то раз я обвинил его в сталинизме. Не могу себе представить, как бы я мог такое сделать. Если все-таки сделал — приношу свои извинения. Возможно, я однажды напомнил ему душераздирающую сцену из оруэлловского «1984», где чиновник ухитряется, пытая узника, заставить того поверить, что, когда два пальца прибавляют к двум, появляется еще и пятый.
Кроме того, Херш заявляет: один раз я обвинил его в том, что он солипсист. И снова я не совсем понимаю, что он имеет в виду. Не исключаю, что я описывал его антиреализм как туманную разновидность социального (коллективного) солипсизма. Херш — большой поклонник статьи антрополога Лесли Уайта «Место математической реальности». Ее место, как заявляет Уайт, не во внешнем мире, а в человеческой культуре. Математические теоремы сходны в этом смысле с правилами дорожного движения, модами, живописью, музыкой и т. п.
Конечно же это не солипсизм в обычном смысле слова. За пределами психиатрических лечебниц вообще нет истинных и последовательных солипсистов. Однако антиреализм Уайта и Херша приправлен социальным солипсизмом — поскольку, по их утверждениям, если исчезнет человеческая цивилизация, уйдет в небытие и вся математика. Ну да, Вселенная при этом не погибнет, однако больше не останется никого, кто занимался бы математикой (разве что ученые на других планетах). Полагаю, Херш согласится: то, что мы называем математическими структурами и явлениями, будет по-прежнему существовать, однако если не останется ни одного разумного существа, которое бы изучало их, во Вселенной не будет ничего, что заслуживало бы названия математики.
И тут снова возникает вопрос о том, какой же научный язык в данном случае самый лучший и наименее противоречивый. Мне кажется, лучше всего сказать, что если исчезнут все разумные существа, то 2+2 по-прежнему будет равно четырем, отношение длины окружности лунного диска к его диаметру по-прежнему будет близко к та, а сумма внутренних углов евклидова треугольника будет по-прежнему составлять 180°. Подозреваю, Херш предпочтет заявить, что ни одно из этих суждений больше не будет верным, поскольку не останется цивилизаций, где такие утверждения могли бы выдвигаться. А если он думает иначе, тогда Херш, чего доброго, превратится в платоника.
Вместе с Полем Дираком и тысячами других выдающихся математиков я верю, что существует Бог — непревзойденный математик, чьи познания в этой науке гораздо, гораздо обширнее наших. Но бесконечны ли они — откуда мне знать? Господу наверняка неведома последняя цифра числа то, ибо такой цифры не существует вообще. Даже будь я атеистом, мне бы казалось чудовищным высокомерием считать, что математика реально существует лишь в сознании разумных обезьян.