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

\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, 05.11.2021}
\maketitle
\thispagestyle{empty}

\begin{enumerate}
%\item Leidke integraal
%\[
%\int_0^{\frac\pi2}\frac{\sin(x^2)}{\sin(x^2)+\sin((\frac\pi2-x)^2)}\,\mathrm{d}x.
%\]
\item Olgu $n$ naturaalarv, $n\geq 2$, olgu maatriksid $A,B,C\in\mathrm{Mat}_n(\mathbb{R})$ sellised, et \[
ABC=E
\] (sümbol $E$ tähistagu $n$-järku ühikmaatriksit).
Tehke iga võrduse kohta kindlaks, kas see kehtib alati või ei tarvitse mõne sellise maatriksite kolmiku $A,B,C$ korral kehtida: 
\[
BAC=E,\quad ACB=E,\quad CAB=E,\quad BCA=E, \quad CBA=E.
\]

\item Leidke rea
\[
\sum_{k=1}^\infty \frac{k}{k^4+k^2+1}
\]
summa või tõestage, et see rida on hajuv.

\item Tähistagu $p_n$ tõenäosust, et suvaliselt valitud elementidega maatriksi $A\in\mathrm{Mat}_n(\mathbb{Z}_2)$ determinant on nullist erinev.
\begin{enumerate}
\item Leidke $p_n$ väärtus.
\item Tõestage, et leidub piirväärtus $\lim_{n\to\infty}p_n =:p > 0$.
\end{enumerate}
\emph{Märkus.} Korpuse $\mathbb{Z}_2=\{0,1\}$ arvutusreeglid on teatavasti sellised, et liitmine ja korrutamine toimuvad \emph{modulo $2$}, nii siis $a+0=a$, $1+1=0$,  $a\cdot0=0$, $1\cdot 1=1$, kus $a\in\mathbb{Z}_2$.

\item Leidke kõik positiivsed täisarvud $n$, mille korral leidub täisarvmaatriks
\[
A=\left(\begin{array}{cc} a & b \\ c & d\end{array}\right)\in\mathrm{Mat}_2(\mathbb{Z})
\]
nii, et $A^n=E$ ja $A^k\ne E$ kõigi täisarvude $k=1,\ldots,n-1$ korral.
(Sümbol $E$ tähistab ühikmaatriksit $\left(\begin{array}{cc} 1 & 0 \\ 0 & 1\end{array}\right)$.)

\item Olgu funktsioon $f\colon [a,b]\to[a,b]$ sürjektiivne ja diferentseeruv lõigus $[a,b]$. Tõestage, et leiduvad punktid
$x_1,x_2,x_3,x_4\in[a,b]$ nii, et kehtib võrdus
\[
\int_a^b f(x)\,\mathrm{d}x=f(x_1)f'(x_2)(x_3-x_4).
\]

\begin{comment}
\item Vaatleme lauseid:\\[1ex]
(A$_1$)\qquad $\lim_n n(a_{n+1}-a_n)=:a\in\mathbb{R}$,\\
(A$_2$)\qquad $\lim_n \frac{a_1+a_2+\ldots+a_n}{n}=:b\in\mathbb{R}$,\\
(A$_3$)\qquad $\lim_n a_n\in\mathbb{R}$.

Millised alljärgnevatest implikatsioonidest on tõesed suvalise arvjada $(a_n)_{n=1}^\infty$ korral?
\begin{enumerate}
\item (A$_1$)$\Rightarrow$(A$_3$),
\item (A$_2$)$\Rightarrow$(A$_3$),
\item (A$_1$)$\land$(A$_2$)$\Rightarrow$(A$_3$).
\end{enumerate}
\end{comment}
\end{enumerate}

\newpage
\title{Math Competition}
\date{Tartu, 05.11.2021}
\maketitle
\thispagestyle{empty}
\begin{enumerate}
\item Let the matrices $A,B,C\in\mathrm{Mat}_n(\mathbb{R})$ (where $n$ is a natural number greater than $1$) be such that \[
ABC=E\]
(the symbol $E$ denotes the unit matrix of $n$-th order).
Determine for all the following equalities whether it always holds or may not hold for some such matrices $A,B,C$: 
\[
BAC=E,\quad ACB=E,\quad CAB=E,\quad BCA=E, \quad CBA=E.
\]

\item Find the sum of the series
\[
\sum_{k=1}^\infty \frac{k}{k^4+k^2+1}
\]
or prove that the series is divergent.

\item Denote by $p_n$ the probability that the determinant of a matrix $A\in\mathrm{Mat}_n(\mathbb{Z}_2)$ whose elements have been chosen arbitrarily, is not zero.
\begin{enumerate}
\item Find $p_n$.
\item Prove that there exists a limit $\lim_{n\to\infty}p_n =:p > 0$.
\end{enumerate}
\emph{Remark.} As is known, calculation in the field $\mathbb{Z}_2=\{0,1\}$ is defined in a way that addition and multiplication are performed \emph{modulo $2$}, i.e., $a+0=a$, $1+1=0$,  $a\cdot0=0$, $1\cdot 1=1$, where $a\in\mathbb{Z}_2$.

\item Find all positive integers $n$ for which there exists a matrix with integer elements
\[
A=\left(\begin{array}{cc} a & b \\ c & d\end{array}\right)\in\mathrm{Mat}_2(\mathbb{Z})
\]
such that $A^n=E$ and $A^k\ne E$ for all integers $k=1,\ldots,n-1$.
(The symbol $E$ denotes the unit matrix $\left(\begin{array}{cc} 1 & 0 \\ 0 & 1\end{array}\right)$.)

\item Let the function $f\colon [a,b]\to[a,b]$ be surjective and differentiable in $[a,b]$. Prove that there exist points $x_1,x_2,x_3,x_4\in[a,b]$ such that
\[
\int_a^b f(x)\,\mathrm{d}x=f(x_1)f'(x_2)(x_3-x_4).
\]

\end{enumerate}

\newpage

\section*{Lahendused}
\begin{enumerate}
\item Kuna $ABC=E$, siis $(\det A)\cdot(\det B)\cdot (\det C)=\det(ABC)=\det E=1$, järelikult on maatriksid $A,B,C$ kõik pööratavad. Saame, et $CABC=C$, millest $C^{-1}$-ga paremalt korrutades leiame, et $CAB=E$; analoogiliselt saame võrduse $BCA=E$.

Valime nüüd maatriksid $A$ ja $B$ nii, et $AB\ne BA$, siis $ABC\ne BAC$ (sest kui kehtiks $ABC=BAC$, siis paremalt $C^{-1}$-ga korrutades tuleks $AB=BA$, vastuolu). Analoogiliselt saame ka ülejäänud kahe võrduse vääramise.

Konkreetse kontranäite koostamiseks on muidugi palju võimalusi. Võime näiteks tähele panna, et $\left(\begin{array}{cc} 1&2\\ 3&4\end{array}\right)\cdot \left(\begin{array}{cc}2 &1\\ 4&3\end{array}\right)\ne \left(\begin{array}{cc}2 &1\\ 4&3\end{array}\right)\cdot \left(\begin{array}{cc} 1&2\\ 3&4\end{array}\right)$ ning kui $n>2$, siis ülejäänud osas "`jätkata"' neid maatrikseid ühikmaatriksiks (st. mujal nullid, peadiagonaalil ühed).

\begin{comment}
\item
Tähistame
\[
I = \int_0^{\frac\pi2}\frac{\sin(x^2)}{\sin(x^2)+\sin((\frac\pi2-x)^2)}\,\mathrm{d}x,\quad
J = \int_0^{\frac\pi2}\frac{\sin((\frac\pi2-x)^2)}{\sin(x^2)+\sin((\frac\pi2-x)^2)}\,\mathrm{d}x.
\]
Paneme tähele, et 
\[
I+J=\int_0^{\frac\pi2}1\,\mathrm{d}x=\frac\pi2.
\]
Tehes muutujavahetuse $y=\frac\pi2-x$, saame, et $I=J$. Seega
\[
I=\frac{I+J}{2}=\frac\pi4.
\]
\end{comment}

\item Kuna
\[
k^4+k^2+1=(k^2-k+1)(k^2+k+1),
\]
siis
\[
\frac{k}{k^4+k^2+1}=\frac{\frac12}{k^2-k+1}-\frac{\frac12}{k^2+k+1}=f(k-1)-f(k),
\]
kus 
\[
f(x)=\frac{\frac12}{x^2+x+1}.
\]
Niisiis
\[
\sum_{k=1}^n\frac{k}{k^4+k^2+1}=\sum_{k=1}^n (f(k-1)-f(k))=f(0)-f(n)=\frac12\cdot\left(1-\frac1{n^2+n+1}\right),
\]
mistõttu uuritava rea summa (osasummade jada piirväärtus) on $\frac12$.

\emph{Märkus.} Ratsionaalmurdude teooriast on teada, et korpuse $Q(\mathbb{R}[x])$ element $\frac{x}{x^4+x^2+1}$ esitub ühesel moel algmurdude summana, kusjuures iga algmurru nimetajas on lineaarpolünoom või tema aste või reaalarvudes taandumatu ruutpolünoom või tema aste (lugejas on vastavalt $0$- või $1$-astme polünoom). Niisiis algmurdudeks esituse leidmiseks on vaja kõigepealt tegurdada polünoom $x^4+x^2+1$, kuni saame taandumatud tegurid ringist $\mathbb{R}[x]$.

Selleks tegurdamiseks on mitu võimalust. Üks võimalus on selline:
\[
x^4+x^2+1=(x^4+2x^2+1)-x^2=(x^2+1)^2-x^2=(x^2+1-x)(x^2+1+x).
\]
Teine võimalus on panna tähele, et polünoom $x^4+x^2+1\in\mathbb{C}[x]$ tegurdub kergesti lineaarteguriteni kompleksarvudes, kuna tegu on biruutpolünoomiga. Saame, et 
\[
t^2+t+1=0\Leftrightarrow t=\frac{-1\pm\mathrm{i}\sqrt{3}}{2}\Leftrightarrow t=\mathrm{e}^{\pm \frac{2\pi}{3}\mathrm{i}},
\]
mistõttu
\[
x^4+x^2+1=\left(x-\mathrm{e}^{\frac\pi3\mathrm{i}}\right)\cdot \left(x-\mathrm{e}^{\frac{4\pi}3\mathrm{i}}\right)\cdot \left(x-\mathrm{e}^{\frac{2\pi}3\mathrm{i}}\right)\cdot \left(x-\mathrm{e}^{\frac{5\pi}3\mathrm{i}}\right).
\]
Grupeerides tegurid teisiti ümber, saamegi, et
\begin{align*}
x^4+x^2+1&=\left(x-\mathrm{e}^{\frac\pi3\mathrm{i}}\right)\cdot \left(x-\mathrm{e}^{\frac{5\pi}3\mathrm{i}}\right)\cdot \left(x-\mathrm{e}^{\frac{2\pi}3\mathrm{i}}\right)\cdot \left(x-\mathrm{e}^{\frac{4\pi}3\mathrm{i}}\right)=\\
&=(x^2-x+1)(x^2+x+1).
\end{align*}

Niisiis
\[
\frac{x}{x^4+x^2+1}=\frac{\alpha x + \beta}{x^2-x+1}+\frac{\gamma x+\delta}{x^2+x+1}
\]
ehk
\begin{equation}\label{osamur}
x=(\alpha x + \beta)(x^2+x+1)+(\gamma x+\delta)(x^2-x+1).
\end{equation}
Siin kordajad $\alpha,\beta,\gamma,\delta$ määrame kas avades mõlemal poolel sulud ja võrdsustades kordajad (nt näeme kohe, et $\alpha+\gamma=0$, $\beta+\delta=0$ jms), või valides võrduses (\ref{osamur}) $x$-le mugavaid väärtusi (või mõlemat korraga). Töötada võime soovi korral nii ringis $\mathbb{R}[x]$ kui ka ringis $\mathbb{C}[x]$, näiteks valides $x=0$, $x=\mathrm{i}$, $x=1$ jms. Tekkivast lineaarvõrrandisüsteemist leiame, et $\alpha=\gamma=0$, $\beta=\frac12$, $\delta=-\frac12$.

\item a) Kõigi selliste $n$-järku maatriksite koguarv on $2^{n^2}$. Uurime võimaluste arvu, saamaks mittenullist determinanti.

Esimese rea võime valida suvaliselt, v.a. nullrida: selleks on $2^n-1$ võimalust. Teine rida ei tohi olla esimese lineaarkattes ehk ei tohi olla esimese koopia ja ei tohi olla nullrida: $2^n-2$ võimalust. Üldiselt ($k+1$). rida ei tohi olla eelmise $k$ rea lineaarkattes, mille vektorite koguarv (kõikvõimalikud summad ning nullrida) on $2^k$, mistõttu $(k+1)$. rea moodustamiseks on $2^n-2^k$ võimalust. (Lineaarkatte moodustamisel muid võimalusi ei tule kui summad, sest kordajateks saavad olla vaid $0$ ja $1$. Ükski kaks summat ei võrdu, muidu oleks mingite ridade mittetriviaalne lineaarkombinatsioon võrdne nulliga.)

Kokku on mittenulliste determinantide koguarv
\[
(2^n-1)\cdot (2^n-2)\cdots(2^n-2^k)\cdots(2^n-2^{n-1}).
\]
Otsitav tõenäosus on järelikult
\[
p_n=\frac{2^n-1}{2^n}\cdot\frac{2^n-2}{2^n}\cdots\frac{2^n-2^k}{2^n}\cdots\frac{2^n-2^{n-1}}{2^n}=\left(1-\frac1{2^n}\right)\cdot\left(1-\frac1{2^{n-1}}\right)\cdots\left(1-\frac12\right).
\]

b) Saame, et
\[
\lim_{n\to\infty} p_n = \prod_{k=1}^\infty\left(1-\frac1{2^k}\right)\geq\frac12\cdot\left(1-\sum_{k=2}^\infty \frac1{2^k}\right)=\frac14>0.
\]

\emph{Märkus 1.} Lõpmatu korrutise
\[
\prod_{k=1}^\infty \left(1-\left(\frac12\right)^k\right)=\lim_{n\to\infty}\prod_{k=1}^n \left(1-\left(\frac12\right)^k\right)
\]
koonduvust on võimalik uurida logaritmi abil, nimelt logaritmi pidevuse tõttu koondub osakorrutiste jada mittenulliseks piirväärtuseks parajasti siis, kui koondub osakorrutiste logaritmide jada ehk jada liikmetega
\[
q_n=\ln \prod_{k=1}^n \left(1-\left(\frac12\right)^k\right)=\sum_{k=1}^n\ln\left(1-\left(\frac12\right)^k\right)
\]
Kuna 
\[
\lim_{k\to\infty}\frac{\ln\left(1-\frac1{2^{k+1}}\right)}{\ln\left(1-\frac1{2^k}\right)}=\frac12<1,
\]
siis d'Alembert'i tunnuse kohaselt koondub uuritav jada $(q_n)$, järelikult ka uuritav lõpmatu korrutis.

\emph{Märkus 2.}
Uuritav lõpmatu korrutis on Euleri funktsiooni
\[
\phi(q)=\prod_{k=1}^\infty (1-q^k)
\]
väärtus $\phi\left(\frac12\right)$.

\item 
\emph{Lahendus 1.}
Tingimus $A^n=E$ annab, et maatriksi $A$ minimaalne polünoom $p\in \mathbb{Z}[x]$ on tegur polünoomile $x^n-1$.
Olgu kompleksarvud $\varepsilon_k$, $k=0,1,\ldots,n-1$ polünoomi $x^n-1\in \mathbb{C}[x]$ juured ($n$-astme ühejuured). Teadupärast ühejuured on kõik mittereaalsed, välja arvatud $\varepsilon_0=1$ ning paaris $n$ korral ka $\varepsilon_{\frac n2}=-1$.

Kuna minimaalne polünoom on maatriksi karakteristliku polünoomi tegur ning karakteristliku polünoomi aste on $2$, siis on kaks varianti. Esiteks, kui $\deg p=1$, on ainsad võimalused, et $p=x-1$ (seega $A=E$) või $p=x+1$ (seega $A=-E$, järelikult $A^2=E$).

Teiseks, kui $\deg p = 2$, siis on mingid kaks $\varepsilon_k,\varepsilon_\ell$ (kus $k\ne \ell$) polünoomi $p$ juured (kui teda vaadelda elemendina ringis $\mathbb{C}[x]$), kusjuures $\varepsilon_\ell=\overline{\varepsilon_k}=:\varepsilon$, sest $p$ on reaalsete (isegi täisarvuliste) kordajatega. Saame, et $p=(x-\varepsilon)(x-\overline{\varepsilon})=x^2-2(\rea \varepsilon) x+1$. Muuseas $\rea \varepsilon\in\mathbb{Z}$, mistõttu $\rea\varepsilon\in\left\{0,\pm\frac12,\pm1\right\}$.

Juhtum $\rea\varepsilon=0$ tähendab, et $p=x^2+1$, seega $A^2+E=\Theta$ ja järelikult $A^4-E=\Theta$. Sobiv maatriks on $A=\left(\begin{array}{cc} 0&1\\ -1 & 0\end{array}\right)$.

Juhtum $\rea\varepsilon=\frac12$ tähendab, et $p=x^2-x+1$, seega $\varepsilon$ on 6. astme algjuur, mistõttu $A^6=E$. Sobiv maatriks on $A=\left(\begin{array}{cc} 0 & 1 \\ -1 & 1\end{array}\right)$.

Juhtum $\rea\varepsilon=-\frac12$ tähendab, et $p=x^2+x+1$, seega $\varepsilon$ on 3. astme algjuur, mistõttu $A^3=E$. Sobiv maatriks on $A=\left(\begin{array}{cc} 0 & 1 \\ -1 & -1\end{array}\right)$.

Juhtumid $\rea \varepsilon=\pm1$ pole võimalikud, sest siis oleks $p=(x-1)^2$ või $p=(x+1)^2$, aga kuna $p\mid x^n-1$, ei saa polünoomil $p$ olla kordseid juuri.

Kokkuvõttes on kõik variandid $n\in\{1,2,3,4,6\}$.

\emph{Lahendus 2 (Hendrik Vija).} Eeldame, et $n\geq2$ (juhtum $n=1$ lahendub triviaalselt).
Paneme tähele, et $A^2=(a+d)A-(\det A)E$. (Selle võrduse kehtivus on nähtav vahetu arvutamise teel, või arvestades, et maatriksi $A$ karakteristliku polünoomi $\det(A-xE)$ $n-1$. astme liikme kordaja tuleb maatriksi jälg $\tr A$ ning vabaliige tuleb polünoomi väärtus kohal $x=0$ ehk $\det A$. Selliselt arutledes tuleb veel teada, et maatriks ise rahuldab oma karakteristlikku võrrandit.)

Tingimus $(\det A)^n=\det (A^n)=\det E=1$ annab, et $\det A\in\{1,-1\}$.

\begin{itemize}
\item 
Juhul, kui $\det A=-1$, siis $A^2=(\tr A)A+E$, järelikult $A^3=((\tr A)^2+1)A+(\tr A)E$ ning $A^4=((\tr A)^3+2(\tr A))A+((\tr A)^2+1)E$. Üldiselt saab induktsiooniga näidata, et $A^k=p_k(\tr A)A+q_k(\tr A)E$, kus polünoomide jadad $(p_k)$ ja $(q_k)$ rahuldavad järgmisi tingimusi: $q_k=p_{k-1}$ ja $p_k=x\cdot p_{k-1}+q_{k-1}$, $p_1=1$, $q_1=0$.

Ülesande tingimuste kohaselt peab kehtima teatava $n$ korral $A^n=E$ ehk $p_n(\tr A)=0$ ja $q_n(\tr A)=1$. 
Juhul, kui $|\tr A|\geq2$, tõestame induktsiooniga, et $|p_k(\tr A)|\geq|q_k(\tr A)|$, siit nähtub, et sellel juhul pole võimalik täita tingimust $A^n=E$. Tõepoolest, baasjuhul saame, et võrratus kehtib triviaalselt ($|\tr A|\geq1$), sammu teostame järgnevalt:
\[
|p_k(\tr A)|\geq |\tr A|\cdot |p_{k-1}(\tr A)|-|q_{k-1}(\tr A)|\geq |q_{k-1}(\tr A)|\cdot(|\tr A|-1)\geq |q_{k-1}(\tr A)|.
\]
Analoogilise võrratuse tõestame ka juhul, kui $\tr A=1$, siis saame, et $p_k(\tr A)=p_{k-1}(\tr A)+q_{k-1}(\tr A)\geq 2q_{k-1}(\tr A)\geq q_{k-1}(\tr A)$.

Niisiis peab kehtima $\tr A=0$ või $\tr A = -1$. Kui $\tr A=0$, siis $A^2=E$, sobivaks maatriksiks on $A=-E$. Kui $\tr A=-1$, siis saab matemaatilise induktsiooni teel tõestada, et $p_k(-1)=(-1)^k F_k$ ja $q_k(-1)=(-1)^{k-1}F_{k-1}$, kus $(F_k)$ on Fibonacci arvude jada. Seega pole võimalik, et $p_n(-1)=0$ ja $q_n(-1)=1$.

\item 
Olgu nüüd $\det A=1$.
Analoogiliselt eelmise punktiga tuletame seose $A^k=p_k(\tr A)A+q_k(\tr A)E$, kus polünoomide jadad $(p_k)$ ja $(q_k)$ rahuldavad nüüd tingimusi $q_k=-p_{k-1}$ ja $p_k=x\cdot p_{k-1}+q_{k-1}$. Analoogselt eelnevaga annab ka nüüd juhtum $|\tr A|\geq2$ samasuguse vastuolu.

Juhul $\tr A=0$ saame, et $A^2=-E$, mistõttu $A^4=E$.

Juhul $\tr A=1$ saame, et $A^3=-E$, mistõttu $A^6=E$.

Juhul $\tr A=-1$ saame, et $A^3=E$.

Konkreetsed maatriksite näited leiame kõigi juhtude jaoks samamoodi nagu eelmises lahenduses.
\end{itemize}


\item
Integraalarvutuse keskväärtusteoreemi, funktsiooni $f$ pidevuse tõttu lõigus $[a,b]$ ja $f$ sürjektiivsuse tõttu leiduvad arvud $x_1,x_3,x_4\in[a,b]$ nii, et
\[
\int_a^b f(x)\,\mathrm{d}x=f(x_1)(b-a)=f(x_1)(f(x_3)-f(x_4)).
\]
Rakendades funktsioonile $f$ Lagrange'i keskväärtusteoreemi lõigus otspunktidega $x_3$ ja $x_4$, leiame, et
\[
f(x_3)-f(x_4)=f'(x_2)(x_3-x_4),
\]
kus $x_2$ asub punktide $x_3$ ja $x_4$ vahel. Pannes need kaks võrdust kokku, saame otsitava tingimuse.
\end{enumerate}
\end{document}
