Когда ты была рыбкой, головастиком - я...

Глава 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).

_Рис. 1

_{Рис. 2. Площадь = 63 кв. ед.}

В данном случае сторона квадрата — 8, площадь — 64. В ряду Фибоначчи 8 находится между 5 и 13. Следовательно, 5 и 13 автоматически становятся сторонами прямоугольника, площадь которого должна составлять 65: отсюда выигрыш в одну квадратную единицу.

Благодаря этому свойству нашего ряда мы можем построить квадрат со стороной, длина которой представляет любое число из этого ряда (больше 1), а затем разрезать фигуру в соотношении, определяемом двумя предшествующими членами ряда. Так, выбрав квадрат со стороной 13, можно разделить три из его сторон на сегменты с длинами 5 и 8, а затем провести линии разреза, как показано на рис. 3. Площадь этого квадрата — 169. Из его фрагментов можно сложить прямоугольник с длинами сторон 21 и 8, а площадь этого прямоугольника будет равна 168. Из-за своего рода «перекрывания», происходящего вдоль диагонали прямоугольника, здесь мы теряем, а не приобретаем одну квадратную единицу.

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

_Рис. 3

По всей видимости, первую попытку обобщить этот парадокс квадрата и прямоугольника с помощью упомянутого ряда Фибоначчи предпринял В. Шлегель (см. его статью в «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. Доказательство Гомори}

Проведем по доске жирные линии, как показано на рис. 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-го порядка можно при этом поворачивать так, чтобы эта клетка попадала на любое из его шестнадцати полей.

_{Рис. 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-го порядка.

_{Рис. 3. Голомбово индуктивное доказательство}