Loading [MathJax]/jax/output/SVG/jax.js

Азия-тынық мұхит математикалық олимпиадасы, 2006 жыл


Кез келген натурал санды ақырлы алтын қиманың τ (τ=1+52) әртүрлі бүтін дәрежелерінің қосындысы ретінде көрсетуге болатынын дәлелдеңіз. Мұндағы алтын қиманың τ бүтін дәрежесі ретінде мына τi түрдегі санды түсінеміз, мұндағы i-бүтін (міндетті түрде оң емес).
посмотреть в олимпиаде

Комментарий/решение:

  3
3 года 2 месяца назад #

Заметим, что верно следующее тождество r2=r+1rj+2=rj+1+rj,jZ. Пусть мы хотим представить число N. Тогда представим N в r-ичной системе счисления. То есть akak1...a0...ak, где ai{0,1}. Будем доказывать задачу по индукции.

База: N=1, очевидна. 1=r0.

Предположение: мы смогли представить N1 в виде суммы степеней золотого сечения.

Переход: Покажем, что можно представить N. Рассмотрим r-ичное представление числа N1. Если aj=aj+1=1 то можно заменить aj+2 на 1 и aj,aj+1 на 0. Значит мы можем считать, что в r-ичной записи нет двух единиц подряд. Если a0=0, то заменяя значение на 1 мы представляем в требуемом виде число N. Значит a0=1. Если a1=a2=0, то заменяя a0=0,a1=a2=1 представляем в требуемом виде N. Значит a1=0,a2=1. Делая аналогичное рассуждения мы получим, что a0=a2=a4=...=1. Но так как r-ичная запись числа N1 содержит конечное число разрядов, то в какой то момент r2k=0, после чего последовательно заменяя все r2i на 0, получим что r0=0, и значит можно представить число N в виде суммы различных степеней золотого сечения, что и требовалось доказать.