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

Гарднер Мартин

Добавьте два нуля в числитель и по девятке в начало и конец знаменателя, и у вас получится дробь 10000/9899, то есть

1,0102030508132134559046368…

Заметьте: первая единица, а затем девять следующих парцифр представляют собой десять первых чисел в ряду Фибоначчи!

Авторы приводят доказательство, что если такую процедуру повторять бесконечно, то можно получить всечисла Фибоначчи из этого ряда! Каждый следующий шаг увеличивает количество получаемых чисел Фибоначчи на пять. Таким образом, если представить дробь 1000000/998999 в десятичном виде и объединить составляющие ее цифры в триады, мы увидим, что перед нами первые пятнадцатьчисел

Фибоначчи; следующий шаг даст нам первые двадцать пять элементов ряда, и так до бесконечности!

Этот забавный случай рассмотрен в упражнении G43 «Конкретной математики» Грэхема, Кнута и Паташника [69] , заметивших, что данное явление впервые обнаружили Брук и Уолл (дается ссылка на их статью в «Fibonacci Quarterly») [70] . Кнут сообщил мне, что похожие дроби, такие как 1000000/989899 и 1000000000/898998999, сходным образом порождают числа трибоначчи!

Полагаю, мало кто из математиков догадывается, что ряд Фибоначчи может служить основой для арифметической записи. Каждое целое положительное число можно уникальным способом выразить как сумму некоторого набора чисел Фибоначчи, не следующих одно за другим. Знаете ли вы, что двенадцатое число Фибоначчи — квадрат двенадцати, 144? Это единственное число Фибоначчи, являющееся полным квадратом, если не считать 1. А «кубы Фибоначчи» — только 1 и 8. Другие забавные подробности см. в главе 13 моего «Математического цирка» [71] .

69

R. Graham, D. Knuth, and 0. Patashnik, «Exercise G43», Concrete Mathematics (Reading, MA: Addison-Wesley, 1994).

70

Brooke and Wall, The Fibonacci Quarterly 1: 80, 1963.

71

M. Gardner, Mathematical Circus (New York: Knopf, 1979).

А существует ли простой способ проверить, принадлежит ли какое-нибудь число к ряду Фибоначчи? Да, такой способ есть. Целое положительное число n является числом Фибоначчи, если (и только если) 5n ²+ 4 или 5n ²— 4 представляет собой полный квадрат! Можете развлечься, проверяя какие-нибудь целые положительные числа на калькуляторе. 666 — число Фибоначчи? Нет! А 123? A 987?

И наконец — странное уравнение, объединяющее ряд Фибоначчи с последовательностью факториалов и дающее в пределе значение числа е. Подобно , это трансцендентное число так и норовит появиться в самых неожиданных местах. Загадочную дробь мне прислал О'Ши, добавив, что нашел ее в Интернете.

Глава11

Покрытие «изуродованных» шахматных досок с помощью L-тримино

Среди современных математиков приобрела большую популярность так называемая теория покрытий. Нижеследующий текст первоначально был опубликован в «College Mathematical Journal» (май 2009).

Введение

Пусть стандартную шахматную доску «изуродовали», удалив два крайних угловых поля, расположенных по диагонали друг напротив друга. Можно ли оставшиеся 62 квадрата покрыть с помощью 31 прямоугольной костяшки домино? Ответ — нет, потому что убранные квадраты — одногоцвета. Допустим, их цвет — белый. Тогда среди оставшихся 62 полей окажутся два «лишних» черных квадрата. Между тем каждая костяшка домино покрывает одну черную и одну белую клетку. После того как мы поместим на доску 30 костяшек, две черные клетки останутся свободными. Они не могут примыкать друг к другу (иметь общую сторону), а следовательно, их невозможно покрыть при помощи костяшек домино. Эта широко известная задача, которая решается элементарной проверкой равенства, являет собой простой пример задачи покрытия изуродованной шахматной доски.

Менее известна связанная с ней другая задача. Предположим, доску изуродовали, удалив две клетки разногоцвета из любых мест доски. Всегда ли можно будет покрыть при помощи костяшек домино оставшиеся 62 клетки? Ответ — да, и существует прелестное доказательство, полученное Ральфом Гомори [72] .

_{Рис. 1. Доказательство Гомори}

<

72

М. Gardner, «The Eight Queens and Chessboard Divisions», in The Unexpected Hanging and Other Mathematical Diversions (Chicago: University of Chicago Press, 1991).

empty-line />

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

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

Если вместо пластинок домино покрывать доску с помощью L-тримино (называемых также косыми, или V-тримино, или угловыми тримино), тогда все квадратные доски, у которых число клеток без остатка делится на 3, можно будет покрыть такими фигурами (кроме доски 3x3). Среди них мы не будем рассматривать «неповрежденные», а возьмем лишь такие изуродованные доски, где число клеток кратно 3 после того, как из произвольного места доски удалили одну клетку. Будем называть такие доски дефицитными.Иными словами, доска со стороной n является дефицитной, если n ²–1 кратно 3; т. е. само n некратно 3. Длины сторон таких досок образуют ряд (1):

2, 4, 5, 7, 8, 10, 11, 13, 14… (1)

Каждое из этих чисел будем называть порядкомдоски. И еще: здесь и далее слово «тримино» будет означать исключительно L-тримино.

Основной вопрос: какие дефицитные доски (полученные после того, как из произвольного места обычной доски убрано одно поле) со сторонами из ряда (1) можно покрыть (без разрывов и наложений) с помощью L-тримино? Мы будем рассматривать эти доски, грубо говоря, по возрастанию их порядка, кульминацией же станет полное и универсальное решение задачи.

Степени двойки

Рассмотрим доску второго порядка. Ее можно покрыть, какую бы клетку мы ни удалили (см. рис. 2, слева). На рис. 2, справа, показано, как можно покрыть доску 4-го порядка. Вырезанная клетка неизбежно оказывается в квадрате 2x2, в каком-то из его четырех углов. Остальная часть доски покрывается благодаря приему, который Соломон Голомб окрестил rep-tile («рептилия»): элемент покрытия (tile) как бы воспроизводит увеличенную копию (replica) самого себя. Левый верхний квадрат 2x2 можно поворачивать, чтобы недостающая клетка оказывалась в четырех разных местах, и весь квадрат 4-го порядка можно при этом поворачивать так, чтобы эта клетка попадала на любое из его шестнадцати полей.