\documentclass{article}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{fullpage}
\usepackage{verbatim}
\usepackage[estonian]{babel}
\usepackage{titling}

\newcommand{\Mat}{\operatorname{Mat}}
\newcommand{\e}{\varepsilon}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\bb}{\mathbb}
\everymath{\displaystyle}

\begin{document}
\title{Matemaatika treeningvõistlus}
\date{Tartu, 19.03.2021}
\maketitle
\thispagestyle{empty}

\begin{enumerate}
\item
Olgu $(a_n)$ mittenegatiivsete reaalarvude jada. Tähistame
\[
x_n := \sqrt{a_1 + \sqrt{a_2 + \dots + \sqrt{a_n}}},
\]
kus parempoolses avaldises on $n$ juuremärki; näiteks $x_1 = \sqrt{a_1}$ ja $x_4 = \sqrt{a_1 + \sqrt{a_2 + \sqrt{a_3 + \sqrt{a_4}}}}$.
\begin{enumerate}
\item
Juhul, kui $a_n = a > 0$ iga $n \in \bb N$ korral, leia piirväärtus $\lim x_n$,
\item
juhul, kui $a_n > 1$ iga $n \in \bb N$ korral ja $\lim \frac 1 n \ln (\ln a_n) < \ln 2$, tõesta, et leidub lõplik piirväärtus $\lim x_n$.
\end{enumerate}

\item
Mitme positiivse täisarvu $n < 10^{2021}$ korral $n^2 -n$ jagub arvuga $10^{2021}$?
\item
Olgu $G$ lõplik rühm. Iga $x \in G$ korral tähistame
$N_x = \{y \in G \mid yx = xy\}$ ja $K_x = \{y^{-1}xy \mid y \in G\}$.
Tõesta, et
\begin{enumerate}
\item
$|G| = |K_x| \cdot |N_x|$ iga $x \in G$ korral,
\item
kui $|G| = 121$, siis leiduvad $g, h \in G$ nii, et $g \neq h$ ja $N_g = N_h = G$.
\end{enumerate}

\item
Milliste $d \geq 2$ jaoks leidub kasvav funktsioon $f \colon [0,\infty) \to (0, \infty)$ nii, et 
\[
\int_0^y f(x)^2 dx \geq \left(\int_0^y f(x) dx\right)^d
\]
iga $y > 0$ korral?
\item
Olgu $P(x)$ reaalkordajatega polünoom, kusjuures $P(x) \geq 0$ iga $x\in \bb R$ korral. Tõesta, et leiduvad 
reaalkordajatega polünoomid $Q(x)$ ja $R(x)$ nii, et
$P(x) = Q(x)^2 + R(x)^2$ iga $x \in \bb R$ korral.
\end{enumerate}


\newpage
\title{Math Competition}
\date{Tartu, 19.03.2021}
\maketitle
\thispagestyle{empty}
\begin{enumerate}
\item
Let $(a_n)$ be a sequence of non-negative real numbers. Denote
\[
x_n := \sqrt{a_1 + \sqrt{a_2 + \dots + \sqrt{a_n}}},
\]
where there are $n$ square root operations; e.g., $x_1 = \sqrt{a_1}$ and $x_4 = \sqrt{a_1 + \sqrt{a_2 + \sqrt{a_3 + \sqrt{a_4}}}}$.
\begin{enumerate}
\item
In case, when $a_n = a > 0$ for all $n \in \bb N$, find $\lim x_n$,
\item
in case, when $a_n > 1$ for all $n \in \bb N$ and $\lim \frac 1 n \ln (\ln a_n) < \ln 2$, prove that $\lim x_n$ exists and is finite.
\end{enumerate}

\item
For how many positive integers $n < 10^{2021}$ it is true that $n^2 -n$ is divided by $10^{2021}$?
\item
Let $G$ be a finite group. For all $x \in G$ denote
$N_x = \{y \in G \mid yx = xy\}$ and $K_x = \{y^{-1}xy \mid y \in G\}$.
Prove that
\begin{enumerate}
\item
$|G| = |K_x| \cdot |N_x|$ for all $x \in G$,
\item
if $|G| = 121$, there there exist $g, h \in G$ such that $g \neq h$ and $N_g = N_h = G$.
\end{enumerate}

\item
For which $d \geq 2$ there exists an increasing function $f \colon [0,\infty) \to (0, \infty)$ such that
\[
\int_0^y f(x)^2 dx \geq \left(\int_0^y f(x) dx\right)^d
\]
for all $y > 0$?
\item
Let $P(x)$ be a polynomial with real coefficients such that $P(x) \geq 0$ for all $x\in \bb R$. Prove that there exist polynomials $Q(x)$ and $R(x)$ with real coefficients such that
$P(x) = Q(x)^2 + R(x)^2$ for all $x \in \bb R$.
\end{enumerate}

\newpage
\paragraph{Lahendused}
\begin{enumerate}
\item
Kuna mõlemal korral jada on rangelt kasvav, siis piirväärtuse olemasolu jaoks piisab näidata, et jada on ülalt tõkestatud.
\begin{enumerate}
\item
Paneme tähele, et $x_{n+1}^2 = a + x_n$. Olgu $c$ ruutvõrrandi $x^2 = a + x$ positiivne lahend ehk $c = \frac{1 + \sqrt{1 + 4a}}2$. Siis $c > \sqrt{a} = x_1$.
Seega $x_2^2 = a + x_1 < a + c = c^2$ ehk $x_2 < c$ jne tõttu saame, et $x_n < c$ iga $n \in \bb N$ korral. Seega leidub lõplik $x := \lim x_n$. Minnes esialgses rekurrentses võrrandis piirväärtusele saame, et $x^2 = a + x$ ehk $x = c$.
\item
Eeldus ütleb, et $a_n < e^{2^n}$, kui $n$ on piisavalt suur. Seega leidub mingisugune $a > 0$ nii, et $a_n < ae^{2^n}$ kõigi $n$ korral. Nüüd 
$a_{n-1} + \sqrt{a_n} < ae^{2^{n-1}} + \sqrt{ae^{2^n}} = e^{2^{n-1}}(a + \sqrt{a})$. Jätkates edasi, saame, et
$x_n < e (\sqrt{a + \sqrt{a + \dots + \sqrt{a}}}) < ec$ (eelmise punkti tähistusega).
\end{enumerate}
\item
Tähistame $S_k = \{0 < n < 10^k \mid 10^k | n^2 -n \}$.
Paneme tähele, et $S_1 = \{1, 5, 6\}$.
Vaatame suvalist arvu $y = 10^{k}a + b \in S_{k+1}$, kus $0 \leq a < 10$ ja $0 \leq b < 10^{k}$. Siis $0 \equiv y^2 - y \equiv b^2 - b \ (\mbox{mod }10^k)$ ehk $b \in S_k$. Teisel poolt, kui $b \in S_k$, siis 
$10^k a + b \in S_{k+1}$ parajasti siis, kui
\[
10^{2k} a^2 + 2ab\cdot 10^k + b^2 - 10^k a - b = n \cdot 10^{k+1}
\]
ehk (tähistades $b^2 -b = 10^k z$ mingi $z \in \bb N$ korral) 
\[
10^{k} a^2 + 2ab - a + z = n \cdot 10,
\]
kust $a(2b-1) \equiv z \ (\mbox{mod }10)$. On selge, et $2b - 1 \not \equiv 0$. Ka $2b - 1 \not \equiv 5$, sest $b \equiv 3$ on vastuolus võrdusega $b^2 - b \equiv 0$. Seega $2b-1$ on pööratav ringis $\bb Z_{10}$
ja $a \equiv z(2b-1)^{-1}$ on üheselt määratud. Seetõttu hulgad $S_{k+1}$ ja $S_k$ on üksüheses vastavuses ning $|S_{k+1}| = |S_k| = |S_1| = 3$.
\item
\begin{enumerate}
\item
Paneme tähele, et $a^{-1}xa = b^{-1}xb \iff ba^{-1}x = xba^{-1} \iff ba^{-1} \in N_x \iff b \in N_x\cdot a$.
Olgu $|K_x| = m$ ja $a_1, \dots, a_m$ sellised, et kõik $a_i^{-1}xa_i$ on paarikaupa erinevad. Siis hulgad $N_x\cdot a_i$ on paarikaupa ühisosata ning moodustavad rühma $G$ klassijaotuse. Kuid $|N_x \cdot a_i| = |N_x|$, mistõttu $|G| = m |N_x|$.
\item
On lihtne kontrollida, et $y \in K_x \iff x \in K_y \iff K_x = K_y$. Seega leiduvad $x_1, \dots, x_n$ nii, et hulgad $K_{x_i}$ on paarikaupa ühisosata ja moodustavad rühma $G$ klassijaotuse. Seega
$|G| = \sum_{i=1}^n |K_{x_i}|$. Eelmisest osast teame, et $|G| = 11^2$ jagub arvuga $|K_{x_i}|$, mistõttu
$|K_{x_i}|$ on kas $1$ või jagub arvuga $11$.
Tähistagu $c$ nende indeksite $i$ arv, mille korral $|K_{x_i}| = 1$ (paneme tähele, et see on samaväärne tingimusega $N_{x_i} = G$). Siis $c$ samuti peab jaguma arvuga $11$.
Kuna $N_{e} = G$ ühikelemendi $e \in G$ korral, siis $c \neq 0$, kust $c \geq 11 \geq 2$, nagu vaja.
\end{enumerate}
\item
Juhul $d > 2$ paneme tähele, et 
\[
f(y)\int_0^y f(x) dx  \geq \int_0^y f(x)^2 dx \geq \left(\int_0^y f(x) dx\right)^d,
\]
millest
\[
f(y) \geq \left(\int_0^y f(x) dx\right)^{d-1}
\]
ehk $F'(y) \geq F(y)^{d-1}$, kus $F(y) = \int_0^y f(x) dx > 0$ on kasvav funktsioon. Saame, et 
$1 \leq F'(y) F(y)^{1-d} = \frac{(F(y)^{2-d})'}{2-d}$ ehk $\left(\frac{1}{\alpha F(y)^\alpha}\right)' \leq -1$, kus $\alpha = d-2 > 0$. Seega $g'(y) \leq -1$ igas punktis $y \in (0,\infty)$ mingi funktsiooni $g:(0,\infty) \to (0,\infty)$ korral. Seda ei saa olla, sest siis $g(b) - g(a) \leq a - b$, kust $g(b) \leq a + g(a) - b$, mistõttu $g(a + g(a)) \leq 0$.

Juhu $d = 2$ jaoks sobib funktsioon $f(x) = e^{e^{x+1}} e^{x+1}$. Tõepoolest, $\int_0^y f(x) dx = \left.e^{e^{x+1}}\right|_0^y = e^{e^{y+1}} - e^e$ ja
\[
\int_0^y f(x)^2 dx = \int_0^y e^{2e^{x+1}} e^{2(x+1)} dx \geq \int_0^y e^{2e^{x+1}} 2e^{x+1} dx
= \left.e^{2e^{x+1}}\right|_0^y = e^{2e^{y+1}} - e^{2e},
\]
kus me kasutasime võrratuse $e^{2(x+1)} \geq e \cdot e^{x+1} \geq 2e^{x+1}$. Nõutud võrratus nüüd kehtib, kuna $a^2 - b^2 \geq (a-b)^2$, kui $a \geq b > 0$.
\item
Paneme tähele, et 
\[
(Q_1^2 + R_1^2)(Q_2^2 + R_2^2) = (Q_1Q_2 + R_1R_2)^2 + (Q_1 R_2 - Q_2 R_1)^2.
\]
Seega meil piisab esitada $P$ sobivate polünoomide korrutisena.
Olgu 
\[
P(x) = 
a\prod_{i=1}^n (x-x_i)^{k_i} \cdot \prod_{j=1}^m (x-z_j)(x-\bar z_j),
\]
kus $a > 0$, $x_i \in \bb R$ ja $z_j \in \bb C \setminus \bb R$. Paneme tähele, et iga $k_i$ on paarisarv, sest muidu $P(x)$ vahetaks oma märgi vähemalt üks kord. Jääb märgata, et $a = (\sqrt{a})^2 + 0^2$, $(x-x_i)^k_i = ((x-x_i)^{k_i/2})^2 + 0^2$ ja
\[
(x-z_j)(x-\bar z_j) = (x - \mbox{Re}\, z_j)^2 + (\mbox{Im}\, z_j)^2.
\]
\end{enumerate}
\end{document}
