Задача 60577

Темы:    [ Числа Фибоначчи ] [ Системы счисления (прочее) ]

Сложность: 4+ Классы: 8,9,10,11

Условие

Фибоначчиева система счисления. Докажите, что произвольное натуральное число n, не превосходящее F_m, единственным образом можно представит в виде

n = b_kF_k,

где все числа b₂, ..., b_m равны 0 либо 1, причем среди этих чисел нет двух единиц стоящих рядом, то есть b_kb_{k + 1} = 0 (2 k m - 1). Для записи числа в фибоначчиевой системе счисления используется обозначение:

n = (b_k...b₂)_F.

Подсказка

Для разложения числа n в фибоначчиевой системе счисления нужно воспользоваться ``жадным'' алгоритмом: вычитать из n наибольшее число F_m, не превосходящее n.

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

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	3
Название	Алгоритм Евклида и основная теорема арифметики
Тема	Алгебра и арифметика
параграф
Номер	4
Название	О том, как размножаются кролики
Тема	Классическая комбинаторика
задача
Номер	03.125