Математическая эссенция

Арифметика Фибоначчи В обычной позиционной системе перенос устроен одинаково во всех разрядах: 10 единиц превращаются в 1 десяток. В фибоначчиевой системе единого основания нет: веса разрядов не являются степенями одного числа. Вместо степеней одного числа используются веса 1, 2, 3, 5, 8, 13, … а каноническая запись не содержит двух соседних чисел Фибоначчи. Поэтому и переносы здесь другие. Главное правило следует прямо из определения последовательности: Fₙ + Fₙ₊₁ = Fₙ₊₂. То есть два соседних веса можно заменить следующим: 3 + 5 = 8, 5 + 8 = 13 и так далее. Посмотрим, как сложить 7 = 5 + 2  и  4 = 3 + 1. Сначала просто складываем: 7 + 4 = 5 + 3 + 2 + 1. Но такая запись не каноническая: соседние числа Фибоначчи встречаются сразу несколько раз. Сначала 3 + 2 = 5, поэтому 5 + 3 + 2 + 1 = 5 + 5 + 1. Теперь возникли два одинаковых веса. Для них есть другое правило. Из соотношений Фибоначчи следует 2Fₙ = Fₙ₊₁ + Fₙ₋₂. Например, 5 + 5 = 8 + 2. Получаем 5 + 5 + 1 = 8 + 2 + 1. Но 2 + 1 = 3, поэтому окончательно 7 + 4 = 8 + 3 = 11. Это уже запись Цекендорфа: два использованных числа Фибоначчи не соседние. Получается необычная арифметика. Один тип переноса идёт к старшему разряду: 3 + 5 → 8, а при появлении двух одинаковых весов перенос может одновременно затронуть разряды по обе стороны: 5 + 5 → 8 + 2. Поэтому сложение здесь — это не просто движение переносов справа налево, как в десятичной системе. Сначала коэффициенты складываются, а затем запись нормализуется с помощью тождеств для чисел Фибоначчи. И результат нормализации единственный — это следует из теоремы Цекендорфа. В фибоначчиевой системе арифметика определяется не основанием, а рекуррентным законом самих разрядов.

Считали ли инки по Фибоначчи? Инки использовали счётные устройства, которые сейчас называют юпанами. До нас дошли каменные, глиняные и деревянные доски с углублениями для камешков или зёрен. Но точные правила работы с ними не сохранились. Особенно известна юпана, изображённая около 1615 года перуанским хронистом Фелипе Гуаманом Помой де Айялой. На его рисунке рядом с инкским счётчиком находится таблица, в каждой строке которой четыре группы содержат соответственно 5, 3, 2 и 1 кружок. Если читать в обратном порядке, получаем 1, 2, 3, 5. В 1976 году перуанский исследователь Эмилио Мендисабаль обратил внимание на эту последовательность и предположил, что устройство юпаны могло быть связано с числами Фибоначчи. Отсюда возникла гипотеза, что инки в счёте могли использовать систему, основанную не на одинаковом числе состояний в каждом разряде, а на последовательности 1, 2, 3, 5, … Но достоверно мы не знаем, действительно ли инки использовали фибоначчиев принцип и тем более пользовались системой счисления, подобной современной записи Цекендорфа.

Считать с запретами Пусть aₙ — число двоичных строк длины n, в которых нет двух соседних единиц. Если первая цифра 0, дальше можно поставить любую допустимую строку длины n−1. Если первая цифра 1, следующая обязана быть нулём, и остаётся строка длины n−2. Поэтому aₙ = aₙ₋₁ + aₙ₋₂. Получаем последовательность 2, 3, 5, 8, 13, …, то есть числа Фибоначчи со сдвигом: aₙ = Fₙ₊₂. Но здесь можно пойти в обратную сторону. Возьмём числа Фибоначчи 1, 2, 3, 5, 8, 13, 21, … (одну из двух начальных единиц опускаем) и будем записывать число нулями и единицами: единица означает, что соответствующее число Фибоначчи входит в сумму. Запретим только соседние единицы. Например, 11 = 8 + 3. Числа 8 и 3 не соседствуют в последовательности 1, 2, 3, 5, 8, 13, …. Оказывается, каждое положительное целое число имеет ровно одно представление как сумма несоседних чисел Фибоначчи. Это теорема Цекендорфа. Например, 2026 = 1597 + 377 + 34 + 13 + 5. Причём такую запись можно находить жадно: каждый раз брать наибольшее число Фибоначчи, не превосходящее остатка. Теорема гарантирует, что результат будет единственным. Получается необычная система записи: веса разрядов уже не являются степенями основания, зато сама структура запрещённых сочетаний обеспечивает однозначность.

Бесконечная скорость Появление бесконечности в физической модели часто служит сигналом: мы дошли до границы, за которой прежнее описание уже недостаточно. Хороший пример даёт геометрическая оптика. Свет в ней представляют лучами. Лучи могут сходиться и образовывать каустику — например, знакомую яркую кривую на дне чашки или бассейна. Если буквально продолжать лучевую модель, в некоторых точках плотность лучей становится бесконечной, а вместе с ней должна стать бесконечной и интенсивность света. В реальности этого, конечно, не происходит. Просто именно здесь перестаёт работать приближение «свет — это лучи»: становится существенной его волновая природа, и дифракция сглаживает математическую бесконечность. В газовой динамике потеря гладкости возникает уже в самих уравнениях движения. Уравнения Эйлера описывают сжимаемый газ без вязкости. Представим плавную волну сжатия. Разные её участки распространяются с разными скоростями, поэтому более быстрые части могут догонять более медленные. Профиль волны становится всё круче. В момент образования ударной волны производные скорости, давления и плотности становятся неограниченными, хотя сами величины остаются конечными. Затем гладкое решение уже нельзя продолжить в прежнем смысле: возникает скачок, который описывают как слабое решение. Но у настоящего газа есть вязкость и теплопроводность. Если их учесть, идеальный скачок превращается в очень тонкий, но гладкий переходный слой. Вязкость сглаживает эту сингулярность. И отсюда возникает естественный вопрос: может ли вязкость вообще гарантировать, что гладкость решения никогда не разрушится? Для трёхмерных уравнений Навье–Стокса ∂u/∂t + (u·∇)u = −∇p + νΔu + f, div u = 0 ответа на этот вопрос не было почти сто лет. Вопрос о том, обязано ли гладкое решение этой системы оставаться гладким при всех временах, входит в список семи задач тысячелетия Института Клэя. Причём здесь ситуация ещё строже, чем с ударной волной. Рассматривается несжимаемая жидкость: условие div u = 0 означает сохранение объёма, а плотность считается постоянной, поэтому скачок уплотнения возникнуть в принципе не может. И жидкость вязкая. Член νΔu стремится сглаживать различия скоростей. Но рядом с ним стоит нелинейный член (u·∇)u: скорость сама переносит поле скорости. В трёхмерном течении связанная с ним динамика позволяет вихревым линиям растягиваться. Из-за несжимаемости вытягивание вихревой трубки сопровождается её поперечным сжатием, а вращение может усиливаться. 8 сентября OpenAI опубликовала доказательство, согласно которому даже при наличии вязкости такое течение может прийти к сингулярности. В построенном решении первоначально покоящаяся жидкость приводится в движение специально устроенной гладкой внешней силой. Вихревая структура спирально стягивается во всё меньшую область и одновременно вытягивается вдоль оси, а скорость в ней растёт и за конечное время становится неограниченной. При этом коэффициент вязкости остаётся положительным, внешняя сила — гладкой, а полная кинетическая энергия — конечной. Это уже не ударная волна. Там невязкая модель допускает потерю гладкости и образование скачка, а вязкость превращает его в гладкий слой. Здесь вязкость присутствует с самого начала — и всё же не предотвращает образование сингулярности. Физически бесконечной скорости быть не может. Значит, реальная жидкость должна раньше выйти за пределы предположений модели. При достаточно больших скоростях станет существенной сжимаемость. При достаточно малых масштабах перестанет работать и представление жидкости как сплошной среды: придётся учитывать молекулярное строение вещества. И в этом отличие от истории Ньютона и Максвелла. Границу ньютоновской механики обнаружила другая теория. Здесь внешняя теория для этого не понадобилась. Если опубликованное доказательство подтвердится, получится, что уравнения Навье–Стокса сами привели своё решение к границе, за которой уже перестают быть физически адекватной моделью.

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

Система счисления из сочетаний Треугольник Паскаля можно использовать не только для подсчёта сочетаний. Из его чисел получается система записи целых чисел. Зафиксируем число k. Оказывается, любое целое N ≥ 0 можно единственным образом записать в виде N = Cₐₖᵏ + Cₐₖ₋₁ᵏ⁻¹ + … + Cₐ₁¹, где aₖ > aₖ₋₁ > … > a₁ ≥ 0. Будем считать Cₙʳ = 0 при n < r. Почему такая запись вообще существует? Её можно строить жадным алгоритмом. Сначала выбираем наибольший коэффициент Cₘᵏ, не превосходящий N. Пусть это Cₐₖᵏ. Тогда Cₐₖᵏ ≤ N < Cₐₖ₊₁ᵏ. Вычтем выбранный коэффициент. Для остатка R получаем R < Cₐₖ₊₁ᵏ − Cₐₖᵏ. Но по формуле Паскаля Cₐₖ₊₁ᵏ − Cₐₖᵏ = Cₐₖᵏ⁻¹. Значит, R < Cₐₖᵏ⁻¹, и следующий верхний индекс обязательно можно взять меньше aₖ. Затем повторяем тот же шаг для коэффициентов с верхним индексом k−1, потом k−2 и так далее. Так запись всегда строится. Более того, она единственна: неравенства Cₐₖᵏ ≤ N < Cₐₖ₊₁ᵏ однозначно определяют первый индекс aₖ, после чего тот же аргумент применяется к остатку. Посмотрим на пример: 15 = C₅³ + C₃² + C₂¹ = 10 + 3 + 2. Действительно, сначала выбираем наибольший коэффициент вида Cₘ³, не превосходящий 15: C₅³ = 10. Остаётся 5. Теперь берём наибольший Cₘ² при m < 5: C₃² = 3. Остаётся 2, то есть C₂¹ = 2. Если элементы сочетания нумеровать начиная с 1, такой записи естественно сопоставить (a₁+1; a₂+1; a₃+1). Поэтому числу 15 соответствует сочетание (3; 4; 6). Но особенно интересно, что происходит при прибавлении единицы. Имеем 15 = C₅³ + C₃² + C₂¹. Тогда 16 = C₅³ + C₃² + C₂¹ + 1. Сначала C₂¹ + 1 = 2 + 1 = 3 = C₃¹. Получается 16 = C₅³ + C₃² + C₃¹. Теперь срабатывает формула Паскаля: C₃² + C₃¹ = C₄². Поэтому 16 = C₅³ + C₄² + C₀¹, где C₀¹ = 0. Числу 16 соответствует уже сочетание (1; 5; 6). Это не лексикографический порядок из предыдущего поста, а другой способ нумерации — комбинаторная система счисления. В обычной позиционной системе числа собираются из степеней основания: 1, b, b², b³, … Здесь вместо них используются биномиальные коэффициенты, а формула Паскаля выполняет роль правила переноса. Так треугольник Паскаля превращается из таблицы для подсчёта сочетаний в систему записи целых чисел.

Сочетание как путь Треугольник Паскаля обычно воспринимают как таблицу чисел: 1 1 1 1 2 1 1 3 3 1 … Но его можно читать как карту. Начнём в верхней вершине. На каждом шаге разрешено двигаться вниз влево или вниз вправо. Если верхнюю строку считать нулевой, после n шагов окажемся в n-й строке. Чтобы попасть в позицию Cₙᵏ, нужно ровно k раз пойти вправо. А выбрать, на каких именно k шагах из n мы повернём вправо, — это и значит выбрать k элементов из n. Поэтому число путей к Cₙᵏ равно Cₙᵏ. Например, сочетанию (2; 5) из пяти элементов соответствует путь, в котором вправо мы идём на втором и пятом шагах: влево, вправо, влево, влево, вправо. Всего таких путей C₅² = 10, ровно столько же, сколько существует способов выбрать два элемента из пяти. Так сочетанию (2; 5) соответствует путь по треугольнику Паскаля: на втором и пятом шагах идём вправо, на остальных — влево. Из этой картины сразу видна и главная формула треугольника Паскаля. В любую вершину Cₙᵏ можно попасть последним шагом только двумя способами: из Cₙ₋₁ᵏ — если последний шаг был влево, или из Cₙ₋₁ᵏ⁻¹ — если он был вправо. Поэтому Cₙᵏ = Cₙ₋₁ᵏ + Cₙ₋₁ᵏ⁻¹. Есть ещё одна связь. Когда мы нумеровали сочетания в лексикографическом порядке, приходилось пропускать целые блоки сочетаний. Размер каждого такого блока был биномиальным коэффициентом. На языке путей это становится наглядно: выбирая одну ветвь, мы пропускаем все допустимые продолжения другой. Число таких продолжений — биномиальный коэффициент. Поэтому те же числа, из которых состоит треугольник Паскаля, естественно возникают и при нумерации сочетаний. А если начать использовать эти размеры уже не только для подсчёта, но и как веса разрядов, получится новая система счисления — из биномиальных коэффициентов.

А если порядок важен? К предыдущей задаче возник естественный вопрос: а что изменится, если порядок выбранных дней учитывать? Тогда это уже не сочетания, а размещения. Например, (1; 4; 8; 13) и (1; 8; 13; 4) будут считаться разными вариантами. Число размещений из 20 элементов по 4 равно A₂₀⁴ = 20·19·18·17. Попробуем теперь найти 2026-е размещение в лексикографическом порядке. Все размещения, начинающиеся с 1, образуют блок размером 19·18·17 = 5814. Поэтому 2026-е размещение действительно начинается с 1. После этого для каждого фиксированного второго элемента остаётся 18·17 = 306 вариантов. Удобно считать от нуля:  2026−1 = 2025, 2025 = 6·306 + 189. Значит, второй элемент — 7-й среди оставшихся: 8.  Далее  189 = 11·17 + 2. После 1 и 8 третий элемент — 12-й среди оставшихся: 14.  Наконец, остаётся выбрать 3-й из ещё не использованных чисел: 4.  Получаем (1; 8; 14; 4). Комментарий к предыдущей задаче подсвечивает важное различие. Для сочетаний порядок не учитывается, и размеры блоков задаются биномиальными коэффициентами:  C₁₉³, C₁₈³, … Для размещений порядок важен, и вместо них появляются произведения 19·18·17, 18·17, 17, … Стоит разрешить перестановку выбранных элементов — и у того же лексикографического списка меняется вся арифметика блоков.

Как найти сочетание по номеру Всего наборов C₂₀⁴ = 4845. Но искать 2026-й перебором не нужно. Сколько наборов начинается с 1? После единицы остаётся выбрать три дня из девятнадцати: C₁₉³ = 969. Начинающихся с 2: C₁₈³ = 816. Итак, 969 + 816 = 1785, поэтому 2026-й набор начинается с 3. Внутри этого блока нам нужен 2026 − 1785 = 241-й набор. Если второй день равен 4, получаем C₁₆² = 120 вариантов. Если второй день равен 5 — ещё C₁₅² = 105. После них остаётся 241 − 120 − 105 = 16. Следовательно, второй день — 6. Если третий день 7, имеется 13 вариантов последнего дня. Остаётся третий вариант следующего блока, значит третий день — 8, а четвёртый — 11. Ответ: (3; 6; 8; 11). Чтобы найти сочетание по его номеру, не нужно выписывать весь список: достаточно последовательно отсекать блоки, размеры которых задаются биномиальными коэффициентами.

Случайный беспорядок Факториальная система позволяет не только пронумеровать все перестановки, но и естественным образом получить случайную. Пусть нужно случайно расставить 7 книг. В факториальном коде перестановки цифры имеют диапазоны a₁ ∈ {0; 1}, a₂ ∈ {0; 1; 2}, … a₆ ∈ {0; 1; …; 6}. Выберем их независимо, каждую равновероятно из своего набора. Число возможных наборов равно 2·3·4·5·6·7 = 7!. А вероятность получить любой конкретный набор — 1/2 · 1/3 · 1/4 · 1/5 · 1/6 · 1/7 = 1/7!. Код Лемера устанавливает взаимно однозначное соответствие между такими наборами и 7! перестановками. Значит, каждая перестановка действительно возникает с вероятностью 1/7!. Но за этой формулой стоит очень простой алгоритм. Старшая цифра a₆ выбирает одну из 7 книг. Убираем её. Следующая цифра a₅ выбирает одну из оставшихся 6. Затем выбираем одну из 5, одну из 4 и так далее. Иными словами, случайную перестановку можно получить последовательностью независимых выборов: один из 7 вариантов, затем один из 6, затем один из 5, … затем один из 2. Вероятность любого полного пути равна 1/7 · 1/6 · … · 1/2 = 1/7!. Можно представить это даже как набор необычных игральных костей с 7, 6, 5, 4, 3 и 2 равновероятными гранями. Один бросок каждой кости определяет одну из 7! перестановок, и все они получаются с одинаковой вероятностью. Для n объектов происходит то же самое. Факториальные цифры становятся независимыми координатами перестановки: каждая говорит, какой по счёту элемент выбрать среди ещё оставшихся. Факториальная система раскладывает один случайный выбор из n! вариантов на независимые выборы из n, n−1, …, 2 вариантов.

Арифметика с меняющимся основанием В обычной десятичной системе каждый разряд живёт по одному правилу: после 9 возникает перенос. В факториальной системе правила в каждом разряде свои. Напомним запись: aₙ·n! + aₙ₋₁·(n−1)! + … + a₂·2! + a₁·1!, причём 0 ≤ aₖ ≤ k. Разряд при 0! всегда равен 0, поэтому его обычно просто дописывают справа. В разряде при 1! можно использовать цифры 0 и 1. При 2! — 0, 1, 2. При 3! — 0, 1, 2, 3. И так далее. Значит, переносы происходят соответственно после 2, 3, 4, 5, … Это система счисления со смешанным основанием. Посчитаем, например, 3210₍!₎ + 110₍!₎. Начинаем справа. В разряде 1! получаем 1 + 1 = 2. Но цифры 2 здесь быть не может. Поскольку 2·1! = 1·2!, пишем 0 и переносим 1 в следующий разряд. В разряде 2! получается 2 + 1 + 1 = 4. Здесь допустимы только цифры 0, 1, 2. Поэтому 4 = 1 + 1·3: пишем 1 и переносим 1 в разряд 3!. Наконец,  3 + 1 = 4, а 4·3! = 4!. Снова пишем 0 и переносим 1. Получаем 3210₍!₎ + 110₍!₎ = 10100₍!₎. Проверим в обычной записи: 3210₍!₎ = 23, 110₍!₎ = 3, 10100₍!₎ = 26. Вычитание работает симметрично. Только при заимствовании соседний разряд даёт не всегда 10 единиц, а соответственно 2, 3, 4, 5, … Например, 10000₍!₎ − 10₍!₎ = 3210₍!₎, то есть 24 − 1 = 23. Есть ещё одно отличие от обычной позиционной записи. В десятичной системе сдвинуть запись на один разряд влево — значит умножить число на 10. В факториальной системе единого множителя нет: 10₍!₎ = 1, 100₍!₎ = 2, 1000₍!₎ = 6, 10000₍!₎ = 24. При переходе к следующему разряду вес увеличивается каждый раз во столько раз, сколько требует именно этот разряд: 2, затем 3, затем 4, … Поэтому сложение и вычитание здесь устроены вполне естественно, а привычного правила умножения «сдвигом разрядов» уже нет. Можно посмотреть на факториальную запись как на счётчик. Его первое содержательное «колесо» имеет 2 положения:  0, 1. Следующее — 3:  0, 1, 2. Следующее — 4:  0, 1, 2, 3, и так далее. Разряды при 1!, 2!, …, (n−1)! вместе имеют 2·3·4·…·n = n! различных состояний. Отсюда понятно, почему факториальная система так естественно связана с перестановками: перестановок n объектов тоже ровно n!. Код Лемера устанавливает точное соответствие между числами 0, 1, 2, …, n!−1  и всеми n! перестановками в лексикографическом порядке. Поэтому прибавить 1 к факториальному коду — значит перейти к следующей перестановке. Обычный арифметический перенос оказывается тем же механизмом, который перебирает все возможные порядки n объектов. Факториальная система не просто считает перестановки: сама её арифметика устроена так, чтобы пройти их одну за другой.

Четыре карты вместо пяти Среди пяти карт обязательно найдутся две одной масти: мастей всего четыре. Допустим, это две пики. Расположим достоинства по кругу: A, 2, 3, …, Q, K, снова A. Из двух карт одной масти можно выбрать порядок так, чтобы от первой до второй по циклу из 13 достоинств было от 1 до 6 шагов. Ассистент прячет вторую карту, а первую кладёт на первое место. Тем самым он уже сообщает фокуснику масть спрятанной карты. Остаются ещё три открытые карты. Их можно расположить 3! = 6 способами. Ассистент и фокусник заранее нумеруют эти шесть перестановок числами от 1 до 6. Поэтому порядок трёх карт сообщает, на сколько шагов нужно продвинуться от первой карты той же масти. Например, первая карта показывает: «спрятана пика», а порядок остальных трёх сообщает: «+4». Этого достаточно, чтобы однозначно восстановить карту. Здесь перестановка используется буквально как число. Фокус известен как пятикарточный фокус Фитча—Чейни; его относят примерно к 1950 году.