Леонард Эйлер атындағы олимпиада, 2020-2021 оқу жылы, қорытынды кезеңнің 1-ші туры

Ажалсыз Кощей «Спёрбанк» банкінде шот ашты. Алғашында шотта 0 тг болды. Бірінші күні Кощей өз шотына $k$ $(k > 0)$ тг салды. Ал әрбір келесі күні алдыңғы күнге қарағанда 1 тг артық салып отырған (яғни екінші күні $k+1$ тг, үшінші күні $k+2$ тг, т.с.с. кете береді). Бірақ әрбір салымыннан кейін, мезетте есеп шоттың жалпы мөлшері екі есе азайып отырған. Кощейдің есеп шоттындағы ақша мөлшері әрқашанда бүтін сан болып отыратындай барлық $k$ сандарын табыңыз. ( С. Берлов )

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

Комментарии от администратора Комментарии от администратора №1.    
Ответ. 2.
Решение. Покажем по индукции, что если Кощей в первый день внёс 2 рубля, то на $n$-ый день у него на счету будет $n$ рублей. База $n = 1$: на первый день два внесённых Кощеем рубля стараниями Спёрбанка тут же превратились в 1 рубль. Пусть на $n$-ый день на счету у Кощея оказалось $n$ рублей. Добавив на $(n+1)$-ый день $n+2$ рубля, Кощей получит на счету $(n+n+2)/2 = n+1$ рублей, что и требовалось доказать.
   Допустим теперь, что в первый день Кощей внёс $2+k$ рублей, где $k \ne 0.$ Покажем, что в этом случае у Кощея в $n$-ый день на счету будет $n+(k/2+k/4+\ldots +k/2^n)$ рублей. Из этого будет следовать единственность ответа 2, так как при $n = m+1,$ где $m$ — степень, с которой двойка входит в разложение числа $k$ на простые множители, сумма в скобках окажется дробной. База $n = 1$ индукции очевидна. Пусть на $n$-ый день на счету у Кощея оказалось $n+k/2+k/4+\ldots +k/2^n$ рублей. Добавив на $(n+1)$-ый день $n+2+k$ рублей, Кощей получит на счету $(2n+2+k+k/2+k/4+\ldots +k/2^n)/2 = n+1+k/2+k/4+\ldots +k/2^{n+1}$ рублей, что и требовалось доказать.