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

Одна двойка — много записей

В системе с основанием φ запись числа может быть не единственной.
Например, из φ² = φ+1
следует φ⁻¹+φ⁻² = 1,
поэтому 2 = 1,11ᵩ.
Но верно и 2 = φ+φ⁻² = 10,01ᵩ.
Более того, конечных записей числа 2 бесконечно много.
Поскольку 100 ⟷ 011,
можно заменять в любых трёх соседних разрядах, не меняя числа, получаем:
2 = 10,01ᵩ =
= 10,0011ᵩ =
= 10,001011ᵩ =
= 10,00101011ᵩ =
= …
Чтобы выбрать одну запись, вводят правило: две единицы не должны стоять рядом.
Тогда стандартная запись двойки — 10,01ᵩ.
Дополнительное правило возвращает системе то, чего у неё не было изначально: единственность записи.

1 + 1

В привычной позиционной системе веса разрядов равны
1, b, b², b³, …
Но основание b вовсе не обязано быть целым.
Возьмём золотое сечение
φ = (1+√5)/2 ≈ 1,618.
Будем использовать только цифры 0 и 1, а разрядам приписывать веса
…, φ⁻², φ⁻¹, 1, φ, φ², φ³, …
Получается система счисления с основанием φ.
Главное свойство золотого сечения:
φ² = φ + 1.
Поэтому две записи — 11ᵩ и 100ᵩ — обозначают одно и то же число:
φ + 1 = φ².
То есть здесь сразу возникает необычный «перенос»:
011 → 100.
Он очень напоминает фибоначчиеву систему, где два соседних веса тоже заменяются следующим:
Fₙ + Fₙ₊₁ = Fₙ₊₂.
Связь не случайна:
φ² = φ + 1,
φ³ = 2φ + 1,
φ⁴ = 3φ + 2,
φ⁵ = 5φ + 3, …
Коэффициентами здесь снова становятся числа Фибоначчи.
Но есть ещё более странный эффект.
Чему равно 1+1?
Запись 10ᵩ означает просто φ, а 11ᵩ — φ+1=φ². Ни то ни другое не равно 2.
Используем равенство φ² = φ+1.
Из него следует φ⁻² = 2−φ.
Поэтому 2 = φ + φ⁻².
Значит, 2 = 10,01ᵩ.
Так в системе с иррациональным основанием обычное целое число неожиданно получает цифры после запятой.
Арифметика продолжает работать:
3 = φ² + φ⁻²,
Поэтому 3 = 100,01ᵩ.
А  4 = φ² + 1 + φ⁻²,
то есть 4 = 101,01ᵩ.
Из-за равенства 011ᵩ = 100ᵩ
запись, вообще говоря, не единственна. Поэтому, как и в фибоначчиевой системе, для натуральных чисел запрет соседних единиц выделяет единственную стандартную запись.
В системе Цекендорфа разрядными весами были
1, 2, 3, 5, 8, …
а перенос определялся рекуррентным соотношением Фибоначчи.
Теперь разрядные веса —
…, φ⁻², φ⁻¹, 1, φ, φ², …
но то же соотношение уже заключено в самом основании:
φ² = φ+1.
То, что в фибоначчиевой системе задавалось рекуррентным правилом разрядов, здесь выполняется автоматически из алгебраического свойства самого основания.

Сколько стоит запрет 11

В фибоначчиевой записи нельзя использовать два соседних числа Фибоначчи. Поэтому в соответствующей строке из нулей и единиц запрещена комбинация 11.
Насколько сильно это ограничение уменьшает число возможных записей?
Пусть Aₙ — число двоичных строк длины n без соседних единиц.
Разделим их на два типа.
Если строка заканчивается нулём, перед ним может стоять любая допустимая строка длины n−1. Таких Aₙ₋₁.
Если строка заканчивается единицей, предыдущий символ обязан быть нулём. Поэтому перед окончанием 01 может стоять любая допустимая строка длины n−2. Таких Aₙ₋₂.
Получаем
Aₙ = Aₙ₋₁ + Aₙ₋₂.
С начальными значениями A₁ = 2, A₂ = 3
получается  2, 3, 5, 8, 13, 21, …,
то есть Aₙ = Fₙ₊₂.
Поэтому для десяти разрядов имеется не 2¹⁰ = 1024,
а только F₁₂ = 144 допустимые строки.
Это и есть цена запрета 11.
Но числа Фибоначчи растут примерно как степени золотого сечения
φ = (1+√5)/2 ≈ 1,618.
Точнее, Fₙ ≈ φⁿ/√5.
Значит, число допустимых строк длины n растёт примерно как φⁿ, тогда как число обычных двоичных строк — как 2ⁿ.
В логарифмическом масштабе один обычный двоичный разряд несёт 1 бит информации, а на один разряд приходится асимптотически log₂φ ≈ 0,694 бита информации.
Иными словами, чтобы закодировать то же количество вариантов, фибоначчиевых разрядов требуется примерно в 1/log₂φ ≈ 1,44 раза больше, чем двоичных.
Например, 100 обычных двоичных разрядов по ёмкости соответствуют примерно 144 фибоначчиевым.
Так что фибоначчиева запись проигрывает двоичной в компактности.
Но тот же самый запрет 11 даёт другое преимущество: комбинацию 11 можно использовать как признак конца числа и передавать последовательность чисел без внешних разделителей.
Получается характерный обмен:
запрет уменьшает число допустимых записей, зато создаёт структуру, которой у обычной двоичной записи нет.
А скорость роста этой структуры определяется тем же числом φ, которое появляется во всей последовательности Фибоначчи.

Код без разделителей

В фибоначчиевой системе каждое натуральное число единственным образом представляется суммой несоседних чисел 1, 2, 3, 5, 8, 13, 21, 34, 55, …
Первый символ относится к весу 1, второй — к весу 2 и так далее. Поэтому нули в начале здесь значимы.
Используем главное свойство представления Цекендорфа: соседние числа Фибоначчи одновременно не используются.
Поэтому внутри такой последовательности никогда не встречается 11. Эта комбинация остаётся свободной.
Чтобы отметить конец числа, достаточно приписать ещё одну единицу. Например, для числа 57:
010000001 → 0100000011.
Появившаяся в конце пара 11 служит меткой окончания.
Теперь несколько кодов можно записывать подряд без пробелов.
Первая единица заключительной пары 11 — последний коэффициент самого числа, вторая — специально приписанная служебная единица.
Такой способ называется кодом Фибоначчи. Он саморазделяющийся: длину каждого числа заранее знать не требуется.
Если просто записывать обычные двоичные представления одно за другим, приходится отдельно сообщать их длины или использовать разделители.
А здесь сам запрет на соседние единицы создаёт комбинацию, которую можно отдать под знак конца.
Запрещённая внутри записи комбинация становится естественной границей между числами.

Арифметика Фибоначчи

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