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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Перші 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 може бути представлено у вигляді суми 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 не містять загальних елементів, 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, якщо в його уявленні є Fn, і 0 у протилежному випадку. наприклад, 24 кодується рядком 100101001, в якій одиниці стоять на 9-й, 6-й, 4-й і 1-й позиціях, оскільки 24 = F−1 + F−4 + F−6 + F−9. Ціле число x представляється словом непарної довжини тоді і тільки тоді, коли x > 0.

Дивись також[ред. | ред. код]

Виноски[ред. | ред. код]

Зовнішні посилання[ред. | ред. код]

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