ЕГЭОГЭ
Задание № 1 · ЕГЭ

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

Единственное представление натурального числа суммой непоследовательных чисел Фибоначчи
2 мин чтенияСложность: Обновлено 29 сентября 2026

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

Теорема ЦекендорфаНазвана в честь бельгийского математика Эдуарда Цекендорфа.
Для любого натурального числа \(n\) существует единственное представление в виде суммы одного или нескольких чисел последовательности \(1, 2, 3, 5, 8, 13, \ldots\), в которой никакие два выбранных числа не являются соседними членами последовательности. Числа \(1\) и \(2\) здесь принимаются за первые числа Фибоначчи, а каждое следующее равно сумме двух предыдущих.
\[n=\sum_{i=1}^{k} a_iF_i,\qquad a_i\in\{0,1\},\qquad a_i a_{i+1}=0,\quad F_1=1,\ F_2=2,\ F_{i+2}=F_{i+1}+F_i\]

Коэффициент \(a_i=1\) означает, что число \(F_i\) входит в сумму, а \(a_i=0\) — что не входит. Условие \(a_i a_{i+1}=0\) запрещает одновременно выбирать два соседних числа Фибоначчи. Благодаря этому каждому натуральному числу соответствует ровно одна последовательность цифр без соседних единиц — каноническая фибоначчиева запись.

№
Пример

Число \(17\) раскладывается так: \(17=13+3+1\). Числа \(13\) и \(3\) не соседние, как и \(3\) и \(1\), поэтому представление удовлетворяет теореме. Запись по числам \(1,2,3,5,8,13\) имеет вид \(100101\).

!
Не путайте с обычной записью

В теореме используются различные числа Фибоначчи, поэтому повторять одно и то же число нельзя. Кроме того, запрещены соседние числа: например, сумма \(8+5\) не является допустимой частью представления, хотя оба слагаемых — числа Фибоначчи.

Проверьте себя

Какое представление числа \(20\) удовлетворяет теореме Цекендорфа?

Главное за минуту

Главное

  • Каждое натуральное число представляется суммой чисел Фибоначчи единственным способом.
  • Слагаемые должны быть различными, а соседние числа Фибоначчи нельзя выбирать одновременно.
  • Такое представление называют канонической фибоначчиевой записью.