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

\begin{enumerate}
\item Olgu antud kaks hajuvat rida $\sum_n a_n$ ja $\sum_n b_n$, kusjuures on teada, et mõlema rea liikmete jadad $(a_n)$ ja $(b_n)$ on kahanevad ning piirväärtusega $0$. Kas rida $\sum_n \min\{a_n,b_n\}$ võib olla koonduv? on alati koonduv? võib olla hajuv? on alati hajuv?

\item Olgu 
\[
A=\left(\begin{array}{rrr}1&-1&0\\-1&2&-1\\ 0&-1&1\end{array}\right).
\]
Leidke kõik reaalarvud $a$, mille korral piirväärtus $\lim_{k\to\infty} a^k A^k$ leidub ning on nullmaatriksist erinev.

\emph{Märkus.} Maatriksite jada $\left(X^{(k)}\right)_{k=1}^\infty$ koondumine maatriksiks $Y$ ehk $\lim_{k\to\infty} X^{(k)}=Y$ tähendab siin seda, et vastavad elementide jadad koonduvad $Y$ vastavaks elemendiks ehk $\lim_{k\to\infty} \max_{i,j}|x^{(k)}_{i,j}-y_{i,j}|=0$.

\item 
Kükametsa Kõrgkoolis õpitakse $2n$ ainet. Kõik kooli lõpetanud üliõpilased on õppinud hinnetele "`A"' ja "`B"'. Ei leidu kaht lõpetanut, kes oleks õppinud ühtemoodi (st. hinnete komplektid ühtiksid), ning ei saa väita, et mõni lõpetanu oleks õppinud paremini kui teine (loeme, et üks üliõpilane õpib teisest paremini, kui tema hinded kõigis ainetes on vähemalt sama head kui teisel ning mõnes aines on hinne koguni parem kui teisel). Milline on Kükametsa Kõrgkooli lõpetanute suurim võimalik arv?

\item Tõestage, et võrrandil
\[
\int_0^x \mathrm{e}^{-t}\left(1+t+\frac{t^2}{2!}+\ldots+\frac{t^{100}}{100!}\right)\,\mathrm{d}t=50
\]
leidub lahend $x_0\in(50,100)$.

\item Olgu $S_{999}$ hulga $\{1,2,\ldots,999\}$ permutatsioonide rühm (\emph{sümmeetriline rühm}). Vaatleme suvalist $1111$-elemendilist kommutatiivset alamrühma $G$ rühmas $S_{999}$. Tõestage, et leidub element $i\in\{1,2,\ldots,999\}$, mis jäetakse kõigi $G$-sse kuuluvate permutatsioonide poolt paigale, st. iga $\sigma\in G$ korral $\sigma(i)=i$.

\end{enumerate}

\newpage
\selectlanguage{english}
\title{Math Competition}
\date{Tartu, 04.11.2022}
\maketitle
\thispagestyle{empty}
\begin{enumerate}
\item Consider two divergent series $\sum_n a_n$ and $\sum_n b_n$ such that the sequences of members $(a_n)$ and $(b_n)$ are decreasing and have the limit $0$. Can the series $\sum_n \min\{a_n,b_n\}$ be convergent? Must it always be convergent? Can it be divergent? Must it always be divergent?

\item Let
\[
A=\left(\begin{array}{rrr}1&-1&0\\-1&2&-1\\ 0&-1&1\end{array}\right).
\]
Find all real numbers $a$ for which the limit $\lim_{k\to\infty} a^k A^k$ exists and differs from zero matrix.

\emph{Remark.} The convergence of a sequence of matrices $\left(X^{(k)}\right)_{k=1}^\infty$ to a matrix $Y$ (or $\lim_{k\to\infty} X^{(k)}=Y$) here means that the respective sequences of elements of the matrices converge to respective elements in $Y$, in other words, $\lim_{k\to\infty} \max_{i,j}|x^{(k)}_{i,j}-y_{i,j}|=0$.

\item In the University of Timbuctoo $2n$ courses are taught. All graduates have obtained only grades "A" and "B". There do not exist two graduates whose grades fully coincide, and one cannot say that any graduate has better grades than any other (we say that a student has better grades than the other if all grades are at least as good as the grades of the other one, and in some subject the grade is strictly better). What is the largest possible number of graduates in the University of Timbuctoo?

\item Prove that the equation
\[
\int_0^x \mathrm{e}^{-t}\left(1+t+\frac{t^2}{2!}+\ldots+\frac{t^{100}}{100!}\right)\,\mathrm{d}t=50
\]
has a solution $x_0\in(50,100)$.

\item Let $S_{999}$ be the permutation group of the set $\{1,2,\ldots,999\}$ (\emph{symmetric group}). Consider a commutative subgroup $G$ of $S_{999}$ that contains $1111$ elements. Prove that there exists an element $i\in\{1,2,\ldots,999\}$ that remains unchanged for all permutations in $G$, i.e., for every $\sigma\in G$ there holds $\sigma(i)=i$.

\end{enumerate}

\newpage
\selectlanguage{estonian}
\section*{Lahendused}
\begin{enumerate}
\item Vastus: Rida $\sum_n \min\{a_n,b_n\}$ võib olla koonduv ja võib olla hajuv.

Hajuva rea näite saamine on triviaalne: valime $a_n=b_n$.
Koonduva rea saamiseks valime näiteks sellised liikmed
\begin{align*}
(a_n)&=\left(1,\underbrace{\frac1{2^2},\frac1{2^2},\frac1{2^2},\frac1{2^2},\frac1{2^2}}_{\text{$2^2+1$ tükki}},\frac1{7^2},\frac1{8^2},\frac1{9^2},\ldots\right)\\
(b_n)&=\left(1,\frac1{2^2},\frac1{3^2},\frac1{4^2},\frac1{5^2},\frac1{6^2},\frac1{7^2},\underbrace{\frac1{8^2},\frac1{8^2},\ldots,\frac1{8^2}}_{\text{$8^2+1$ tükki}},\ldots\right)
\end{align*}

Kummaski reas on lõpmata palju plokke, mille summa on suurem kui $1$, seega read $\sum_n a_n$ ja $\sum_n b_n$ on hajuvad. Kuna $\min\{a_n,b_n\}=\frac1{n^2}$, siis üldistatud harmooniline rida $\sum_n\min\{a_n,b_n\}$ on koonduv.

\emph{Märkus.} Mitmel moel on võimalik näidata, et $\sum_{n=1}^\infty\frac1{n^2}=\frac{\pi^2}{6}$. Võib-olla lihtsaim on seda tõestada, arendades funktsiooni $f(x)=x^2$ Fourier' ritta. Saame, et
\[
x^2=\frac{\pi^2}{3}+4\sum_{n=1}^\infty (-1)^n\frac{\cos nx}{n^2},\qquad x\in[-\pi,\pi],
\]
ning valime ülalsaadud võrduses $x=\pi$.

\item \emph{Lahendus 1.} Maatriksi $A$ karakteristlik polünoom on 
\[
\left|\begin{array}{ccc}1-X&-1&0\\ -1&2-X&-1\\ 0&-1&1-X\end{array}\right|=-X^3+4X^2-3X=-X(X-1)(X-3).
\]
Seega leidub selline regulaarne maatriks $T$, et
\[
T^{-1}AT=\left(\begin{array}{ccc}0&0&0\\ 0&1&0\\ 0&0&3\end{array}\right)
\]
ehk
\[
A=T\left(\begin{array}{ccc}0&0&0\\ 0&1&0\\ 0&0&3\end{array}\right)T^{-1}.
\]
Kuna $(TAT^{-1})(TAT^{-1})=TA^2T^{-1}$, siis saame, et
\[
a^kA^k =T\left(\begin{array}{ccc}0&0&0\\ 0&a^k&0\\ 0&0&a^k3^k\end{array}\right)T^{-1}.
\]

Oletame, et $\lim_k a^k A^k=B$, siis $B=TCT^{-1}$, kus
\[
C=\left(\begin{array}{ccc}0&0&0\\ 0&\lim_n a^k&0\\ 0&0&\lim_n (3a)^k\end{array}\right).
\]
Siit omakorda nähtub, et $a\in(-1,1]$ ja $3a\in(-1,1]$ (et nende piirväärtus oleks lõplik) ning samas korraga ei tohi kehtida $|a|<1$ ja $|3a|<1$ (et ei tuleks $C=\Theta$). Sellist tingimust rahuldab ainult arv $a=\frac13$.

Teiselt poolt on selge, et kui $a=\frac13$, siis koondumise 
\[
\left(\begin{array}{ccc}0&0&0\\ 0&\left(\frac13\right)^k&0\\ 0&0&1\end{array}\right)\to \left(\begin{array}{ccc}0&0&0\\ 0&0&0\\ 0&0&1\end{array}\right)=:C
\]
tõttu leiab aset ka koondumine
\[
\left(\frac13\right)^k A^k \to T\left(\begin{array}{ccc}0&0&0\\ 0&0&0\\ 0&0&1\end{array}\right)T^{-1}.
\]

\emph{Märkus 1.} Tõestuse käigus kasutasime korduvalt asjaolu, et kui $X^{(k)}\to Y$, siis $HX^{(k)}\to HY$ mistahes sobivamõõtmelise maatriksi $H$ korral (ja analoogselt ka paremalt korrutamise korral). Sedasorti omadus kehtib tänu sellele, et tingimus $X^{(k)}\to Y$ tähendab maatriksi $X^{(k)}-Y$ kõigi elementide jadade hääbuvust, maatriksi $B(X^{(k)}-Y)$ elemendid on aga maatriksi $X^{(k)}-Y$ elementide lineaarkombinatsioonid.

\emph{Märkus 2.} Lahendusest ei selgu (seda polnud ka nõutud leida), mis tegelikult on $\lim_k \left(\frac13\right)^k A^k$. Arvutame selle välja. Saame, et
\[
T=\left(\begin{array}{ccc}1&1&1\\ -1&0&1\\ 1&-2&1\end{array}\right)^t=\left(\begin{array}{ccc}1&-1&1\\ 1&0&-2\\ 1&1&1\end{array}\right),
\]
mistõttu
\[
B=T\left(\begin{array}{ccc}0&0&0\\ 0&0&0\\ 0&0&1\end{array}\right)T^{-1}=\frac16\left(\begin{array}{ccc}1&-2&1\\ -2&4&-2\\ 1&-2&1\end{array}\right).
\]

\emph{Lahendus 2.} Tõestame matemaatilise induktsiooniga, et kehtib valem:
\[
A^k = \left(\begin{array}{ccc} \frac{3^{k-1}+1}{2} & -3^{k-1} & \frac{3^{k-1}-1}{2} \\ -3^{k-1} & 2\cdot 3^{k-1} & -3^{k-1} \\ \frac{3^{k-1}-1}{2} & -3^{k-1} & \frac{3^{k-1}+1}{2}\end{array}\right).
\]
Tõestamine pole keeruline: baasi kehtivuse kontroll ($k=1$) on vahetu ning sammu teostamiseks korrutame:
\[
\left(\begin{array}{ccc} \frac{3^{k-1}+1}{2} & -3^{k-1} & \frac{3^{k-1}-1}{2} \\ -3^{k-1} & 2\cdot 3^{k-1} & -3^{k-1} \\ \frac{3^{k-1}-1}{2} & -3^{k-1} & \frac{3^{k-1}+1}{2}\end{array}\right)\cdot \left(\begin{array}{rrr}1&-1&0\\-1&2&-1\\ 0&-1&1\end{array}\right)=
\left(\begin{array}{ccc} \frac{3^{k}+1}{2} & -3^{k} & \frac{3^{k}-1}{2} \\ -3^{k} & 2\cdot 3^{k} & -3^{k} \\ \frac{3^{k}-1}{2} & -3^{k} & \frac{3^{k}+1}{2}\end{array}\right).
\]

Niisiis
\[
a^k A^k = \left(\begin{array}{ccc} \frac1{6}\cdot ((3a)^k+3a^k) & -\frac13 (3a)^{k} & \frac1{6}\cdot ((3a)^k-3a^k) \\ -\frac13 (3a)^{k} & \frac23\cdot (3a)^{k} & -\frac13 (3a)^{k} \\ \frac1{6}\cdot ((3a)^k-3a^k) & -\frac13 (3a)^{k} & \frac1{6}\cdot ((3a)^k+3a^k)\end{array}\right)
\]

On selge, et piirväärtuse olemasoluks peab kehtima $3a\in(-1,1]$. Teiselt poolt, kui $|3a|<1$, on kõigi liikmete piirväärtused nullid ja saaksime nullmaatriksi, mis pole ülesande tingimustega lubatud. Jääb üle võimalus, et $3a=1$ ehk $a=\frac13$, misjuhul
\[
A^k A^k\to\frac16\left(\begin{array}{ccc}1&-2&1\\ -2&4&-2\\ 1&-2&1\end{array}\right).
\]

\item Vastus: $\binom{2n}{n}$.

Kõigepealt, lõpetanute arv $\binom{2n}{n}$ on vahetult realiseeritav, kuna vektoris pikkusega $2n$ märgitakse ära $n$ positsiooni (hinde "`A"' positsioonid; ülejäänud $n$ positsioonis seisab siis hinne "`B"') ning ühegi kahe sellise vektori kohta ei saa öelda, et üks oleks parem kui teine (kuna vektorid on erinevad, on mingis positsioonis erinev hinne; kui see erinevus oleks ainult ühtpidi, oleks üht liiki hindeid rohkem kui teisi, mis on võimatu).

Tarvis on näidata, et lõpetanute arv ei ületa $\binom{2n}{n}$. Tõestame järgnevalt, et kui mõnel lõpetanul on hindeid "`A"' vähem kui $n$, ei saa lõpetanute arv olla suurim. (Sellega sümmeetriline arutelu näitaks sedasama ka olukorras, kui mõnel lõpetanul on hindeid "`B"' vähem kui $n$.)

Tähistame $A(a)$ abil nende ainete hulga, milles lõpetanul $a$ on hinne "`A"'. Kõik sellised hulgad koosnevad ülimalt $2n$ elemendist, kusjuures ülesande tingimuse kohaselt ei sisaldu ükski niisugune hulk teises. 

Jaotame hulgad $A(a)$ klassidesse elementide arvu kaupa. Olgu $r$ vähim elementide arv vaadeldavates hulkades. Näitame, et kui $r<n$, siis võib antud hulkade süsteemi asendada uuega nii, et
\begin{enumerate}[a)]
\item ükski uue süsteemi hulk ei sisaldu mõnes teises,
\item uues süsteemis on rohkem hulki kui esialgses,
\item vähim elementide arv uue süsteemi hulkades on $r+1$.
\end{enumerate}
Selleks lisame kõigile $r$-elemendilistele hulkadele kõikvõimalikel viisidel ühe uue elemendi. Süsteemi ülejäänud hulgad jätame endiseks.

On selge, et niisuguse operatsiooni järel saame hulkade süsteemi, kus vähim elementide arv hulkades on $r+1$. Seejuures pole ükski uue süsteemi hulk teise osaks: kui hulk $B$ sisaldaks uut hulka $A'$, siis oleks ta sisaldanud ka $r$-nda klassi hulka $A$, millest $A'$ saadi elemendi lisamisel. Peale selle märgime, et ükski uus hulk ei ühti esialgsega. Tekkigu uus hulk näiteks elemendi $x$ lisamisel hulgale $A$. Kui ta ühtiks mõne esialgse hulgaga $B$, siis tähendaks see, et $B$ sisaldab ülesande tingimuse vastaselt hulka $A$.

On jäänud veel näidata, et uusi hulki on \textbf{rohkem} kui esialgseid. Iga $r$-elemendilise hulga $A$ jaoks leidub $2n-r$ elementi, mida saab lisada, seega igast $r$-elemendilisest hulgast tekib $2n-r$ uut hulka. Tõsi, mõned nendest võivad langeda kokku (näiteks $\{a,b\}$ ja $\{b,c\}$ annavad vastavalt $c$ ja $a$ lisamisel mõlemad hulga $\{a,b,c\}$). Kuid iga $(r+1)$-elemendilise hulga võib $r$-elemendilisest hulgast saada vaid $r+1$ eri viisil. Seepärast, kui $r$-elemendilisi hulki on $m$ ja neist on tekkinud $p$ erinevat uut hulka, siis $m(2n-r)\leq p(r+1)$. Et $r<n$ puhul $2n-r>r+1$, siis $m<p$, mis tähendab, et hulkade arv on suurenenud.

\emph{Märkus.} Ülesandeks on tegelikult tõestada \emph{Sperner'i teoreem}, mis väidab, et $n$ elemendilise hulga baasil moodustatud alamhulkade \emph{antiahel} (selline hulkade süsteem, kus ükski kaks hulka pole omavahel võrreldavad) koosneb mitte rohkem kui $\binom{n}{\lfloor\frac n2\rfloor}$ hulgast, kusjuures maksimum realiseerub täpselt juhul, kui kõik antiahela hulgad sisaldavad täpselt $\lfloor \frac n2\rfloor$ elementi või kõik antiahela hulgad sisaldavad täpselt $\lceil \frac n2\rceil$ elementi.

\item Tähistame
\[
f(x)=\int_0^x \mathrm{e}^{-t}\left(1+t+\frac{t^2}{2!}+\ldots+\frac{t^{100}}{100!}\right)\,\mathrm{d}t.\]
Määratud integraali range monotoonsuse tõttu (pidevate funktsioonide jaoks) saame, et
\[
f(50)<\int_0^{50} e^{-t}e^t\,\mathrm{d}t=\int_0^{50}\,\mathrm{d}t=50,
\]
kuna 
\[
1+t+\frac{t^2}{2!}+\ldots+\frac{t^{100}}{100!}<e^t,\quad t>0.
\]
Et
\begin{align*}
f'(x)&=\mathrm{e}^{-x}\left(1+x+\frac{x^2}{2!}+\ldots+\frac{x^{100}}{100!}\right),\\
f''(x)&=-\mathrm{e}^{-x}\cdot \frac{x^{100}}{100!},\\
f'''(x) &= \mathrm{e}^{-x}\cdot\frac{x^{99}}{99!}\left(\frac{x}{100}-1\right)<0,
\end{align*}
siis tuletisfunktsiooni $f'$ graafik on rangelt kumera kujuga intervallis $[0,100]$. Järelikult
graafikualune pindala on suurem kui sellise trapetsi pindala, mille alused on $f'(0)$ ja $f'(100)$:
\[
f(100)=\int_0^{100}f'(t)\,\mathrm{d}t > \frac{f'(0)+f'(100)}{2}\cdot100=50\cdot(1+f'(100))>50.
\]
Et $f(50)<50<f(100)$ ja funktsioon $f$ on lõigus $[50,100]$ pidev, siis Bolzano--Cauchy teoreemi kohaselt leidub arv $x_0\in(50,100)$ nii, et $f(x_0)=50$.


\item Paneme tähele, et $1111=11\cdot101$ ning tegurid on algarvud.

Osutub, et $G$ on tsükliline rühm, see tähendab, kõik tema elemendid on mingi moodustaja astmed. Tõepoolest, Lagrange'i teoreemi kohaselt rühma $G$ iga elemendi järk on rühma elementide arvu tegur, niisiis iga $a\in G$ kohta kehtib üks neljast: $a^1=1$, $a^{11}=1$, $a^{101}=1$ või $a^{1111}=1$ (ning kui mingi tingimus kehtib, siis väiksema astendaja korral ei kehti). Juhtum $a=1$ pole huvipakkuv ning juhtum $a^{1111}=1$ juba tähendakski, et $a,a^2,a^3,\ldots,a^{1111}=1$ on kõik erinevad ning seega $G=\langle a\rangle$. Oletame, et elementi järguga $1111$ ei ole, siis jääb üle võimalus, et rühmas $G$ on elemendid $u$ ja $v$ nii, et $u^{11}=v^{101}=1$. Aga nüüd elemendi $uv$ järk siiski on $1111$. Selle märkamiseks olgu $uv$ järguks $k$, siis \[
v^{11k}=1\cdot v^{11k}=u^{11k}v^{11k}=(uv)^{11k}=1,
\]
mistõttu $101\mid 11k$. Kuna $101$ ja $11$ on ühistegurita, siis $101\mid k$. Analoogse argumendiga näitame, et $11\mid k$. Kokkuvõttes $k=1111$.

Niisiis, leidub $a\in G$ nii, et $G=\{1,a,a^2,\ldots,a^{1110}\}$. Element $a$ on permutatsioon nagu kõik $S_{999}$ elemendid; tema esituses lõikumatute tsüklite korrutisena muidugi pole tsüklit pikkusega $1111$. Järelikult tema tsüklid on kõik pikkustega kas $1$, $11$ või $101$. Olgu $x,y,z$ elementide $\{1,\ldots,999\}$ arvud, mis asuvad tsüklites vastavalt pikkustega $1,11,101$. Tsükkel pikkusega $1$ tähendabki mingi elemendi $\{1,\ldots,999\}$ paigalejäämist (nii permutatsiooni $a$ kui tema kõigi astmete juures) ja selle olemasolul oleks ülesanne lahendatud. Oletame vastuväiteliselt, et $x=0$. Nüüd $11y+101z=999$. Saadud diofantiline võrrand on vasturääkiv, sest mooduli $11$ järgi saame $2z\equiv9$, mistõttu $z\equiv10$, järelikult $z\geq10$ ja seega $999=11y+101z\geq1010$, vastuolu.

Saadud vastuolu näitab, et $x>0$ ja leidub element, mis asub tsüklis pikkusega $1$ ehk jääb paigale.

\emph{Märkus.} Ülesande lahendusest tegelikult ka selgub, et taoline $G$ on olemas ning see, et kuidas ta koostada (ehk millised on \textbf{kõik} sellised Abeli alamrühmad $G$). Korraldada tuleb võrduse $x+11y+101z=999$ rahuldatus ning seejärel panna arvud õiges koguses (vastavalt $x$, $y$ ja $z$ tükki) sõltumatutes tsüklites roteeruma.
\end{enumerate}
\end{document}

