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

Ограничения фибоначчиевой записи

Почему в записи нельзя ставить единицы рядом и как проверить корректность числа

2 мин чтенияСложность: Обновлено 29 сентября 2026

Фибоначчиева запись корректна, если число представлено суммой разрешённых весов Фибоначчиевой системы, а соседние разряды не содержат одновременно единицы. Запрет соседних единиц делает запись однозначной и называется каноническим условием.

Для записи используют веса \(F_2,F_3,F_4,\ldots\), где \(F_2=1\), \(F_3=2\), а каждый следующий вес равен сумме двух предыдущих. Цифры обычно равны только \(0\) или \(1\). Запись считается корректной, если в ней нет фрагмента \(11\), то есть две единицы не стоят в соседних разрядах. Такая запись называется канонической.

В канонической фибоначчиевой записи разряды перечисляют от большего веса к меньшему. Если цифры записи равны \(a_k,a_{k-1},\ldots,a_2\), то значение числа находят сложением весов, отмеченных единицами. Ограничение \(a_i a_{i+1}=0\) для всех соседних разрядов запрещает одновременное присутствие двух соседних весов.

\[N=\sum_{i=2}^{k}a_iF_i,\qquad a_i\in\{0,1\},\qquad a_i+a_{i+1}\le 1\]

№

Пример проверки

Запись \(101001\) корректна: в ней нет соседних единиц. Она обозначает \(F_7+F_5+F_2=13+5+1=19\). Запись \(101101\) некорректна, потому что содержит фрагмент \(11\) в середине.

Не путайте с двоичной системой

В двоичной системе соседние единицы разрешены: например, \(110_2\) — обычная запись числа 6. Запрет \(11\) относится именно к фибоначчиевой системе счисления. Кроме того, два первых одинаковых веса \(1\) и \(1\) не считают разными стандартными разрядами: используют соглашение \(F_2=1\), \(F_3=2\).

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

Какая запись удовлетворяет ограничению фибоначчиевой записи?

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

Главное

Цифры фибоначчиевой записи — \(0\) и \(1\), а веса — числа Фибоначчи, начиная с \(1,2,3,5,\ldots\).
Корректная каноническая запись не содержит соседних единиц: фрагмент \(11\) запрещён.
Ограничение нужно для однозначности представления числа и не действует в обычной двоичной системе.