Когда ты была рыбкой, головастиком - я... (Гарднер) - страница 81

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

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

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

Введение

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

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

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

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