Теорема Цекендорфа

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Первые 160 целых чисел (по оси x), разбитые по представлению Цекендорфа. Каждый прямоугольник цвет соответствует числу Фибоначчи, его высота соответствует значению числа.

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

Теорема Цекендорфа гласит, что всякое натуральное число можно единственным образом представить в виде суммы одного или нескольких различных чисел Фибоначчи так, чтобы в этом представлении не оказалось двух соседних чисел из последовательности Фибоначчи. Формулируя строже, для любого натурального числа N существуют натуральные числа  ci ≥ 2, ci + 1 > ci + 1, такие, что

где Fn — n-е число Фибоначчи. Эта сумма называется представлением Цекендорфа числа N. На основе цекендорфова представления строится фибоначчиева система счисления.

Например, представление Цекендорфа для 100 есть

100 = 89 + 8 + 3.

Можно представить 100 в виде суммы чисел Фибоначчи и по-другому – например,

100 = 89 + 8 + 2 + 1
100 = 55 + 34 + 8 + 3

но все это не будут цекендорфовы представления, поскольку 1 и 2 или 34 и 55 являются последовательными числами Фибоначчи.

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

История[править | править вики-текст]

Хотя теорема названа в честь автора, опубликовавшего свою работу в 1972 году, этот же результат был опубликован двадцатью годами ранее Герритом Леккеркеркером.[1] Как таковая, эта теорема служит иллюстрацией закона Стиглера.

Доказательство[править | править вики-текст]

Теорема Цекендорфа состоит из двух частей:

  1. Существование: каждое натуральное числоимеет представление Цекендорфа.
  2. Единственность: никакое натуральное число не имеет двух различных представлений Цекендорфа.

Первую часть теоремы можно доказать по индукции. Для n = 1, 2, 3 утверждение очевидно верно (поскольку это числа Фибоначчи), для n = 4 имеем 4 = 3 + 1. Предположим, всякое натуральное nk имеет цекендорфово представление. Если k + 1 — число Фибоначчи, утверждение доказано, если нет, то существует такое j, что Fj < k + 1 < Fj + 1. Рассмотрим a = k + 1 − Fj. Поскольку ak, оно имеет цекендорфово представление (по предположению индукции). При этом Fj + a < Fj + 1, и поскольку Fj + 1 = Fj + Fj − 1 (по определению чисел Фибоначчи), a < Fj − 1, так что цекендорфово представление a не содержит Fj − 1. Таким образом, k + 1 может быть представлено в виде суммы FjFj  и цекендорфова прдставления a.

Вторая часть теоремы требует для доказательства следующую лемму:

Лемма: Сумма элементов любого непустого множества различных чисел Фибоначчи (без последовательных), с максимальным числом Fj строго меньше, чем следующее число Фибоначчи Fj + 1.

Лемма доказывается индукцией по j.

Теперь возьмем два непустых множества из различных непоследовательных чисел Фибоначчи S и T с одной и той же суммой элементов. Рассмотрим множества S и T, равные S и T, из которых удалены общие элементы (т.е. S = S\T и T = T\S). Поскольку S и T имеют одну и ту же сумму элементов, и из них удалены одни и те же элементы (а именно элементы из S T), S и T также должны иметь одну и ту же сумму элементов.

Докажем от противного, что хотя бы одно из множеств S и T пусто. Предположим, что это не так, т.е. что S и T оба непусты, и пусть наибольший элемент S есть Fs, а наибольший элемент T есть Ft. Поскольку S и T не содержат общих элементов, FsFt. Без потери общности предположим, что Fs < Ft. Тогда по лемме сумма элементов S строго меньше, чем Fs + 1, т.е. строго меньше, чем Ft, поскольку сумма элементов T не меньше, чем Ft. А это противорчеит тому, что S и T имеют одинаковую сумму элементов, следовательно, либо S, либо T пусто.

Пусть (без потери общности) пусто S. Тогда сумма элементов S равна нулю, значит, сумма элементов T также равна нулю, значит, T также пустое множество (оно содержит только натуральные числа). Значит, S = T = ∅, т.е. S = T, что и требовалось доказать.

Фибоначчиево умножение[править | править вики-текст]

С помощью представления Цекендорфа можно ввести следующую операцию. Для натуральных чисел a и b с представлениями Цекендорфа и можно определить фибоначчиево умножение Подробнее о фибоначчиевом умножении см. в статье, посвященной фибоначчиевой системе счисления.

Представление негафибоначчиевых чисел[править | править вики-текст]

Последовательность Фибоначчи можно распространить на отрицательные индексы рекуррентным соотношением

который дает последовательность чисел "негафибоначчи", удовлетворяющих равенству

Любое целое число также можно единственным образом представить[2] в виде суммы чисел негафибоначчи, в котором никакие два последовательных числа негафибоначчи используются. Например:

  • −11 = F−4 + F−6 = (−3) + (−8)
  • 12 = F−2 + F−7 = (−1) + 13
  • 24 = F−1 + F−4 + F−6 + F−9 = 1 + (−3) + (−8) + 34
  • −43 = F−2 + F−7 + F−10 = (−1) + 13 + (−55)
  • 0 — пустая сумма.

Заметим, что 0 = F−1 + F−2, поэтому единственность представления существенно зависит от того условия, что двух последовательных чисел негафибоначчи не используется.

Это дает систему кодирования целых чисел, аналогичную представлению Цекендорфа. В представлении целого числа x n-я цифра равна 1, если в его представлении имеется FnFn, и 0 в противном случае. например, 24 кодируется строкой 100101001, в которой единицы стоят на 9-й, 6-й, 4-й и 1-й позициях, поскольку 24 = F−1 + F−4 + F−6 + F−9. Целое число x представляется словом нечетной длины тогда и только тогда, когда x > 0.

См. также[править | править вики-текст]

References[править | править вики-текст]

Внешние ссылки[править | править вики-текст]

Эта статья использует материал "proof that the Zeckendorf representation of a positive integer is unique" с PlanetMath, под лицензией Creative Commons Attribution/Share-Alike License.