\documentclass{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{fullpage}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{xcolor}
\usepackage{verbatim}
\usepackage{pgf,tikz,pgfplots}
\pgfplotsset{compat=1.15}
\usepackage{mathrsfs}
\usetikzlibrary{arrows}

\usepackage{subfigure}

\newcommand{\rank}{\operatorname{rank}}
\DeclareMathOperator{\Mat}{Mat}
\newcommand{\e}{\varepsilon}
\newcommand{\bb}{\mathbb}

\begin{document}

\paragraph{Tartu Ülikooli matemaatikaolümpiaad 2021 | 21.05.2021}
\thispagestyle{empty}
\begin{enumerate}
\item
Olgu $\|\cdot\|$ norm vektorruumil $X$. Tõesta, et
kui $x_1, \dots, x_n \in X$ on sellised, et 
\[
\|x_1 + \ldots + x_n\| = \|x_1\| + \ldots + \|x_n\|
\]
ja $t_1, \ldots, t_n \geq 0$, siis ka
\[
\|t_1x_1 + \ldots + t_nx_n\| = t_1\|x_1\| + \ldots + t_n\|x_n\|. 
\]

(\emph{Norm} vektorruumil $X$ on selline kujutus $\|\cdot\|\colon X \to [0, \infty)$, et kõigi vektorite $x,y \in X$ ja skalaaride $\lambda$ korral
\begin{enumerate}
\item
$x = 0 \iff \|x\| = 0$,
\item
$\|\lambda x\| = |\lambda|\|x\|$,
\item
$\|x+y\| \leq \|x\| + \|y\|$.)
\end{enumerate}

\item
Olgu $Q$ loenduv reaalsete $(n\times m)$-maatriksite hulk. Olgu $B$ selline reaalne $(n\times m)$-maatriks, et $Bx \in \{Ax \mid A \in Q\}$ iga $x \in \bb R^m$ korral. Kas $B \in Q$?

\item
Olgu $n \in \bb N$ ning olgu antud $n+1$ erinevat kolmeelemendilist hulka $k_1, \dots, k_{n+1} \subset \{1, \dots, n\}$. Tõesta, et leiduvad $k_i$ ja $k_j$ nii, et hulk
$k_i \cap k_j$ on üheelemendiline.
\item
Arvuta
\[
\sum_{n=0}^\infty \frac{(-1)^n}{3^n(2n+1)}.
\]

\item
Olgu $A, B$ sama mõõtmega komplekssed ruutmaatriksid, kusjuures $AB = BA$ ja $A^{2021} = B^{2022} = E$, kus $E$ tähistab ühikmaatriksit. Kas $A + B + E$ saab olla singulaarne?
\item
Olgu $f \colon \bb R \to \bb R$ pidev perioodiline funktsioon perioodiga $2$, seejuures olgu $f$ kahanev lõigul $[0,1]$, kasvav lõigul $[1,2]$ ning $f(x) = f(2-x)$ kõigi $x \in \bb R$ korral. Tõesta, et funktsioon
\[
g(y) = \int_0^2 f(x) f(x+y) dx
\]
omandab punktis $y = 1$ minimaalse väärtuse.
\end{enumerate}
\newpage

\paragraph{Mathematics Olympiad of the Univerisity of Tartu 2021 | 21.05.2021}
\thispagestyle{empty}
\begin{enumerate}


\item
Let $\|\cdot\|$ be a norm on a vector space $X$. Prove that
if $x_1, \dots, x_n \in X$ are such that 
\[
\|x_1 + \ldots + x_n\| = \|x_1\| + \ldots + \|x_n\|
\]
and $t_1, \ldots, t_n \geq 0$, then also
\[
\|t_1x_1 + \ldots + t_nx_n\| = t_1\|x_1\| + \ldots + t_n\|x_n\|. 
\]

(A \emph{norm} on a vector space $X$ is a mapping $\|\cdot\|\colon X \to [0, \infty)$ such that for all $x,y \in X$ and all scalars $\lambda$ one has
\begin{enumerate}
\item
$x = 0 \iff \|x\| = 0$,
\item
$\|\lambda x\| = |\lambda|\|x\|$,
\item
$\|x+y\| \leq \|x\| + \|y\|$.)
\end{enumerate}

\item
Let $Q$ be a countable set of real $(n\times m)$-matrices. Let $B$ be a real $(n\times m)$-matrix such that\\ $Bx \in \{Ax \mid A \in Q\}$ for all $x \in \bb R^m$. Is it true that $B \in Q$?

\item
Assume that $n \in \bb N$ and we are given $n+1$ distinct three-element sets $k_1, \dots, k_{n+1} \subset \{1, \dots, n\}$. Prove that there are $k_i$ and $k_j$ such that
$k_i \cap k_j$ consists of a single number.
\item
Calculate
\[
\sum_{n=0}^\infty \frac{(-1)^n}{3^n(2n+1)}.
\]

\item
Let $A, B$ be complex square matrices of the same size such that $AB = BA$ and $A^{2021} = B^{2022} = E$, where $E$ denotes the identity matrix. Can $A + B + E$ be a singular matrix?
\item
Let $f \colon \bb R \to \bb R$ be a continuous periodic function with period $2$ such that $f$ is decreasing on $[0,1]$, increasing on $[1,2]$ and $f(x) = f(2-x)$ for all $x \in \bb R$. Prove that the function
\[
g(y) = \int_0^2 f(x) f(x+y) dx
\]
obtains its minimum at $y = 1$.
\end{enumerate}
\newpage
\textbf{Lahendused}
\begin{enumerate}
\item
Nimetame ülesandes kirjeldatud tingimust $\sum \|x_i\|=\left\|\sum x_i\right\|$ rahuldavat vektorite hulka $\{x_i\}$ \emph{aditiivseks}. Aditiivse hulga iga alamhulk on samuti aditiivne. Kui hulk $A$ on aditiivne, siis on seda ka $tA$ suvalise $t \in \bb R$ korral. Lõpliku aditiivse hulga $\{x_i\}$ korral on aditiivne ka hulk $\bigcup_i\{t_i x_i, (1-t_i) x_i\}$ iga arvukomplekti $\{t_i\} \subset [0,1]$ korral, mistõttu on aditiivne ka $\{t_i x_i\}$. Niisiis on aditiivne ka $\{t_ix_i\} = t\{\frac{t_i}t x_i\}$ iga arvukomplekti $\{t_i\} \subset [0, t]$ jaoks.
\item
Iga $x \in \bb R^m$ jaoks leidub maatriks $A \in Q$ nii, et
$(A-B)x = 0$. Teisisõnu, $\bb R^m \subset \bigcup_{B \in Q} \ker(A-B)$. Ent hulk $\bb R^n$ ei ole esitatav loenduva hulga pärisalamruumide ühendina ($*$). Järelikult $\bb R^n = \ker (A-B)$ mingi maatriksi $A \in Q$ korral, mis tähendab, et $A = B$.

Kontrollimaks väite ($*$) kehtivust, paneme tähele, et iga pärisalamruumi Lebesgue'i mõõt on 0 ning seega nende loenduv ühend on samuti nullmõõduga. Teine võimalus, juhul $n=2$, oleks märgata, et iga ühemõõtmeline alamruum vastab kahele (üksteise vastas asuvale) punktile ühikringjoonel.
\item
\emph{Lahendus 1.} Oletame väitevastaselt, et alati kas $k_i \cap k_j = \emptyset$ või $|k_i \cap k_j| = 2$ iga $i \neq j$ korral.
Tähistame $k_i \sim k_j$, kui $|k_i \cap k_j| \geq 2$. Paneme tähele, et seos $\sim$ on transitiivne ja seetõttu ekvivalentsusseos.
Niisiis laguneb meie kolmikute hulk lõikumatuteks ekvivalentsiklassideks.
Vastuolu on käes, kui näitame, et kolmikute arv igas klassis pole suurem kui elementide arv nende ühendis. (Tõepoolest, kolmikute koguarv on $n+1$, elementide koguarv kõigi kolmikute ühendis aga ülimalt $n$, ning vastavalt väitevastasele oletusele ei saa ükski element kuuluda korraga mitme ekvivalentsiklassi kolmikutesse.)

Kui ekvivalentsiklass koosneb ühest või kahest kolmikust, siis on elementide arv ühendis vastavalt kas $3$ or $4$.

Kui ekvivalentsiklass koosneb kolmest või neljast kolmikust, on elementide arv ühendis vähemalt $4$. (Minimaalne arv $4$ realiseerub juhul, kui kolmikud on $\{x,y,z\}$, $\{x,y,u\}$, $\{x,z,u\}$ ja $\{y,z,u\}$.)

Olgu nüüd ekvivalentsiklassis viis või enam kolmikut.
Konstrueerides kolmikuid, millest iga kolme ühisosa oleks ülimalt ühe-elemendiline, jõuame ainult nelja kolmikuni $\{x,y,z\}$, $\{x,y,u\}$, $\{x,z,u\}$ ja $\{y,z,u\}$, klassis on aga kolmikuid vähemalt viis. Seetõttu on meie ekvivalentsiklassi kolmes kolmikus samad elemendid $x$ ja $y$, mis esinevad siis selle klassi kõigis kolmikutes. (Tõepoolest, kui klassis on kolmikud $k_1=\{x,y,z\}$, $k_2=\{x,y,u\}$ ja $k_3=\{x,y,v\}$, siis suvaline selle klassi kolmik, mitte sisaldamaks mõlemat elementi $x$ ja $y$, peaks sisaldama (ühisosa tõttu $k_1$-ga) näiteks elemente $x$ ja $z$, (ühisosa tõttu $k_2$-ga) elemente $x$ ja $u$ ning (ühisosa tõttu $k_3$-ga) elemente $x$ ja $v$, see on aga võimatu.)

Järelikult on elementide arv ühendis kahe võrra suurem kui kolmikute arv.

\emph{Lahendus 2.} Moodustame ekvivalentsiklassid nagu lahenduses 1. Nagu sealgi, on meie eesmärk tõestada, et
kolmikute arv igas klassis pole suurem kui elementide arv nende ühendis.

Vaatleme ekvivalentsiklassi kolmikute ühendi suurust.

Kui kolmikute ühendi suurus on $3$, siis on tegu ühe kolmikuga.

Kui ühendi suurus on $4$, siis nendest elementidest saab moodustada $4$ kolme-elemendilist alamhulka $\{x,y,z\}$, $\{x,y,u\}$, $\{x,z,u\}$ ja $\{y,z,u\}$. Seega kolmikute arv sel juhul ülimalt neli.

Kui ühendi suurus on vähemalt $5$, siis leiduvad kaks elementi, mis sisalduvad kõigis kolmikutes.
Tõepoolest, vaatleme kolmikuid $\{x,y,z\}$ ja $\{x,y,u\}$, siis leidub kolmik, mille ühisosa hulgaga $\{x,y,z,u\}$ on suurusega 2, seega $x$ ja $y$ sisalduvad ka selles kolmikus. Nüüd peab ka iga muu kolmik sisaldama elemente $x$ ja $y$ (seda selgitati lahenduse 1 lõpus detailselt). Järelikult sel juhul on ühendi suurus kahe võrra suurem kolmikute arvust.

\emph{Lahendus 3.} Oletame väitevastaselt, et kõikide ühisosade suurused on 0 või 2. Vaatleme $(n+1)\times n$  maatriksit $A$, mille ridu indekseerivad hulgad $k_i$ ja veerge põhihulga $\{1,2,\ldots,n\}$ elemendid. Maatriks $A$ olgu \emph{intsidentsusmaatriks}, see tähendab, et $A_{ij}=1$, kui $j\in k_i$, ja $A_{ij}=0$ muul juhul.
$(n+1)\times(n+1)$ maatriksi $AA^T$ element $\alpha_{ij}$ loendab nüüd ühisosa $k_i\cap k_j$ elementide arvu. Niisiis maatriksi $AA^T$ determinant on nullist erinev, sest peadiagonaalil on kolmed ja väljaspool peadiagonaali paarisarvud. Järelikult peaks maatriksi A astak olema vähemalt $n+1$ -- vastuolu maatriksi $A$ mõõtmega.

\emph{Märkus 1.} Lahendus 2 kirjeldab ülesandes vaadeldavate kolmikute süsteemi (kus kolmikute hulga ja põhihulga võimsused võivad olla suvalised) kõikvõimalikke struktuure: klasside kolmikute ühendid on paarikaupa ühisosata. Kui sellise ühe ühendi suurus on 4, siis on seal kaks kuni neli suvalist 3-elemendist alamhulka kolmikuteks, vastasel korral on klassi kolmikud kujul $\{x,y,z_1\}$, $...$, $\{x,y,z_k\}$, kus $k$ on klassi kolmikute arv.

\emph{Märkus 2.} Kombinatoorikas tõestatakse üldisem väide, nn \emph{paaritu linna teoreem}: kui $\mathcal{F}$ on hulga $\{1,\ldots,n\}$ alamhulkade kogum, mille kõik elemendid (alamhulgad) koosnevad paaritust arvust elementidest ning kõik (erinevate alamhulkade) ühisosad paarisarvust elementidest, siis $\mathcal{F}$ elementide (alamhulkade) arv ei ületa arvu $n$. Käesolev ülesanne on selle vahetu rakendus -- $\mathcal{F}$ on kolmikute hulk, $3$ on paaritu arv ning $0$ ja $2$ on paarisarvud.

\item
Vaatleme rida $\sum_{n=1}^\infty (-1)^{2n} x^{2n}$. Vahemikus $(-1, 1)$ koondub see rida summaks $\frac 1 {1+x^2}$. Igas lõigus $[-q,q]$ (kus $q \in (0,1)$) on koondumine ühtlane ning võime integreerida lõigul $[0,x]$ mitahes $x \in (-1, 1)$ jaoks:
\[
\int_0^x \frac{dt}{1+t^2} = \sum_{n=0}^\infty (-1)^n \int_0^x t^{2n} dt
\]
ehk
\[
\arctan x = \sum_{n=0}^\infty \frac{(-1)^n x^{2n+1}}{2n+1},
\]
seega
\[
\frac \pi 6 = \arctan(1 / \sqrt 3) = \frac 1 {\sqrt 3} \sum_{n=0}^\infty \frac{(-1)^n}{3^n(2n+1)}.
\]
Järelikult on rea summa $\frac{\pi \sqrt 3} 6$.
\item
Oletame, et $A+B+E$ on singulaarne. Siis $-Ax = (B+E)x$ mingi vektori $x \neq 0$ korral. Kuna maatriksid $A$ ja $B+E$ kommuteeruvad, siis $A$-ga korrutades saame, et $A^2 x = (B+E)^2 x$. Selliselt jätkates leiame, et $(-1)^k A^k x = (B+E)^k x$ iga $k \in \bb N$ korral. Järelikult $((B+E)^{2021} + E)x = 0$. Teiselt poolt $(B^{2022}- E) x = 0$.

Paneme tähele, et polünoomid $(z+1)^{2021} + 1$ ja $z^{2022}-1$ on ühistegurita. Tõepoolest, ühine juur  $z_0$ rahuldaks tingimusi $|z_0| = |z_0 + 1| = 1$,
mistõttu arvud $0, 1, z_0+1$ oleks komplekstasandil võrdkülgse kolmnurga tippudeks ja järelikult $\arg(z_0+1) = \pm \frac \pi 3$. Et $3 \mid 2022$, kehtiks $(z_0 + 1)^{2022} = \pm 1$. Nüüd $z_0 + 1 = \frac{\pm 1}{-1} = \mp 1$,
mis on vastuolus tingimusega $|z_0| = 1$.

Seega leiduvad polünoomid $P$ ja $Q$ nii, et
\[
P(z)((z+1)^{2021} + 1) + Q(z)(z^{2022}-1) = 1
\]
kõigi $z \in \bb C$ jaoks. Järelikult
\[
x = Ex = (P(B)((B+E)^{2021} + E) + Q(B)(B^{2022}-E))x = 0,
\]
vastuolu.
\item
Iga $n, i \in \bb N$ korral tähistame $I_{n,i} := (\frac i n, \frac{i+1} n)$ ning vaatleme treppfunktsiooni
\[
f_n(x) := \inf_{x,t \in I_{n,i}} f(t).
\]
Kui $y = \frac m n$ mingi $m \in \bb N$ jaoks, siis
\begin{equation}\label{intvord}
\int_0^2 f_n(x) f_n(x+y) dx \geq \int_0^2 f_n(x) f_n(x+1) dx.
\end{equation}
Tõepoolest, tähistanud $a_i := \inf_{t \in I_{n,i}} f(t)$, leiame, et
\[
\int_0^2 f_n(x) f_n(x+y) dx = \sum_{i=0}^{2n-1} a_i a_{i+m},
\]
mistõttu võrratus \eqref{intvord} on samaväärne võrratusega
\[
\sum_{i=0}^{2n-1} a_i a_{i+m} \geq \sum_{i=0}^{2n-1} a_i a_{i+n}.
\]
Märgime, et $\{a_{i+m}\}_i$ on jada $\{a_{i+n}\}_i$ ümberjärjestus. Tõepoolest, selleks, et tõestada ülesande võrratust, on piisav märgata, seda, et võrratus $a_i \leq a_j$ on samaväärne võrratusega $a_{i + n} \geq a_{j+n}$, kus $i, j \in \{0, \dots, n-1\}$, ning rakendada ümberpaigutusvõrratust.

Et koondumine $f_{nk} \to_k f$ on ühtlane, saame, et $\int_0^2 f_{nk}(x) f_{nk}(x+y)dx \to_k \int_0^2 f(x) f(x+y)dx$ mistahes $y = \frac m n$ korral. Järelikult saame soovitud võrratuse mistahes ratsionaalarvu $y$ jaoks. Funktsiooni $g$ pidevuse tõttu kehtib võrratus ka kõigi reaalarvude $y$ jaoks.
\end{enumerate}
\end{document}
