Азия-тынық мұхит математикалық олимпиадасы, 2006 жыл
Комментарий/решение:
Заметим, что верно следующее тождество r2=r+1⇒rj+2=rj+1+rj,∀j∈Z. Пусть мы хотим представить число N. Тогда представим N в r-ичной системе счисления. То есть akak−1...a0...a−k, где ai∈{0,1}. Будем доказывать задачу по индукции.
База: N=1, очевидна. 1=r0.
Предположение: мы смогли представить N−1 в виде суммы степеней золотого сечения.
Переход: Покажем, что можно представить N. Рассмотрим r-ичное представление числа N−1. Если aj=aj+1=1 то можно заменить aj+2 на 1 и aj,aj+1 на 0. Значит мы можем считать, что в r-ичной записи нет двух единиц подряд. Если a0=0, то заменяя значение на 1 мы представляем в требуемом виде число N. Значит a0=1. Если a−1=a−2=0, то заменяя a0=0,a−1=a−2=1 представляем в требуемом виде N. Значит a−1=0,a−2=1. Делая аналогичное рассуждения мы получим, что a0=a−2=a−4=...=1. Но так как r-ичная запись числа N−1 содержит конечное число разрядов, то в какой то момент r−2k=0, после чего последовательно заменяя все r−2i на 0, получим что r0=0, и значит можно представить число N в виде суммы различных степеней золотого сечения, что и требовалось доказать.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.