альтернированная фибоначчиева система счисления

[maxal]

Доказать, что любое целое число $n$ однозначно представимо в виде

$$n = c_1\cdot F_1 - c_2\cdot F_2 + c_3\cdot F_3 - c_4\cdot F_4 + \dots,$$

где коэффициенты $c_i\in\{0,1\}$ и никакие два соседних коэффициента не равны $1$ одновременно.

[Capella]

А что такое

$$F_i$$

? Множество натуральных чисел?

[ИСН]

Числа Фибоначчи, ясное дело.
Сабжевая система со всеми плюсами известна давно. Вопрос в том, можно ли развернуться вот эдак - с минусами через один.

[Capella]

ИСН писал(а):

Числа Фибоначчи, ясное дело.

А ну да, сорри за оффтоп

[maxal]

Можете начать с единственности, ее доказать просто
А там глядишь и насчет существования идеи появятся.

[Mathemt]

maxal писал(а):

Можете начать с единственности, ее доказать просто
А там глядишь и насчет существования идеи появятся.

Рассмотрим максимальное по номеру число Фибо, участвующее в представлении числа. Допустим, этот номер нечетен, т.е. оно участвует с плюсом.

1. Минимально возможное число, представимое с соблюдением правил этой системы счисления, равно разности между этим максимальным Фибо и суммой Фиб с четными номерами, начиная с номера на 3 меньше номера максимального Фибо.
2. Это число строго больше нуля.

Оба утверждения вроде как легко доказываются. Первое немного посложнее. Но идея его доказательства в том, что если в пункте 1 есть еще положительные члены, то они автоматически "выключают" соседние отрицательные, и минимально возможное представимое число становится еще больше.

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

Но это только начало, потому что, вычитая друг из друга два разных представления одного и того же числа, мы получим нуль, представленный уже в другой системе! Правда, даже в самом худшем случае сумма Фиб до индекса n всегда меньше Фибы с индексом n+2. Это тоже легкое утверждение, и вот оно и доказывает единственность представления любого числа в этой системе.

Короче, именно с этого и надо было начинать. Просто вычитаем друг из друга два идентичных числа, по-разному представленных в системе. Получим сумму Фиб с коэффициентами из множества {-1, 0, 1}. А дальше применяем рассуждения пп. 1-2, усиленные моим последним утверждением "даже в самом худшем случае сумма Фиб до индекса n всегда меньше Фибы с индексом n+2". Это утверждение доказывается очень легко, по индукции.

Почему именно n+2? Потому что идентичные числа, даже представленные в этой системе по-разному, должны иметь одинаковые знаки, т.е. номера их максимальных по модулю Фиб имеют одинаковую четность. Следовательно, следующие меньшие по модулю Фибы отстоят от максимальных по модулю минимум на одну "дырку".

Теорема существования доказывается прямым построением. Вначале построим алгоритм для положительных чисел, не равных Фибам. Выбираем ближайшее Фибо, большее нашего числа, которое хотим представить. Пусть номер этого Фибо равен n. Разность между этим Фибо и нашим числом не превышает Фибы с номером n-2. А дальше применяем те же рассуждения уже к оставшейся разнице. «Дырку» вместо числа n-1 мы уже имеем, и условие об отсутствии соседних единиц в представлении числа автоматически выполняется, так что алгоритм сходится, так как Фиб остается конечное число. Аналогичен алгоритм для отрицательных чисел, не равных Фибам.

Остались последние штрихи. Надо придумать представление для самих Фиб, в том числе и со знаками.

Если число положительно и равно Фибо с нечетным номером, то его представление - это оно и есть.

Если это Фибо с четным номером и знаком "минус", то оно тоже равно своему представлению.

Если это Фибо с нечетным номером n и оно отрицательно, то в качестве первого приближения берем большее по номеру Фибо со знаком "минус" и четным номером n+1. Остается прибавить Фибо с четным номером n-1, которое всегда в точности равно сумме всех предшествующих Фиб с нечетными номерами (и они и будут со знаками "плюс" в нашем представлении).

И последний случай: Фибо с четным номером и знаком "плюс". Случай сводится к предыдущему рассмотренному.

Кажется, теперь все. Но как-то не очень красиво...

P.S. Кажется, есть подвох с самими числами Фибо. Будем ждать провокационных вопросов.

[maxal]

maxal в сообщении #45975 писал(а):

Доказать, что любое целое число $n$ однозначно представимо в виде

$$n = c_1\cdot F_1 - c_2\cdot F_2 + c_3\cdot F_3 - c_4\cdot F_4 + \dots,$$

где коэффициенты $c_i\in\{0,1\}$ и никакие два соседних коэффициента не равны $1$ одновременно.

Это результат статьи:

Bunder M. W. Zeckendorf representations using negative Fibonacci numbers. The Fibonacci Quarterly 30:2 (1992), 111-115.