\documentclass[12pt]{article}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{fullpage}
\usepackage{verbatim}
\usepackage{comment}
\usepackage{enumerate}
\usepackage[english,estonian]{babel}
\usepackage{titling}
\DeclareMathOperator{\Realpart}{Re}
\DeclareMathOperator{\res}{res}

\newcommand{\Mat}{\operatorname{Mat}}
\newcommand{\e}{\varepsilon}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\rea}{\operatorname{Re}}
\everymath{\displaystyle}
\renewcommand{\geq}{\geqslant}
\renewcommand{\leq}{\leqslant}

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

\begin{enumerate}
\item Vaatleme Fibonacci jada $(F_n)$, mis on defineeritud valemitega $F_1=1$, $F_2=1$ ja $F_{n+2}=F_{n+1}+F_n$ iga $n\in\mathbb{N}$ jaoks. Tõestage, et
\[
F_n =\left|\begin{array}{rrrrrrr}
1&-1&1&-1&1&-1&\ldots\\
1&1&0&1&0&1&\ldots\\
0&1&1&0&1&0&\ldots\\
0&0&1&1&0&1&\ldots\\
0&0&0&1&1&0&\ldots\\
0&0&0&0&1&1&\ldots\\
\hdotsfor{7}
\end{array}\right|,\qquad n\geq 2,
\]
kus paremal seisev maatriks on $(n-1)$. järku, esimeses reas on vaheldumisi $1$ ja $-1$ ning igal järgneval real on alguses (ühekaupa suurenev arv) nulle, edasi paiknevad $1$ ja $1$ ning edasi vaheldumisi nullid ja ühed.

\item Leidke rea
\[
\arctan\frac1{2}+\arctan\frac1{8}+\arctan\frac1{18}+\ldots+\arctan\frac1{2n^2}+\ldots
\]
summa või tõestage, et see rida on hajuv.

\item Olgu $a>0$. Olgu funktsioon $f\colon(a,\infty)\to\mathbb{R}$ diferentseeruv ning kehtigu
\[
\lim_{x\to\infty} f'(x)=0.
\]
Tõestage, et
\[
\lim_{x\to\infty}\frac{f(x)}{x}=0.
\]

\item 
Olgu $p$, $q$, $r$ ja $s$ sellised positiivsed täisarvud, et $p\geq q\geq r$, $p<q+r$ ning $p+q+r=2s$. On olemas $p$ musta, $q$ valget ja $r$ punast kuuli. Tõestage, et need kuulid saab täpselt \[s^2+s+1-\frac12(p^2+q^2+r^2)\] viisil jaotada kahe isiku vahel nii, et kumbki saaks $s$ kuuli.

\item Liouville on tõestanud, et kui $f$ ja $g$ on ratsionaalmurrud (jagatised kujul $\frac pq$, kus $p,q\in\mathbb{R}[x]$, $q\ne0$), kusjuures $\deg g>0$, ning määramata integraal
\[
\int f(x)\mathrm{e}^{g(x)}\,\mathrm{d}x
\]
on elementaarfunktsioon, siis
\[
\int f(x)\mathrm{e}^{g(x)}\,\mathrm{d}x = h(x)\mathrm{e}^{g(x)}+C,
\]
kus $h$ on mingi ratsionaalmurd.

Tõestage, et 
\[
\int\mathrm{e}^{-x^2}\,\mathrm{d}x
\]
ei ole elementaarfunktsioon. (Liouville'i tulemust võib tõestuseta kasutada.)

\emph{Märkus 1.} Elementaarfunktsioonid on reaalsete väärtustega reaalmuutuja funktsioonid, mis on liitmise, korrutamise, jagamise ja kompositsiooni korduva rakendamise teel saadud järgmist liiki funktsioonidest: polünoomfunktsioonid, astmefunktsioon $x\mapsto x^a$, eksponentfunktsioon $x\mapsto a^x$, logaritmfunktsioon $x\mapsto \log_a x$, trigonomeetrilised funktsioonid ja arkusfunktsioonid.

\emph{Märkus 2.} Kuna kõik algfunktsioonid erinevad üksteisest vaid konstandi võrra, tuleb väljendit "`määramata integraal on/ei ole elementaarfunktsioon"' tõlgendada kui "`integrandi kõik algfunktsioonid on/ei ole elementaarfunktsioonid"', kuna kui neist juba üks on elementaarfunktsioon, on nad seda kõik, ja kui mõni ei ole, ei saa ka teised olla.
\end{enumerate}



\newpage
\selectlanguage{english}
\title{Math Competition}
\date{Tartu, 10.03.2023}
\maketitle
\thispagestyle{empty}
\begin{enumerate}
\item Consider the Fibonacci sequence $(F_n)$ defined by $F_1=1$, $F_2=1$ and $F_{n+2}=F_{n+1}+F_n$ for every $n\in\mathbb{N}$. Prove that
\[
F_n =\left|\begin{array}{rrrrrrr}
1&-1&1&-1&1&-1&\ldots\\
1&1&0&1&0&1&\ldots\\
0&1&1&0&1&0&\ldots\\
0&0&1&1&0&1&\ldots\\
0&0&0&1&1&0&\ldots\\
0&0&0&0&1&1&\ldots\\
\hdotsfor{7}
\end{array}\right|,\qquad n\geq 2,
\]
where the matrix in the rhs has order $(n-1)$, its first row contains alternatingly $1$ and $-1$, and all the following rows start with an (increasing by one) number of zeros, followed by $1$ and $1$, and after that alternatingly zeros and ones.

\item Find the sum of the following series
\[
\arctan\frac1{2}+\arctan\frac1{8}+\arctan\frac1{18}+\ldots+\arctan\frac1{2n^2}+\ldots
\]
or prove that it diverges.

\item Let $a>0$. Let a function $f\colon(a,\infty)\to\mathbb{R}$ be differentiable and assume that 
\[
\lim_{x\to\infty} f'(x)=0.
\]
Prove that
\[
\lim_{x\to\infty}\frac{f(x)}{x}=0.
\]

\item 
Let $p$, $q$, $r$, and $s$ be positive integers such that $p\geq q\geq r$, $p<q+r$, and $p+q+r=2s$. Assume that there are $p$ black, $q$ white and $r$ red balls. Prove that these balls can be divided among two persons such that both of them get $s$ balls, exactly in \[s^2+s+1-\frac12(p^2+q^2+r^2)\] ways.

\item Liouville proved that if $f$ and $g$ are rational fractions (quotients in a form $\frac pq$, where $p,q\in\mathbb{R}[x]$, $q\ne0$), whereas $\deg g>0$, and the indefinite integral
\[
\int f(x)\mathrm{e}^{g(x)}\,\mathrm{d}x
\]
is an elementary function, then 
\[
\int f(x)\mathrm{e}^{g(x)}\,\mathrm{d}x = h(x)\mathrm{e}^{g(x)}+C,
\]
where $h$ is some rational fraction.

Prove that
\[
\int\mathrm{e}^{-x^2}\,\mathrm{d}x
\]
is not elementary function. (One can use Liouville's result without proof.)

\emph{Remark 1.} The elementary functions are real-valued functions of a real variable such that they have been obtained using repeated application of addition, multiplication, division and composition from the following functions: polynomial functions, power function $x\mapsto x^a$, exponent function $x\mapsto a^x$, logarithm function $x\mapsto \log_a x$, trigonometric functions and arcfunctions.

\emph{Remark 2.} Since all primitive functions differ by a constant, the phrase ``indefinite integral is/is not an elementary function'' must be interpreted as ``all primitive functions of the integrand are/are not elementary functions''. Indeed, if one of the primitive functions already is an elementary function, then they all are elementary functions, and if some of them is not, then none of them can be elementary functions.

\end{enumerate}

\newpage
\selectlanguage{estonian}
\section*{Lahendused}
\begin{enumerate}
\item Tähistame uuritava maatriksi tähega $G_n$. Paneme tähele, et
\[
G_2=\begin{vmatrix} 1\end{vmatrix}=1,\qquad G_3=\begin{vmatrix} 1 & -1\\ 1 & 1\end{vmatrix}=2,\qquad G_4=\begin{vmatrix} 1& -1& 1\\ 1 & 1 &0\\ 0 & 1 & 1\end{vmatrix}=3.
\]
Üldise $G_n$ (kus $n\geq4$) arvutamiseks lahutame $(n-1)$. veerust $(n-3)$. veeru, seejärel $(n-2)$. veerust $(n-4)$. veeru ja nii edasi, kuni lõpuks $3$. veerust $1$. veeru. Tulemusena saame, et
\[
G_n =\left|\begin{array}{rrrrrrr}
1&-1&0&0&0&0&\ldots\\
1&1&-1&0&0&0&\ldots\\
0&1&1&-1&0&0&\ldots\\
0&0&1&1&-1&0&\ldots\\
0&0&0&1&1&-1&\ldots\\
0&0&0&0&1&1&\ldots\\
\hdotsfor{7}
\end{array}\right|.
\]
Saadud kolmediagonaalse maatriksi determinant on lihtsasti leitav, kui teostada arendamine esimese rea järgi. Saame, et 
\begin{align*}
G_n &=\left|\begin{array}{rrrrrr}
1&-1&0&0&0&\ldots\\
1&1&-1&0&0&\ldots\\
0&1&1&-1&0&\ldots\\
0&0&1&1&-1&\ldots\\
0&0&0&1&1&\ldots\\
\hdotsfor{6}
\end{array}\right|+\left|\begin{array}{rrrrrr}
1&-1&0&0&0&\ldots\\
0&1&-1&0&0&\ldots\\
0&1&1&-1&0&\ldots\\
0&0&1&1&-1&\ldots\\
0&0&0&1&1&\ldots\\
\hdotsfor{6}
\end{array}\right|=\\
&=G_{n-1}+\left|\begin{array}{rrrrr}
1&-1&0&0&\ldots\\
1&1&-1&0&\ldots\\
0&1&1&-1&\ldots\\
0&0&1&1&\ldots\\
\hdotsfor{5}
\end{array}\right|=\\
&=G_{n-1}+G_{n-2}.
\end{align*}
Oleme saanud, et $(F_n)=(G_n)$, kuna $G_n$ allub samale rekurrentsele seosele mis $F_n$ ning kaks esimest väärtust on ka samad.

\item \emph{Lahendus 1.} Teadaolevalt
\[
\tan(\alpha+\beta)=\frac{\tan\alpha+\tan\beta}{1-\tan\alpha\tan\beta}.
\]
Valides $\alpha=\arctan x$ ja $\beta=\arctan y$, saame valemi
\begin{equation}\label{arctanvalem}
\arctan x+\arctan y=\arctan\frac{x+y}{1-xy}.
\end{equation}
Valemi \eqref{arctanvalem} abil saame antud rea osasummasid uurida:
\begin{align*}
\arctan \frac12+\arctan\frac18&=\arctan\frac {\frac58}{\frac{15}{16}}=\arctan\frac23,\\
\arctan \frac23+\arctan\frac1{18}&=\arctan\frac{\frac{13}{18}}{\frac{26}{27}}=\arctan\frac{3}{4},
\end{align*}
järelikult võiksime tõestada hüpoteesi, et
\[
S_n=\arctan\frac1{2}+\arctan\frac1{8}+\arctan\frac1{18}+\ldots+\arctan\frac1{2n^2}=\arctan\frac{n}{n+1}.
\]
Induktiivselt leiame, et
\begin{align*}
S_{n+1}&=S_{n}+\arctan\frac1{2(n+1)^2}=\arctan\frac{n}{n+1}+\arctan\frac1{2(n+1)^2}=\arctan\frac{\frac{2n(n+1)+1}{2(n+1)^2}}{1-\frac n{2(n+1)^3}}=\\
&=\arctan\frac{(2n^2+2n+1)(n+1)}{2n^3+6n^2+5n+2}=\arctan\frac{(2n^2+2n+1)(n+1)}{(2n^2+2n+1)(n+1)}=\arctan\frac{n+1}{n+2},
\end{align*}
nagu soovitud.

Järelikult on otsitava rea summaks
\[
\lim_n S_n=\lim_n \arctan\frac{n+1}{n+2}=\arctan 1=\frac\pi4.
\]

\emph{Lahendus 2.} Kuna $-\arg\left(1-\frac{\mathrm{i}}{2n^2}\right)=\arctan\frac1{2n^2}$ ning kompleksarvude korrutamisel argumendid (nurgad) liituvad, siis
\[
S_n=\sum_{k=1}^n\arctan\frac1{2k^2}=\sum_{k=1}^n\left(-\arg\left(1-\frac{\mathrm{i}}{2k^2}\right)\right)=-\arg\prod_{k=1}^n\left(1-\frac{\mathrm{i}}{2k^2}\right).
\]
Minnes võrduse pooltel piirile (rida on koonduv, sest $\arctan \frac1{2n^2}\sim \frac1{2n^2}$ ja liikmetega $\frac1{2n^2}$ üldistatud harmooniline rida on koonduv) ja kasutades Euleri korrutist $\frac{\sin \pi z}{\pi z}=\prod_{n=1}^\infty\left(1-\frac{z^2}{n^2}\right)$, saame, et
\[
\lim_n S_n = -\arg\prod_{k=1}^\infty\left(1-\frac{\mathrm{i}}{2n^2}\right)=
-\arg\prod_{k=1}^\infty\left(1-\frac{\left(\sqrt{\frac{\mathrm{i}}{2}}\right)^2}{n^2}\right)=
-\arg \frac{\sin \pi\sqrt{\frac{\mathrm{i}}{2}}}{\pi\sqrt{\frac{\mathrm{i}}{2}}}.
\]
Leiame juure $\sqrt{\frac{\mathrm{i}}{2}}$ väärtused.
Kuna \[
\frac{\mathrm{i}}{2}=\frac12\exp \mathrm{i}\frac\pi2,
\]
siis
\begin{align*}
\sqrt{\frac{\mathrm{i}}{2}}&=\left\{\frac{1}{\sqrt{2}}\exp\mathrm{i}\left(\frac\pi4+k\pi\right)\colon k\in\{0,1\}\right\}=\\
&=\left\{\frac{1}{\sqrt{2}}\exp\mathrm{i}\frac\pi4,
\frac{1}{\sqrt{2}}\exp\mathrm{i}\frac{5\pi}4\right\}=\pm\frac12(1+\mathrm{i})
\end{align*}

Saame, et
\[
\sin \left(\frac{\pi}{2}+\frac{\mathrm{i}\pi}{2}\right)=\sin\frac\pi2\cos\frac{\mathrm{i}\pi}{2}+\cos\frac\pi2\sin\frac{\mathrm{i}\pi}{2}=\cos\frac{\mathrm{i}\pi}{2}=\cosh\frac\pi2>0.
\]
Seega 
\[
\lim_n S_n=-\arg \frac{\sin \pi\sqrt{\frac{\mathrm{i}}{2}}}{\pi\sqrt{\frac{\mathrm{i}}{2}}}=
-\arg \frac{1}{1+\mathrm{i}}=
-\arg\left(\frac12-\frac{\mathrm{i}}{2}\right)=-\left(-\frac\pi4\right)=\frac\pi4.
\]


\item Kehtigu ülesande eeldused. Väite $\lim_{x\to \infty} \frac{f(x)}{x}=0$ tõestamiseks kasutame Heine kriteeriumit. Valime suvalise jada $(x_n)$, $x_n>a$, omadusega $\lim_n x_n=\infty$. Meie eesmärk on tõestada, et $\lim_n \frac{f(x_n)}{x_n}=0$ ehk
\begin{equation}\label{koond}
\forall \varepsilon>0\,\exists N\in\mathbb{N}\colon \forall n\in\mathbb{N}\quad\left(n>N \Rightarrow \left|\frac{f(x_n)}{x_n}\right|<\varepsilon\right).
\end{equation}

Fikseerime $\varepsilon>0$, siis ülesande eelduse tõttu leidub selline reaalarv $D>a$, et iga reaalarvu $x$ korral kehtib implikatsioon
\[
x>D\Rightarrow |f'(x)|<\frac\varepsilon3.
\]

Lisaks, koondumise $\lim_n x_n=\infty$ tõttu leidub naturaalarv $N_0$ nii, et kui $n\geq N_0$, siis $x_n>D$. (See muidugi annab siis ka, et $|f'(x_n)|<\frac\varepsilon3$.)

Olgu $n>N_0$. Vaatleme punkte $x_n$ ja $x_{N_0}$. Eeldusel, et need punktid on erinevad, rahuldab funktsioon $f$ nende otspunktidega lõigus Lagrange'i keskväärtusteoreemi eeldusi, mistõttu
\[
f(x_n)-f(x_{N_0})=(x_n-x_{N_0})f'(c_n),
\]
kus $c_n$ asub $x_n$ ja $x_{N_0}$ vahel (seega $c_n>D$). (Selline võrdus kehtib ka juhul, kui $x_n=x_{N_0}$, siis näiteks $c_n=x_n$ ja võrduse mõlemal poolel on nullid.) Järelikult
\[
|f(x_n)|-|f(x_{N_0})|\leq |f(x_n)-f(x_{N_0})|=|x_n-x_{N_0}|\cdot |f'(c_n)|<\frac\varepsilon3\cdot |x_n-x_{N_0}|,
\]
millest saame, et
\[
\frac{|f(x_n)|}{x_n}<\frac{|f(x_{N_0})|}{x_n}+\frac\varepsilon3 \cdot\frac{|x_n-x_{N_0}|}{x_n}.
\]

Kuna $\lim_n \frac1{x_n}=0$, siis leidub naturaalarv $N_1$, et kui $n\geq N_1$, siis $\frac{|f(x_{N_0})|}{x_n}<\frac\varepsilon3$. Lisaks sellele, koondumise 
\[
\frac{|x_n-x_{N_0}|}{x_n}=\left|1-\frac{x_{N_0}}{x_n}\right|\to 1
\]
tõttu leidub naturaalarv $N_2$, et kui $n\geq N_2$, siis $\frac{|x_n-x_{N_0}|}{x_n}<2$.

Valime $N=\max\{N_0,N_1,N_2\}$. Olgu $n>N$, siis
\[
\left|\frac{f(x_n)}{x_n}\right|=\frac{|f(x_n)|}{x_n}<\frac{|f(x_{N_0})|}{x_n}+\frac\varepsilon3 \cdot\frac{|x_n-x_{N_0}|}{x_n}<\frac\varepsilon3+\frac\varepsilon3\cdot 2=\varepsilon,
\]
nagu soovitud.

\item Vaatleme formaalset astmerida
\[
P=(1+x+x^2+\ldots+x^p)(1+x+x^2+\ldots+x^q)(1+x+x^2+\ldots+x^r).
\]
Otsitav jaotamisviiside arv on liikme $x^s$ kordaja formaalses astmereas $P$, kuna iga jaotamisviis vastab kindla liidetava valikule igast tegurist (valitud mustade, valgete ja punaste kuulide arv). Kui ühele isikule on kuulid antud, on teisele isikule antavad kuulid sellega üheselt määratud, sest kuulide koguarv on $2s$.

Kuna
\[
(1-x)^{-1}=1+x+x^2+\ldots=\sum_{n=0}^\infty x^n,
\]
siis
\[
-(1-x)^{-2}=1+2x+3x^2+\ldots=\sum_{n=0}^\infty (n+1)x^n
\]
ning
\[
2(1-x)^{-3}=2+3\cdot2 x+4\cdot 3 x^2+\ldots=\sum_{n=0}^\infty(n+1)(n+2)x^n,
\]
mistõttu
\[
(1-x)^{-3}=\sum_{n=0}^\infty\frac{(n+1)(n+2)}{2}x^n=\sum_{n=0}^\infty \binom{n+2}{2} x^n.
\]

Saame, et
\begin{align*}
P(x)&=(1-x^{p+1})(1-x^{q+1})(1-x^{r+1})(1-x)^{-3}=\\
&=(1-x^{r+1}-x^{q+1}-x^{p+1}+\ldots)\left(1+3x+6x^2+\ldots+\binom{n+2}{2}x^n+\ldots\right).
\end{align*}

Kuna $p<q+r$, siis $p<s$, $q<s$ ja $r<s$ ning $q+r>s$. Järelikult liikme $x^s$ kordaja leidmisel tulevad arvesse vaid liikmed 
$1\cdot \binom{s+2}{2}x^s$, $-x^{r+1}\cdot \binom{s-r+1}{2}x^{s-r-1}$, $-x^{q+1}\cdot \binom{s-q+1}{2}x^{s-q-1}$ ja $-x^{p+1}\cdot \binom{s-p+1}{2}x^{s-p-1}$,
aga mitte liikmed, kus vasakult poolt tuleb kokku $x^{r+1}x^{q+1}$ või muud kõrgema astme liikmed.

Et $p+q+r=2s$, siis on otsitav kordaja
\begin{align*}
&\binom{s+2}{2}-\binom{s-r+1}{2}-\binom{s-q+1}{2}-\binom{s-p+1}{2}=\\
&\quad{}=\frac12\left((s+2)(s+1)-(s-r+1)(s-r)-(s-q+1)(s-q)-(s-p+1)(s-p)\right)=\\
&\quad{}=\frac12\left(s^2+3s+2-s^2+(2r-1)s-r^2+r-{}\right.\\
&\quad\quad\left.{}-s^2+(2q-1)s-q^2+q-s^2+(2p-1)s-p^2+p\right)=\\
&\quad{}=\frac12\left(-2s^2+2(p+q+r)s+2-(p^2+q^2+r^2)+(p+q+r)\right)=\\
&\quad{}=\frac12\left(2s^2+2s+2-(p^2+q^2+r^2)\right)=\\
&\quad{}=s^2+s+1-\frac12(p^2+q^2+r^2).
\end{align*}

\item Oletame väitevastaselt, et $\int\mathrm{e}^{-x^2}\,\mathrm{d}x$ on elementaarfunktsioon. Valides Liouville'i tulemuses $f=1$ (konstantne polünoom) ning $g=-x^2$, peab kehtima
\begin{equation}\label{liou}\int\mathrm{e}^{-x^2}\,\mathrm{d}x=h(x)\mathrm{e}^{-x^2}+C,
\end{equation}
kus $h$ on ratsionaalmurd.
Võrduse \eqref{liou} diferentseerimisel saame, et
\[
\mathrm{e}^{-x^2}=h'(x)\mathrm{e}^{-x^2}-2xh(x)\mathrm{e}^{-x^2},\qquad x\in\mathbb{R}
\]
ehk
\[
1=h'(x)-2xh(x),\qquad x\in\mathbb{R}.
\]
Et $h=\frac pq$, kus $p$ ja $q$ on polünoomid (võime eeldada, et $\text{SÜT}(p,q)=1$ ning et $q$ pole nullpolünoom), saame viimase võrduse ümber kirjutada kujul
\[
1=\frac{p'q-pq'}{q^2}-\frac{2x p}{q}
\]
ehk
\begin{equation}\label{polyq}
q^2=p'q-pq'-2xpq
\end{equation}
Saadud võrdus tekitab probleeme polünoomi $q$ tegurite seisukohast.

Kõigepealt, kui polünoom $q$ on konstantne polünoom, olgu $q=A$, siis on võrduse \eqref{polyq} vasakul poolel $0$-astme polünoom, aga parem pool on $p'-2A xp$, seega kindlasti $(\deg p + 1)$-astme polünoom, mis on võimatu.

Olgu nüüd $c$ polünoomi $q$ mõni (kompleksne) juur, olgu $(x-c)^m \parallel q$ (st. teguri $x-c$ kõrgeim aste, millega $q$ veel jagub, on $m$), siis vastavalt tuletise omadustele $(x-c)^{m-1}\parallel q'$. Ent nüüd võrdusest
\[
p q' = (p'-2xp-q)q
\]
järeldub, et $x-c\mid p$, kuna vasakul on teguris $q'$ ainult $m-1$ korda kaksliiget $x-c$, aga paremal on seda kaksliiget (vähemalt) $m$ korda. Tulemus, et $x-c\mid p$ ja $x-c\mid q$ on vastuolus asjaoluga, et $\text{SÜT}(p,q)=1$.

Saadud vastuolu näitab, et $\int\mathrm{e}^{-x^2}\,\mathrm{d}x$ pole elementaarfunktsioon.


\end{enumerate}
\end{document}
