10. Konvergujúca Mamutia Šmakocinka vzorové riešenie

Počas riešenia budeme nazývať \(a_{i+1}=\frac {a_i}2\) ťah prvého typu, a \(a_{i+1}=2a_i^2\) ťah druhého typu. Tak na začiatok si premyslime, že sa chceme zaoberať iba nezápornými postupnosťami \(\{a_n\}_{n=0}^{2020}\). Teda oba možné kroky vyrobia z nezáporného \(a_i\) nezáporné \(a_{i+1}\) a krok typu dva vyrobí zo všetkého nezáporné číslo. Teda teraz keby sme mali nejaké začínajúce číslo \(a_0<0\), tak ak niektorý z našich krokov by bol druhého typu, tak odtiaľ by sme mali nezápornú postupnosť, a teda platilo by \(a_0<0\leq a_{2020}\), čo je pre nás nevyhovujúca postupnosť. Teda všetky ťahy by mali byť prvého typu, ale kvôli zápornosti \(a_0\) by znova platilo \(a_0<a_{2020}\). Teda nutne platí \(a_0\geq0\). Teraz si poďme rozobrať prípady:

1. Môžeme si všimnúť, že ak \(a_0=\frac 12\), tak oba možné ťahy z neho spravia znovu \(\frac 12\) a pripíše sa k našej sume \(0\) alebo \(a_0=\frac 12\). Teda keď vždy pripíšeme \(a_0=\frac 12\), dostaneme sumu \(1010\). Ideme si ukázať, že táto hodnota je maximálna dosiahnuteľná.

2. Ak \(0\leq a_0\leq \frac 12\), tak aj \(0\leq a_1\leq \frac 12\), a teda pre všetky \(i\) platí \(0\leq a_i\leq \frac 12\), z čoho hneď vyplýva \(0\leq b_i\leq \frac 12\), teda \(\sum_{i=1}^{2020}b_i\leq 2020\cdot\frac12=1010\).

3. Zostáva nám overiť prípad \(a_0>\frac12\). Chceli by sme skonštruovať nejaký monovariant¹ pre našu postupnosť, ktorý sa bude dať používať pri neskorších odhadoch. Preto si definujeme funkciu \(f : \{1, 2,\dots, 2020\} \rightarrow\mathbb{R}\)² nasledovne: \[f(n) = b_1 + \cdots + b_n -\frac n2-a_n.\] Pre túto funkciu, pre všetky rozumné \(n\) platí \(f(n + 1) \leq f(n)\):

a) Ak \(a_{n+1} = \frac{a_n}{2}\) a \(b_{n+1}=\frac12-a_n\), tak \[f(n+1) = b_1 + \cdots + b_n + b_{n+1}-\frac{n+1}{2}-a_{n+1}=\] \[= f(n) + a_n + b_{n+1}-\frac 12-a_{n+1}= f(n)-a_{n+1} \leq f(n).\]

b) Ak \(a_{n+1} = 2a_n^2\) a \(b_{n+1} = a_n\), tak \[f(n+1)=b_1+\cdots+b_n+b_{n+1}-\frac{n+1}{2}-a_{n+1}=\] \[=f(n)+a_n+b_{n+1}-\frac12-a_{n+1}=\] \[=f(n)+a_n+a_n-\frac{1}{2}-2a_n^2=\] \[= f(n)-\frac12(2a_n-1)^2\leq f(n).\]

Platí teda \(f(2020) \leq f(2019) \leq f(2018) \leq \cdots \leq f(1)\), takže \(f(2020) \leq f(1),\) \[b_1+\cdots+b_{2020}-1010-a_{2020}\leq b_1-\frac12-a_1,\] \[b_1+\cdots+b_{2020}\leq1010+a_{2020}+b_1-\frac12-a_1.\] Podľa zadania platí \(a_{2020}\leq a_0\). Ak \(a_1 =\frac{a_0}{2}\) a \(b_1=\frac12-a_0\), tak \[b_1 + \cdots + b_{2020} \leq 1010+a_0+\frac12-a_0-\frac12-\frac{a_0}{2}=1010-\frac{a_0}{2}\leq 1010.\] V opačnom prípade, teda keď \(a_1=2a_0^2\) a \(b_1=a_0\), platí \[b_1 + \cdots + b_{2020} \leq1010+a_0+a_0-\frac12-2a_0^2=1010-\frac12(2a_0-1)^2\leq1010.\] Hodnota výrazu \(b_1 + \cdots + b_{2020}\) tak môže byť nanajvýš \(1010\) a túto hodnotu už môže dosiahnuť, napríklad pre tieto dve postupnosti: \[a_0=a_1=a_2=\cdots=a_{2020}=0 \quad \text{a} \quad b_1=b_2=\cdots=b_{2020}=\frac12,\] \[a_0=a_1=a_2=\cdots=a_{2020}=\frac12 \quad \text{a} \quad b_1=b_2=\cdots=b_{2020}=\frac12.\]