Олимпиада имени Леонарда Эйлера2013-2014 учебный год, I тур заключительного этапа

На сотом году правления Казначей Бессмертный решил начать выпускать новые монеты. В этом году он выпустил в обращение неограниченный запас монет достоинством $2^{100} -1$, на следующий год — достоинством $2^{101} -1$, и т.д. Как только достоинство очередной новой монеты можно будет без сдачи набрать выпущенными ранее новыми монетами, Казначея сместят. На каком году его правления это случится? ( И. Богданов )

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

Комментарии от администратора Комментарии от администратора №1.     Ответ. На двухсотом.
Решение. Пусть на $k$-ом году правления $2^k -1$ можно набрать выпущенными ранее монетами: $2^k -1 = a_1+ \dots +a_n = N -n$, где $N$ — сумма степеней двойки, каждое из слагаемых в которой делится на $2^{100}$. Так как $2^k$ тоже делится на $2^{100}$, на $2^{100}$ должно делиться и число $n -1$. Так как, очевидно, $n > 1$, получаем $n \geq 2^{100}+1$, откуда $2^k -1 \geq (2^{100} -1)(2^{100}+1) \geq 2^{200} -1$, то есть $k \geq 200$, и раньше 200-го года Казначея не сместят. А на 200-ом году сместят, так как $2^{200} -1 = (2^{100}+1)(2^{100} -1)$.