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

Матеріал з testwiki
Перейти до навігації Перейти до пошуку
Перші 160 цілих чисел (по осі x), розбиті за поданням Цекендорфа. Колір кожного прямокутника відповідає числу Фібоначчі, його висота відповідає значенню числа.

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

Теорема Цекендорфа свідчить, що будь-яке натуральне число можна єдиним чином представити у вигляді суми одного або декількох різних чисел Фібоначчі так, щоб в цьому поданні не виявилося двох сусідніх чисел з послідовності Фібоначчі. Формулюючи суворіше, для будь-якого натурального числа N існують натуральні числа Шаблон:Math, Шаблон:Math, такі, що

N=∑i=0kFci,

де Шаблон:Math — n-не число Фібоначчі. Ця сума називається поданням Цекендорфа числа N. На основі подання Цекендорфа будується система числення Фібоначчі.

Наприклад, подання Цекендорфа для 100 є

Шаблон:Math.

Можна подати 100 у вигляді суми чисел Фібоначчі і по-іншому, наприклад:

Шаблон:Math
Шаблон:Math.

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

Для будь-якого заданого натурального числа його подання Цекендорфа перебуває за допомогою жадібного алгоритму, коли на кожному етапі вибирається найбільше можливе число Фібоначчі.

Історія

Хоча теорема названа на честь автора, який опублікував свою роботу в 1972 році, цей же результат був опублікований двадцятьма роками раніше Шаблон:Нп[1]. Як така, ця теорема служить ілюстрацією закону Стіглера.

Доведення

Теорема Цекендорфа складається з двох частин:

  1. Існування: для кожного натурального числа існує подання Цекендорфа.
  2. Єдиність: жодне натуральне число не має двох різних поданнів Цекендорфа.

Першу частину теореми можна довести за індукцією. Для Шаблон:Math твердження очевидно правильне (оскільки це числа Фібоначчі), для Шаблон:Math маємо Шаблон:Math. Припустимо, кожне натуральне Шаблон:Math має подання Цекендорфа. Якщо Шаблон:Math — число Фібоначчі, твердження доведено, якщо ні, то існує таке j, Шаблон:Math. Розглянемо Шаблон:Math. Оскільки Шаблон:Math, воно має подання Цекендорфа (за припущенням індукції). При цьому Шаблон:Math, і оскільки Шаблон:Math (за визначенням чисел Фібоначчі), Шаблон:Math, так що подання Цекендорфа a не містить Шаблон:Math. Таким чином, Шаблон:Math може бути представлено у вигляді суми Fj, Шаблон:Math і подання Цекендорфа a.

Для доведення другої частини теореми використовується така лема:

Лема: Сума елементів будь-якої непорожньої множини різних чисел Фібоначчі (без послідовних), з максимальним числом Fj строго менше, ніж наступне число Фібоначчі Шаблон:Math.

Лема доводиться індукцією по j.

Тепер візьмемо дві непорожні множини, що складаються з довільних непослідовних чисел Фібоначчі Шаблон:Math і Шаблон:Math з однією і тією ж сумою елементів. Розглянемо множини Шаблон:Math і Шаблон:Math, рівні Шаблон:Math і Шаблон:Math, з яких видалені спільні елементи (тобто Шаблон:Math і Шаблон:Math). Оскільки Шаблон:Math і Шаблон:Math мають одну і ту ж суму елементів, і з них видалені одні і ті ж елементи (а саме елементи з Шаблон:Math∩Шаблон:Math), Шаблон:Math і Шаблон:Math також повинні мати одну і ту ж суму елементів.

Доведемо від супротивного, що хоча б одна з множин Шаблон:Math і Шаблон:Math порожня. Припустимо, що це не так, тобто що Шаблон:Math і Шаблон:Math непорожні, і нехай найбільший елемент Шаблон:Math є Шаблон:Math, а найбільший елемент Шаблон:Math є Шаблон:Math. Оскільки Шаблон:Math і Шаблон:Math не містять загальних елементів, Шаблон:Math. Не зменшуючи загальності доведення припустимо, що Шаблон:Math. Тоді за лемою сума елементів Шаблон:Math строго менше, ніж Шаблон:Math, тобто строго менше, ніж Шаблон:Math, оскільки сума елементів Шаблон:Math не менша, ніж Шаблон:Math. А це суперечить тому, що Шаблон:Math і Шаблон:Math мають однакову суму елементів, отже, або Шаблон:Math, або Шаблон:Math порожня.

Нехай (не зменшуючи загальності) порожня Шаблон:Math. Тоді сума елементів Шаблон:Math дорівнює нулю, отже, сума елементів Шаблон:Math також дорівнює нулю, значить, Шаблон:Math також порожня множина (вона містить тільки натуральні числа). Значить, Шаблон:Math ∅, тобто Шаблон:Math, що і було потрібно довести.

Множення Фібоначчі

З допомогою подання Цекендорфа можна ввести наступну операцію. Для натуральних чисел a і b з поданням Цекендорфа a=∑i=0kFci(ci≥2) і b=∑j=0lFdj(dj≥2) можна визначити додаток Фібоначчі a∘b=∑i=0k∑j=0lFci+dj.

Детальніше про множення Фібоначчі див. у статті, присвяченій системі числення Фібоначчі.

Подання чисел негафібоначчі

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

Fn−2=Fn−Fn−1,

який дає послідовність чисел «негафібоначчі», що задовольняють рівності

F−n=(−1)n+1Fn.

Будь-яке ціле число також можна єдиним чином подати[2] у вигляді суми чисел негафібоначчі, в якому ніякі два послідовні числа негафібоначчі не використовуються. Наприклад:

Зауважимо, що Шаблон:Math, тому єдиність подання істотно залежить від тієї умови, що два послідовні числа негафібонначі не використовуються.

Це дає систему кодування цілих чисел, аналогічну поданням Цекендорфа. У поданні цілого числа x n-на цифра дорівнює 1, якщо в його уявленні є Шаблон:Math, і 0 у протилежному випадку. наприклад, 24 кодується рядком 100101001, в якій одиниці стоять на 9-й, 6-й, 4-й і 1-й позиціях, оскільки Шаблон:Math. Ціле число x представляється словом непарної довжини тоді і тільки тоді, коли Шаблон:Math.

Дивись також

Виноски

Шаблон:Reflist

Джерела

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

  1. ↑ Шаблон:Cite web
  2. ↑ Шаблон:Cite conference
Отримано з https://uk.wiki.beta.math.wmflabs.org/w/index.php?title=Теорема_Цекендорфа&oldid=7252