структуры, что помогает сохранять сжатую программу, на основе которой можно восстанавливать воспоминания. Вот вам маленькая задачка. Посмотрите на заштрихованные клетки в показанной ниже таблице размером 6 × 6. Затем закройте книгу. Можете ли вы воспроизвести эту таблицу по памяти? Тут важно не пытаться запомнить каждую из 36 клеток изображения по отдельности, а найти паттерн, который поможет вам восстановить все изображение.
Рис. 1.3. Можете ли вы запомнить расположение заштрихованных клеток?
Хотя доля заштрихованных клеток на этом изображении приблизительно та же, что и доля черных клеток на шахматной доске размером 6 × 6, из-за отсутствия явного паттерна запомнить их расположение гораздо труднее. Чтобы получить это изображение, я подбрасывал монету и заштриховывал те клетки, для которых она выпадала орлом. С математической точки зрения вероятность получения рисунка, аналогичного шахматной доске, с регулярным чередованием орлов и решек, равна вероятности случайного расположения заштрихованных клеток. Однако рисунок шахматной доски намного легче запомнить.
Если вам удается выявить в изображении паттерн, вы можете записать инструкцию воспроизведения этого изображения. В математике такую инструкцию называют алгоритмом. Оценка размеров алгоритма, необходимого для запоминания изображения, дает довольно точную меру случайности этого изображения. Рисунок шахматной доски обладает высокой упорядоченностью. Алгоритм его воспроизведения занимает мало места. Для изображения, созданного путем подбрасывания монеты, вероятно, потребуется алгоритм не меньший, чем запись содержания каждой из 36 клеток таблицы по отдельности.
Можно заметить, что из фотографии, изображающей сцену с очевидным сюжетом, получается файл формата JPEG гораздо меньшего размера, чем исходное изображение, а картинка, состоящая из случайных пикселей, не становится меньше, если попытаться сжать ее алгоритмом JPEG: в ней нет паттернов, помогающих сжатию.
Кто бы и что бы, будь то человек или машина, ни запоминал что-либо, они прибегают к математической стороне своего разума. Запоминание требует обнаружения в данных, которые мы пытаемся сохранить, паттернов, связей, ассоциаций и логики. Паттерны – это шорткат к хорошей памяти.
Со ступеньки на ступеньку
Вернемся к вопросу, который я задал в начале этой главы. Сколько существует способов подняться на пролет из 10 ступенек, если использовать комбинации шагов на одну ступеньку (одинарных) и на две ступеньки (двойных)? К решению этой задачи можно подойти несколькими разными путями. Один из них – просто начать выписывать в случайном порядке разные варианты. При таком несистематическом подходе некоторые возможности наверняка будут пропущены, а чтобы записать их все, понадобится много времени. Нет ли стратегии получше?
Чуть более систематическим будет следующий подход. Начнем с одних лишь одинарных шагов. С ними решение только одно: 1111111111. Затем добавим к одинарным шагам один двойной. Тогда нужно сделать в общей сложности девять шагов – восемь одинарных и один двойной, причем каким по счету будет двойной шаг, можно выбирать. Этот двойной шаг можно сделать в девяти разных местах.
Эта стратегия кажется перспективной. На следующем этапе можно рассмотреть комбинации с двумя двойными шагами, перемешанными с шестью одинарными. В этом варианте подъем совершается за восемь шагов. Но придется вычислить, сколько существует вариантов выбора, то есть какой из восьми шагов будет двойным. Один двойной шаг можно сделать в восьми разных местах, а второй – в семи оставшихся после первого. Создается впечатление, что число возможных вариантов – 8 × 7. Но тут нужно действовать осторожно, потому что на самом деле мы учли одни и те же варианты дважды. Можно назначить первый двойной шаг на положение № 1, а второй – на положение № 2, а можно сделать наоборот. Результат от этого не изменится. Поэтому суммарное число возможных вариантов равно (8 × 7)/2 = 28. Собственно говоря, у этого числа есть особое математическое название. Оно называется числом сочетаний из 8 по 2 и обозначается следующим образом [20]:
В более общем случае число вариантов выбора двух чисел из N + 1 чисел вычисляется по формуле 1/2 N(N + 1) – той же самой формуле, которую Гаусс использовал для треугольных чисел. Снова то же самое колесо, которое мы уже изобрели! Задачу о выборе двух чисел из N + 1 действительно можно свести к задаче вычисления треугольных чисел. В главе 3 я покажу, каким прекрасным шорткатом к решению одной задачи часто может быть ее преобразование в другую.
Эти инструменты для вычисления количества вариантов выбора, называемые биномиальными коэффициентами, были и в числе тех формул, которые Гаусс и помощник его учителя Бартельс вместе разбирали в своих книгах по алгебре.
Но чтобы решить нашу головоломку, на следующем этапе нужно вычислить, какими способами можно выбрать три места для трех двойных шагов по лестнице из семи возможных. Хотя этот метод кажется разумным и систематическим, нам нужно будет придумывать все новые формулы для включения в подъем по лестнице все большего числа двойных шагов. Эта работа начинает казаться трудоемкой и медленной – совсем не такой, каким должен быть шорткат.
Поэтому я опишу более удобный способ, основанный на том, о чем я рассказывал в этой главе. Очень действенной стратегией для решения таких головоломок мне кажется следующая: нужно рассмотреть малое количество ступенек и выяснить, есть ли в получающихся для них числах какой-нибудь паттерн.
Вот все варианты для лестниц из 1, 2, 3, 4 и 5 ступенек, которые можно быстро перебрать вручную:
1 ступенька: 1.
2 ступеньки: 11 или 2.
3 ступеньки: 111 или 12 или 21.
4 ступеньки: 1111 или 112 или 121 или 211 или 22.
5 ступенек: 11111 или 1112 или 1121 или 1211 или 2111 или 122 или 212 или 221.
Последовательность количества вариантов выглядит так: 1, 2, 3, 5, 8… Возможно, вы уже заметили паттерн. Следующее число получается сложением двух предыдущих. Возможно, вы даже знаете, как называются эти числа. Это же числа Фибоначчи! Они названы в честь математика XII века, открывшего, что эти числа – ключ к
