Купить живой трафик

2 руб / подписчик

Статистика Избранное

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

Гео и язык канала: Россия, Русский

Категория: Образование

Рассказываем о различных математических сюжетах, уделяя особое внимание наглядности и простоте изложения. В математических методах стремимся выделять основную идею, сущность, квинтэссенцию, аромат — essence.
Для связи пишите @math_essence_bot.

Связанные каналы | Похожие каналы

Гео и язык канала

Россия, Русский

Категория

Образование

Статистика

Избранное

Фильтр публикаций

Скрывать удаленные

Скрывать репосты

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

7 Oct, 02:58

Геометрия дерева

Мы привыкли считать 3 гораздо более близким к 1, чем 33. Но попробуем измерять близость иначе.
Сначала разделим все целые числа на две группы — по остатку при делении на 2.
Каждую группу разделим ещё раз — теперь по остатку при делении на 4.
Затем — по остатку при делении на 8, 16, 32 и так далее.
Получается бесконечное двоичное дерево. Чем дольше два числа идут по одной ветви, тем ближе мы будем их считать.
Например, 3 − 1 = 2,
а 33 − 1 = 32 = 2⁵.
Числа 1 и 3 совпадают только по модулю 2, а 1 и 33 — по модулям 2, 4, 8, 16 и 32.
Поэтому в этой геометрии 33 гораздо ближе к 1, чем 3.
Для простого числа p, если x−y делится на pᵏ, но не делится на pᵏ⁺¹, положим
d(x, y) = p⁻ᵏ, а d(x, x)=0.
Это p-адическое расстояние.
Его удобно видеть на дереве. На первом уровне выбирается остаток по модулю p, на втором — уточняется остаток по модулю p², затем — p³ и так далее. Расстояние между двумя числами определяется уровнем, на котором их пути впервые расходятся.
Если x и y идут вместе k уровней, а y и z — l уровней, то x и z обязательно идут вместе хотя бы min (k, l) уровней. Поэтому
d(x, z) ≤ max (d(x, y), d(y, z)).
Это сильное неравенство треугольника. Пространства с таким расстоянием называются ультраметрическими.
Их геометрия совсем не похожа на евклидову.
В любом треугольнике две наибольшие стороны равны.
Любая точка шара может служить его центром.
Два шара либо не пересекаются, либо один целиком содержится в другом.
Более того, каждый шар одновременно открыт и замкнут.
На дереве всё это почти очевидно. Замкнутый шар радиуса p⁻ᵏ — это множество всех ветвей, имеющих общий начальный участок длины k.
Теперь вспомним позиционную запись:
x = a₀ + a₁p + a₂p² + a₃p³ + …
Цифра a₀ выбирает первую ветвь дерева, a₁ — следующую, a₂ — следующую и так далее.
Поэтому каждой бесконечной ветви соответствует p-адическое целое число, а каждому p-адическому целому числу — бесконечная ветвь.
Обычная система счисления неожиданно приобрела геометрию: цифры задают путь по дереву, а расстояние измеряет глубину общей части этого пути.
Само такое дерево можно строить и для других оснований. Простое p становится особенно важным для арифметики: p-адическая норма тогда согласуется с умножением, а пополнение рациональных чисел даёт поле ℚₚ.
Ультраметрика возникает не только из p-адической арифметики. Если объекты организованы в строгую вложенную иерархию, расстояние можно определить высотой их последнего общего узла.
p-адические числа — особенно красивый случай: дерево здесь не строится после вычислений, а уже содержится в арифметике делимости.

300 0 9 12

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

7 Oct, 02:22

Будем считать два целых числа тем ближе, чем на большую степень 2 делится их разность. Какое из чисел ближе к 1 по такому правилу?

Опрос

3
9
17
33

7 голосов

316 0 1 1

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

4 Oct, 12:22

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

432 0 9 3 34

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

3 Oct, 03:57

00:51

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

Положим β = −1 + i. Тогда
β² = −2i,
β³ = 2 + 2i.
Следовательно,
(1100)ᵦ = β³ + β² = (2 + 2i) − 2i = 2.
Запись выглядит двоичной, но её разряды уже не лежат на числовой прямой.
Умножение на β делает сразу две вещи: увеличивает длину в √2 раз и поворачивает направление на 135°.
Поэтому последовательные веса
1, β, β², β³, …
можно представить как векторы разных длин и направлений.
И приписывание нуля справа теперь имеет геометрический смысл: оно поворачивает соответствующую точку на 135° и удаляет её от начала координат в √2 раз.
Например,
1 → 10ᵦ = −1+i → 100ᵦ = −2i → 1000ᵦ = 2+2i → 10000ᵦ = −4.
За четыре сдвига мы умножили число на
β⁴ = −4:
масштаб увеличился в 4 раза, а направление развернулось на 180°.
Но система умеет гораздо больше. Каждое гауссово целое
a+bi, a, b ∈ ℤ,
имеет единственную конечную запись без ведущих нулей цифрами 0 и 1 в системе с основанием −1+i.
Например,
11ᵦ = β+1 = i,
111ᵦ = β²+β+1 = −i,
1110ᵦ = β³+β²+β = 1+i.
Поскольку
2 = 1100ᵦ = β³+β²,
то если в каком-то разряде при сложении появилась цифра 2, её можно заменить двумя единицами в более старших разрядах:
2βⁿ = βⁿ⁺³+βⁿ⁺².
Например, в младшем разряде
1+1 = 1100ᵦ.
В обычной двоичной системе две единицы дают перенос на один разряд влево. Здесь они порождают сразу две единицы — через два и через три разряда.
Сложение остаётся поразрядным, но «перенос» уже совсем не похож на обычный.
Эту комплексную двоичную систему описал Уолтер Пенни в 1965 году.
Есть у неё и неожиданная геометрическая сторона. Рассмотрим все бесконечные дробные хвосты
0,a₁a₂a₃…ᵦ,
где каждая aₖ равна 0 или 1.
Если разрешать всё более длинные дробные хвосты из нулей и единиц, их значения заполняют фрактальную область twindragon — «двойной дракон». На гифке видно, как возникают её последовательные конечные приближения.
Получается, что одна и та же система одновременно задаёт арифметику гауссовых целых и фрактальную геометрию их дробных частей.
Ещё раньше, в 1960 году, Дональд Кнут предложил другую комплексную систему: с основанием 2i и цифрами 0, 1, 2, 3.
После комплексных чисел естественно спросить: нельзя ли тем же способом перейти к кватернионам?
В прямом аналоге системы Пенни — нельзя.
Любой кватернион можно записать как β = a + v,
где v — его векторная часть. Поскольку
v² = −|v|²,
любая степень β имеет вид A + Bv.
Значит, все числа
a₀ + a₁β + a₂β² + …
с обычными вещественными цифрами остаются в одной двумерной плоскости внутри четырёхмерного пространства кватернионов.
Одного кватернионного основания с вещественными цифрами недостаточно, чтобы охватить всё пространство.
Кватернионные системы счисления построить можно, но приходится усложнять саму конструкцию. Красивый трюк Пенни — одно основание и всего две обычные цифры — в четырёх измерениях уже не переносится напрямую.

556 0 9 1 15

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

3 Oct, 03:10

Пусть основание системы счисления равно −1 + i, а разрешённые цифры — только 0 и 1. Какое число обозначает запись 1100₋₁₊ᵢ ?

Опрос

2
12
−2
2i
1 + i

7 голосов

496 0 2 1 5

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

30 Sep, 02:42

Отрицательный перенос

В двоичной системе
1 + 1 = 10₂:
пишем 0 и переносим 1 в следующий разряд.
В системе с основанием −2 так нельзя:
10₋₂ = −2,
а нам нужно получить +2.
Что происходит при переполнении разряда?
Пусть в нём получилось 2. Пишем 0, а перенос должен удовлетворять равенству
2 = 0 + (−1)·(−2).
Значит, в следующий разряд нужно перенести −1.
Но и цифры −1 у нас нет. Если в некотором разряде получилось −1, то
−1 = 1 + 1·(−2).
Поэтому пишем 1, а дальше переносим уже +1.
Получаются два необычных правила:
2 → пишем 0, переносим −1;
−1 → пишем 1, переносим +1.
Именно они дают уже знакомую запись
1 + 1 = 110₋₂.
Теперь сложим
111₋₂ + 111₋₂.
Мы знаем, что это 3 + 3 = 6, но попробуем получить результат непосредственно по разрядам.
В первом разряде:
1 + 1 = 2.
Пишем 0, переносим −1.
Во втором:
1 + 1 − 1 = 1.
Пишем 1, переноса нет.
В третьем снова:
1 + 1 = 2.
Пишем 0, переносим −1.
Следующего разряда в исходных числах уже нет. Там оказалось −1, поэтому пишем 1 и переносим +1 ещё на один разряд.
Получаем
111₋₂ + 111₋₂ = 11010₋₂.
Проверка:
11010₋₂ = 16 − 8 − 2 = 6.
Внешне это всё ещё обычное сложение по разрядам. Но перенос теперь может быть как положительным, так и отрицательным.
Причина в том, что переход на один разряд влево означает умножение не на 2, а на −2.
Отрицательное основание меняет не только запись чисел, но и саму арифметику переноса.

684 0 6 1 6

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

30 Sep, 01:59

В системе с основанием −2 разрешены только цифры 0 и 1. Какая запись получится при сложении 111₋₂ + 111₋₂ ?

Опрос

110₋₂
1110₋₂
11010₋₂
1010₋₂

6 голосов

528 0 3 2

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

29 Sep, 03:24

Без знака минус

В обычной позиционной системе веса разрядов равны
1, 2, 4, 8, …
если основание равно 2.
А если взять основание −2, веса станут
1, −2, 4, −8, 16, …
Поэтому
1101₋₂ = (−2)³ + (−2)² + 1 = −8 + 4 + 1 = −3.
Никакого знака минус в самой записи нет.
Это не случайный фокус: каждое целое число — положительное, отрицательное или ноль — имеет единственную конечную запись в системе с основанием −2 с цифрами 0 и 1.
Например,
1 = 1₋₂,
2 = 110₋₂,
3 = 111₋₂,
4 = 100₋₂,
а
−1 = 11₋₂,
−2 = 10₋₂,
−3 = 1101₋₂,
−4 = 1100₋₂.
Есть одна необычная особенность. В любой позиционной системе приписать справа ноль — значит умножить число на основание.
Здесь основание отрицательное. Поэтому
111₋₂ = 3,
1110₋₂ = −6,
11100₋₂ = 12,
111000₋₂ = −24.
Каждый сдвиг на один разряд не только удваивает модуль, но и меняет знак числа.
Более того, знак можно определить уже по длине записи.
Если старшая единица стоит при (−2)ⁿ, её абсолютный вклад равен 2ⁿ. Все младшие разряды вместе по абсолютной величине дают не больше
1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ−1.
Поэтому они не способны изменить знак старшего слагаемого.
Значит, запись нечётной длины представляет положительное число, а чётной — отрицательное.
В обычной системе знак приходится добавлять к записи отдельно.
Здесь знак зашит в саму структуру разрядов: один дополнительный разряд способен превратить положительное число в отрицательное.
Эта система не осталась математической игрушкой. Польский компьютер UMC-1, серийно выпускавшийся с 1962 года, использовал нега-двоичную арифметику, разработанную Здиславом Павляком.

666 0 8 5 14

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

29 Sep, 02:56

Запись 1101₋₂ сделана в позиционной системе с основанием −2. Какое обычное число она обозначает?

Опрос

13
−3
−11
5

10 голосов

622 0 2 1 3

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

27 Sep, 02:58

Когда период может не появиться

В основании φ стандартная запись любой рациональной дроби в конце концов становится периодической.
Но для произвольного иррационального основания это уже неверно.
Посмотрим, чем в этом отношении отличаются φ и √2.
Минимальный многочлен для φ — x² − x − 1.
Его корни: φ = (1+√5)/2
и (1−√5)/2 = −1/ φ.
Второй корень по модулю меньше 1.
Числа с таким свойством выделяют в особый класс.
Число Пизо — это вещественное число β > 1, минимальный многочлен которого имеет целые коэффициенты и старший коэффициент 1, а все остальные его корни имеют модуль меньше 1.
Золотое сечение — число Пизо.
Для любого основания β, являющегося числом Пизо, стандартная β-запись каждой рациональной дроби x, 0 ≤ x < 1, в конце концов становится периодической. Более того, это верно для всех чисел из ℚ(β).
Теперь возьмём β = √2. Его минимальный многочлен — x² − 2,
а корни равны √2 и −√2.
У второго корня модуль тоже равен √2, то есть больше 1.
И здесь действует обратное ограничение: если у минимального многочлена основания есть другой корень с модулем больше 1, то не каждая рациональная дробь может иметь в итоге периодическую стандартную запись.
Значит, существуют рациональные дроби, стандартные записи которых в основании √2 не становятся периодическими.
Почему вообще важны остальные корни многочлена?
Смысл этого условия можно увидеть так. При построении β-записи возникают последовательные остатки. В доказательстве те же выражения рассматривают и при остальных корнях минимального многочлена. Если их модули меньше 1, эти величины остаются ограниченными.
После умножения на общий знаменатель соответствующие состояния образуют точки дискретной решётки. В ограниченной области таких точек лишь конечное число.
Значит, какое-то состояние повторится — и вслед за ним начнут повторяться цифры.
У φ этот механизм работает, а у √2 условие нарушается: второй корень по модулю больше 1.
Любопытно, что обычные целые основания тоже укладываются в эту картину. Например, минимальный многочлен числа 10 — это x − 10.
Других корней у него нет, поэтому 10 тоже является числом Пизо.
Действительно, любое целое число больше 1 формально относится к числам Пизо.
Получается, привычная периодичность рациональных дробей в десятичной системе и периодичность в основании φ связаны одним общим свойством основания.
А иррациональность сама по себе периода вовсе не гарантирует.

756 0 5 1 9

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

27 Sep, 02:32

Пусть основание системы счисления равно √2. Обязательно ли стандартная (жадная) запись любой рациональной дроби x (0 < x < 1) в конце концов станет периодической?

Опрос

Да, как с основанием φ
Нет, некоторые рациональные дроби имеют непериодические записи
Только если знаменатель нечётный
Все такие записи конечны

3 голосов

549 0 2 4

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

26 Sep, 03:37

Почему ½ не заканчивается

Основание φ иррационально, но натуральные числа в этой системе могут иметь конечные записи:
2 = 10,01ᵩ,
3 = 100,01ᵩ,
4 = 101,01ᵩ.
А что будет с самым обычным рациональным числом ½?
Оказывается, оно не имеет конечной записи цифрами 0 и 1.
Причина довольно неожиданная.
Из φ² = φ + 1
следует
φ⁻¹ = φ − 1.
Поэтому любая целая степень φ имеет вид a+bφ,
где a и b — целые числа.
Значит, любая конечная запись в основании φ тоже имеет такой вид.
Но φ иррационально. Если число a+bφ рационально, то b = 0. А тогда оно просто целое.
Отсюда следует: если рациональное число имеет конечную запись в основании φ с цифрами 0 и 1, то оно обязательно целое.
Поэтому ½ записывается бесконечно:
½ = 0,010010010010…ᵩ,
то есть блок 010 повторяется бесконечно.
Единицы стоят при степенях
φ⁻², φ⁻⁵, φ⁻⁸, …
Поэтому значение записи равно
φ⁻² + φ⁻⁵ + φ⁻⁸ + … .
Это геометрическая прогрессия:
φ⁻²/(1−φ⁻³).
Но из φ³ = 2φ + 1
получаем
1 − φ⁻³ = 2φ⁻².
Следовательно,
φ⁻²/(1−φ⁻³) = ½.
В десятичной системе мы привыкли к другому:
дробь ½ = 0,5 заканчивается,
а ⅓ = 0,333… является периодической.
В основании φ граница проходит иначе: уже ½ не имеет конечной записи, зато его стандартная запись оказывается периодической.
Иррациональное основание позволяет целым числам заканчиваться, а простейшую дробь заставляет повторяться бесконечно.

717 0 3 2 16

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

26 Sep, 03:06

В системе с основанием φ будем выбирать стандартную запись без соседних единиц. Число 2 имеет конечную запись: 2 = 10,01ᵩ. А какой будет стандартная запись числа ½?

Опрос

Конечной
Бесконечной периодической
Бесконечной непериодической
Это число нельзя записать цифрами 0 и 1

2 голосов

587 0 1 8

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

25 Sep, 03:34

Перенос в обе стороны

В обычной системе счисления сложение устроено очень локально: если в некотором разряде получилось 10 единиц, перенос уходит на один разряд влево.
С основанием φ всё интереснее. Запись числа здесь вообще говоря не единственна: например, 2 = 1,11ᵩ = 10,01ᵩ.
Будем приводить результат к стандартной записи без соседних единиц.
Мы знаем, что
φ² = φ + 1,
поэтому соседние единицы можно объединять:
011ᵩ → 100ᵩ.
Но что делать, если при сложении в одном разряде появилась цифра 2?
Из равенства φ² = φ + 1
можно получить
2 = φ + φ⁻².
А значит, для любого n
2φⁿ = φⁿ⁺¹ + φⁿ⁻².
Иными словами, вместо двойки при весе φⁿ появляются две единицы при весах φⁿ⁺¹ и φⁿ⁻².
Посмотрим на сложение:
2 = 10,01ᵩ,
3 = 100,01ᵩ.
Складываем коэффициенты:
2 + 3 = 110,02ᵩ.
Но в стандартной записи разрешены только цифры 0 и 1, поэтому двойку нужно устранить. Используем правило
2φ⁻² = φ⁻¹ + φ⁻⁴.
Получаем
110,02ᵩ → 110,1001ᵩ.
Теперь в целой части стоят две соседние единицы:
110ᵩ → 1000ᵩ.
Поэтому
2 + 3 = 1000,1001ᵩ.
Проверим:
1000,1001ᵩ =
φ³ + φ⁻¹ + φ⁻⁴ = 5.
Получилась обычная пятёрка — но путь к ней совсем не похож на школьное сложение столбиком.
Здесь работают два правила нормализации:
соседние единицы объединяются благодаря
φⁿ + φⁿ⁻¹ = φⁿ⁺¹,
а появившаяся цифра 2 распадается по правилу
2φⁿ = φⁿ⁺¹ + φⁿ⁻².
Поэтому перенос уже не движется только справа налево. Он может одновременно породить разряды по обе стороны от исходного — и даже перескочить через запятую.
В системе с целым основанием правила переноса задаются самим основанием. Здесь их задаёт алгебраическое равенство φ²=φ+1.
Поэтому перенос здесь может идти не только влево: соотношение φ²=φ+1 заставляет его распространяться сразу по нескольким разрядам.

710 0 1 12

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

25 Sep, 02:48

В системе с основанием φ будем использовать стандартную запись без соседних единиц. Известно: 2 = 10,01ᵩ, 3 = 100,01ᵩ. Какая стандартная запись получится для 2 + 3?

Опрос

110,02ᵩ
1000,1001ᵩ
1001,01ᵩ
1010ᵩ

9 голосов

610 0 2 6

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

24 Sep, 02:44

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

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

688 0 6 1 13

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

22 Sep, 04:44

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.
То, что в фибоначчиевой системе задавалось рекуррентным правилом разрядов, здесь выполняется автоматически из алгебраического свойства самого основания.

836 0 6 1 20

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

22 Sep, 03:22

Пусть основанием системы счисления служит золотое сечение φ = (1+√5)/2. Разрешены только цифры 0 и 1. Как будет записано число 2?

Опрос

10,10
11
10,01
100

20 голосов

684 0 4 5 5

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

21 Sep, 05:21

Сколько стоит запрет 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 можно использовать как признак конца числа и передавать последовательность чисел без внешних разделителей.
Получается характерный обмен:
запрет уменьшает число допустимых записей, зато создаёт структуру, которой у обычной двоичной записи нет.
А скорость роста этой структуры определяется тем же числом φ, которое появляется во всей последовательности Фибоначчи.

800 0 4 1 19

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

21 Sep, 04:24

Обычная двоичная строка длины 10 имеет 2¹⁰ = 1024 возможных вариантов. А сколько строк длины 10 остаётся, если запретить две единицы подряд?

Опрос

89
144
512
676

17 голосов

634 0 1 2 4

Показано 20 последних публикаций.

3 086

подписчиков

Статистика канала

Популярное в канале

Считать с запретами Пусть aₙ — число двоичных строк длины n, в которых нет двух соседних единиц....

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

Система счисления из сочетаний Треугольник Паскаля можно использовать не только для подсчёта соч...

1 + 1 В привычной позиционной системе веса разрядов равны 1, b, b², b³, … Но основание b вовсе н...

Считали ли инки по Фибоначчи? Инки использовали счётные устройства, которые сейчас называют юпан...