Глава 1

Простые числа

Физик Ричард Фейнман верил: если человечество столкнется с опасностью потери всего научного знания, но у него будет возможность передать потомкам всего одну фразу о науке, эта фраза должна описывать, как атомы образуют материю. Продолжим фантазировать в том же духе. Если бы мы могли передать следующему поколению всего одну математическую идею, это, как мне кажется, должен быть ответ на вопрос: как много существует простых чисел?

Целые числа

Математическая мысль начинается со счета. Мы используем для счета натуральные числа: 1, 2, 3 и т. д. Отсутствие объектов для счета – и необходимость подобрать число для этого отсутствия – приводит нас к понятию нуля. Когда мы складываем или умножаем натуральные числа, результат всегда представляет собой другое натуральное число. Но вычитание внушает беспокойство. Все хорошо, когда мы вычитаем три из пяти: 5 – 3, но если мы поступим наоборот, то получится 3 – 5, и результат не будет натуральным числом. Мы восполняем этот недостаток, вводя отрицательные числа: –1, –2, –3 и т. д.

Множество всех натуральных и полученных при их вычитании отрицательных чисел вместе с нулем называют целыми числами. Математики используют стилизованную букву Z, чтобы обозначить все целые числа:

ℤ = {…, –4, –3, –2, –1, 0, 1, 2, 3, 4, …}.

Когда мы делим целые числа друг на друга, возникает загвоздка. В то время как мы можем складывать, перемножать целые числа и вычитать их друг из друга в полной уверенности, что получим целое число, результат деления одного целого числа на другое иногда оказывается целым числом, а иногда и нет.

Возьмем два положительных целых числа а и b. Мы говорим, что а делится на b, если частное a / b – тоже целое число. Мы называем a – делимым, b – делителем.

Например, 24 делится на 6 (потому что частное от деления – целое число), но не на 7 (потому что частное не является целым числом). Всякое положительное целое число делится само на себя: если а – положительное целое число, то частное от а / а равно 1, и это, разумеется, целое число. Также всякое положительное целое число делится на 1, потому что, если а – положительное целое число, результат деления а / 1 равен а.

Положительное целое число называется простым, если у него есть ровно два делителя: 1 и оно само.

Например, 17 – простое число, потому что 1 и 17 – его единственные делители. По той же причине 2 – простое число.

С другой стороны, 18 не является простым числом, потому что помимо 1 и самого себя оно делится на 2, 3, 6 и 9. Такие числа, как 18, называют составными. Если говорить математическим языком, то положительное целое число называют составным, если у него есть другие делители помимо 1 и самого себя.

Размежевание чисел на простые и составные касается всех натуральных чисел, кроме 1. Мы выделяем 1 в отдельную категорию и называем единичным элементом, или единицей. Кого-то расстраивает тот факт, что Плутон больше не причисляют к планетам, другие раздражены тем, что 1 не считается простым числом.

Если подытожить, у нас есть три категории положительных целых чисел:

• единица с одним положительным делителем;

• простое число с двумя положительными делителями;

• составное число с тремя и более положительными делителями.

Отмечу, что 1 – единственное в своем роде число, а вот составных чисел бесконечно много: 4, 6, 8, 10, 12 и т. д. – составные числа (и таких еще много).

Но сколько же простых чисел существует?

Разложение на множители

Разложить число на множители означает представить его в виде произведения. Рассмотрим число 84. Мы можем разложить его на множители несколькими способами, например:

2 × 42; 3 × 28; 12 × 7; 2 × 6 × 7; 21 × 4.

В пределе разложить на множители означает найти произведение простых чисел, например: 84 = 2 × 2 × 3 × 7. Нельзя разбить эти множители на части, потому что каждый из них представляет собой простое число. Разумеется, мы можем добавить какое-то количество единиц, например:

84 = 1 × 1 × 2 × 2 × 3 × 7,

но дополнительные множители усложняют, а не упрощают выражение, другие множители от этого не становятся меньше.

Возьмем другой пример: 120. Мы можем представить 120 как 12 × 10 и затем 12 как 2 × 2 × 3, а 10 – как 2 × 5. Это дает:

120 = (2 × 2 × 3) × (2 × 5). (A)

С другой стороны, мы можем начать так: 120 = 4 × 30 и далее заметить, что 4 = 2 × 2, а 30 = 2 × 3 × 5. Вместе это дает:

120 = (2 × 2) × (2 × 3 × 5). (B)

Важно отметить, что простые числа в выражениях (A) и (B) одинаковые, различается лишь порядок, в котором они перемножаются. Это показано на рисунке.

Любой способ представления числа 120 в качестве произведения простых чисел дает один и тот же результат.

Эта единственность разложения на множители зафиксирована в следующей теореме.

Теорема (основная теорема арифметики). Любое положительное целое (натуральное) число может быть разложено на простые множители единственным образом (если пренебречь порядком множителей) [18] .

(Здесь необходимо небольшое пояснение. В случае, скажем, числа 30 это утверждение достаточно ясно. Мы можем представить 30 как 2 × 3 × 5 или как 5 × 3 × 2 – разницы нет, отличается лишь порядок множителей. Простое число имеет всего один простой множитель – само себя. Например, множитель 13 – это 13. Но как быть с 1? Принято говорить, что пустое произведение равно единичному элементу; таким образом, произведение отсутствующих элементов равно 1.)

Сочетая простые числа, мы выстраиваем все положительные целые числа. Простые числа – это атомы умножения.

Насколько много?

Вернемся к вопросу: сколько всего простых чисел существует? Ответ – на следующей строчке.

Теорема. Простых чисел бесконечно много.

Утверждение приписывают Евклиду. Доказательство этой теоремы – математическая жемчужина. Мы не можем доказать ее методом перебора. Очевидно, что время от времени в числовом ряде попадаются простые числа. Вот несколько первых простых чисел:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 и 67.

Но чем дальше мы идем по последовательности простых чисел, тем обширнее становятся промежутки между ними. Если посмотреть на перечень выше, можно увидеть, что два числа отстоят друг от друга максимум на 6 единиц (например, 53 и 59). Но простые числа 89 и 97 отстоят друг от друга на 8 единиц, все целые числа между ними составные. Или вот другой пример: 139 и 149 – их отделяет 10 единиц. Чем дальше мы двигаемся, тем быстрее увеличиваются промежутки между соседними простыми числами. Можно предположить, что в конечном итоге простые числа должны совсем исчезнуть. На самом деле, хотя они и встречаются все реже, их список в числовом ряду не имеет конца. Впрочем, прежде чем говорить об этом уверенно, мы должны привести доказательство.

Ключевая идея – задаться вопросом: а что, если?..

А что, если количество простых чисел конечно? Если мы продемонстрируем, что предположение: «Количество простых чисел конечно» – приводит к абсурдному выводу, то будем считать его ложным. Вслед за Шерлоком Холмсом мы найдем истину, отбросив невозможные варианты, и у нас получится, что простых чисел бесконечно много.

Вот что нам надо будет сделать:

1. Предположить, что количество простых чисел конечно;

2. Показать, что это предположение ведет к невозможному выводу;

3. Сделать умозаключение, что, раз предположение ведет к логическому противоречию, оно ложно;

4. Вывести из этого, что простых чисел бесконечно много.

А теперь перейдем к делу. Предположим, что простые числа можно пересчитать, и посмотрим, к чему это приведет.

Если количество простых чисел конечно, должно существовать наибольшее простое число P – крайнее в ряду простых чисел. В таком случае полный перечень простых чисел будет выглядеть так:

2, 3, 5, 7, 11, 13, …, P .

Перемножим все эти числа и приплюсуем единицу. Назовем получившееся гигантское число N:

N = (2 × 3 × 5 × 7 × 11 × 13 × … × P ) + 1.

Число N – простое? Наше предположение заставляет нас ответить: нет, потому что N больше P, последнего простого числа. Значит, N – составное число, и его можно разложить на множители. Здесь мы попадаем в западню.

Мы знаем, что у N есть простые делители. Может ли таким делителем быть 2? Мы утверждаем: нет. Посмотрите на формулу для вычисления N и обратите внимание, что число в скобках четное, потому что среди множителей присутствует 2:

N = ( 2 × 3 × 5 × 7 × 11 × 13 × … × P ) + 1.

Таким образом, N на единицу больше некоторого гигантского четного числа. Другими словами, N – нечетное, следовательно, оно не делится на 2.

Ну и ладно. Мы же знаем, что у N есть простой делитель, так что нет ничего страшного в том, что 2 не подходит. Как насчет 3? Посмотрим снова на число в скобках и обнаружим, что среди множителей есть 3:

N = (2 × 3 × 5 × 7 × 11 × 13 × … × P ) + 1.

Таким образом, N на единицу больше некоторого гигантского числа, делящегося на 3. Это означает, что при вычислении частного N / 3 мы получим остаток 1. Следовательно, N не делится на 3.

Видите, куда мы движемся? Возьмем очередное простое число, 5. Мы утверждаем, что N не делится на 5, потому что оно на единицу больше числа, без остатка делящегося на 5:

N = (2 × 3 × 5 × 7 × 11 × 13 × … × P ) + 1.

Точно так же мы доказываем, что N не делится ни на 7, ни на 11, ни на 13 и ни на какое угодно другое простое число!

К чему мы пришли? Наше предположение о том, что количество простых чисел конечно, привело нас к двум выводам:

– N делится на некое простое число;

– N не делится ни на какое простое число.

Но это же абсурдно! Из ловушки можно выбраться, только если признать, что предположение о конечном количестве простых чисел было ложным. Таким образом, получается, что простых чисел бесконечно много.

Конструктивный подход

Представленное нами доказательство относится к разряду доказательств от противного. Мы предположили, что утверждение, обратное тому, которое мы хотим доказать, верно, затем продемонстрировали, что это приводит к безвыходной ситуации, после чего сделали умозаключение, что наше предположение ложно, а утверждение, требующее доказательства, истинно. Путеводная путаница, софистика-эквилибристика!

Есть и другой способ доказательства: создать некий механизм по производству простых чисел. Мы засыпаем в него пригоршню простых чисел и – вуаля! – оттуда высыпаются новые простые числа. Вот как работает эта машина.

Зачерпнем полдюжины простых чисел: 2, 3, 5, 7, 11 и 13. Перемножим их и приплюсуем единицу:

(2 × 3 × 5 × 7 × 11 × 13) + 1 = 30 031.

Ясно, что 30 031 не делится на 2, – это легко заметить, потому что последняя цифра нечетная. На 3 оно тоже не делится (потому что на единицу больше, чем 2 × 3 × 5 × 7 × 11 × 13, которое делится на 3). Точно так же оно не делится на 5, 7, 11 и 13. Стало быть, или это число само простое, или его можно разложить на простые множители, не входящие в наш перечень. Кости выпали так, что число 30 031 – составное. Оно раскладывается на простые множители следующим образом: 59 × 509. Этих чисел не было в нашем перечне.

Возьмем их и предыдущие полудюжины чисел и построим новое число:

(2 × 3 × 5 × 7 × 11 × 13 × 59 × 509) + 1,

что равно 901 830 931. Кости выпали так, что число оказалось простым.

Мы можем добавить его в наш перечень и наштамповать так еще много чисел – либо простых, либо разложимых на простые множители. Эта операция позволяет бесконечно получать все новые и новые простые числа.

Другое доказательство

Это не единственное доказательства того, что простых чисел бесконечно много. Вот вам еще одно.

Как и в первом доказательстве, предположим, что количество простых чисел конечно, и покажем, что это предположение ведет к противоречию. Представим, что самое большое простое число равно P, и составим перечень простых чисел:

2, 3, 5, 7, 11, 13, …, P .

Пусть N – результат перемножения всех этих чисел:

N = 2 × 3 × 5 × 7 × 11 × 13 × … × P .

Теперь давайте подумаем обо всех числах от 1 до N включительно. Каждое из них (за исключением 1) делится на одно или несколько простых чисел; иными словами, любое число (кроме 1) делится на какое-то простое число.

Сколько чисел от 1 до N делится на 2? Очевидно, что половина (четные числа). Вычеркнем их и оставим лишь нечетные:

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, …

Количество целых чисел между 1 и N, которые мы вычеркнули, равно N / 2.

Вычеркнем из оставшихся чисел те, которые делятся на 3. Вот что получится:

1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, …

Мы удалили треть оставшихся чисел. Осталось две трети, а от изначального количества –

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

1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, …

Дальше мы вычеркиваем числа, делящиеся на 7, оставив шесть седьмых от нашего перечня, и будем двигаться по этому пути, пока не дойдем до числа P.

В конце концов количество тех чисел, которые мы не вычеркнули, станет равно

Так как все числа от 1 до N, кроме 1, делятся на какое-то простое число, выражение (C) должно быть равно 1. Верно? Вспомним, что N = 2 × 3 × 5 × 7 × 11 × 13 × … × P, подставим это произведение в выражение (C) и перегруппируем множители:

Это дает 1 × 2 × 4 × 6 × … × (P – 1), что существенно больше 1! Выражение (C) должно быть равно 1, но очевидным образом не равно 1. Ошибка заключалась в изначальном предположении о том, что количество простых чисел конечно. Следовательно, их бесконечно много.

Две сложные задачи

Есть много захватывающих вопросов о простых числах. Здесь я расскажу про две самые печально известные проблемы.

Хотя простых чисел бесконечно много, они встречаются все реже и реже, когда мы последовательно двигаемся от единицы к бесконечности. Позже (в главе 7) мы проанализируем среднюю разность между двумя соседними большими простыми числами. Однако простые числа все равно часто встречаются рядом, отличаясь на две и более единицы (единственная пара с отличием на один – 2 и 3). Если простые числа отличаются на две единицы, их называют простыми числами-близнецами, или парными простыми числами. Наименьшая пара близнецов – числа 3 и 5. Между 1 и 10 000 есть 205 пар близнецов, последние – числа 9929 и 9931.

Вопрос: простых чисел-близнецов бесконечно много?

Надо признать, что это неизвестно до сих пор.

Вот другой вопрос. Принято считать, что впервые его поставил немецкий математик Кристиан Гольдбах (1690–1764). Ему стало любопытно: какие четные числа (кроме 2) можно представить в качестве суммы двух простых? Вот пример:

Вопрос: можем ли мы продолжать этот ряд бесконечно? Гольдбах предположил, что любое четное число (за исключением 2) представляет собой сумму двух простых.

Но на самом деле мы до сих пор не знаем этого наверняка.

Применение простых чисел в криптографии

Изучение простых чисел относится к области математики под названием теория чисел. Британский математик Годфри Харди говорил: «До сих пор никто не обнаружил, как применить теорию чисел в военных целях».

Харди не мог предвидеть появления глобальной компьютерной сети и того факта, что безопасность в сети будет зависеть от простых чисел. Каким образом?

Пусть P и Q – два больших простых числа, скажем стозначных. Перемножить их – титанический труд для человека, но компьютер может посчитать произведение N = P × Q мгновенно. В то же время мы угодим в тупик, если попытаемся выяснить, какие два простых множителя дают N при умножении. Никто не знает эффективного алгоритма разложения таких огромных чисел на простые множители.

(Как это ни странно, определить, простое число или составное, можно достаточно быстро; однако найти простые множители больших чисел совсем не просто.)

Удивительно, однако эта диспропорция – легко перемножить, сложно разложить на множители – легла в основу создания шифров. Криптографическая система с открытым ключом устроена так, что можно раскрыть метод шифровки сообщений, но это не облегчит расшифровку засекреченных текстов. Мы не станем сейчас погружаться в детали метода, но основная идея состоит в том, что в процессе шифрования используется составное число N, представляющее собой произведение двух огромных простых чисел: N = P × Q. Расшифровка требует знания конкретных простых чисел P и Q. Если мы знаем N, этого достаточно для шифровки, но не для декодирования, а найти его простые множители все еще чрезвычайно сложно.

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

Криптографическая система с открытым ключом имеет и военные применения, вплоть до системы приведения в боевую готовность ядерного оружия.

Решение задачи о разложении на множители

211 591 = 457 × 463.

 

Глава 2

Двоичная система счисления

[28]

Однажды в Риме

Древних римлян часто поминают дурным словом за их громоздкую систему записи чисел. Люди не любят римские числа, так как они обременяют вычисления. Никто не обрадуется перспективе перемножать XLVII и DCDXXIV. А вот задача умножить 47 на 924 не выглядит настолько угрожающей (хотя большинство из нас все равно побежит за калькулятором).

Впрочем, прежде чем сбрасывать римские числа со счетов как причудливый анахронизм, нам необходимо признать, что их основополагающий принцип – буквы вместо цифр – используется до сих пор. Этот ключевой аспект римских чисел обрел новое воплощение. Что легче прочесть?

• Реновация школ в нашем округе обойдется в 23000000 долларов.

• Реновация школ в нашем округе обойдется в 23 млн долларов.

Разумеется, я не стал разделять разряды в первом случае, чтобы число было сложнее прочесть (и я попал в точку, не правда ли?). Но, даже если проставить пробелы, фраза «Пентагон требует дополнительные 19 000 000 000 долларов» сложнее для восприятия, чем «Пентагон требует дополнительные 19 млрд долларов». Иногда удобнее использовать слова вместо чисел.

Мнимое преимущество позиционной системы счисления – это то, что в ней проще производить вычисления. Но давайте задумаемся о том, сколько сил уходит на перемножение двух чисел. Во-первых, нам необходимо запоминать дополнительные математические данные. К тому же мы обязаны помнить таблицу умножения. Во-вторых, мы проделываем многоуровневую процедуру: сортируем числа по разрядам, умножаем по соответствующему правилу, получаем промежуточные данные, складываем.

Да, десятичные числа легче перемножать, чем их римские аналоги, однако это по-прежнему утомительно. Возникает вопрос, есть ли способ записывать числа, который бы облегчал вычисления. Мы выяснили, что да, есть, но для этого придется пожертвовать наглядностью.

Единичная система счисления

Простейший способ записи чисел – единичная система счисления: мы просто записываем столько же символов (будем использовать цифру 1), сколько единиц в интересующем нас числе. Например, число 3 окажется трехзначным: 111. Сложение и умножение становятся исключительно простыми. Чтобы сложить 3 и 5, мы просто запишем два числа, 111 и 11111, друг за другом (без пробела) – и вот он, ответ: 11111111. Умножать тоже просто. Мы запишем одно число вертикально, а другое горизонтально и получим следующую таблицу:

Затем мы заполним таблицу, поставив единичку в каждом столбце и в каждой колонке:

Наконец, мы выпишем все единички в ряд и получим ответ: 111111111111111. Складывать и перемножать числа в единичной системе счисления существенно проще, чем десятичные или римские числа.

Разумеется, такая простота вычислений дается ценой титанических затрат внимания и времени. Никому не захочется прибегать к этому методу, чтобы перемножить 47 и 924.

Компромисс

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

Для записи чисел в десятичной системе счисления используют десять символов, располагаемых в разных комбинациях в ряд по горизонтали. Значение символа зависит от его места в ряду. 29 и 92 означают разные числа, потому что 2 и 9 занимают разные позиции. 29 означает «два десятка и девять единиц». 5804 означает «пять тысяч, восемь сотен, ни одного десятка и четыре единицы». Позиция цифры в десятичном числе означает, на какую степень десяти мы ее умножаем. Разряды растут справа налево: единицы, десятки, сотни, тысячи, десятки тысяч и т. д. Иными словами, запись 5804 означает:

5 × 10³ + 8 × 10² + 0 × 10 1 + 4 × 10 0 .

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

Двоичная система устроена схожим образом, просто позиция в записи означает, на какую степень двух (а не десяти) мы должны умножить эту конкретную цифру.

В двоичной системе счисления используются всего два символа: 0 и 1. Разряды здесь тоже растут справа налево, обозначая количество единиц, двоек, четверок, восьмерок и т. д. Например, в двоичной записи 10110 означает:

1 × 2⁴ + 0 × 2³ + 1 × 2² + 1 × 2 1 + 0 × 2 0 = 16 + 4 + 2 = 22.

Проверьте, насколько вы ориентируетесь в новой теме: чему равно число 42 в двоичной системе и чему равно число 110112 в десятичной? Ответы – в конце главы.

Вычисления

Двоичные числа труднее для чтения, чем десятичные. Двоичная запись 1011001 кажется менее привычной, чем десятичная запись того же числа: 89. Преимущество двоичных чисел в том, что их использование облегчает вычисления. Вместо огромного количества математических данных нам необходимы всего две таблицы:

Заметьте, что в таблице умножения 10 означает число два.

Сложение двоичных чисел устроено так же, как в десятичной системе. Например, нам нужно найти сумму 101002 и 11102. Расположим эти числа друг над другом:

Дальше нужно двигаться справа налево, складывая цифры в каждом столбце и при необходимости перемещая единицу на столбец влево. В нашем случае мы сложим два нуля и получим ноль:

Дальше идет столбец двоек. Мы складываем 1 и 0 (переносить ничего не требуется):

Дальше – столбец четверок. Мы складываем 1 и 1, получаем 10, пишем 0, держим 1 в уме и переносим на столбец влево:

Следующий столбец – восьмерки. Складываем 1 и 0 и 1, получаем 10, пишем 0 и держим 1 в уме:

Заканчиваем на столбце, означающем, сколько раз в числе встречается 16. Сложение дает 10, мы пишем 0 в текущем столбце и 1 в столбце с разрядом 32:

Мы обнаружили, что 10100 + 1110 = 100010.

Переведем это на язык десятичных чисел:

10100 2 = 20, 1110 2 = 14, 100010 2 = 34.

Разумеется, 20 + 14 = 34.

Умножение в двоичной системе проще, чем в десятичной. Достаточно усвоить два принципа: сложение двоичных чисел (мы в нем только что разобрались) и умножение на степени двойки.

Умножение числа на 10 в десятичной системе не представляет сложности: мы просто добавляем цифру 0 справа: 23 × 10 = 230. Точно так же выглядит умножение на 2 в двоичной системе: 1101 × 10 = 11010. В случае десятичных чисел это очевидно, в случае двоичных 1101 означает:

1 × 8 + 1 × 4 + 0 × 2 + 1 × 1.

Умножение на 2:

1 × 16 + 1 × 8 + 0 × 4 + 1 × 2 + 0 × 1.

Лишний ноль на конце дает 11010.

Умножение на 4, 8 и другие степени двойки тоже просто: например, умножение на 810 (10002) равнозначно приращению трех нулей с правой стороны числа.

Итак, умножение превращается в игру «перемести-и-добавь-цифры». Проиллюстрируем это на примере умножения 11010 на 1011. Для начала запишем второе число так:

1011 = 1000 + 10 + 1.

Умножение на 11010 можно представить так:

11010 × 1011 = 11010 × (1000 + 10 + 1) = 11010 × 1000 + 11010 × 10 + 11010 × 1 = 11010 000 + 11010 0 + 11010.

Удобнее умножать в столбик:

А вот и ответ:

Давайте переведем числа в десятичные, чтобы удостовериться, что все правильно:

11010 2 = 16 + 8 + 2 = 26;

1011 2 = 8 + 2 + 1 = 11;

100011110 2 = 256 + 16 + 8 + 4 + 2 = 286.

Мы не ошиблись: 26 × 11 = 286.

Дроби

В десятичной системе мы можем записывать не только целые числа. Если поставить в конце запятую, мы получим новые места для цифр: по мере движения вправо степени десяти будут все меньше. Например, 34,27 – это компактный способ записи такого выражения:

Двоичная система тоже позволяет записывать дробные значения. Каждую следующую цифру после запятой мы умножаем на предыдущую степень двойки. Например, 101,0112 означает:

Непривычный способ записать одну вторую: 0,12!

Есть и другие системы счисления, помимо десятичной, единичной и двоичной. В третичной системе мы пользуемся цифрами 0, 1 и 2, здесь все строится на степенях тройки. Скажем, 11023 означает:

1 × 27 + 1 × 9 + 0 × 3 + 2 × 1 = 38.

В дробях первая позиция справа от запятой означает умножение на одну третью, вторая позиция – на одну девятую и т. д.:

Ответ на задачу в разделе «Компромисс»

Если представить 42 в виде суммы степеней двойки, мы увидим, что это 101010 2 . А число 11011 2 можно представить как 16 + 8 + 2 + 1 = 27.

 

Глава 3

0,99999999999…

Безусловно, простейший способ записать число один – это цифра 1. Но вы можете столкнуться с тем фактом, что уходящая в бесконечность десятичная дробь 0,999999… представляет собой другой способ записи того же числа. В главе 3 мы присмотримся к этому обстоятельству повнимательнее.

Что означают десятичные числа?

Привычная нам десятичная система счисления удобна и работает отменно, почти без перебоев. Она хорошо подходит для записи целых чисел. 235 – это компактный способ сказать «две сотни, три десятка и пять единиц». Или, на языке математики:

235 = 2 × 100 + 3 × 10 + 5 × 1.

Для некоторых дробных величин десятичная система счисления также чрезвычайно эффективна. Возьмем число 3/4. В десятичной системе его можно записать так: 0,75. Эта запись означает:

Десятичная дробь 0,75 в точности равна 3/4.

Тем не менее если мы предпримем попытку записать 2/7 в виде десятичной дроби, то потерпим фиаско. Если мы попробуем разделить два на семь с помощью калькулятора, то получим неприглядное 0,28571429, причем это будет лишь приближенное значение, не равное в точности 2/7.

Такие числа, как 3/8, могут быть представлены в виде десятичной дроби, потому что знаменатель в них легко представить в виде одной из степеней десятки: 3/8 = 375/1000. Но нельзя найти целое число A, для которого выполнялось бы условие:

так как это подразумевает 2 × 10ⁿ = 7 × A. Ни одно целое число A не подходит в качестве решения уравнения, потому что левая сторона не делится на 7, а правая сторона делится. Представить 2/7 в качестве десятичной дроби невозможно. Если только не…

Десятичные дроби с бесконечным числом символов

Идея десятичной дроби с бесконечным числом символов содержит в себе один подвох, и сейчас мы выясним, какой именно. Вернемся к началу главы: что означает 0,99999… и почему оно равно 1?

Для начала давайте представим 0,999999… не как одно число, а как ряд чисел, где каждое следующее – это предыдущее с приделанной справа цифрой 9. Вот как выглядит такой ряд:

0,9 0,99 0,999 0,9999 … (*)

и так далее ad infinitum. Ясно, что элементы ряда (*) постоянно возрастают. Каждый следующий элемент пусть ненамного, но больше предыдущего.

Докажем два факта:

1. Все элементы возрастающего ряда (*) меньше 1.

2. Тем не менее для любого числа x, которое меньше 1, рано или поздно отыщется элемент ряда (*), превышающий x.

Представим элементы ряда (*) в виде обыкновенных дробей:

Есть компактный способ записать эти дроби. Знаменатели представляют собой степени десяти: 101, 10², 10³ и т. д. Каждый числитель на единицу меньше соответствующего ему знаменателя. Перепишем ряд снова:

Очевидно, что n-ный элемент ряда будет выглядеть так:

Легко убедиться, что все члены ряда (*) меньше 1, потому что числитель всякий раз оказывается меньше знаменателя.

Теперь докажем второе утверждение: если число x меньше 1, рано или поздно найдется элемент ряда (*), превышающий x.

Так как x меньше 1, разность (1 – x) положительна. Даже если x невероятно близок к единице, разница между ними будет мизерная, но положительная. Умножим (1 – x) на одну из степеней десяти:

10 ⁿ × (1 – x ).

Так как разность (1 – x) положительна, это произведение будет больше 1, если 10ⁿ достаточно велико:

10 ⁿ × (1 – x ) > 1.

Раскроем скобки:

10 ⁿ  – 10 ⁿx > 1,

перенесем 1 в левую часть, а 10ⁿx в правую:

10 ⁿ  – 1 > 10 ⁿx ,

поделим обе части на 10ⁿ:

Что мы выяснили? С одной стороны, все элементы интересующего нас возрастающего ряда меньше 1. С другой стороны, какое бы число x меньше единицы мы ни взяли, рано или поздно возникнет элемент ряда, превышающий x (а последующие будут нарастать и все больше удаляться от x).

Наш ряд неуклонно приближается к 1. Математики говорят, что этот ряд стремится к 1. Или, что то же самое, 1 представляет собой предел ряда.

Значение десятичной дроби с конечным числом символов – это сумма определенного количества десятых, сотых, тысячных и т. д. Например:

К сожалению, язык десятичных дробей с конечным числом символов слишком скуден, чтобы выразить, например, 2/7. Поэтому нам необходимо расширить лексикон.

Значение десятичной дроби с бесконечным числом символов равно пределу ряда, где на каждой ступени элемент прирастает на одну цифру. Это сложно, однако дает нам возможность выражать все числа, используя десятичную систему счисления.

Уходим в беспредел!

Нужно приложить определенные усилия, чтобы увидеть в бесконечной десятичной дроби предел ряда. Попробуем посмотреть проще.

Вернемся к знакомому нам 0,999999… Пусть:

X = 0,999999… (A)

Умножим обе части равенства на 10:

10 X = 9,999999… (B)

Вычтем (A) из (B):

9 X = 9,000000…

Теперь поделим обе части на 9 и убедимся, что X = 1. Готово! Все оказалось просто.

Этот фокус можно повторить для любой периодической десятичной дроби. Например:

Y = 0,27272727… (C)

Умножим обе части на 100 (чтобы цифры встали в строй):

100 Y = 27,27272727… – (D)

и вычтем (C) из (D):

99 Y = 27,000000…

Таким образом, Y = 27/99 = 3/11.

Вот видите! Зачем утруждать себя «сходимостями» и «пределами»? Но с бесконечными последовательностями нужно быть осторожнее. Представим себе сумму:

Z = 1 + 2 + 4 + 8 + 16 + 32 + … (E)

Умножим обе части равенства на 2:

2Z = 2 + 4 + 8 + 16 + 32 + … – (F)

и привычно вычтем (E) из (F):

–  Z = 1.

Стало быть, Z = –1? Что за абсурд?

Где мы допустили оплошность? Мы ушли в беспредел. Алгоритм, позволяющий установить значение 0,9999999… и 0,2727272727…, дал сбой, когда мы взялись за ряд 1 + 2 + 4 + 8 + 16… Во всех трех случаях речь шла о бесконечной последовательности. В чем разница? Ответ: в сходимости. Не понимая толком, что такое сходимость ряда, мы запросто придем к выводу, что сумма положительных чисел может быть отрицательным числом. Операции с выражениями (A) и (B), а также (C) и (D) математически корректны, потому что мы имеем дело со сходящимися последовательностями.

 

Глава 4

√2

Перед началом концерта музыканты настраивают инструменты по одной ноте, чтобы добиться гармоничного звучания. Однако это невозможно. Скоро мы увидим почему.

Рациональные числа

Целые числа прекрасно ладят с тремя простейшими арифметическими действиями – со сложением, вычитанием и умножением. Мы производим эти операции над двумя целыми числами и получаем целое же число. А вот деление одного целого числа на другое может привести к дробному результату.

Числа, представляющие собой результат деления целого числа на целое, называют рациональными. Например, 1,5 – это рациональное число, потому что равно 3/2.

Целое число 3 рациональное, потому что 3 = 3/1 (а еще 6/2, 12/4 и т. д.). Все целые числа – рациональные.

Целые числа ладят с тремя арифметическими действиями, а рациональные числа – со всеми четырьмя. Сумма, разность, произведение и частное рациональных чисел всегда будут рациональным числом (с привычной оговоркой о неправомерности деления на ноль).

Рациональные числа пригодны для описания повседневной жизни. Величины, которые мы измеряем, – вес, интенсивность звука, расстояние, цена, температура, время, численность населения, радиочастоты – выражаются рациональными числами.

Но если рациональные числа удобны для работы и над ними можно осуществлять арифметические операции, зачем нам другие числа?

Можно задаться более фундаментальным вопросом: существуют ли другие числа?

Диагональ квадрата

Каково расстояние между противоположными вершинами квадрата? Позже, в главе 14, мы обсудим решение этой задачи. Сейчас же достаточно знать, что длина диагонали квадрата 1 × 1 равна √2

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

Начнем с того, что, если возвести в квадрат 0, получится 0, а если возвести в квадрат 1, получится 1. Наша цель 2, а найденные числа меньше. С другой стороны, если возвести в квадрат 2, мы получим 4, а если возвести в квадрат 3, получим 9. Это больше, чем нам нужно.

1² – слишком ма́ло, 2² – слишком много. Попробуем найти величину между 1 и 2, перемещаясь с шагом 0,1, как показано в таблице.

Легко заметить: 1,4 слишком мало для квадратного корня из двух, а 1,5 – слишком велико. Следовательно, √2 лежит между этими двумя величинами.

Продолжим в том же духе. Будем возводить в квадрат числа между 1,4 и 1,5, двигаясь с шагом 0,01. Мы обнаружим, что 1,41² = 1,9881, а 1,42² = 2,0164. Из этого можно сделать умозаключение, что

Мы можем двигаться таким образом все дальше и дальше, приближаясь к √2

Рано или поздно мы либо успокоимся (достигнув числа, фантастически близкого к либо почувствуем отчаяние (увидев, что никогда не сможем точно вычислить √2

Но что означает это «точно»?

За границами рационального

Разумный способ определить точное значение числа – представить его в виде рационального числа, то есть отношения двух целых чисел. Если бы мы сумели представить √2 в виде дроби где a и b – целые числа, мы бы нашли его точное значение.

Увы, но такое невозможно. Однако это нужно доказать.

Теорема. √2 не является рациональным числом.

Будем идти от противного, как и в главе 1, где мы подсчитывали количество простых чисел. Предположим, что √2 – рациональное число. Если это допущение приведет к абсурдным выводам, значит, оно несостоятельно.

Итак, приступим. Если √2 – рациональное число, его можно выразить в виде отношения двух целых чисел:

Возведем обе части тождества в квадрат:

Раскроем скобки:

Таким образом:

или:

2 b ² = a ². (С)

Если a – целое число, мы можем разложить его на простые множители, причем (согласно основной теореме арифметики) одним-единственным способом:

a = p 1 × p 2 × … × p n .

Проделаем аналогичную процедуру с b:

b = q 1 × q 2 × … × q m .

Следовательно, левую часть равенства (С) можно представить в таком виде:

2 b ² = 2 × ( q 1 × q 2 × … × q m )² = 2 × ( q 1 × q 1 ) × ( q 2 × q 2 ) × … × ( q m × q m ).

Несложно заметить, что 2b² раскладывается на нечетное число простых множителей.

Аналогично поступаем с правой частью (С):

a ² = ( p 1 × p 2 × … × p n ) ² = ( p 1 × p 1 ) × ( p 2 × p 2 ) × … × ( p n × p n ).

В отличие от 2b², выражение a² раскладывается на четное число простых множителей.

Подытожим. В соответствии с нашим предположением 2b² = a². Это означает, что некоторое число одновременно можно разложить на четное и нечетное количество простых множителей. Но это противоречит основной теореме арифметики.

Мы пришли к невозможному выводу. Таким образом, наша изначальная посылка была ошибочна. Следовательно, √2 не является рациональным числом.

Такие числа, как √2 называют иррациональными. Рациональные числа хороши для операций с физическими величинами, но их недостаточно для всех математических величин. Длина диагонали квадрата 1 × 1 – иррациональное число.

Конструктивные числа

Начав с числа 1 и шаг за шагом проделывая операции сложения, вычитания и умножения, мы можем получить любое целое число, но и только. Если мы добавим операцию деления, нам откроются все рациональные числа, но ими же мы и будем ограничены.

Если мы введем операцию извлечения квадратного корня, то получим числа, которые не являются отношением целых чисел. Например:

Для удобства мы будем называть конструктивными такие числа, которые можно получить с помощью числа 1 и пяти операций – сложения, вычитания, умножения, деления и извлечения квадратного корня – с привычными оговорками: нельзя делить на ноль и извлекать корень из отрицательных величин.

Разумеется, возникает вопрос: все ли числа конструктивные?

Древние греки усматривали магическую внутреннюю связь между арифметикой и геометрией. Эта связь подтверждалась операциями с использованием двух инструментов: линейки без делений и циркуля. Возьмем отрезок единичной длины; какова может быть длина отрезков, построенных на его основе с помощью карандаша, линейки без делений и циркуля?

Складывать и вычитать отрезки просто. Пусть у нас есть отрезки длиной a и b. С помощью линейки мы продлеваем первый отрезок. Ставим иглу циркуля в начало второго отрезка, а острие карандаша на другой ножке циркуля – в конец отрезка. После этого мы перемещаем иглу в конец первого отрезка и отмечаем точку на продленной линии. Так мы находим сумму двух отрезков. Что касается вычитания, оно будет означать не приращение, а укорочение отрезков.

Дальше дело пойдет несколько сложнее, но мы вполне способны умножать, делить и даже извлекать квадратные корни из длин отрезков с помощью линейки без делений и циркуля.

Да, это так: с помощью двух простейших инструментов мы можем найти длины, равные всем положительным конструктивным числам!

Было время, когда греки думали, что все числа рациональные, но пифагорейцы доказали, что это не так.

Однако грекам было непросто расстаться с верой в связь арифметики и геометрии. В основе этой веры лежали представления об эстетике. Неужели не все числа можно выразить с помощью линейки без делений и циркуля?

Эта вера подкреплялась решениями двух из трех знаменитых древнегреческих геометрических задач. Наиболее известна задача о трисекции угла: с помощью линейки без делений и циркуля нужно поделить заданный угол на три равных угла.

Менее известны две другие головоломки:

• Удвоение куба. Необходимо найти длину ребра куба, чей объем в два раза больше заданного. Если длина ребра первого куба – единица, это равносильно построению отрезка длиной

• Квадратура круга. Необходимо построить квадрат, чья площадь равна площади заданного круга. Если радиус круга равен единице, его площадь равна π. Тогда сторона квадрата будет равна

Понадобилось две тысячи лет, чтобы понять: эти задачи неразрешимы. Ни ни не являются конструктивными числами. Решая проблему трисекции угла, мы сталкиваемся с тем фактом, что некоторая величина (косинус 20°) не является конструктивным числом.

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

Музыкальная гармония

Если музыканты перед концертом не настроили инструменты, возникает акустический диссонанс: музыка становится неблагозвучной.

Когда на двух инструментах берут одинаковые ноты, акустическая частота звуковых волн оказывается одинаковой. Рассогласованность же действует слушателю на нервы. Впрочем, можно брать и разные ноты, и музыка все равно будет ласкать слух, если эти ноты гармонируют друг с другом. Но как достичь гармонии? Что именно нам приятно слышать?

Этот вопрос волновал еще древних греков. Они выяснили, что, если акустические частоты соотносятся как малые целые числа (например, 2 и 3), сочетание нот ласкает слух. Так был открыт первый музыкальный строй (по легенде, его создал Пифагор). Подбирая частоты для нот, важно выполнить главное требование: частоты нот, находящихся на противоположных концах октавы, должны соотноситься примерно как 2:1. Ради гармоничных звуков древние греки подбирали ноты так, чтобы парное соотношение частот до и фа, а также до и соль выражалось малыми целыми числами. В пифагорейском варианте соотношение между частотами соседних нот было равно 9/8 для целого тона (например, между до и ре) и 256/243 для полутона (например, между ми и фа).

Вот весь пифагоров строй:

Из этого соотношения можно посчитать соотношение, скажем, между частотами нот до и фа. Мы получим частоту фа, если умножим частоту до на

Акустические частоты, соотносящиеся как 4:3, прекрасно звучат вместе.

Мы можем визуализировать звуковые волны, возникающие, когда до и фа звучат вместе. Это будет выглядеть примерно так:

А частота ноты ля окажется немножко выше, звуковая волна будет выглядеть так:

Разница, заметная для глаза, заметна также и для слуха; вы видите диссонанс.

Недостаток пифагорова строя в том, что широко распространенное мажорное трезвучие до мажор – до-ми-соль – звучит как диссонанс; соотношение частот достаточно сложное.

Спустя много веков были найдены другие варианты. Например, так называемый чистый строй, или натуральный строй, выглядит так:

В этом варианте частоты до, ми и си прекрасным образом соотносятся как 4:5:6. Но полный тон от до до ре звучит иначе, чем другой полный тон от ре до ми.

И у пифагорова строя, и у натурального строя есть еще один серьезный изъян: если ансамбль исполняет произведение в тональности, скажем, до мажор, а затем музыканты должны переключиться на тональность фа, инструменты придется перенастраивать. Это довольно затруднительно для лютниста, невероятно сложно для клавикордиста и совершенно нереально для тех, кто играет на деревянных духовых.

Исправить изъян можно, если создать музыкальный строй, действующий одинаково хорошо во всех тональностях. Это накладывает два условия:

1. Частоты нот на противоположных концах октавы должны соотноситься как 2:1;

2. Если ноты отделены полутоном, соотношение их частот должно быть таким же, как у остальных полутонов октавы (например, соотношение частот до и ми-диез равно соотношению частот до-диез и ре). Всего в октаве двенадцать полутонов: до, до-диез, ре, ми, ми-диез, фа, фа-диез, соль, соль-диез, ля, ля-диез и си.

Если соотношение частот любых двух соседних нот равно r (условие 2), а соотношение частот двенадцатой и первой ноты равно 2 (условие 1), то r12 = 2. Следовательно,

Если настроить музыкальные инструменты таким образом, чтобы соотношение частот соседних нот в октаве было равно не придется перенастраиваться при переходе в другую тональность. Этот музыкальный строй называют равномерно темперированным, и сегодня им пользуются все профессиональные музыканты.

К сожалению, число иррационально. Иными словами, соотношение частот двенадцати нот в равномерно темперированном строе (за исключением начала и конца октавы) не может быть выражено через соотношение целых чисел. Соотношение частот до и соль в таком случае равно не 3:2, а примерно 1,4983 (число принято округлять до 1,5).

Как это звучит? Сейчас почти все музыкальные инструменты настраивают по равномерно темперированному строю, и они ласкают наш слух. Но что мы теряем?

Вот как выглядит звуковая волна для трезвучия до мажор. В первом варианте частоты нот соотносятся как 4:5:6, во втором подобраны в соответствии с равномерно темперированным строем. Первый вариант выглядит (и звучит!) гораздо гармоничнее.

Преимущество равномерно темперированного строя состоит в том, что в нем нет необходимости постоянно перенастраивать музыкальные инструменты. Но есть один инструмент, способный менять тональность мгновенно: человеческий голос.

Вокальные ансамбли без инструментального сопровождения (например, «парикмахерские» квартеты) не нуждаются в равномерно темперированном строе и берут ноты, соотношение частот которых можно выразить целыми числами. И мы слышим чудесные хорошо резонирующие звуки.

 

Глава 5

i

Еще одна головоломка квадратного корня

В главе 4 мы поразмышляли над «точным» значением числа √2 и пришли к выводу, что его нельзя выразить в виде соотношения двух целых чисел и, следовательно, оно иррационально. Тем не менее мы можем найти его значение с невероятной точностью.

Число √2 не относится к рациональным числам, однако нас не мучает вопрос, существует ли такое число, что x² = 2. Несмотря ни на что, √2 имеет законную прописку где-то между 1,41 и 1,42. Это пример действительного числа. Оно может быть выражено так:

± XXXX, XXXXXXXXXX …

Символом X помечены разные цифры. Число может быть положительным или отрицательным (знак + перед числом ставить не принято), количество цифр до запятой конечно, количество цифр после запятой бесконечно. Скажем, 1⅔ можно записать так:

1,666666666666…

Такие числа, как 3/4, в десятичной системе счисления записываются с конечным числом цифр после запятой (0,75), но ничто не мешает прикрутить справа бесконечное количество нулей: 0,7500000000…

Таким образом,  – реальное число, просто иррациональное. Точнее говоря, существует такое число, что x² = 2. Точно так же существует такое число, что x² = 3, а именно И так далее… Или нет?

Всякое ли уравнение x² = a имеет решение? Если a – положительное действительное число (или ноль), тогда решение равно и ответ можно записать в виде десятичного числа сколько угодно точно. Если мы изобразим график y = x² – a (для любого квадратного уравнения он представляет собой параболу), решением будут те точки, где кривая пересекает ось абсцисс, или ось x. Иными словами, это такие значения x, при которых x² = a. На первом рисунке вы можете видеть графики y = x² – 3 и y = x² – 7. Первая парабола пересекает ось абсцисс при вторая парабола – при

Вопрос кардинально меняется, когда мы ищем такое число, что x² = –1. А существует ли оно в принципе? Если возвести в квадрат положительное число, ответом будет положительное число, скажем 5² = 5 × 5 = 25 > 0. Если возвести в квадрат отрицательное число, результат снова будет положительным числом: (–5)² = (–5) × (–5) = 25 > 0. Если возвести в квадрат ноль, получится ноль. Наше положение выглядит безнадежно.

Мы испытаем еще большее отчаянье, когда нарисуем график уравнения y = x² + 1 и увидим, что парабола нигде не пересекает ось абсцисс.

Есть искушение сдаться и объявить: «Нельзя извлекать квадратные корни из отрицательных чисел». На самом деле нам просто не хватает воображения. Да, не существует ни одного действительного числа, удовлетворяющего условию x² = –1, но, возможно, есть какие-то другие?

Мнимые числа

Решение на редкость просто. Раз нет такого действительного числа, что x² = –1, то мы просто создадим новое число, назовем его i и поставим условие i² = –1.

Конечно, в голове сразу зазвучит сигнал тревоги: «Откуда взялось это число? Выдумывать числа нельзя! Что за чепуха!»

Чтобы облегчить душу, назовем новое число мнимым. В наших глазах такое число – второго сорта: мы не кладем i кубиков сахара в чашку кофе и не боимся, что расстояние до университета окажется равным i миль.

Мы просто решили поиграть и сами придумали правила. Хорошо, теперь давайте поразмышляем. Посмотрим, на что годно это число i. Мы знаем, что i × i = –1. А как насчет i + i? Если следовать привычным арифметическим правилам, то получится другое мнимое число: 2i. А что, если возвести это число в квадрат? Попробуем!

(2 i ) ² = (2 i ) × (2 i ) = 2 × i × 2 × i = 2 × 2 × i × i = 4 × ( i × i ) = 4 × (–1) = –4.

Другими словами, число 2i представляет собой квадратный корень из числа –4.

Теперь возведем в квадрат и посмотрим, что получится:

Таким образом, представляет собой квадратный корень из числа –2. Когда мы приютили мнимое число i в семье всех чисел, мы заполучили не просто а в придачу еще и квадратные корни из всех отрицательных действительных чисел! Любое число вида b × i, где b – это действительное число, называют мнимым числом.

Если сложить два мнимых числа, например 2i и 4i, мы получим другое мнимое число: 6i. Если мы перемножим два мнимых числа, например 3i и –2i, то получим действительное число:

3 i × (–2 i ) = 3 × (–2) × i × i = (–6) × (–1) = 6.

Комплексные числа

Чтобы мнимые числа прижились в семье всех чисел, нужно научиться складывать, вычитать, умножать и делить мнимые и действительные числа вместе. Мы будем работать с множеством комплексных чисел. Это расширение множества действительных чисел, включающее все числа вида a + bi, где a и b – действительные числа, например 3 + 4i.

Само число i комплексное, потому что может быть представлено в виде 0 + 1i. Точно так же действительные числа могут быть представлены в виде –7 + 0i.

Складывать комплексные числа несложно, мы просто приводим подобные слагаемые:

(3 + 2 i ) + (4 – 3 i ) = (3 + 4) + (2 – 3) i = 7 – i .

Более педантично мы можем записать это так: 7 + (–1) i.

Вычитание ничуть не сложнее:

(3 + 2 i ) – (4 – 3 i ) = (3 – 4) + (2 – (–3)) i = –1 + 5 i .

Очевидно, что сумма или разность двух комплексных чисел – тоже комплексное число. На языке алгебры мы можем продублировать эту фразу так (числа a, b, c, d здесь – действительные):

( a + bi ) + ( c + di ) = ( a + c ) + ( b + d ) i ;

( a + bi ) – ( c + di ) = ( a – c ) + ( b – d ) i .

Умножение комплексных чисел дается несколько труднее. Попробуем перемножить наших друзей 3 + 2i и 4 – 3i:

(3 + 2 i ) × (4 – 3 i ) = 3 × (4 – 3 i ) + 2 i × (4 – 3 i ) = (3 × 4 – 3 × 3 i ) + (2 i × 4 – 2 i × 3 i ) = (12 – 9 i ) + (8 i + 6) = 18 – i .

На алгебраическом языке произведение двух комплексных чисел выражает формула:

( a + bi ) × ( c + di ) = ( ac – bd ) + ( ad + bc ) i .

Очевидно, что при перемножении двух комплексных чисел мы получаем комплексное число.

Из всех арифметических операций деление комплексных чисел сложнее всего. Оно приводит нас к выражению (a + bi) / (c + di), поэтому сначала нам придется поговорить о взаимно обратных числах. Число x называют взаимно обратным числу y, если xy = 1. Например, дробь 1/2 взаимно обратна числу 2.

Какое комплексное число взаимно обратно 1 + 2i? Нам нужно такое число a + bi, что (1 + 2i) × (a + bi) = 1. Докажем, что этому требованию удовлетворяет число

Общая формула для комплексного числа, обратного числу a + bi, выглядит следующим образом:

В этом легко убедиться: достаточно умножить (A) на a + bi, аккуратно произвести все необходимые арифметические действия – и получить в итоге единицу.

Заметим, что оба знаменателя в (A) равны a² + b². Если вдруг эта сумма окажется равной нулю, формула потеряет смысл, потому что деление на ноль запрещено. Но такое возможно лишь в том случае, если a = 0 и b = 0. Другими словами, все комплексные числа имеют взаимно обратные, кроме числа 0 + 0i. Это подтверждает ожидания: ноль – единственное действительное число, не имеющее взаимно обратного, и среди комплексных чисел дело обстоит так же. Но обратное по отношению к любому ненулевому комплексному числу – тоже комплексное число.

Расправившись со взаимно обратными числами, мы можем наконец перейти к делению. Деление числа X на число Y дает такой же результат, как умножение числа X на число, взаимно обратное Y. Следовательно, частное двух комплексных чисел (если делитель не равен нулю) – комплексное число.

Отсюда можно сделать вывод: основные арифметические действия – сложение, вычитание, умножение и деление – прекрасно справляются с комплексными числами. Мы можем проделать эти операции над парой любых комплексных чисел (исключение составляет деление на ноль) и получить комплексное число.

Сейчас мы снова попытаемся извлечь квадратный корень. Сперва именно эта задача загнала нас в тупик. Действительные числа, так сказать, неполноценны: из каких-то квадратный корень извлекается, а из каких-то – нет. И вот мы дополняем действительные числа мнимыми, придумав новое число Мы заново осваиваем арифметические операции, и система действительных чисел разрастается до системы комплексных чисел. Но как решить вопрос с квадратным корнем? Чему равен Нам что, опять нужно изобрести какое-то несуществующее число и создать монструозное множество «сверхкомплексных» чисел?

К счастью, множество комплексных чисел уже содержит все квадратные корни из комплексных чисел. Посмотрим, как извлечь корень из мнимой единицы, не создавая новых сущностей.

Нам нужно найти такое комплексное число a + bi, что (a + bi) ² = i. Начнем с перемножения (a + bi) и (a + bi):

( a + bi ) × ( a + bi ) = ( a ² – b ²) + (2 ab ) i .

Теперь нам нужно приравнять это выражение к i = 0 + 1 × i. В результате мы получим: a² – b² = 0 и 2ab = 1.

Первое условие тождественно тому, что a = b или a = –b.

Если a = b и 2ab = 1, то 2a² = 1.

Таким образом,

Так как a = b, мы нашли два квадратных корня из мнимой единицы:

Проверьте, так ли это, возведя оба ответа в квадрат.

Если a = –b, решение будет таким же.

Итак, затратив некоторые усилия, мы показали, что извлечение квадратного корня из комплексного числа дает комплексное число, поэтому придумывать новые числа для извлечения корней не нужно.

Основная теорема алгебры

А как насчет кубических корней? Кубический корень из числа c – это такое число x, что x³ = c. Вопрос: входит ли множество корней из комплексных чисел во множество комплексных чисел или нам нужно изобретать еще какие-нибудь новые числа?

Уравнение x³ = c может быть записано иначе: x³ – c = 0. Сформулируем вопрос в общем виде: всякое ли полиномиальное уравнение имеет решение среди комплексных чисел? Скажем, есть ли такое комплексное число x, что

3 x ⁵ + (2 – i ) x ⁴ + (4 + i ) x ³ + x  – 2 i = 0?

Принципиально важный факт в теории комплексных чисел состоит в том, что любое полиномиальное уравнение имеет комплексное решение! Об этом говорит основная теорема алгебры. На математическом языке данный тезис можно переформулировать так: поле комплексных чисел алгебраически замкнуто.

Вот как звучит это важнейшее утверждение в строгой форме.

Теорема (основная теорема алгебры). Пусть d – положительное целое число и c 0 , c 1 , c 2 , …, c d  – комплексные числа, причем c d ≠ 0. Тогда существует такое комплексное число z, что

c d z d + c d – 1 z d – 1 + … + c 2 z ² + c 1 z + c 0 = 0.

Поле действительных чисел незамкнуто, потому что среди действительных чисел не всегда можно найти решение полиномиального уравнения с действительными коэффициентами (например, среди действительных чисел нет такого числа a, что a × a + 1 = 0. Доказательство общей теоремы алгебры состоит в том, что решение приведенного выше полиномиального уравнение находят в общем виде.

 

Глава 6

π

Что такое π?

Число π завораживает человечество на протяжении многих поколений. Оно проникло в массовую культуру (например, стало названием фильма и маркой одеколона). Школьники отмечают День π и соревнуются, кто запомнит больше знаков числа π после запятой.

Пи – шестнадцатая буква греческого алфавита. В математике ею обозначают отношение длины окружности к ее диаметру. Длина окружности в π раз длиннее диаметра, или C = πd. Можно записать иначе: C = 2πr, где r – радиус окружности.

Площадь окружности можно вычислить по формуле S = πr².

С помощью числа π можно определить и площадь сферы – 4πr², а также объем шара –

Эти геометрические формулы не сообщают нам величину числа π. Начнем с того, что π больше 3. Нарисуем круг с радиусом 1, впишем в него равносторонний шестиугольник, а затем поделим его на равносторонние треугольники.

Очевидно, что стороны всех треугольников равны 1. Периметр шестиугольника равен 6. Длина окружности несколько больше, чем периметр шестиугольника. Таким образом, 2π > 6, следовательно, π > 3. На рисунке мы видим, что разница между периметрами двух фигур невелика. Значит, π немногим больше 3.

Дальше мы можем поступить наоборот – описать правильный шестиугольник вокруг окружности радиусом 1. Вновь поделим шестиугольник на шесть равных треугольников. Длина любой стороны каждого треугольника будет равна (вы с легкостью поймете, почему это так, применив теорему Пифагора, о которой идет речь в главе 14; объяснение вы найдете в конце главы).

Таким образом, периметр большого шестиугольника равен Периметр окружности немного меньше. Следовательно,

Дальше мы можем снова и снова вписывать в окружность и описывать вокруг нее правильные многоугольники со все бо́льшим количеством сторон. Когда мы дойдем до правильного 100-угольника, точность наших вычислений значительно повысится:

3,1410759… < π < 3,1426266…

В пределе, увеличивая число сторон вписанных и описанных правильных многоугольников до бесконечности, мы будем получать все более точное значение интересующего нас числа:

π = 3,141592653589793238462643383279502884…

Так чему же в точности равно число π? В главе 4 мы уже выяснили, что число иррационально, то есть не может быть выражено через отношение двух целых чисел. Так же обстоит дело и с числом π. Школьников часто просят запомнить, что но это лишь приблизительное значение.

Число π не так-то просто представить в виде ряда, но вот пара попыток:

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

Ни та ни другая формула на практике не используются. Когда мы доведем расчеты по формуле (A) до получится, что π ≈ 3,134. Когда мы доведем расчеты по формуле (B) до получится, что π ≈ 3,13159.

Число π можно вычислить быстрее и точнее с помощью гораздо более изощренных алгоритмов. Для науки и инженерного дела достаточно знать где-то 30 знаков после запятой. Исключительно ради забавы и спортивного интереса математики и программисты вычислили число π с точностью больше триллиона знаков после запятой.

Трансцендентность

Числа π и  – иррациональные, но мы можем сделать более сильное утверждение: число π – трансцендентно.

Рациональные числа выражаются через соотношение целых чисел; скажем, 5/2, – 2/3, 7/1. Иными словами, это решения уравнений вида ax + b = 0, где a и b – целые числа. Например, 5/2 – это решение уравнения 2x – 5 = 0.

Число не входит во множество рациональных чисел (см. главу 4) и не является решением линейного уравнения вида ax + b = 0, где a и b – целые числа. Зато оно является решением квадратного уравнения x² – 2 = 0.

А что насчет π? Оно иррационально и, конечно, тоже не является решением линейного уравнения с коэффициентами среди целых чисел. Может быть, оно является решением какого-нибудь квадратного уравнения с коэффициентами среди целых чисел: ax² + bx + c = 0? Придется вас разочаровать, это не так. А может, стоит повысить степень? Кубическое уравнение ax³ + bx² + cx + d = 0? Снова нет. Биквадратное? Уравнение пятой степени? Сотой? Миллионной?..

На самом деле число π не является решением полиномиального уравнения любой степени с целочисленными коэффициентами. Другими словами, нет такого уравнения

a n xⁿ + a n –1 xⁿ –1 + … + a 2 x ² + a 1 x + a 0 = 0

(где любое a k представляло бы собой целое число), куда можно было бы подставить π вместо x, чтобы все сошлось. Это и означает, что число π трансцендентное.

Взаимно простые числа

Странным образом число π встречается в областях математики, не имеющих ничего общего ни с кругами в частности, ни с геометрией в целом. Например, число π мистически входит в формулу Стирлинга для вычисления приблизительного значения факториалов (см. главу 10). А сейчас мы узнаем, как наше заветное число связано с важным свойством очередного вида целых чисел – взаимно простых.

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

Например, присмотримся к числам 15 и 28. У них следующие делители:

Таким образом, 15 и 28 взаимно простые.

С другой стороны, числа 21 и 35 не взаимно простые, потому что оба делятся на 7.

Сыграем в кости? Какова вероятность того, что очки, выпавшие на обоих кубиках, будут взаимно простыми?

С равной вероятностью любой из них может выпасть гранью с цифрой 1, 2, 3, 4, 5 или 6. Каким бы ни был результат на первому кубике, второй выпадет по-своему независимо от него. Там тоже 6 вариантов. Всего это дает 36 комбинаций:

Все эти варианты равновероятны. С помощью таблицы мы можем вычислить, скажем, вероятность того, что сумма чисел на гранях двух кубиков будет равна 7. Это произойдет в шести случаях: (1, 6), (2, 5), (3, 4), (4, 3), (5, 2) и (6, 1). Таким образом, вероятность такого события равна

Вернемся к нашему вопросу: какова вероятность того, что два числа, выпавшие на разных кубиках, – взаимно простые? Давайте нарисуем новую таблицу и поставим звездочку везде, где пары чисел взаимно простые, например 5 и 2 или 2 и 5, но не 4 и 6.

Мы видим, что нам подходит 23 варианта. Таким образом, вероятность равна

Теперь поиграем в двадцатигранные кости! Какова вероятность того, что они выпадут гранями со взаимно простыми числами? Нам придется построить таблицу побольше! В ней будет 20 строк, 20 столбцов и 400 клеток.

Если мы педантично пересчитаем все звездочки, то придем к выводу, что вероятность составляет

Поговорим про общий случай. Какова вероятность того, что два произвольных числа от 1 до N – взаимно простые? Здесь нам уже понадобится компьютер. Рассмотрим все комбинации – (1, 1), (1, 2), (1, 3) и т. д. до (N, N) – и посчитаем, как много пар взаимно простых чисел нам повстречается. Всего придется перебрать N² вариантов. У нас получатся такие результаты:

Чем дальше мы уходим в бесконечность, тем ближе вероятность к 0,6079. И откуда же взялось это число? Чудесным образом предел нашего ряда оказался равен:

Число π встречается не только в геометрии, оно вращается в разнообразных кругах!

 

Глава 7

e

Леонард Эйлер [68]

Когда твоим именем называют число, это ли не величайшая честь для математика? Швейцарец Леонард Эйлер жил в XVIII веке, и в главе 7 мы поговорим о числе Эйлера. Его обозначают буквой e.

Число Эйлера можно задать разными способами, но стандартным считается следующий:

Этот ряд уходит в бесконечность. Восклицательными знаками обозначен факториал. Для положительного целого числа n факториал считают по такой формуле:

n ! = n × ( n  – 1) × ( n  – 2) × ( n  – 3) × … × 2 × 1.

Например, 4! = 4 × 3 × 2 × 1 = 24. Факториал нуля равен 1. Вы можете узнать о факториале больше в главе 10.

Достаточно сделать всего несколько шагов по приведенному выше алгоритму, чтобы вычислить e c хорошей точностью. Когда мы дойдем до 1/10! сумма будет равна

Это довольно близко к более точному значению 2,718281828459045…

Число Эйлера повсеместно встречается в разных областях математики. Далее я покажу вам три совершенно разные задачи, для решения которых нужно e.

«Прибыльное» число

Банк выдает депозитный сертификат на десять лет. Когда этот срок истекает, вклад удваивается. Если ваш вклад составляет 1000 долларов, через десять лет вы получите 2000 долларов. Рост ваших инвестиций составляет 100 %. Не исключено, что для банка выгоднее выплачивать 10 % ежегодно, а не 100 % спустя десять лет.

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

Начнем с 1000 долларов. В конце года вы получите 100 долларов. Теперь у вас 1100 долларов. На следующий год ваша прибыль возрастет. Банк выдаст вам уже не 100 долларов, а 10 % от 1100, то есть 110 долларов. Теперь у вас 1210 долларов. На третий год банк выдаст 10 % от этой суммы. Посмотрим, какую прибыль вы будете получать год от года и насколько станет увеличиваться ваш вклад:

Вначале у вас было A долларов. В первый год прибыль составила 10 %. В конце года вы получили 1,1 × A. На второй год 1,1 × 1,1 × A. Несложно увидеть, что в конце десятого года у вас на руках окажется

Это близко к нашим недавним расчетам. Таким образом, новый депозитный сертификат оказывается существенно выгоднее – денег становится больше не в 2, а почти в 2,6 раза.

А что произойдет, если банк начнет выдавать прибыль раз в три месяца, а не ежегодно? Если за год выручка составляет 10 %, то за три месяца набегает 2,5 %. В первом квартале ваша доход составит 0,025 × 1000 = 25 долларов. Общая сумма будет равна 1,025 × 1000 = 1025 долларов. В конце второго квартала вы получите уже 0,025 × 1,025 = 25,63 доллара (если округлить до сотых). Теперь у вас 1,025 × 1025 = 1050,63 доллара.

Спустя N кварталов ваша 1000 долларов увеличивается следующим образом:

Подставим N = 40 (поскольку в 10 годах 40 раз по 3 месяца) и увидим, что депозитный сертификат принес 2685,06 доллара.

В первом случае деньги удвоились. Во втором сумма выросла в 2,59 раза. В третьем – в 2,69 раза. А что произойдет, если требовать прибыль ежемесячно, сохраняя условие, что деньги можно тут же снова класть на счет? А еще лучше – ежедневно?

В случае ежемесячных выплат вы станете получать 10/12 %. Если в начале месяца у вас на руках была сумма A, в конце месяца она вырастет:

Спустя N месяцев вы получите:

Если N = 120, ваша итоговая сумма составит 2707,04 доллара.

Число дней в високосном году больше, чем в обычном, но для упрощения вычислений давайте примем за данность, что длительность каждого года 365 дней. За день вы будете получать Спустя N дней общая сумма составит:

Если N = 3650, вы будете обладать суммой в 2717,91 доллара.

А что, если вам и этого мало? Что, если вы потребуете от банка платить вам ежечасно?.. ежеминутно?.. ежесекундно?

В году 31 556 926 секунд, так что спустя 10 лет у вас будет:

Это дает 2718,28 доллара.

Подытожим:

А зачем останавливаться на секундах? Пусть банк выплачивает вам деньги каждую миллисекунду или наносекунду. Впрочем, это не изменит общей суммы. Вы все равно получите те же 2718,28 доллара, потому что вынуждены округлять до центов.

В пределе вы достигнете непрерывных выплат. Если посчитать всю сумму в точности, банк должен будет отдать вам 1000 × e долларов!

Непрерывные выплаты – пример экспоненциального роста. Пусть A – начальное число (денег, микробов и т. д.). Оно вырастает со скоростью r на протяжении периода времени t. Если новое число вырастает с той же скоростью и этот рост непрерывный, то в конце мы получим:

Ae rt ,

где e – знакомое нам число Эйлера. В нашем примере A = 1000 (первоначальный вклад), r = 0,1 (процентная ставка), t = 10 (количество лет). В конце мы имеем 2718,28 доллара.

Процесс может быть и обратным, когда нечто непрерывно убывает. Тогда в конце мы получим Ae–rt .

Переполох со шляпами

В одном городе был театр. Его посетители на время представления сдавали шляпы в гардероб, а потом забирали обратно.

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

Сформулируем вопрос точнее. В театр пришло N зрителей. Они встают в очередь за шляпами. Сумасшедший гардеробщик выдает шляпы в произвольном порядке. Таким образом, шляпы могут быть выданы N! различными вариантами. Все они равновероятны. Это математическая формулировка выражения «в произвольном порядке».

Разберем случай N = 4. Укажем в таблице все варианты выдачи шляп и пометим стрелочкой те случаи, когда ни один из зрителей не получает свою шляпу.

В 9 случаях из 24 никто не получает свою шляпу. Таким образом, при N = 4 интересующая нас вероятность равна

Для N = 5 существует 5! = 120 различных вариантов вернуть шляпы. Из них 44 нам подходят: ни один человек не получит свою шляпу. Таким образом, вероятность будет равна В таблице вы можете видеть, как меняется вероятность по мере возрастания N.

Вероятность меняется и дальше, но на ничтожно малую величину.

Хорошенько подумав, мы можем вывести формулу зависимости вероятности того, что никто из N зрителей не получит свою шляпу, от числа N:

Например, при N = 4

Это согласуется с нашими предыдущими выкладками.

В пределе, когда N стремится к бесконечности, вероятность того, что никто не получит свою шляпу, равна

Этот ряд уходит в бесконечность. Обратите внимание, что эта формула похожа на формулу (A) для подсчета числа e. Сумма ряда (B) равна Мы снова встретили наше заветное число!

Уже при N = 10 сумма ряда будет равна

Это достаточно близко к следующему значению:

Среднее расстояние между двумя простыми числами

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

Какие простые числа можно найти между 1 и 20?

2, 3, 5, 7, 11, 13, 17, 19.

Промежутки (разности) между этими числами следующие:

1, 2, 2, 4, 2, 4, 2.

Следовательно, среднее расстояние между ними равно:

Теперь посчитаем, сколько простых чисел между 1 и 1000. Всего их 168: начиная с 2, 3 и 5 и заканчивая 983, 991 и 997. Среднее расстояние между соседними простыми числами в этом случае составит:

Знаменатель равен 167, так как простых чисел 168, а промежутков между ними на 1 меньше. Числитель можно посчитать довольно просто. Обратите внимание, что число 3 встречается дважды с разными знаками. Та же история с числом 5. Разумеется, это верно для всех чисел, кроме первого и последнего. Таким образом, нам достаточно вычесть 2 из 997. Получается, что среднее расстояние между простыми числами от 1 до 1000 равно

Это в два с лишним раза больше, чем в случае, когда мы брали числовой ряд от 1 до 20.

Введем обозначение agap(N) для среднего расстояния между простыми числами от 1 до N. Тогда наши предыдущие расчеты могут быть записаны в таком виде:

Вычислим среднее расстояние между простыми числами от 1 до N, когда N равно 100, 1000, 10 000 и так далее до 1 000 000 000. И округлим результат до тысячных:

Легко заметить: когда N становится больше в десять раз, agap(N) возрастает примерно на 2,3.

Мы можем проиллюстрировать эту закономерность на графике. Будем отмечать число N по оси абсцисс и agap(N) по оси ординат. Масштаб по оси ординат оставим обычным, а по оси абсцисс разница между делениями пусть постоянно возрастает в 10 раз (это называется логарифмическая шкала):

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

Если бы звездочки на графике в точности выстроились в линию, мы получили бы следующую формулу, включающую число Эйлера:

N = e a + 1 . (C)

Здесь а=agap(N) Скажем, если N = 1012, то agap(N) ≈ 26,59. Для выполнения (C) необходимо, чтобы a ≈ 26,63, и наш результат близок к этому числу.

Чудесная формула

Три главы были посвящены трем важным числам: π, i, e. Хотите верьте, хотите нет, но все они встречаются в одной формуле (которую вывел Эйлер):

e i π + 1 = 0.

Формула поражает невероятным изяществом и простотой, однако как можно возводить число в мнимую степень?!

Мы знаем, как возвести e в целую положительную степень. Например, e³ = e × e × e. Отрицательная степень – это произведение дробей: Дробные степени могут быть выражены через квадратные корни, кубические корни и т. д.: Можно посчитать даже такую жутковатую величину, как

Но eiπ не вписывается в эти стандарты. Нам нужен иной принцип.

Мы знаем, что e представляет собой сумму бесконечного ряда:

Для любого x значение e x будет:

Скажем, в случае x = –1 мы получим знакомый по казусу со шляпами ряд (B):

Чтобы узнать, чему равно e i π, подставим iπ вместо x:

Чему равны числители дробей в этой сумме?

( i π) ² = ( i π) × ( i π) = i ² × π² = – π².

( i π) ³ = i × i × i × π³ = –1 × i × π³ = –i π³.

( i π) ⁴ = i ⁴ × π⁴ = π⁴.

( i π) ⁵ = – i π⁵.

( i π) ⁶ = –π⁶.

( i π) ⁷ = – i π⁷.

( i π) ⁸ = π⁸.

Элементы ряда поочередно оказываются то действительными, то мнимыми. Сгруппируем эти две категории элементов:

Оказывается, что выражение между первыми двумя скобками представляет собой в точности cos(π), то есть –1, а выражение между вторыми скобками равно sin(π), то есть 0. Таким образом,

e i π = cos(π) + i sin(π) = –1 + 0 i = –1.

Теперь мы понимаем, как возникла чудесная формула Эйлера.

 

Глава 8

∞

«В бесконечность и дальше!» – таков был лозунг Базза Лайтера, бесстрашного космического рейнджера из мультфильма «История игрушек». Эта фраза вызывает смех, ибо абсурдна: куда уж дальше бесконечности? Если что-то бесконечно велико, то может ли существовать что-то большее? Такие вопросы кажутся безумными, и математики до поры до времени предпочитали их не задавать. Но в конце XIX века Георг Кантор набрался смелости и стал искать ответ. Интуиция подсказывает, что нет ничего больше бесконечности.

Оказывается, здесь интуиция нас подводит.

Множества

В математике все сложное объяснимо через простое. Если быть достаточно скрупулезным, то комплексные числа можно определить с помощью действительных, действительные – с помощью рациональных, рациональные – с помощью целых и т. д. Все здание математики покоится на фундаментальной концепции множества.

Множество – это просто набор объектов. Например, {1, 2, 5} – множество, состоящее из трех чисел. Оно совпадает с множеством {1, 5, 2}, потому что порядок чисел в данном случае не важен. Кроме того, объект либо входит, либо не входит во множество. Входить во множество два раза нельзя. Множество {1, 1, 2, 5} совпадает с множеством {1, 2, 5}, второе появление числа 1 избыточно.

Если элемент входит в некоторое множество, математики используют значок ∈. Например, выражение 2∈ {1, 2, 5} следует понимать так: «Число 2 входит во множество, состоящие из чисел 1, 2, 5». Перечеркнутый значок показывает, что элемент не входит во множество; например: 3∉ {1, 2, 5}.

Число элементов, входящих во множество A, мы обозначаем |A|. Например, |{1, 2, 5}| = 3. Число |A| называют мощностью множества A.

Мощность такого рода множеств, как {1, 2, 5}, конечна. Однако мощность множества ℤ (все целые числа) бесконечна, как и мощность множества ℝ (все действительные числа).

Как сравнить размеры двух множеств? Простейший способ – пересчитать их элементы. Например, и у множества {1, 2, 5}, и у множества {3, 8, 11} мощность равна 3, стало быть, они равновелики.

Другой способ установить, что мощность множеств совпадает, – построить взаимно однозначное соответствие между их элементами. Иными словами, нам не обязательно перебирать все элементы, достаточно ввести правило, по которому мы сопоставляем элемент из одного множества с каким-либо элементом из второго. Вот взаимно однозначное соответствие между множествами {1, 2, 5} и {3, 8, 11}:

1 ↔ 3,

2 ↔ 8,

5 ↔ 11.

Впрочем, когда элементов мало, поиски взаимно однозначного соответствия обременительны и не приносят большой пользы.

Разберем более запутанный пример. Представьте себе, что в некоторый клуб входит семь человек (для удобства будем называть их по номерам: 1, 2, 3, …, 7).

Клубу разрешили послать трех членов на ежегодную национальную конференцию. Есть много способов выбрать трех человек из семи. Пусть A – множество всех возможных групп по три человека:

A = {123, 124, 125, …, 567}.

Здесь мы под «123» подразумеваем, что на конференцию поедут члены клуба под номерами 1, 2 и 3.

На следующий год членов клуба оповещают, что они могут отправить на конференцию четырех человек. Пусть B – множество всех групп по четыре человека:

B = {1234, 1235, 1236, …, 4567}.

Итак, A – множество групп по три человека, B – множество групп по четыре человека.

Совпадают ли их мощности?

Если внимательно пересчитать все элементы, выяснится, что мощности этих множеств совпадают. Но выписывать все возможности одну за одной – нудная и не застрахованная от ошибок работа.

Гораздо проще показать, что эти множества равновелики, если найти взаимно однозначное соответствие между их элементами. В голову приходит следующая мысль. Допустим, члены клуба решают, что на вторую конференцию больше не поедут те, кто побывал там в первый год. Тогда каждую группу по три человека из первого множества можно сопоставить с другой группой по четыре человека из второго множества. Например, если 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, …}.

Введем обозначение ℤ+ для множества положительных целых чисел:

ℤ + = {1, 2, 3, 4, …}.

Совпадают ли мощности ℤ и ℤ+?

Есть искушение сказать, что ℤ содержит вдвое больше элементов, чем ℤ+ и потому «в два раза более бесконечно». Однако мощности данных множеств совпадают. Почему? Мы покажем это с помощью взаимно однозначного соответствия.

Составим два перечня. Первый будет включать все положительные целые числа, а второй – вообще все целые числа, и положительные, и отрицательные, но в необычном порядке. Сопоставляя числа в первом и втором перечне, мы выстроим взаимно однозначное соответствие. Это показано в таблице.

Таким образом, мощности ℤ и ℤ+ равны, что, в принципе, и неудивительно – ведь оба эти множества бесконечны.

Бесконечные множества разных мощностей

Выстроив взаимно однозначное соответствие между элементами двух множеств, мы показали, что мощности ℤ и ℤ+ совпадают, что они, так сказать, «одинаково бесконечны». Пришло время для вопроса поинтереснее: совпадают ли мощности ℤ+ и ℝ? Да, разумеется, оба бесконечны. Впрочем, лучше не утверждать наверняка, пока мы не выстроим взаимно однозначное соответствие между их элементами. Сейчас мы убедимся, что это невозможно.

Итак, мы должны сопоставить каждый элемент первого множества с элементом второго множества и убедиться, что каждый элемент второго множества сопоставлен с элементом первого. Как же доказать, что это невозможно? Мы покажем, что попытки выстроить все элементы ℤ+ и ℝ в пары обречены на провал, потому что кое-какие элементы ℝ окажутся пропущены. А теперь к делу!

Допустим, мы все-таки нашли взаимно однозначное соответствие между ℤ+ и ℝ. Тогда все элементы можно занести в таблицу такого рода:

Все целые положительные числа занесены в левую колонку, все (вроде бы) действительные числа занесены в правую колонку. Сейчас мы убедимся: как ни заполняй правую колонку, будут действительные числа, которые туда не попадут.

Но прежде нам придется отвлечься на одну досадную техническую проблему. Некоторые действительные числа в десятичной системе счисления записываются двумя способами. Например, число 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 ↔ Y k = x . Но мы все время будем сталкиваться с одной и той же проблемой. Какая цифра стоит в числе Y k на позиции k после запятой? Если тройка, то на соответствующей позиции в x обнаружится семерка; если не тройка, то на соответствующей позиции в x как раз тройка. Это выглядит так:

Эта проверка показывает, что x в правом столбце отсутствует. Мы, конечно, можем выстроить новую таблицу и поместить x на первую позицию. Но, если применить к новой таблице алгоритм с правилами (A) и (B), мы обнаружим, что в ней отсутствует некое число x'.

Вывод: всякая таблица будет ущербной! Таким образом, взаимно однозначное соответствие между ℤ+ и ℝ построить невозможно.

Мощности бесконечных множеств

Мы доказали, что мощности ℤ и ℤ+ совпадают. И дело тут не только в том, что оба множества бесконечно велики, а еще в том, что мы построили биекцию.

ℤ+ и ℝ тоже содержат бесконечное число элементов, но биекция между ними неосуществима. Так как любое целое положительное число – действительное, можно сказать, что ℝ «больше» ℤ+. Целых положительных чисел недостаточно, чтобы по одному сопоставить их со всеми действительными.

Мощность конечного множества – это число. Мощность множества A = {1, 3, 7, 9} равна четырем: |A| = 4. Но как зафиксировать мощность бесконечного множества? До выкладок Кантора математики довольствовались красивым символом ∞. Есть искушение написать: |ℤ+| = ∞ и |ℝ| = ∞, а затем сделать ошибочное заключение, что |ℤ+| = |ℝ|. Символ ∞ не передает всех особенностей, присущих мощностям бесконечных множеств.

Кантор решил исправить это и разработал новую систему чисел за пределами конечных. Такие числа называются трансфинитными и могут отразить мощность бесконечных множеств.

Мы выяснили, что ℤ+ – «наименьшее» бесконечное множество. Что это означает? Предположим, X – бесконечное множество. Между X и ℤ+ может быть биекция, а может и не быть. Но математики показали, что всегда есть взаимно однозначное соответствие между ℤ+ и некоторой частью множества X: либо ℤ+ и X равновелики, либо ℤ+ равновелико с частью множества X. Грубо говоря, либо ℤ+ и X имеют одинаковый размер, либо X больше.

Множества мощности ℤ+ называют счетными. Это самые маленькие бесконечные множества. Кантор ввел символ для обозначения их мощности: Мощности ℤ и ℤ+ совпадают, потому Так как ℝ обширнее, чем ℤ+, логичным будет записать: Величина обозначает мощность бесконечного множества, и это не обычное число. Его называют трансфинитным числом, причем  – наименьшее из трансфинитных чисел.

Мощности бесконечных множеств описывает целая вселенная трансфинитных чисел. Множества мощностью больше называют несчетными, и математики показали, что есть новый «уровень бесконечности», на ступень выше Мы можем доказать, что существует множество X, которое обладает двумя свойствами:

1.

2. Нет множеств с мощностью между |X| и

Таким множествам присвоили мощность Иначе говоря, и между этими двумя величинами нет других трансфинитных чисел.

Существует целая последовательность трансфинитных чисел. Она выглядит следующим образом: и т. д. Иерархия подразумевает, что есть трансфинитное число, превышающее любое אk . Наименьшее трансфинитное число, превышающее любое אk , мы обозначаем אω, и есть бесконечно много еще больших чисел!

Где в этой схеме находится ℝ? Мы выяснили, что Но можем ли мы определить мощность ℝ в точности? Сколько всего действительных чисел?

Тайна семьи множеств

Вообразите: вы переступаете порог великолепного сооружения. За огромными воротами – мраморная лестница, ведущая в дивные палаты. Но стоит вам открыть дверь в подвал, как картина резко переменится. Там вы обнаружите ржавые трубы, искрящую проводку, бьющий в глаза электрический свет и разбитый пол, а может, и скопища тараканов. Подвал ужасен, но здания наверху без него не было бы.

Это хорошая метафора для сооружения под названием «математика». Как мы уже говорили в начале главы, все объекты в математике (от чисел до кругов) можно определить через другие объекты, попроще. Рано или поздно мы дойдем до самого дна и обнаружим объект, через который объясняются все другие. Это и будет множество.

Мы определили множество как набор объектов, но не сказали, что такое набор (в общем-то, это просто другое слово вместо «множества»), и не задались вопросом, какого рода объекты мы собираем вместе (и даже не дали определение объекта). Как нам выпутаться из этой ситуации?

Вначале математики относились к ней довольно беззаботно. Говорили просто: есть такая штука – множество и есть свойство «быть элементом множества», которое обозначают символом, а раз так, то можно двигаться дальше. Но все это рано или поздно приводит к затруднениям.

Первое множество, приходящее нам в голову, – пустое множество. Там нет никаких элементов, и мы обозначаем его символом ∅. Мощность пустого множества равна нулю, и утверждение x ∈ ∅ ложно для любого x (потому что внутри ∅ ничего нет).

Дальше нам приходит в голову, что множества можно характеризовать через свойства их элементов. Например, множество четных чисел задают следующим образом:

Форма записи {x | свойства x} определяет множество всех объектов, обладающих указанными свойствами.

А дальше возникает уйма сложностей.

В начале XX века философ и математик Бертран Рассел размышлял о множестве A = {x | x – такое множество, что x ∉ x}.

Это множество всех множеств, чьими элементами не являются они сами. Например, пустое множество удовлетворяет условию: ∅ ∉ ∅, потому что пустое множество не содержит элементов. Таким образом, ∅ ∈ A.

Дальше Рассел задал роковой вопрос: входит ли множество A во множество A?

• Если ответ «да», то A∈A. Но тогда не выполняется условие попадания во множество A: оно не должно быть элементом самого себя.

• Если ответ «нет», то A∉A. Тогда выполняется условие попадания во множество A, и оно является элементом самого себя.

Если A∈A, то A∉A. Если A∉A, то A∈A. Но не может же такого быть, что A и входит, и не входит в A! Что-то пошло не так.

Одно из решений этого противоречия заключается в том, что множества A просто не существует. Нет его, и все тут.

После работ Рассела подход к теории множеств претерпел существенные изменения. Четкие, ясные, применимые на практике правила закрепили, как формировать множества и какие операции с ними можно совершать. Определение множества и ∈ входит в свод правил непрямым образом. Мы не объясняем, что́ это; мы просто описываем, как оно себя проявляет. Мы говорим, что есть такие вещи, как множества, у них есть определенные свойства, а еще есть правила, по которым мы с ними работаем. Эти правила не позволили парадоксу Рассела вздыбить свою безобразную голову, и противоречий больше не возникало.

Но вернемся к вопросу: сколько всего действительных чисел? Мы знаем, что мощность множества положительных целых чисел равна И мы знаем, что Следует ли из этого, что Иными словами, существуют ли множества, чья мощность больше, чем ℤ+, но меньше, чем ℝ? Кантор верил, что но не мог найти доказательство; свое предположение он назвал континуум-гипотезой. Многие ученые заинтересовались этим вопросом. В 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.

Подытожим. Мы обозначили F N количество способов заполнения рамки 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. И так далее. Мы обнаружили следующую взаимосвязь:

F n = F n – 1 + F n – 2 .

Еще несколько шагов – и мы найдем искомое число F10. Правильный ответ – в конце главы.

Числа Фибоначчи

Числа Фибоначчи – это последовательность:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Она выстраивается по таким правилам:

– первые два числа 1 и 1;

– каждое следующее число получаем сложением двух предыдущих.

Будем обозначать n-ный элемент последовательности F n , начиная с нуля:

F 0 = 1, F 1 = 1, F 2 = 2, F 3 = 3 , F 4 = 5, …

Очередной элемент мы вычисляем по формуле:

F n = F n – 1 + F n – 2 .

Как мы видим, задача об укладке квадратов и домино привела нас к последовательности чисел Фибоначчи.

Сумма чисел Фибоначчи

Попробуем сложить первые несколько чисел Фибоначчи. Что мы можем сказать о сумме F0 + F1 + … + F n для любого n? Давайте проделаем кое-какие вычисления и посмотрим, что получится.

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

Хочется верить, вы увидели, что результаты суммирования, если к ним приплюсовать по единице, тоже выстраиваются в последовательность чисел Фибоначчи. Например, сложение чисел от F0 до F5 дает:

F 0 + F 1 + F 2 + F 3 + F 4 + F 5 = 1 + 1 + 2 + 3 + 5 + 8 = 20 = F 7  – 1.

Сложение чисел от F0 до F6 дает 33, что на единицу меньше F8 = 34. Мы можем записать формулу для неотрицательных целых чисел n:

F 0 + F 1 + F 2 + … + F n = F n + 2 –1. (*)

Вероятно, лично вам достаточно будет увидеть, что формула (*) работает в дюжине случаев, чтобы вы поверили, что она верна, но математики жаждут доказательств. Мы рады представить вам два возможных доказательства того, что она верна для всех неотрицательных целых чисел n. Первое называется доказательством по индукции, второе – комбинаторным доказательством.

Доказательство по индукции

Формула (*) представляет собой бесконечно много формул в свернутом виде. Доказать, что (*) верно для конкретного значения n, скажем для n = 6, – простая арифметическая задача. Достаточно будет записать числа от F0 до F6 и сложить их:

F 0 + F 1 + … + F 6 = 1 + 1 + 2 + 3 + 5 + 8 + 13 = 33.

Несложно увидеть, что F8 = 34, поэтому формула действует.

Перейдем к F7. Не будем тратить время и складывать все числа: мы уже знаем сумму вплоть до F6. Таким образом,

( F 0 + F 1 + … + F 6 ) + F 7 = 33 + 21 = 54.

Как и раньше, все сходится: F9 = 55.

Если сейчас мы начнем проверять, работает ли формула для n = 8, наши силы окончательно иссякнут. Но все же посмотрим, что мы уже знаем и что хотим выяснить:

F 0 + F 1 + … + F 7 = F 9 –1. F 0 + F 1 + … + F 7 + F 8 =?

Воспользуемся предыдущим результатом:

( F 0 + F 1 + … + F 7 ) + F 8 = ( F 9 – 1) + F 8 .

Мы, конечно, можем вычислить (F9 – 1) + F8 арифметически. Но так мы устанем еще больше. В то же время мы знаем, что F8 + F9 = F10. Таким образом, нам не нужно ничего высчитывать или заглядывать в таблицу чисел Фибоначчи:

( F 0 + F 1 + … + F 7 ) + F 8 = ( F 9 –1) + F 8 = ( F 8 + F 9 ) – 1 = F 10 – 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.

Предположим, мы уже знаем, что

F 0 + F 1 + … + F k = F k + 2 – 1.

Мы ищем величину

F 0 + F 1 + … + F k + F k + 1 .

Мы уже знаем сумму чисел Фибоначчи вплоть до F k , поэтому у нас получается:

( F 0 + F 1 + … + F k ) + F k + 1 = ( F k + 2 –1) + F k + 1 .

Правая часть равна F k + 2 – 1 + F k + 1, и мы знаем, чему равна сумма следующих друг за другом чисел Фибоначчи:

F k + 2 –1 + F k + 1 = ( F k + 2 + F k + 1 ) – 1 = F k + 3 – 1

Подставим в наше равенство:

( F 0 + F 1 + … + F k ) + F k + 1 = F k + 3 – 1

Сейчас я объясню, что мы сделали. Если мы знаем, что (*) верно, когда мы суммируем числа вплоть до F k , тогда (*) должно быть верно, если мы приплюсуем F k + 1.

Подытожим:

• Формула (*) верна для n = 0.

• Если формула (*) верна для n, она верна и для n + 1.

Мы можем уверенно сказать, что (*) верно для любых значений n. Верно ли (*) для n = 4987? Это так, если выражение верно для n = 4986, что основано на верности выражения для n = 4985, и так далее до n = 0. Следовательно, формула (*) верна для всех возможных значений n.

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

Комбинаторное доказательство

А вот совершенно другое доказательство тождества (*). Основной подход тут – воспользоваться тем фактом, что число F n  – это количество способов облицевать прямоугольник 1 × n квадратами и костяшками домино.

Напомню, что нам нужно доказать:

F 0 + F 1 + F 2 + … + F n = F n + 2 – 1. (*)

Идея заключается в том, чтобы рассматривать обе части уравнения как решение задачи с облицовкой. Если мы докажем, что левая и правая часть – решение для одного и того же прямоугольника, они совпадут между собой. Эта техника носит название комбинаторного доказательства.

На какой вопрос по комбинаторике уравнение (*) дает два верных ответа? Эта головоломка похожа на те, что встречаются в шоу Jeopardy!, где участники должны формулировать вопрос, заранее зная правильный ответ.

Правая часть выглядит проще, поэтому начнем с нее. Ответ: F n + 2 – 1. Каков вопрос? Если бы ответ был равен просто F n + 2, мы с легкостью сформулировали бы вопрос: сколькими способами можно облицевать прямоугольник 1 × (n + 2) с помощью квадратов и костяшек домино?

Это почти то, что нужно, но ответ меньше на единицу. Попробуем мягко поменять вопрос и уменьшить ответ. Уберем один вариант облицовки и пересчитаем оставшиеся. Сложность состоит в том, чтобы найти один вариант, который кардинально отличается от остальных. Есть ли такой?

Каждый способ облицовки подразумевает использование квадратов и/или домино. Только квадраты задействованы в единственном варианте, в прочих есть хотя бы одна костяшка домино. Возьмем это за основу нового вопроса.

Вопрос: Сколько существует вариантов облицовки квадратами и костяшками домино прямоугольной рамки 1 × ( n + 2), включающих по меньшей мере одну костяшку домино?

Сейчас мы найдем два ответа на этот вопрос. Так как оба будут верны, между числами мы сможем уверенно поставить знак равенства.

Один из ответов мы уже обсуждали. Есть F n + 2 вариантов укладки. Только один из них подразумевает использование исключительно квадратов, без домино.

Таким образом, ответ № 1 на наш вопрос таков: F n + 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 равно

F 4 + F 3 + F 2 + F 1 + F 0 = 12.

Вывод:

F 0 + F 1 + F 2 + F 3 + F 4 = 12 = F 6  – 1.

Рассмотрим общий случай. Нам дана рамка длиной n + 2. Сколько есть вариантов ее заполнения, при которых первая костяшка домино находится на некой позиции k? В этом случае первые k – 1 позиций заняты квадратами. Таким образом, в общей сложности занята k + 1 позиция. Оставшиеся (n + 2) – (k + 1) = n – k + 1 можно заполнить любыми способами. Это дает F n – k + 1 вариантов. Построим диаграмму:

Если k меняется от 1 до n + 1, величина n – k + 1 меняется от 0 до n. Таким образом, количество вариантов заполнения нашей рамки с использованием хотя бы одной костяшки домино равно

F n + F n – 1 + … + F 1 + F 0 .

Если поставить слагаемые в обратном порядке, мы получим левую часть выражения (*). Таким образом, мы нашли второй ответ на поставленный вопрос:

F 0 + F 1 + … + F n .

Итак, у нас есть два ответа на вопрос. Величины, полученные с помощью двух выведенных нами формул, совпадают, и тождество (*) доказано.

Соотношение чисел Фибоначчи и золотое сечение

Сложение двух следующих друг за другом чисел Фибоначчи дает очередное число Фибоначчи. В этом разделе мы затронем вопрос поинтереснее: что будет, если мы поделим число Фибоначчи на предшествующее ему в ряду? Посчитаем соотношение Для возрастающих значений k. В таблице вы можете видеть соотношения от

Чем больше становятся числа Фибоначчи, тем ближе соотношение к константе, примерно равной 1,61803.

Это число – вы будете удивлены – достаточно известное, и если вы введете его в поисковую систему, вывалится уйма страниц о золотом сечении. Что это такое?

Соотношение соседних чисел Фибоначчи не одинаково. Однако оно почти одинаково, если числа достаточно велики. Давайте найдем формулу для числа 1,61803 и для этого на время будем считать, что все соотношения одинаковы. Введем обозначение x:

Это значит, что F k + 1 = xF k , F k + 2 = xF k + 1 и т. д. Можно переформулировать:

F k + 2 = xF k + 1 = x ² F k .

Но мы же знаем, что F k + 2 = F k + 1 + F k . Таким образом,

x ² F k = xF k + F k .

Если мы поделим обе части на F k и перегруппируем слагаемые, то получим квадратное уравнение:

x ² – x  – 1 = 0.

Оно имеет два решения:

Соотношение должно быть положительным. И вот мы получили знакомое нам число. Обычно для обозначения золотого сечения используют греческую букву ϕ (фи):

Мы уже приметили, что соотношение соседних чисел Фибоначчи приближается (стремится) к ϕ. Это замечательно. Это дает нам еще один способ вычислять приблизительные значения чисел Фибоначчи.

Последовательность чисел Фибоначчи – это ряд F0, F1, F2, F3, F4, F5… Если все соотношения будут одинаковы, мы получим формулу:

F n = c ϕ ⁿ .

Здесь с – еще одна константа. Сравним округленные значения F n и ϕⁿ для разных n:

Для больших значений n соотношение Это число равно в точности Другими словами,

Насколько хороша эта формула? Настало время новых подсчетов!

Обратите внимание: если округлить до ближайшего целого числа, мы получим в точности F n .

Если вы не хотите утруждать себя округлениями до целого числа, то формула, названная в честь Жака Бине, даст вам точное значение:

 

Глава 10

Факториал!

Книги на полке

Сколькими способами можно расставить ваши книги на полке? Разумеется, это зависит от того, сколько у вас книг. Начнем с простейшего примера. Допустим, ваша библиотека насчитывает всего три книги с незамысловатыми названиями A, B и C.

Вначале решим, какую книгу поставить с левого края. Пусть это будет A. В таком случае остается всего два варианта расположения книг на полке: ABC и ACB. То есть, когда A стоит слева, существует две комбинации.

Если поставить на левую позицию книгу B, тогда снова возможны два варианта: BAC и BCA. Если слева стоит книга C, появляются еще две комбинации: CAB и CBA.

В общей сложности есть шесть вариантов расстановки книг:

ABC, ACB, BAC, BCA, CAB, CBA.

Теперь представим, что у нас появилась четвертая книга: D. Сколькими способами можно расставить книги теперь? Используем тот же метод. Для начала решим, какую книгу поставить слева; пусть на первый раз снова будет A. Оставшиеся три книги, как мы знаем, можно расставить шестью способами – только что мы обосновали, почему это так.

Точно так же есть шесть способов расположить оставшиеся книги, если слева будет B, C или D. В общей сложности получается 6 × 4 = 24 способа. Вот они:

Прежде чем мы перейдем к вопросу о произвольном количестве книг, давайте проанализируем вариант с пятью книгами: A, B, C, D и E. Как и раньше, вначале решаем, какую книгу поставить на крайнюю левую позицию. Если это A, у нас остается четыре книги. Сколькими способами можно их расставить? Мы уже выяснили, что таких способов 24. Еще 24 способа появляется, если на крайней левой позиции стоит B. То же самое для C, D и E. Итого в совокупности 24 + 24 + 24 + 24 + 24 = 120.

Каков был наш путь решения проблемы пяти книг? Есть пять вариантов, какую книгу поставить на крайнюю левую позицию. Когда она уже там, остаются четыре книги. Таким образом, количество вариантов для пяти книг в пять раз больше, чем количество вариантов для четырех. Давайте запишем это на математическом языке.

Пусть A5 – количество вариантов расстановки пяти книг. Мы получаем формулу:

A 5 = 5 × A 4 .

Здесь A4, как вы догадались, – количество вариантов для четырех книг.

Как найти A4? Да точно так же! Слева может быть одна из четырех книг; в каждом случае останется три книги и соответствующее количество вариантов их взаиморасположения. Мы получаем:

A 4 = 4 × A 3 .

Соответственно, A3 = 3 × A2. Количество вариантов для двух книг (куда уж проще) составляет A2 = 2 × A1, где, разумеется, A1 = 1.

И что же мы имеем?

A 5 = 5 × A 4 = 5 × 4 × A 3 = 5 × 4 × 3 × A 2 = 5 × 4 × 3 × 2 × A 1 = 5 × 4 × 3 × 2 × 1 = 120.

Теперь все ясно и с общим случаем. Количество способов расставить N книг на полке:

N × ( N  – 1) × ( N  – 2) × … × 3 × 2 × 1. (A)

Выражение (A) носит название N факториал. Факториал обозначают восклицательным знаком: N!. Например, 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720.

А есть ли формула?

Если мы задались целью вычислить значение 10! самый простой путь – перемножить числа от 1 до 10 и получить:

10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 3 628 800.

Но для подсчета 20! придется перемножать двадцать чисел. А вычислять 100! таким манером – просто каторжный труд. Есть ли какой-нибудь быстрый способ?

Красивая, но никуда не годная с точки зрения реальных вычислений идея состоит в том, чтобы определить 10! через 9!. Это же «проще простого»:

10! = 10 × (9 × 8 × … × 3 × 2 × 1) = 10 × 9!.

Для произвольного значения N мы имеем:

N ! = N × [( N  – 1) × ( N  – 2) × … × 3 × 2 × 1].

Иными словами,

N ! = N × ( N  – 1)!. (B)

Формула (B) чудесна, но она мало помогает при вычислении, скажем, 20!. Мы должны вычислить 19! и умножить его на 20. Само собой, она подсказывает, как вычислить 19!: для этого надо посчитать 18!. А затем умножить на 19. В конце концов нам придется перемножать все целые числа от 1 до 20.

Вот бы найти способ побыстрее… Есть ли основания предполагать, что мы можем ускорить вычисления? Да, и про это нам говорят треугольные числа – суммы вида:

1 + 2 + 3 + … + N .

Например, пятое треугольное число равно 1 + 2 + 3 + 4 + 5 = 15. Обозначим T N треугольное число, представляющее собой сумму N элементов:

T N = N + ( N  – 1) + ( N  – 2) + … + 3 + 2 + 1.

Например:

T 10 = 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 55.

Это похоже на факториал, но со сложением вместо умножения. Есть ли способ посчитать T10, не складывая все десять чисел?

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

Если мы сложим все эти 20 чисел, результат будет равен удвоенному T10. Но мы не станем сразу суммировать числа по горизонтали. Для начала сложим их попарно по вертикали:

В нижней строке все элементы равны 11, потому ответ прост: 11 × 10 = 110. Теперь поделим этот результат пополам: T10 = 110 / 2 = 55.

Как мы будем действовать в общем случае? Для вычисления T N запишем целые числа от 1 до N в возрастающем и убывающем порядке и сложим пару в каждом столбце:

В нижней строке N элементов, каждый равен N + 1; таким образом, их сумма равна N × (N + 1). Поскольку это «двойная порция» T N , получается:

Для вычисления T100 нет необходимости складывать сотню чисел. Нужно лишь посчитать:

(100 × 101) / 2 = 5050.

Вот и ответ.

Существует ли простая, элегантная формула вычисления факториала? Увы, нет. Однако есть формула для вычисления приближенного значения факториала, выведенная Джеймсом Стирлингом:

Эта формула включает два замечательных числа, о которых шла речь в предыдущих главах: π ≈ 3,14159, представляющее собой частное от деления длины окружности на ее радиус (см. главу 6), и число Эйлера e ≈ 2,71828 (см. главу 7).

Точность формулы Стирлинга возрастает при больших значениях N. Например, для N = 10 факториал 10! = 3 628 800, а вычисления по формуле (C) дают 3 598 695,6187. Погрешность – всего около 0,8 %.

Для N = 20 мы получаем:

20! = 2 432 902 008 176 640 000.

По формуле (C):

20! = 2 422 786 846 761 133 393,6839075390.

Погрешность равна около 0,4 %. Если мы перепрыгнем к N = 1000, погрешность составит менее 0,01 %.

Головоломка

Число 145 называют факторионом, потому что оно обладает волшебным свойством. Если мы сложим факториалы составляющих его цифр, то получим то же самое число:

1! + 4! + 5! = 1 + 24 + 120 = 145.

Числа 1 и 2 тоже являются факторионами (но не ноль, как мы увидим чуть позже). Существует всего четыре факториона. Попробуйте самостоятельно найти четвертый.

Это сложновато без компьютерной программы. Ответ приведен в конце главы.

Как вычислить 0!?

Многие испытывают необоримое желание ответить: «0! равен нулю!» (Второй восклицательный знак всего лишь подчеркивает экспрессивность этой фразы.) Первый множитель в N! равен N, а умножение на ноль дает ноль. Однако математики договорились, что 0! = 1, и я завершу главу разъяснением этого факта.

В главе 1 мы обсудили концепцию пустого произведения – умножения при отсутствии элементов. Факториал нуля – пример пустого произведения. Для любого N факториал представляет собой результат перемножения N элементов. Это ясно для положительных значений N, но это верно и для N = 0. По определению, при подсчете N! мы перемножаем все целые числа от 1 до N. В случае N = 0 таких чисел просто-напросто нет, и произведение оказывается пустым. По договоренности, пустое произведение равно 1.

А вот еще одно обоснование того, почему 0! = 1. При подстановке N = 1 в формулу (B) мы получаем:

N ! = N × ( N  – 1)! => 1! = 1 × 0!

Поскольку 1! = 1, мы получаем 0! = 1.

А теперь давайте вернемся к расстановке книг на полке. Сколькими способами можно расставить на полке ноль книг? Есть один-единственный вариант: оставить полку пустой.

 

Глава 11

Закон Бенфорда

Для нас очевидно, что все цифры сотворены равными. Нет, мы не имеем в виду «равными друг другу» – разумеется, нет! Но внутри нас теплится вера в то, что все десять цифр, от 0 до 9, играют одинаковые роли в мире чисел.

Печальная правда заключается в том, что числа могут быть такими же нескромными, как люди: они все стремятся к первенству. Представьте, что вам приглянулась вещь стоимостью 43,52 доллара. Какая из цифр кажется вам более значимой? Важнее всего для вас цифра четыре, а двойка на конце не играет почти никакой роли. Вы встревожитесь, если четверка вдруг изменится на девятку, а если изменится двойка, вряд ли вас это сильно взволнует.

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

Мы верим, что цифры от 1 до 9 участвуют в математике на равных правах и каждая начинает одну девятую часть всех существующих чисел (примерно 11 %). Разумеется, не может быть большего количества чисел, начинающихся с двойки, чем с пятерки.

Ведь так?

Дикорастущие величины

Утверждение о том, что все цифры от 1 до 9 равно представлены в качестве первой значащей цифры, приобретает смысл, если иметь в виду определенный диапазон чисел: скажем, от 1 до 999 999. В этом случае все цифры от 1 до 9 одинаково часто занимают место первой значащей цифры.

Разумеется, на результат влияет, какой именно диапазон мы выбрали. Если мы посмотрим на другой ряд чисел, скажем от 1 до 19, то обнаружим, что здесь все цифры от 2 до 9 занимают первую позицию всего единожды, в то время как 1 становится первой значащей цифрой в 11 случаях.

Ради беспристрастности давайте возьмем какие-нибудь величины из внешнего мира. Мы должны быть аккуратными и не искать числа, сконцентрированные в узком диапазоне. Поэтому мы не станем брать такой параметр, как рост взрослого человека, ведь практически все результаты измерений будут начинаться с 1 или 2 (ничтожно малое количество людей имеет рост выше 299 или ниже 100 сантиметров).

Ради уверенности в том, что все цифры имеют одинаковые шансы стать первой значащей цифрой числа, мы будем вести измерения в широком диапазоне. Например, давайте зададимся вопросом, насколько велико население разных стран. Это значение будет колебаться от миллиарда с лишним (Китай и Индия) до менее чем десяти тысяч (в случае с карликовым государством на коралловом острове Науру). Вдобавок к численности населения давайте выясним следующие параметры для сотен государств:

– валовой внутренний продукт (в долларах США);

– количество аэропортов;

– площадь (в квадратных километрах);

– ежегодную выработку электроэнергии (в киловатт-часах);

– ежегодное потребление продуктов нефтепереработки (в баррелях);

– общую длину всех железных дорог (в километрах);

– количество телефонов.

Таким образом, мы соберем около 2000 параметров и затем подсчитаем, сколько чисел начинается с цифры 1, сколько – с цифры 2 и т. д. Вот что у нас получится:

Невероятно: чаще всего на первой позиции встречается цифра 1 (примерно в 30 % случаев) и реже всего – цифра 9 (меньше 5 % случаев)!

Мы призываем читателей повторить эксперимент самостоятельно: взять статистический справочник, выписать первые цифры длин рек, высот гор, курсов акций, среднего роста различных видов животных, количества слов в романах, производства риса в разных странах и т. д.

Соберите как можно больше параметров, покрывающих широкий диапазон значений, и вы увидите все ту же логику. Чаще всего первой цифрой оказывается единица, реже всего – девятка.

Такое неравномерное распределение первых значащих цифр известно как закон Бенфорда, названный в честь Фрэнка Бенфорда. Он опубликовал статью об этом феномене в 1938 году, хотя необходимо отметить, что еще в 1881 году к такому же выводу пришел Саймон Ньюком.

Закон Бенфорда утверждает нечто большее, чем «единица на первой значащей позиции встречается чаще всего, а девятка – реже всего». Закон Бенфорда констатирует (при наличии большого количества данных) следующую частотность:

Таблицы умножения

Есть и другая область, где обнаруживается неравномерное распределение первых значащих цифр, – это знакомая всем таблица умножения:

Среди 81 числа в этой таблице 18 начинаются на 1, а именно:

При этом всего 3 числа начинаются на 9:

Вот процентное соотношение первых значащих цифр в обычной таблице умножения.

Мы видим, что цифры поменьше встречаются чаще, чем цифры побольше, но частотность здесь не совсем такая, какую предсказывает закон Бенфорда.

Таблица умножения дает нам все возможные результаты умножения одного однозначного числа на другое от 1 × 1 до 9 × 9.

Давайте расширим этот принцип и переберем все варианты умножения трех однозначных чисел. Проделаем следующие вычисления:

В общей сложности это дает 9³ = 729 троек. Посмотрим, как часто встречаются разные цифры в первой позиции:

Нет резона останавливаться на перемножении трех чисел. Мы можем составить четырехмерные, пятимерные, шестимерные таблицы умножения и т. д. Давайте сразу посмотрим, что получится с десятимерной таблицей умножения. Она содержит все возможные комбинации произведений десяти чисел от 1 до 9. Другими словами, мы проделываем следующие вычисления:

Занесем в таблицу, как много чисел начинается с 1, 2 и т. д.:

Мы увидим, что частотность первых цифр в этом случае уже хорошо согласуется с законом Бенфорда.

Поимка жулика

Перед тем как вникнуть в детали закона Бенфорда, давайте обратим внимание на одно его практическое применение.

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

Судебный эксперт может быстро проверить, совпадает ли распределение первых цифр с законом Бенфорда. Если не совпадает, возникают подозрения, что числа подделаны. Но это еще не строгое доказательство вины.

Экспоненциальное представление

Сверхбольшие и сверхмалые числа удобно записывать в экспоненциальном виде. Например, число 12 300 000 в экспоненциальном представлении выглядит так: 1,23 × 10⁷. Мы записываем число от 1 до 10, умноженное на степень 10. Основное число называется мантисса. Например, мантисса 853 100 000 равна 8,531:

По определению, мантисса не может быть меньше одного и не может быть больше или равна десяти: 1 ≤ мантисса < 10.

Мантисса поможет нам сформулировать усовершенствованный вариант закона Бенфорда. Грубо говоря, закон гласит, что среди большого количества измерений около 30 % чисел имеют первую значащую цифру 1, то есть имеют мантиссу меньше 2.

Уточняя закон Бенфорда, мы можем присмотреться к первым двум цифрам большого количества измерений и задаться вопросом: с какой частотой мантисса будет, скажем, меньше 1,7? Вот другая формулировка того же вопроса: с какой частотой первые две цифры будут 10, 11, 12, 13, 14, 15 и 16?

В более общем виде: для любого числа m между 1 и 10 мы обозначим f(m) долю чисел, чья мантисса меньше m.

Например, f(2) – доля чисел, начинающихся на цифру 1. Величина f(3) означает долю чисел с начальной цифрой 1 и 2. Такая запись поможет понять, как возрастают частоты в законе Бенфорда.

Как использовать такую форму записи для обозначения доли измерений с начальной цифрой, скажем, 4?

• Заметим, что запись f(4) не означает, что начальная цифра равна 4. Это может быть также 1, 2 или 3.

• Точно так же запись f(5) означает, что первые цифры могут быть 1, 2, 3, 4.

• Чтобы выяснить, сколько чисел начинается на цифру 4, вычтем одну величину из другой: f(5) – f(4). Тогда мы исключим числа с начальной цифрой 1, 2, 3.

Есть две особые величины: чему равно f(1) и f(10)? Подумайте минуту, прежде чем читать дальше.

Вспомним: f(m) обозначает долю чисел с мантиссой меньше m. В то же время 1 ≤ m < 10. Что из этого следует?

• Нет ни одного числа с мантиссой меньше 1. Таким образом, f(1) = 0.

• Мантиссы всех чисел меньше 10. Таким образом, f(10) = 1 (или, если вам угодно, 100 %).

Между этими границами величина f(m) возрастает. Чем больше чисел с мантиссой меньше m, тем больше f(m).

Следующий шаг – понять, как f(m) зависит от m. Но вначале мы рассмотрим общий случай перехода из одной единицы измерения в другую.

Ярды или футы [117] ?

Мы собрали тысячи измерений длин в километрах и увидели закон распределения первых цифр. Если мы переведем километры в мили, распределение не изменится. Измерения внутреннего валового продукта в долларах США дают примерно такую же частотность первых цифр. Ничего не изменится, если мы будем измерять ВВП в евро (или британских фунтах, или российских рублях). Но давайте присмотримся к переводу ярдов в футы.

Предположим, мы измеряем огромное количество расстояний в ярдах и в футах и изучаем распределение первых цифр. Как много величин имеют первую значащую цифру 2? Это множество включает и 2,1, и 28, и 0,213, и 299,8 ярда. В обозначениях, которые мы приняли в предыдущем разделе, доля величин такого рода по отношению ко всем измерениям равна f(3) – f(2).

А теперь переведем наши измерения в футы. Иными словами, просто умножим всё на 3. 2,1 ярда равны 6,3 фута. Измерения в ярдах с первой значащей цифрой 2 превратятся в измерения с первой значащей цифрой от 6 до 9, не включая 9. Вы удивлены?

Вначале может показаться, что, если первая значащая цифра величин в ярдах равна 2, первая значащая цифра величин в футах будет равна 6. Это не так: 2,8 ярда равны 8,4 фута. Если мантисса измерений в ярдах находится в пределах от 2 до 3 (не включая 3), мантисса тех же измерений в футах будет в пределах от 6 до 9 (не включая 9).

Какая доля измерений имеет первую значащую цифру 6, 7 или 8? Ответ: f(9) – f(6).

Близится кульминация: мы имеем дело с одними и теми же измерениями в разных единицах длины, поэтому доля измерений в ярдах с мантиссой 2 будет равна доле измерений в футах с мантиссой 6, 7 или 8. Иными словами, f(3) – f(2) в ярдах равно f(9) – f(6) в футах. Посмотрите на рисунок. Оба прямоугольника символизируют всю совокупность наших измерений: первый прямоугольник – в ярдах, второй прямоугольник – в футах. Серая область в первом прямоугольнике обозначает измерения с мантиссой 2. Соответствующая область во втором прямоугольнике обозначает измерения с мантиссой 6, 7 или 8.

Важно понимать, что обе закрашенные области идентичны! Так что доля измерений в ярдах с мантиссой 2 равна доле измерений в футах с мантиссой 6, 7 или 8.

Рассмотрим более общий случай. Вообразим, что мы собрали множество измерений и хотим выяснить, сколько из них имеют мантиссу меньше определенного числа a. Доля величин, удовлетворяющих этому условию, равна f(a).

Мы переводим результаты в другие единицы измерения. Пусть коэффициент будет равен числу b. Иными словами, если длина объекта в одних единицах измерения равна 23,5, в других она будет равна 23,5 × b.

Напомню, что f(a) равно доле величин с мантиссой от 1 до a, не включая a. Те же величины в других единицах имеют мантиссу строго меньше ab. Их доля равна f(ab).

На языке формул тезис о равенстве долей величин с мантиссой меньше a в одних единицах и с мантиссой меньше ab в других единицах выглядит так:

f ( a ) = f ( ab ) – f ( b ).

Или:

f ( ab ) = f ( a ) + f ( b ). (*)

Новый вопрос: какого рода функция удовлетворяет этому правилу и условиям f(1) = 0 и f(10) = 1?

Что дают логарифмы [122] ?

Некоторые математические операции можно проделать наоборот. Например, мы возводим в квадрат какое-нибудь число: 6² = 36. А теперь проделываем обратную операцию – извлекаем квадратный корень: Для положительных чисел операции возведения в квадрат и извлечения квадратного корня обратны друг другу. Операция, обратная возведению в степень, называется извлечением логарифма.

Например, 10⁴ = 10 000. Мы проделываем наоборот операцию возведения в степень и применяем логарифмическую функцию:

lg(10 000) = 4.

Можно воспринимать логарифмическую функцию как ответ на вопрос: «В какую степень возводить?» В какую степень нужно возвести 10, чтобы получить некое число? Скажем, какая степень 10 дает 1000? Поскольку 1000 = 10 × 10 × 10 = 10³, ответ равен 3. Иными словами, lg(1000) = 3.

Несложно уяснить, что происходит, когда мы возводим 10 в степень, равную целому положительному числу, – мы просто перемножаем 10 заданное число раз:

Если мы посчитаем нули в одной из степеней 10, то поймем значение логарифма:

lg(1 000 000 000) = 9.

Возведение 10 в дробную степень несколько сложнее. Ключевая идея здесь – понять, чему равно произведение 10m и 10ⁿ.

Чему равно произведение 10⁶ × 10⁵? Не бойтесь, перемножать десятки просто. Давайте распишем нашу формулу:

Каков результат? Нет нужды перемножать! Просто посчитайте, сколько раз встречается 10 в правой части формулы: одиннадцать. Иными словами,

10⁶ × 10⁵ = 10 11 .

Таким образом, для целых положительных степеней

10 m × 10 ⁿ = 10 m + ⁿ .

Это тождество называется законом умножения степеней.

Ключевая идея вычисления дробной степени – применение данного закона для любых показателей степени. Давайте посмотрим, к чему это приведет.

Возьмем 100,5. Мы можем не знать, чему оно равно, но нам известно, чему равно произведение 100,5 × 100,5. А именно:

10 0,5 × 10 0,5 = 10 0,5 + 0,5 = 10.

Если умножить 100,5 само на себя, получится 10. Таким образом, 100,5 равно квадратному корню из десяти:

Так мы можем посчитать все степени 10. На рисунке вы видите график функции 10х при x от 0 до 1.

При каком значении x выполняется условие 10х = 2? При взгляде на график функции 10х кажется, что подойдет x = 0,3. Если мы возьмем калькулятор, то выясним: 100,3 ≈ 1,99526… Близко, но не равно точно 2. Чуть-чуть увеличим степень. Попробуем x = 0,301; результат 100,301 ≈ 1,99986… Ближе, но все еще мимо цели. Нам нужно число немного больше. Величина x должна быть равна 0,30102999566398114… Это и будет log(2). (Вы уже встречали такое число раньше. Отыщите его!)

Закон умножения степеней 10m × 10ⁿ = 10m + ⁿ можно переформулировать для логарифмов. Посмотрим, как такое сделать. Допустим, a = 10m и b = 10ⁿ.

Чему равен десятичный логарифм a? Это степень, в которую нужно возвести 10, чтобы получить a. Иными словами, lg(a) = m. Аналогично lg(b) = n.

Чему равен логарифм произведения ab? Мы знаем, что a = 10m и b = 10ⁿ. Таким образом, ab = 10m + ⁿ. В какую степень нужно возвести 10, чтобы получить ab? Ответ: m + n. На языке математических символов это выглядит так: lg(ab) = m + n.

Подытожим:

lg( a ) = m,

lg( b ) = n,

lg( ab ) = m + n .

Отсюда мы выводим закон сложения для логарифмов:

lg( ab ) = lg( a ) + lg( b ). (**)

Похоже, мы уже встречали эту формулу…

Завязываем узелки

Давайте подытожим то, что мы узнали из предыдущих разделов. Мы определили функцию f(m) как долю тех величин среди большого количества измерений, мантисса которых меньше m. Эта функция удовлетворяет трем условиям:

f (1) = 0,

f (10) = 1,

f ( ab ) = f ( a ) + f ( b ).

Потом мы обсудили логарифмы и выяснили следующее:

lg(1) = 0,

lg(10) = 1,

lg( ab ) = lg( a ) + lg( b ).

Другими словами, значения f при 0 и 10 совпадает со значением десятичного логарифма от тех же величин. Кроме того, f и логарифм подчиняются одному и тому же правилу в соответствии с формулами (*) и (**). На основе этих фактов (и чисто технической оговорки, что функция f непрерывна) математики могут доказать, что f представляет собой логарифмическую функцию.

Теперь мы наконец готовы указать точную частотность первых значащих цифр при большом количестве измерений.

Какая доля измерений имеет первую значащую цифру 1? Сформулируем вопрос иначе: какая доля этих величин имеет мантиссу меньше 2? Ответ равен f(2) = lg(2) ≈ 0,3010 = 30,1 %.

Какая доля величин начинается с 9? Ответ равен f(10) – f(9), так как мы должны вычесть из общего количества величин те, первая значащая цифра которых меньше 9.

Это дает f(10) – f(9) = lg(10) – lg(9) ≈ 1 – 0,9542 = 0,0458 = 4,58 %.

Когда-то я задавал вопрос о значении f(1,7). Теперь можно уверенно ответить:

f (1,7) = lg(1,7) ≈ 0,23 = 23 %.

 

Глава 12

Алгоритм

Шеф-повара с фантазией редко руководствуются точными рецептами. Скорее, они следуют за вдохновением. А повара-новички покорно выполняют все указания поваренных книг.

Точно так же водителям с хорошей ориентацией на местности не нужны карты или детальные инструкции, как добраться до места назначения. А неопытным автомобилистам необходимы пошаговые указания.

В этом плане компьютеры похожи на новичков. Скажем, если нужно сложить несколько чисел, они скрупулезно выполняют операцию за операцией, руководствуясь инструкциями программистов. Эти инструкции называют алгоритмами. Компьютерные алгоритмы окружают нас повсюду: они высчитывают проценты для банков, определяют разрывы страниц в текстовых документах, превращают цифровые данные на DVD-диске в кино, предсказывают погоду, рыщут по интернету в поисках рецепта, включающего заданные ингредиенты, и дают советы, сверяясь со спутниками GPS, когда мы ищем дом с хитрым адресом.

Первый математический алгоритм, который изучает большинство людей, – как складывать числа. Когда нужно просуммировать в столбик 25 и 18, мы знаем: вначале нужно к 5 прибавить 8 (и запомнить результат: 13), записать 3 в колонке единиц, а 1 держать в уме. Затем сложить 2 и 1, увеличить результат на 1 и записать 4 в колонке десятков. Получится 43.

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

Сортировка

В конце каждого семестра у меня накапливается груда проверенных домашних заданий, которые необходимо вернуть студентам. Когда они заходят ко мне в кабинет за своими работами, у меня нет ни малейшего желания копаться в этой свалке, чтобы найти конкретную тетрадку. Конечно же, я сортирую все работы по алфавитному списку студентов. Прежде чем я объявлю, что проверенные тетради можно забирать, их необходимо систематизировать.

Итак, перед нами встает проблема: имеется стопка тетрадей, перемешанных в хаотичном порядке, необходимо разложить их по алфавиту. Как это сделать наилучшим образом?

Начнем с простой, но неэффективной идеи. Допустим, у меня учится 100 студентов. Я беру из стопки первую тетрадку и смотрю, должна ли она идти первой по алфавиту. Каким образом? Я сравниваю имена на всех тетрадках с именем на этой тетрадке. Если не повезло и тетрадка по алфавиту не первая, я кладу ее в самый низ стопки и начинаю сначала. Я стану действовать так, пока не обнаружу первую по алфавиту тетрадку. Тогда я переложу ее в новую стопку, где тетрадки будут лежать упорядоченным образом.

Дальше я вернусь к неупорядоченной стопке – сейчас там 99 тетрадей – и, как и раньше, начну искать первую по алфавиту тетрадку. Я возьму тетрадку сверху, сравню со всеми остальными и положу в самый низ стопки, если она не подойдет. Когда я найду искомую тетрадку, я положу ее во вторую стопку снизу.

Теперь у меня есть «всего-навсего» 98 тетрадей, и я повторяю все по новой: ищу первую по алфавиту тетрадь и кладу ее в низ второй стопки.

Сколько времени это займет?

Основная операция заключается в том, чтобы сравнить два имени и решить, какое следует первым по алфавиту. Мы будем оценивать эффективность алгоритма по количеству сравнений, которые необходимо провести. У меня 100 учащихся; как долго мне придется сопоставлять имена и решать, какое идет первым?

В неупорядоченной стопке из 100 тетрадей я сравниваю первую с 99 остальными. Необходимо проделать эту операцию со всеми 100 тетрадями (не исключено, что искомая лежит в самом конце). Поиск первой по алфавиту потребует максимум 100 × 99 = 9900 сопоставлений.

Я кладу свою находку во вторую стопку и повторяю процедуру с 99 неотсортированными тетрадями. Я сравниваю верхнюю тетрадь с 98 оставшимися. Поиск второй по алфавиту тетради потребует максимум 99 × 98 = 9702 сопоставления.

Третья тетрадь потребует максимум 98 × 97 сравнений, четвертая – максимум 97 × 96. Не исключено, что придется проделать 100 × 99 + 99 × 98 + 98 × 97 + … + 2 × 1 = 333 300 сравнений.

Мы проанализировали худший случай. На каждой итерации мы нашли максимум из возможного числа операций и посчитали, сколько их всего потребуется. Несомненно, такой результат настраивает нас на пессимистический лад и показывает, насколько неэффективным был наш алгоритм. Давайте попробуем что-нибудь другое.

Мы снова начинаем со стопки из 100 тетрадей, перемешанных случайным образом. Берем первые две тетради. Если они идут не в правильном порядке, меняем их местами (первая станет второй, вторая – первой). Если порядок верный, оставляем все без изменений. Дальше смотрим на вторую и третью тетрадь. Если порядок верный, идем дальше. Если нет, меняем их местами. Так мы действуем по этому алгоритму, пока не доберемся до конца стопки. Один заход требует 99 сравнений.

Когда мы дойдем до конца стопки, тетради с именами из начала алфавита сместятся вверх, а тетради с именами в конце алфавита сместятся вниз. Но одного захода может быть недостаточно. В худшем случае первая по алфавиту тетрадь изначально лежала в самом низу, и в первом заходе мы переместили ее всего-навсего на 99-ю позицию. В этом случае сортировка потребует 99 операций.

Таким образом, нам придется проделать максимум 99 × 99 = 9801 операцию. Это гораздо лучше первого метода, но все еще неэффективно. Если сравнение и смена позиции требует двух секунд, я закончу спустя пять часов. Это никуда не годится.

И вот я в расстроенных чувствах выхожу из кабинета, чтобы развеяться. В коридоре я встречаю двух постдоков, которые работают под моим научным руководством. Зловещая улыбка змеится на моих губах. Я спешу обратно в кабинет, делю стопку неотсортированных тетрадей пополам и даю по 50 тетрадей каждому постдоку. «Вот вам стопка тетрадей, – говорю я. – Пожалуйста, рассортируйте их по алфавиту и принесите ко мне в кабинет, когда закончите». После чего с воодушевлением возвращаюсь к основной работе.

Мне предстоит доделать сортировку, когда постдоки выполнят задание. Нужно превратить две упорядоченные стопки в одну. Насколько это будет трудно? Допустим, у меня есть две стопки тетрадей в алфавитном порядке. Я смотрю на верхние тетради в той и другой стопке, выбираю первую по алфавиту и кладу в итоговую стопку. Диаграмма иллюстрирует процесс.

Когда одна из стопок иссякает, я просто-напросто кладу оставшуюся в конец итоговой стопки. В худшем случае придется проделать 99 операций. Это потребует всего несколько минут!

Но как насчет моих постдоков? У каждого стопка с 50 тетрадями. Постдоки – люди смышленые, поэтому не станут сортировать тетради самостоятельно. Они, в свою очередь, поделят свои стопки пополам (таким образом, в каждой окажется по 25 тетрадей) и передоверят сортировку аспирантам! Когда те закончат, постдокам останется соединить две отсортированные стопки по 25 тетрадей в одну общую по 50. Это потребует максимум 49 операций.

Но четыре аспиранта тоже не дураки. Они делят свои стопки на две части (в одной 12, в другой 13 тетрадей) и находят восемь старшекурсников, чтобы передоверить работу. В результате каждому аспиранту остается соединить две маленькие стопки и отдать их постдокам.

Как старшекурсники сортируют тетради? Несложно догадаться: они делят свои стопки на две части (в одной 6 тетрадей, в другой 7), ловят 16 третьекурсников и отдают им эти стопки. Те находят 32 второкурсника и отдают им раздербаненные стопки (в одних по 3, в других по 4 тетради). Наконец, второкурсники отлавливают 64 первокурсника и отдают им стопки по 1 и по 2 тетради. Первокурсникам делать нечего: они быстро сортируют свою часть и отдают обратно.

Очевидно, эта «схема Понци» экономит мое время, но насколько она эффективна в целом? Посмотрим, как много операций она потребует в худшем случае. Занесем все данные в таблицу:

Максимальное количество операций оказывается существенно меньше, чем при сортировке пузырьковым методом.

К несчастью, в этой схеме есть изъян: у меня сейчас нет постдоков! Так что вместо вербовки целой армии помощников придется работать самому.

Для начала я найду большой незагроможденный стол. Я поделю стопку из 100 тетрадей пополам и положу две стопки по краям стола. Как я их отсортирую? По тому же алгоритму! Поделю две стопки по 50 тетрадей на четыре по 25, а их буду сортировать тем же методом. В худшем случае понадобится 645 операций. Правда, на сей раз мне придется действовать в одиночку. Однако это лучше, чем почти что 10 000 операций при сортировке пузырьковым методом.

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

Оскудение : результат оскудения [131] .

Что за чушь! Однако наш алгоритм сортировки и слияния грешит именно этой ссылкой на самого себя. Вот более точное определение.

Алгоритм сортировки и слияния

На входе: объекты a 1 , a 2 , a 3 , …, a n .

На выходе: те же объекты в отсортированном виде.

1. Если n = 1, сортировка закончена. Пускаем данные на выход. В противном случае переходим к пункту 2.

2. Поделить множество объектов на равные подмножества, если их количество четно, или на подмножества, отличающиеся на единицу, если количество нечетно. Использовать алгоритм сортировки и слияния.

3. Соединить подмножества [132] и пустить результат на выход.

Алгоритм, ссылающийся сам на себя, называют рекурсивным. В отличие от неудачного определения слова оскудение, наш алгоритм работает, потому что рано или поздно дойдет до конечной точки. Когда-нибудь множество объектов сведется к одному, и больше не придется проделывать процедуру заново. Поэтому нет опасности уйти в «бесконечный цикл».

Наибольший общий делитель

Каково наибольшее среди чисел, на которые нацело делятся одновременно 986 и 748? Простейший способ ответить на вопрос – перепробовать все варианты. Разумеется, 986 и 748 делятся на 1. Несложно видеть, что на 2 они тоже делятся. Но ни то ни другое число не делится на 3. Одно из них, 748, делится на 4, а другое нет. Нам «всего-навсего» нужно перебрать все делители и сравнить их. Мы остановимся после 748, потому что дальше числа не могут быть делителями 748. Наконец мы выясним, что у 748 и 986 четыре общих делителя: 1, 2, 17 и 34. Наибольший общий делитель 748 и 986 равен 34. Для любых положительных целых чисел a и b запись НОД (a, b) означает их наибольший общий делитель.

Описанный выше метод дает незамысловатый и неоспоримый алгоритм поиска наибольшего общего делителя. Его слабая сторона – неэффективность. Для поиска НОД двух трехзначных чисел придется перебрать сотни вариантов. Может быть, есть что-нибудь попроще?

Присмотримся к числам 986 и 748 повнимательней. Мы ищем наибольший общий делитель, поэтому естественно разложить оба числа на простые множители (см. главу 1). Вот результат:

986 = 2 × 17 × 29;

748 = 2 × 2 × 11 × 17.

С помощью этого разложения на простые множители мы можем найти НОД, пуская в дело все простые числа, на которые делятся оба наших числа. Оба делятся на 2 и на 17, потому наибольший общий делитель очевидным образом равен 2 × 17 = 34.

Как разложить число на простые множители самым эффективным способом? Ответ неутешителен: мы этого не знаем (как уже отмечалось в главе 1). Нам нужна идея получше.

Еще одну идею нам подсказал Евклид. Допустим, d – общий делитель 986 и 748. Это означает, что

986 = xd , 748 = yd ,

где x и y – целые числа. Следовательно, d также является делителем разности 986 – 748. Это следует из нехитрых алгебраических выкладок:

986 – 748 = xd – yd = ( x – y ) d .

Так как x и y целые числа, их разность тоже целое число. Потому разность 986 и 748 тоже нацело делится на d. Заметим, что 986–748 = 238.

Точно так же общий делитель 748 и 238 является делителем 986. Почему? Если e – общий делитель 748 и 238, то

748 = ue , 238 = ve ,

где u и v – целые числа. Таким образом,

986 = 748 + 238 = ue + ve = ( u + v ) e ,

откуда мы делаем заключение, что e – делитель 986.

Вывод: общие делители 986 и 748 являются также общими делителями 748 и 238. Для иллюстрации запишем делители всех трех чисел, подчеркивая общие делители:

делители 986 → 1, 2, 17, 29, 34, 58, 493, 986;

делители 748 → 1, 2, 4, 11, 17, 22, 34, 44, 68, 187, 374, 748;

делители 238 → 1, 2, 7, 14, 17, 34, 119, 238.

Отсюда следует, что

НОД (986, 748) = НОД (748, 238). (A)

Таким образом, поиск наибольшего общего делителя 986 и 748 свелся к поиску наибольшего общего делителя 748 и 238. Прогресс, теперь мы имеем дело с числами поменьше. Проделаем то же самое еще раз.

Если некое d – общий делитель 238 и 748, оно также делитель их разности. Этим дело не ограничивается. Мы можем вычесть 238 из 748 несколько раз, и d будет оставаться делителем разностей. Точнее говоря, если 238 и 748 делятся на d, разность 748 – 3 × 238 тоже делится на d. Обратимся к алгебре, чтобы доказать это.

748 = xd , 238 = yd ,

где x и y – целые числа. Следовательно,

748 – 3 × 238 = xd  – 3 yd = ( x  – 3 y ) d .

Таким образом, d – делитель 748 – 3 × 238 = 34. И наоборот: если e – делитель 34 и 238, это также делитель 748. Вернемся к алгебре.

238 = ue , 34 = ve ,

где u и v – целые числа. Таким образом,

748 = 3 × 238 + 34 = 3 ue + ve = (3 u + v ) e .

Таким образом, e – делитель 748. Следовательно, у 748, 238 и 34 есть общие делители, и мы можем сделать вывод, что

НОД (748, 238) = НОД (238, 34). (B)

На основе тождеств (A) и (B) мы имеем:

НОД (986, 748) = НОД (748, 238) = НОД (238, 34).

Мы почти у цели. Обратим внимание, что 238 делится на 34 (потому что 238 = 34 × 7), и поэтому НОД (238, 34) = 34. Финальный аккорд:

НОД (986, 748) = НОД (748, 238) = НОД (238, 34) = 34.

Подытожим: через какие этапы мы пришли к этому результату? Мы вычли 748 из 986 и получили 238. Мы трижды вычли 238 из 748. Почему мы совершили одну операцию вычитания в первом случае и три операции во втором? Мы хотели свести задачу к операциям с как можно меньшими числами, потому что так удобнее. Поэтому мы вычитали меньшее число из большего до упора. Заметим: 748 умещается в 986 всего один раз, и разница между ними равна 238. Однако 238 умещается внутри 748 три раза, и остаток равен 34. Мы можем вычесть 748 из 986 всего один раз, и в то же время мы можем вычесть 238 из 748 три раза.

Теперь мы обобщим этот пример и построим алгоритм вычисления наибольшего общего делителя для двух целых положительных чисел. Нам даны два целых положительных числа a, b, и мы хотим определить НОД (a, b). При этом a больше b. Мы должны вычесть b из a как можно большее число раз. Чтобы выяснить, сколько именно, поделим a на b. Мы получим частное q и остаток c. На языке алгебры:

a – qb = c .

Если окажется, что b – делитель a, тогда остаток будет равен нулю. В ином случае c больше нуля и меньше b (если бы c оказалось больше b, мы смогли бы вычесть b из a еще раз).

Теперь предположим, что d – общий делитель a и b. Тогда

a = xd, b = yd,

где x и y – целые числа. Следовательно,

c = a – qb = xd – q ( yd ) = ( x – qy ) d ,

и c тоже без остатка делится на d (потому что x – qy входит в множество целых чисел).

С другой стороны, если e – общий делитель b и c, тогда

b = ue, c = ve ,

где u и v – целые числа. Следовательно,

a = c + qb = ve + q ( ue ) = ( v + qu ) e ,

и e – еще и делитель a.

Итак, мы доказали, что общие делители a и b совпадают с общими делителями b и c. Таким образом,

НОД ( a, b ) = НОД ( b, c ). (C)

Посмотрим, как тождество (C) позволит нам эффективно вычислить наибольший общий делитель двух больших целых чисел: a = 10 693 и b = 2220.

Мы делим a на b и видим, что 2220 умещается в 10 693 четыре раза, при этом остаток c = 1813. Следовательно,

НОД (10 693, 2220) = НОД (2220, 1813).

Переходим к следующей итерации. Введем обозначения a' = 2220 и b' = 1813. Поделим a' на b' и увидим, что 1813 умещается в 2220 всего один раз и остаток c' = 407. На основании тождества (C)

НОД (10 693, 2220) = НОД (2220, 1813) = НОД (1813, 407).

На новом шаге a'' = 1813 и b'' = 407. После деления мы обнаружим, что 407 умещается внутри 1817 четыре раза и остаток c'' = 185. Опять-таки на основании (C)

НОД (10 693, 2220) = НОД (2220, 1813) = НОД (1813, 407) = НОД (407, 185).

На сей раз мы имеем дело с числами a''' = 407 и b''' = 185. Деление показывает, что 185 умещается внутри 407 два раза и остаток равен c''' = 37. Таким образом,

НОД (10 693, 2220) = НОД (2220, 1813) = НОД (1813, 407) = НОД (407, 185) = НОД (185, 37).

Мы почти у цели! Делим a'''' = 185 на b'''' = 37 и – подумать только! – получаем ровно 5. Следовательно, НОД (185, 37) = 37. Завершаем наши выкладки:

НОД (10 693, 2220) = НОД (2220, 1813) = НОД (1813, 407) = НОД (407, 185) = НОД (185, 37) = 37.

Мы нашли наибольший общий делитель 10693 и 2220, проделав всего пять операций деления!

Алгоритм Евклида для поиска наибольшего общего делителя можно сформулировать так:

Поиск НОД: алгоритм Евклида

На входе: два положительных целых числа a и b .

На выходе: НОД ( a, b ).

1. Найти частное q и остаток c при делении a на b .

2. Если c = 0, то НОД ( a, b ) = b .

3. В противном случае вычислить НОД ( b, c ) = НОД ( a, b ).

Проверьте, насколько хорошо вы усвоили алгоритм Евклида, и вычислите НОД (1309, 1105). Можете воспользоваться калькулятором. Сверьтесь с ответом в конце главы.

Наименьшее общее кратное

Концепция наибольшего общего делителя тесно связана с концепцией наименьшего общего кратного. Для двух положительных целых чисел (допустим, 10 и 15) наименьшее общее кратное – это самое маленькое положительное целое число, которое делится на то и на другое; в нашем случае ответ равен 30. Мы будем использовать обозначение НОК (a, b).

Наименьшее общее кратное полезно при сложении дробей. Например, для сложения 1/10 и 1/15 вначале нужно привести обе дроби к общему знаменателю. Это может быть любое число, которое делится на 10 и на 15; проще всего найти НОК. Так как НОК (10, 15) = 30, то

Найти наименьшее общее кратное для маленьких чисел не слишком сложно, но как быть с большими числами? Скажем, чему равно наименьшее общее кратное 364 и 286?

Один вариант состоит в том, чтобы последовательно выписывать числа, кратные первому и второму, и уповать, что рано или поздно они совпадут:

числа, кратные 364 → 364, 728, 1092, 1456, 1820, 2184, …

числа, кратные 286 → 286, 572, 858, 1144, 1430, 1716, 2002, …

Вскоре мы дойдем до 4004 и запишем ответ: НОК (364, 286) = 4004.

Вот еще одна идея. Разложим 364 и 286 на простые множители:

364 = 2 × 2 × 7 × 13;

286 = 2 × 11 × 13.

Числа, кратные 364, должны делиться на 2 × 2 × 7 × 13, а числа, кратные 286, должны делиться на 2 × 11 × 13. При конструировании наименьшего общего кратного мы должны воспользоваться этими простыми числами – два раза по 2, затем 7, 11 и 13 (нам ни к чему брать два раза по 13):

2 × 2 × 7 × 11 × 13 = 4004.

Разумеется, 4004 и есть наименьшее общее кратное 364 и 286.

Этот метод выглядит потрясающе, однако – как я уже объяснил в главе 1 – мы не знаем эффективного алгоритма разложения больших чисел на простые множители.

Хотя разложение на простые множители не дает достаточно эффективного алгоритма вычисления НОК двух чисел, оно делает важную подсказку. Давайте сравним, как используется разложение на множители при вычислении НОК и НОД.

Вот семь простых множителей двух чисел, взятые вместе:

Мы находим НОД (364, 286) с помощью двух общих простых делителей: 2 и 13.

Для вычисления НОК (364, 286) нам нужны все простые числа в двух списках, хотя нет нужды брать два раза по 13 (достаточно одного) и три раза по 2 (достаточно двух). Иными словами, мы берем каждое простое число из того списка, где оно встретилось большее число раз. Таким образом, нам нужны пять чисел: 2, 2, 7, 11 и 13.

Проверяем:

НОД (364, 286) = 26 = 2 × 13;

НОК (364, 286) = 4004 = 2 × 2 × 7 × 11 × 13.

Заметим, что при подсчете НОК мы выкинули именно те числа, которые нужны для вычисления НОД:

Иначе говоря,

364 × 286 = (2 × 2 × 7 × 13) × (2 × 11 × 13) = (2 × 2 × 7 × 11 × 13) × (2 × 13) = НОК (364, 286) × НОД (364, 286).

Мы можем обобщить этот пример. Для любых двух целых положительных чисел a и b

a × b = НОК ( a, b ) × НОД ( a, b ).

Таким образом,

Так как алгоритм Евклида позволяет эффективно вычислить наибольший общий делитель двух чисел, он также годится – с учетом тождества (D) – для эффективного вычисления наименьшего общего кратного.