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

Өзінің басқаруының жүзінші жылында Ажалсыз Қазынашы жаңа тиындар шығару туралы ойлады. Осы жылы ол тиын құны $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)$.