Путеводитель для влюбленных в математику Шейнерман Эдвард
Гораздо проще показать, что эти множества равновелики, если найти взаимно однозначное соответствие между их элементами. В голову приходит следующая мысль. Допустим, члены клуба решают, что на вторую конференцию больше не поедут те, кто побывал там в первый год. Тогда каждую группу по три человека из первого множества можно сопоставить с другой группой по четыре человека из второго множества. Например, если 1, 4 и 5 поехали на конференцию в первый год, то на следующий год поедут 2, 3, 6 и 7. Или: 145 2367.
Выпишем все возможности:
123 4567
124 3567
125 3467
…
356 1257
…
567 1234
Это взаимно однозначное соответствие показывает, что A и B равновелики.
Вы можете выписать все элементы множеств полностью и убедиться, что их количество совпадает (хотя взаимно однозначное соответствие избавляет нас от этой нудной работы). Перечень всех элементов вы найдете в конце главы.
Подытожим: у нас есть два способа доказать, что конечные множества имеют равные мощности: пересчитать их элементы или найти между ними взаимно однозначное соответствие. Однако, если множество содержит бесконечно много элементов, первый метод перестает работать: ни одно число не подходит на роль мощности (множество действительных чисел). Таким образом, нам остается лишь найти взаимно однозначное соответствие, чтобы показать, что мощности двух бесконечных множеств совпадают. Вот пример.
Как мы помним, буквой обозначается множество целых чисел:
= {…, –3, –2, –1, 0, 1, 2, 3, …}.
Введем обозначение + для множества положительных целых чисел[84]:
+ = {1, 2, 3, 4, …}.
Совпадают ли мощности и +?
Есть искушение сказать, что содержит вдвое больше элементов, чем + и потому «в два раза более бесконечно». Однако мощности данных множеств совпадают. Почему? Мы покажем это с помощью взаимно однозначного соответствия.
Составим два перечня. Первый будет включать все положительные целые числа, а второй – вообще все целые числа, и положительные, и отрицательные, но в необычном порядке. Сопоставляя числа в первом и втором перечне, мы выстроим взаимно однозначное соответствие. Это показано в таблице[85].
Таким образом, мощности и + равны, что, в принципе, и неудивительно – ведь оба эти множества бесконечны.
Выстроив взаимно однозначное соответствие между элементами двух множеств, мы показали, что мощности и + совпадают, что они, так сказать, «одинаково бесконечны». Пришло время для вопроса поинтереснее: совпадают ли мощности + и ? Да, разумеется, оба бесконечны. Впрочем, лучше не утверждать наверняка, пока мы не выстроим взаимно однозначное соответствие между их элементами. Сейчас мы убедимся, что это невозможно.
Итак, мы должны сопоставить каждый элемент первого множества с элементом второго множества и убедиться, что каждый элемент второго множества сопоставлен с элементом первого. Как же доказать, что это невозможно? Мы покажем, что попытки выстроить все элементы + и в пары обречены на провал, потому что кое-какие элементы окажутся пропущены. А теперь к делу!
Допустим, мы все-таки нашли взаимно однозначное соответствие между + и . Тогда все элементы можно занести в таблицу такого рода:
Все целые положительные числа занесены в левую колонку, все (вроде бы) действительные числа занесены в правую колонку. Сейчас мы убедимся: как ни заполняй правую колонку, будут действительные числа, которые туда не попадут.
Но прежде нам придется отвлечься на одну досадную техническую проблему[86]. Некоторые действительные числа в десятичной системе счисления записываются двумя способами. Например, число 1/4. С одной стороны, мы можем записать его как 0,25. С другой стороны, можно записать и так: 0,24999999999999… Ряд девяток уходит в бесконечность. 0,25 тоже можно записать с бесконечным количеством нулей на конце. Таким образом,
Примем решение вносить в таблицу запись числа с нулями на конце. Это никак не влияет на доказательство, мы просто договариваемся о форме записи.
Итак, вернемся к доказательству. Представим, что перед нами уже лежит таблица с колонками целых положительных и действительных чисел. Поищем действительное число, ускользнувшее из правой колонки.
Для начала подчеркнем первую цифру после запятой в первой колонке, вторую цифру после запятой во второй колонке и т. д.:
Выпишем подчеркнутые цифры в ряд: 3, 8, 7, 3, 6… С помощью этого ряда создадим новое число. Начнем его с нуля, поставим десятичную запятую и дальше будем двигаться по ряду подчеркнутых цифр с двумя условиями:
(A) Если подчеркнута цифра 3, пишем 7.
(B) Если подчеркнута не цифра 3, пишем 3.
Как это работает с нашим рядом?
Первая цифра 3. Выполняется условие (A). Мы получаем 0,7___.
Вторая цифра 8. Выполняется условие (B). Мы получаем 0,73___.
Третья цифра 7. Снова выполняется условие (B). Получаем 0,733___.
Четвертая цифра снова 3, по правилу (A) ставим семерку: 0,7337___.
Пятая цифра 6, по правилу (B) ставим тройку: 0,73373___.
Продолжая двигаться вдоль ряда подчеркнутых цифр, мы получим число x. В нашем примере число x = 0,73373…, а остальные цифры заполняются согласно условиям (A) и (B).
Вот процесс выстраивания x в пошаговом виде:
Число x зависит от нашей таблицы. Другая таблица даст другое x. Мы утверждаем, что в любой таблице x, выстроенное таким образом, не встречается в правой колонке; следовательно, взаимно однозначное соответствие между целыми положительными и действительными числами невозможно.
Начнем с самого верха. Очевидно, число x не идентично первому числу в правой колонке, и вот почему. Первая строка 1 Y1. Если первая цифра Y1 после запятой – тройка, то первая цифра числа x после запятой – семерка; но если первая цифра Y1 после запятой – не тройка, то первая цифра числа x после запятой, напротив, – тройка. Ситуация выглядит так:
Таким образом, Y1 и x не совпадают. Какая бы цифра ни стояла после запятой в Y1, первая после запятой цифра x другая. Следовательно, в первой строке таблицы x мы не найдем.
Двигаясь вниз по таблице, мы обнаружим, что во второй строке x тоже нет. Но если соответствие между + и взаимно однозначное, где-нибудь в правой колонке число x просто обязано возникнуть. Иными словами, x появляется в строчке k, где слева стоит целое положительное число k, то есть k Yk = x. Но мы все время будем сталкиваться с одной и той же проблемой. Какая цифра стоит в числе Yk на позиции k после запятой? Если тройка, то на соответствующей позиции в x обнаружитс семерка; если не тройка, то на соответствующей позиции в x как раз тройка. Это выглядит так:
Эта проверка показывает, что x в правом столбце отсутствует. Мы, конечно, можем выстроить новую таблицу и поместить x на первую позицию. Но, если применить к новой таблице алгоритм с правилами (A) и (B), мы обнаружим, что в ней отсутствует некое число x'.
Вывод: всякая таблица будет ущербной! Таким образом, взаимно однозначное соответствие между + и построить невозможно.
Мы доказали, что мощности и + совпадают. И дело тут не только в том, что оба множества бесконечно велики, а еще в том, что мы построили биекцию.
+ и тоже содержат бесконечное число элементов, но биекция между ними неосуществима. Так как любое целое положительное число – действительное, можно сказать, что «больше» +. Целых положительных чисел недостаточно, чтобы по одному сопоставить их со всеми действительными.
Мощность конечного множества – это число. Мощность множества A = {1, 3, 7, 9} равна четырем: |A| = 4. Но как зафиксировать мощность бесконечного множества? До выкладок Кантора математики довольствовались красивым символом . Есть искушение написать: |+| = и || = , а затем сделать ошибочное заключение, что |+| = ||. Символ не передает всех особенностей, присущих мощностям бесконечных множеств.
Кантор решил исправить это и разработал новую систему чисел за пределами конечных. Такие числа называются трансфинитными и могут отразить мощность бесконечных множеств.
Мы выяснили, что + – «наименьшее» бесконечное множество. Что это означает? Предположим, X – бесконечное множество. Между X и + может быть биекция, а может и не быть. Но математики показали, что всегда есть взаимно однозначное соответствие между + и некоторой частью множества X: либо + и X равновелики, либо + равновелико с частью множества X. Грубо говоря, либо + и X имеют одинаковый размер, либо X больше.
Множества мощности + называют счетными. Это самые маленькие бесконечные множества. Кантор ввел символ для обозначения их мощности: Мощности и + совпадают, потому Так как обширнее, чем +, логичным будет записать: Величина обозначает мощность бесконечного множества, и это не обычное число. Его называют трансфинитным числом, причем – наименьшее из трансфинитных чисел[87].
Мощности бесконечных множеств описывает целая вселенная трансфинитных чисел. Множества мощностью больше называют несчетными, и математики показали, что есть новый «уровень бесконечности», на ступень выше Мы можем доказать, что существует множество X, которое обладает двумя свойствами:
1.
2. Нет множеств с мощностью между |X| и
Таким множествам присвоили мощность Иначе говоря, и между этими двумя величинами нет других трансфинитных чисел.
Существует целая последовательность трансфинитных чисел. Она выглядит следующим образом: и т. д. Иерархия подразумевает, что есть трансфинитное число, превышающее любое k[88]. Наименьшее трансфинитное число, превышающее любое k, мы обозначаем , и есть бесконечно много еще больших чисел!
Где в этой схеме находится ? Мы выяснили, что Но можем ли мы определить мощность в точности? Сколько всего действительных чисел?
Вообразите: вы переступаете порог великолепного сооружения. За огромными воротами – мраморная лестница, ведущая в дивные палаты. Но стоит вам открыть дверь в подвал, как картина резко переменится. Там вы обнаружите ржавые трубы, искрящую проводку, бьющий в глаза электрический свет и разбитый пол, а может, и скопища тараканов. Подвал ужасен, но здания наверху без него не было бы.
Это хорошая метафора для сооружения под названием «математика». Как мы уже говорили в начале главы, все объекты в математике (от чисел до кругов) можно определить через другие объекты, попроще. Рано или поздно мы дойдем до самого дна и обнаружим объект, через который объясняются все другие. Это и будет множество.
Мы определили множество как набор объектов[89], но не сказали, что такое набор (в общем-то, это просто другое слово вместо «множества»), и не задались вопросом, какого рода объекты мы собираем вместе (и даже не дали определение объекта). Как нам выпутаться из этой ситуации?
Вначале математики относились к ней довольно беззаботно. Говорили просто: есть такая штука – множество и есть свойство «быть элементом множества», которое обозначают символом, а раз так, то можно двигаться дальше[90]. Но все это рано или поздно приводит к затруднениям.
Первое множество, приходящее нам в голову, – пустое множество. Там нет никаких элементов, и мы обозначаем его символом . Мощность пустого множества равна нулю, и утверждение x ложно для любого x (потому что внутри ничего нет).
Дальше нам приходит в голову, что множества можно характеризовать через свойства их элементов. Например, множество четных чисел задают следующим образом:
Форма записи {x | свойства x} определяет множество всех объектов, обладающих указанными свойствами.
А дальше возникает уйма сложностей.
В начале XX века философ и математик Бертран Рассел[91] размышлял о множестве A = {x | x – такое множество, что x x}.
Это множество всех множеств, чьими элементами не являются они сами. Например, пустое множество удовлетворяет условию: , потому что пустое множество не содержит элементов. Таким образом, A.
Дальше Рассел задал роковой вопрос: входит ли множество A во множество A?
• Если ответ «да», то AA. Но тогда не выполняется условие попадания во множество A: оно не должно быть элементом самого себя.
• Если ответ «нет», то AA. Тогда выполняется условие попадания во множество A, и оно является элементом самого себя.
Если AA, то AA. Если AA, то AA. Но не может же такого быть, что A и входит, и не входит в A! Что-то пошло не так[92].
Одно из решений этого противоречия заключается в том, что множества A просто не существует. Нет его, и все тут.
После работ Рассела подход к теории множеств претерпел существенные изменения. Четкие, ясные, применимые на практике правила закрепили, как формировать множества и какие операции с ними можно совершать[93]. Определение множества и входит в свод правил непрямым образом. Мы не объясняем, что это; мы просто описываем, как оно себя проявляет. Мы говорим, что есть такие вещи, как множества, у них есть определенные свойства, а еще есть правила, по которым мы с ними работаем. Эти правила не позволили парадоксу Рассела вздыбить свою безобразную голову, и противоречий больше не возникало.
Но вернемся к вопроу: сколько всего действительных чисел? Мы знаем, что мощность множества положительных целых чисел равна И мы знаем, что Следует ли из этого, что Иными словами, существуют ли множества, чья мощность больше, чем +, но меньше, чем ?[94] Кантор верил, что но не мог найти доказательство; свое предположение он назвал континуум-гипотезой. Многие ученые заинтересовались этим вопросом. В 1900-е годы немецкий математик Давид Гильберт составил перечень важнейших математических проблем наступающего XX века. Доказательство (или опровержение) континуум-гипотезы вошло в его перечень первым номером.
Эту главную для Гильберта проблему разрешили неожиданным образом. Короткий, но исчерпывающий ответ звучит следующим образом: «Может быть и так, и этак».
Ну и ну! Математику ценят за то, что на все вопросы (обычно) находится точный ответ. «Может быть и так, и этак» разрушает определенность. Как с этим жить?
Работы Курта Гёделя (1940-х годов) и Пола Коэна (1960-х) показали, что общепринятые правила аксиоматической теории множеств неполны и потому не позволяют ответить на поставленный вопрос. Точнее говоря, эти математики продемонстрировали: нельзя ни доказать, ни опровергнуть то, что существуют множества, чья мощность больше, чем +, но меньше, чем . Другими словами, можно принять или допущение или допущение Дальше мы получим две разные математические системы. Обе корректны, просто непохожи друг на друга.
Глава 9
Числа Фибоначчи[95]
Начнем с укладки квадратов и домино. Вообразим длинную горизонтальную рамку размерами 1 10. Мы хотим полностью заполнить ее квадратами 1 1 и костяшками домино 1 2, не оставив ни единой щели. Вот картинка:
Вопрос: сколькими способами это можно сделать?
Для удобства обозначим число вариантов F10. Перебирать их все и потом пересчитывать – тяжелый труд, чреватый ошибками. Гораздо лучше упростить задачу.
Не будем с места в карьер искать F10, начнем с F1. Это проще простого! Нам нужно заполнить рамку 1 1 квадратами 1 1 и костяшками домино 1 2. Домино не поместится, остается единственное решение: взять один квадрат. Другими словами, F1 = 1.
Теперь разберемся с F2. Размер рамки 1 2. Можно заполнить ее двумя квадратами или одной костяшкой домино. Таким образом, есть два варианта, и F2 = 2.
Дальше: сколькими способами можно заполнить рамку 1 3? Первый вариант: три квадрата. Два других варианта: одна костяшка домино (две не влезут) и квадрат слева или справа. Итак, F3 = 3.
Еще один шаг: возьмем рамку 1 4. На рисунке показаны все варианты заполнения:
Мы нашли пять возможностей, но где гарантия, что мы ничего не упустили? Есть способ проверить себя.
В левом конце рамки может быть или квадрат, или костяшка домино. В верхнем ряду на рисунке – варианты, когда слева квадрат, в нижнем ряду – когда слева домино.
Допустим, слева квадрат. Оставшуюся часть нужно заполнить квадратами и домино. Другими словами, нужно заполнить рамку 1 3. Это дает 3 варианта, так как F3 = 3.
Если слева домино, размер оставшейся части 1 2, и заполнить ее можно двумя вариантами, так как F2 = 2.
Таким образом, у нас есть 3 + 2 = 5 вариантов, и мы удостоверились, что F4 = 5.
Теперь ваша очередь. Подумайте пару минут и найдите все варианты заполнения для рамки 1 5. Их немного. Решение – в конце главы. Можете отвлечься и подумать.
Вернемся к нашим квадратам. Хочется верить, что вы нашли 8 вариантов, так как есть 5 способов укладки, где слева квадрат, и еще 3 способа, где слева домино. Таким образом, F5 = 8.
Подытожим. Мы обозначили FN количество способов заполнения рамки 1 n квадратами и костяшками домино. Нам необходимо найти F10. Вот что мы уже знаем:
Двигаемся дальше. Чему равно F6? Можно нарисовать все варианты, но это скучно. Лучше разобьем вопрос на две части. Сколькими способами можно заполнить рамку 1 6, если слева (a) квадрат и (b) костяшка домино? Хорошая новость: мы уже знаем ответ!
В первом случае нам остается пять квадратов, а мы знаем, что F5 = 8. Во втором случае нужно заполнить четыре квадрата; нам известно, что F4 = 5. Таким образом, F5 + F4 = 13.
Чему равно F7? Исходя из тех же соображений, F7 = F6 + F5 = 13 + 8 = 21. А как насчет F8? Очевидно, F8 = F7 + F6 = 21 + 13 = 34. И так далее. Мы обнаружили следующую взаимосвязь:
Fn = Fn – 1 + Fn – 2.
Еще несколько шагов – и мы найдем искомое число F10. Правильный ответ – в конце главы.
Числа Фибоначчи – это последовательность:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Она выстраивается по таким правилам:
– первые два числа 1 и 1;
– каждое следующее число получаем сложением двух предыдущих.
Будем обозначать n-ный элемент последовательности Fn, начиная с нуля:
F0 = 1, F1 = 1, F2 = 2, F3 = 3, F4 = 5, …
Очередной элемент мы вычисляем по формуле:
Fn = Fn – 1 + Fn – 2.
Как мы видим, задача об укладке квадратов и домино привела нас к последовательности чисел Фибоначчи[96].
Попробуем сложить первые несколько чисел Фибоначчи. Что мы можем сказать о сумме F0 + F1 + … + Fn для любого n? Давайте проделаем кое-какие вычисления и посмотрим, что получится.
Обратите внимание на результаты сложения внизу. Видите ли вы закономерность? Повремените немного, прежде чем двигаться дальше: будет лучше, если вы найдете ответ самостоятельно, а не прочтете уже готовое решение.
Хочется верить, вы увидели, что результаты суммирования, если к ним приплюсовать по единице, тоже выстраиваются в последовательность чисел Фибоначчи. Например, сложение чисел от F0 до F5 дает:
F0 + F1 + F2 + F3 + F4 + F5 = 1 + 1 + 2 + 3 + 5 + 8 = 20 = F7 – 1.
Сложение чисел от F0 до F6 дает 33, что на единицу меньше F8 = 34. Мы можем записать формулу для неотрицательных целых чисел n:
F0 + F1 + F2 + … + Fn = Fn + 2–1. (*)
Вероятно, лично вам достаточно будетувидеть, что формула (*) работает в дюжине случаев, чтобы вы поверили, что она верна, но математики жаждут доказательств. Мы рады представить вам два возможных доказательства того, что она верна для всех неотрицательных целых чисел n. Первое называется доказательством по индукции, второе – комбинаторным доказательством.
Формула (*) представляет собой бесконечно много формул в свернутом виде. Доказать, что (*) верно для конкретного значения n, скажем для n = 6, – простая арифметическая задача. Достаточно будет записать числа от F0 до F6 и сложить их:
F0 + F1 + … + F6 = 1 + 1 + 2 + 3 + 5 + 8 + 13 = 33.
Несложно увидеть, что F8 = 34, поэтому формула действует.
Перейдем к F7. Не будем тратить время и складывать все числа: мы уже знаем сумму вплоть до F6. Таким образом,
(F0 + F1 + … + F6) + F7 = 33 + 21 = 54.
Как и раньше, все сходится: F9 = 55.
Если сейчас мы начнем проверять, работает ли формула для n = 8, наши силы окончательно иссякнут. Но все же посмотрим, что мы уже знаем и что хотим выяснить:
F0 + F1 + … + F7 = F9–1.F0 + F1 + … + F7 + F8 =?
Воспользуемся предыдущим результатом:
(F0 + F1 + … + F7) + F8 = (F9– 1) + F8.
Мы, конечно, можем вычислить (F9 – 1) + F8 арифметически. Но так мы устанем еще больше. В то же время мы знаем, что F8 + F9 = F10. Таким образом, нам не нужно ничего высчитывать или заглядывать в таблицу чисел Фибоначчи:
(F0 + F1 + … + F7) + F8 = (F9–1) + F8 = (F8 + F9) – 1 = F10– 1.
Мы удостоверились, что формула работает для n = 8, на основе того, что знали про n = 7.
В случае n = 9 мы точно так же опираемся на результат для n = 8 (убедитесь в этом самостоятельно). Разумеется, доказав верность (*) для n, мы можем быть уверены, что (*) верно и для n + 1.
Мы готовы дать полное доказательство. Как уже было сказано, (*) представляет собой бесконечное количество формул для всех значений n от нуля до бесконечности. Посмотрим, как работает доказательство.
Вначале мы доказываем (*) в простейшем случае, для n = 0. Мы просто проверяем, что F0 = F0 + 2 – 1. Так как F0 = 1, а F2 = 2, очевидным образом 1 = 2 – 1, а F0 = F2 – 1.
Дальше нам достаточно показать, что верность формулы для одного значения n (скажем, n = k) автоматически означает верность для n + 1 (в нашем примере n = k + 1). Нам лишь надо продемонстрировать, как устроено это «автоматически». Что нам нужно сделать?
Возьмем некоторое число k.
Предположим, мы уже знаем, что
F0 + F1 + … + Fk = Fk + 2– 1.
Мы ищем величину
F0 + F1 + … + Fk + Fk + 1.
Мы уже знаем сумму чисел Фибоначчи вплоть до Fk, поэтому у нас получается:
(F0 + F1 + … + Fk) + Fk + 1 = (Fk + 2–1) + Fk + 1.
Правая часть равна Fk + 2 – 1 + Fk + 1, и мы знаем, чему равна сумма следующих друг за другом чисел Фибоначчи:
Fk + 2–1 + Fk + 1 = (Fk + 2 + Fk + 1) – 1 = Fk + 3– 1
Подставим в наше равенство:
(F0 + F1 + … + Fk) + Fk + 1 = Fk + 3– 1
Сейчас я объясню, что мы сделали. Если мы знаем, что (*) верно, когда мы суммируем числа вплоть до Fk, тогда (*) должно быть верно, если мы приплюсуем Fk + 1.
Подытожим:
• Формула (*) верна для n = 0.
• Если формула (*) верна для n, она верна и для n + 1.
Мы можем уверенно сказать, что (*) верно для любых значений n. Верно ли (*) для n = 4987? Это так, если выражение верно для n = 4986, что основано на верности выражения для n = 4985, и так далее до n = 0. Следовательно, формула (*) верна для всех возможных значений n.
Этот метод доказательства известен под названием математическая индукция (или доказательство по индукции). Мы проверяем базовый случай и даем шаблон, по которому каждый следующий случай может быть доказан на основе предыдущего.
А вот совершенно другое доказательство тождества (*). Основной подход тут – воспользоваться тем фактом, что число Fn – это количество способов облицевать прямоугольник 1 n квадратами и костяшками домино.
Напомню, что нам нужно доказать:
F0 + F1 + F2 + … + Fn = Fn + 2– 1. (*)
Идея заключается в том, чтобы рассматривать обе части уравнения как решение задачи с облицовкой. Если мы докажем, что левая и правая часть – решение для одного и того же прямоугольника, они совпадут между собой. Эта техника носит название комбинаторного доказательства[97].
На какой вопрос по комбинаторике уравнение (*) дает два верных ответа? Эта головоломка похожа на те, что встречаются в шоу Jeopardy![98], где участники должны формулировать вопрос, заранее зная правильный ответ.
Правая часть выглядит проще, поэтому начнем с нее. Ответ: Fn + 2 – 1. Каков вопрос? Если бы ответ был равен просто Fn + 2, мы с легкостью сформулировали бы вопрос: сколькими способами можно облицевать прямоугольник 1 (n + 2) с помощью квадратов и костяшек домино?
Это почти то, что нужно, но ответ меньше на единицу. Попробуем мягко поменять вопрос и уменьшить ответ. Уберем один вариант облицовки и пересчитаем оставшиеся. Сложность состоит в том, чтобы найти один вариант, который кардинально отличается от остальных. Есть ли такой?
Каждый способ облицовки подразумевает использование квадратов и/или домино. Только квадраты задействованы в единственном варианте, в прочих есть хотя бы одна костяшка домино. Возьмем это за основу нового впроса.
Вопрос: Сколько существует вариантов облицовки квадратами и костяшками домино прямоугольной рамки 1 (n + 2), включающих по меньшей мере одну костяшку домино?
Сейчас мы найдем два ответа на этот вопрос. Так как оба будут верны, между числами мы сможем уверенно поставить знак равенства.
Один из ответов мы уже обсуждали. Есть Fn + 2 вариантов укладки. Только один из них подразумевает использование исключительно квадратов, без домино.
Таким образом, ответ № 1 на наш вопрос таков: Fn + 2 – 1.
Второй ответ должен быть – я надеюсь – левой частью уравнения (*). Посмотрим, как это работает.
Нужно пересчитать варианты заполнения рамки, включающие хотя бы одну костяшку домино. Давайте подумаем, где будет расположена самая первая костяшка. Есть n + 2 позиций, и первая костяшка может располагаться в позициях от 1 до n + 1.
Рассмотрим случай n = 4. Мы ищем варианты заполнения рамки 1 6, задействующие хотя бы одну костяшку домино. Мы знаем ответ: F6 – 1 = 13 – 1 = 12, но нам необходимо получить его иным путем.
Первая костяшка домино может занимать следующие позиции:
Первая колонка демонстрирует случай, когда костяшка находится на первой позиции, вторая – когда костяшка на второй, и т. д.
Сколько вариантов в каждой колонке?
В первой колонке – пять вариантов. Если отбросить домино слева, мы получим ровно F4 = 5 вариантов для прямоугольника 1 4.
Во второй колонке – три варианта. Отбросим домино и квадрат слева. Мы получим F3 = 3 варианта для прямоугольника 1 3.
Аналогично для других колонок. Вот что мы обнаружили:
Таким образом, количество способов замостить квадратами и домино (хотя бы одной костяшкой) прямоугольную рамку 1 6 равно
F4 + F3 + F2 + F1 + F0 = 12.
Вывод:
F0 + F1 + F2 + F3 + F4 = 12 = F6 – 1.
Рассмотрим общий случай. Нам дана рамка длиной n + 2. Сколько есть вариантов ее заполнения, при которых первая костяшка домино находится на некой позиции k? В этом случае первые k – 1 позиций заняты квадратами. Таким образом, в общей сложности занята k + 1 позиция[99]. Оставшиеся (n + 2) – (k + 1) = n – k + 1 можно заполнить любыми способами. Это дает Fn – k + 1 вариантов. Построим диаграмму:
Если k меняется от 1 до n + 1, величина n – k + 1 меняется от 0 до n. Таким образом, количество вариантов заполнения нашей рамки с использованием хотя бы одной костяшки домино равно
Fn + Fn – 1 + … + F1 + F0.
Если поставить слагаемые в обратном порядке, мы получим левую часть выражения (*). Таким образом, мы нашли второй ответ на поставленный вопрос:
F0 + F1 + … + Fn.
Итак, у нас есть два ответа на вопрос. Величины, полученные с помощью двух выведенных нами формул, совпадают, и тождество (*) доказано.
Сложение двух следующих друг за другом чисел Фибоначчи дает очередное число Фибоначчи. В этом разделе мы затронем вопрос поинтереснее: что будет, если мы поделим число Фибоначчи на предшествующее ему в ряду? Посчитаем соотношение Для возрастающих значений k. В таблице вы можете видеть соотношения от
Чем больше становятся числа Фибоначчи, тем ближе соотношение к константе, примерно равной 1,61803.
Это число – вы будете удивлены – достаточно известное, и если вы введете его в поисковую систему, вывалится уйма страниц о золотом сечении. Что это такое?
Соотношение соседних чисел Фибоначчи не одинаково. Однако оно почти одинаково, если числа достаточно велики. Давайте найдем формулу для числа 1,61803 и для этого на время будем считать, что все соотношения одинаковы. Введем обозначение x:
Это значит, что Fk + 1 = xFk, Fk + 2 = xFk + 1 и т. д. Можно переформулировать:
Fk + 2 = xFk + 1 = xFk.
Но мы же знаем, что Fk + 2 = Fk + 1 + Fk. Таким образом,
xFk = xFk + Fk.
Если мы поделим обе части на Fk и перегруппируем слагаемые, то получим квадратное уравнение:
x – x – 1 = 0.
Оно имеет два решения:
Соотношение должно быть положительным. И вот мы получили знакомое нам число. Обычно для обозначения золотого сечения используют греческую букву (фи):
Мы уже приметили, что соотношение соседних чисел Фибоначчи приближается (стремится) к . Это замечательно. Это дает нам еще один способ вычислять приблизительные значения чисел Фибоначчи.
Последовательность чисел Фибоначчи – это ряд F0, F1, F2, F3, F4, F5… Если все соотношения будут одинаковы, мы получим формулу:
Fn = c.
Здесь с – еще одна константа. Сравним округленные значения Fn и для разных n:
Для больших значений n соотношение Это число равно в точности Другими словами,
Насколько хороша эта формула? Настало время новых подсчетов!
Обратите внимание: если округлить до ближайшего целого числа, мы получим в точности Fn.
Читать бесплатно другие книги:
