Республиканская олимпиада по математике, 2012 год, 10 класс

Последовательность ${a_n}$ определяется следующим образом: $a_1=4$, $a_2=17$ и для любого $k\geq 1$ справедливы соотношения: $$ a_{2k+1}=a_2+a_4+\ldots +a_{2k}+(k+1)(2^{2k+3}-1), $$ $$ a_{2k+2}=(2^{2k+2}+1) a_1+(2^{2k+3}+1)a_3+\ldots+(2^{3k+1}+1)a_{2k-1}+k. $$ Найдите наименьшее $m$, такое что $(a_1+a_2+\ldots+a_m)^{2012^{2012}}-1$ делится на $2^{2012^{2012}}$. ( Сатылханов К. )

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

Решение: Пусть $S_k=a_1+ \dots + a_k.$ Заметим, что $S_{2i}$ нечетное, а $S_{2i-1}$ четное для всех $i\in\mathbf N.$ Это легко доказать по индукции, беря во внимание следующее:

$$a_{2k+1}+a_{2k+2}\equiv a_1+a_2+\dots +a_{2k}+k+(k+1)\cdot(-1)\equiv S_{2k}-1\pmod 2$$

$$a_{2k+2}+a_{2k+3}\equiv a_1+a_2+\dots +a_{2k} + a_{2k+2}+k+(k+2)\cdot(-1)\equiv S_{2k}+a_{2k+2}\pmod 2$$

Лемма: Для любого $k\in\mathbf N$ верно, что $v_2\left(S_{2k}-1\right)=k+1.$

Доказательство: Будем доказывать по индукции. Для $k=1:\ v_2(S_2-1)=v_2(21-1)=2=k+1.$

Пусть для некоторого $k$ лемма верна. Из условия следует, что

$$a_{2k+1}+a_{2k+2}\equiv S_{2k}-1 \pmod {2^{2k+2}} \implies S_{2k+2}\equiv 2S_{2k}-1 \pmod {2^{2k+2}}$$

$$\implies S_{2k+2}-1\equiv 2\left(S_{2k}-1\right)\pmod {2^{2k+2}}\implies v_2\left(S_{2k+2}-1\right)=v_2(S_{2k}-1)+v_2(2)=(k+1)+1,$$

так как $v_2\left(2\left(S_{2k}-1\right)\right)=k+2<2k+2=v_2\left(2^{2k+2}\right).$ Переход доказан. $\quad\square$

Заменим $t=2012^{2012}.$ Пусть $m$ наименьшее число такое, что $2^t\mid S_m^t-1.$ Ясно, что $m=2n,$ тогда из $LTE$ получаем, что

$\big($ поскольку $4\mid S_{2n}-1$ $\big)$

$$t\le v_2\left(S_{2n}^t-1 \right)=v_2(S_{2n}-1)+v_2(t)=(n+1)+v_2(t)$$

$$\implies n\ge t-v_2(t)-1=2012^{2012}-4025\implies m=2n\ge 2\cdot\left(2012^{2012}-4025\right).$$

Очевидно, что $m=2\cdot\left(2012^{2012}-4025\right)$ подходит. Значит ответ: $\boxed{m=2\cdot\left(2012^{2012}-4025\right)}$