Эйлер атындағы олимпиада, 2016-2017 оқу жылы, аймақтық кезеңнің 2 туры

Тақтада 100 натурал сан жазылған, олардың ішінде дәл 33-ші тақ. Әр минут сайын тақтаға жазылып тұрған сандардың қос-қостан алғандағы көбейтінділердің қосындысы жазылады (мысалға, егер тақтада 1, 2, 3, 3 сандары жазылса, онда келесі минутта $1\cdot 2+1\cdot 3+1\cdot 3+2\cdot 3+2\cdot 3+3\cdot 3$ саны жазылады). Қандай да бір уақытта, ерме ме кеш пе, тақтада $2^{10000000}$ санына бөлетін сан пайда болады деп есептеуге болады ма? ( И. Богданов )

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

Комментарии от администратора Комментарии от администратора №1.     Ответ. Можно. Решение. Так как на доске написано 33 нечётных числа, в первую минуту будет дописана сумма попарных произведений, среди которых $33\cdot 32/2$ нечётных. Значит, дописанное число будет чётным, и на доске останется ровно 33 нечётных числа. Повторяя эти рассуждения, получаем, что на доске в любой момент будет ровно 33 нечётных числа.
Пусть $A_n$ — число, записанное на $n$-й минуте, а $S_n$ — сумма всех чисел на доске перед дописыванием $A_n$. По доказанному, число $S_n$ нечётно. Число $A_{n+1}$ отличается от $A_n$ на сумму всех попарных произведений, в которых участвует $A_n$, то есть на $S_nA_n$. Итак, $A_{n+1} = A_n+A_nS_n = A_n(1+S_n)$. Поскольку число $1+S_n$ чётно, получаем, что степень двойки, на которую делится $A_{n+1}$, больше, чем степень двойки, на которую делится $A_n$. Итак, эта степень возрастает с каждой минутой хотя бы на 1, и через 10000000 минут $A_n$ наверняка будет делиться на $2^{10000000}$.