Олимпиада имени Леонарда Эйлера 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}$.