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

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

Перші 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. Припустимо, кожне натуральне n ≤ k має подання Цекендорфа. Якщо k + 1 — число Фібоначчі, твердження доведено, якщо ні, то існує таке j, Fj < k + 1 < Fj + 1. Розглянемо a = k + 1 − Fj. Оскільки a ≤ k, воно має подання Цекендорфа (за припущенням індукції). При цьому Fj + a < Fj + 1, і оскільки Fj + 1 = Fj + Fj − 1 (за визначенням чисел Фібоначчі), a < Fj − 1, так що подання Цекендорфа a не містить Fj − 1. Таким чином, k + 1 може бути представлено у вигляді суми Fj, Fj і подання Цекендорфа 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′ не містять загальних елементів, Fs ≠ Ft. Не зменшуючи загальності доведення припустимо, що 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, якщо в його уявленні є Fn, і 0 у протилежному випадку. наприклад, 24 кодується рядком 100101001, в якій одиниці стоять на 9-й, 6-й, 4-й і 1-й позиціях, оскільки 24 = F−1 + F−4 + F−6 + F−9. Ціле число x представляється словом непарної довжини тоді і тільки тоді, коли x > 0.

Дивись також

Виноски
  1. Historical note on the name Zeckendorf Representation by R Knott, University of Surrey
  2. Knuth, Donald.

Зовнішні посилання

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.