\documentclass{article}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{fullpage}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{xcolor}
\usepackage{verbatim}

\newcommand{\rank}{\operatorname{rank}}

\begin{document}

\title{Tartu Ülikooli üliõpilaste matemaatikaolümpiaad}
\date{25.05.2018}
\maketitle
\thispagestyle{empty}
\begin{enumerate}

\item
Olgu $f: \mathbb R \to \mathbb R$ integreeruv ja $0 < f(z) < \frac{1}{2z}$ iga $z > 0$ korral.
Tõesta, et funktsioon
\[
g(x) := \int_0^x z^2 f(z) dz - \left(\int_0^x zf(z) dz \right)^2
\]
on kasvav vahemikus $(0, \infty)$.
\item
Iga arvrida, mille elemendid on paarikaupa erinevad hulga $S \subset \mathbb R$
elemendid, on koonduv. Tõesta, et $S$ on ülimalt loenduv.

\item
Olgu $n \in \mathbb N$.
Maatriksi $A \in \operatorname{Mat}_n(\mathbb R)$ peadiagonaalil on ainult nullid ning kõik teised elemendid on kas $1$ või $2018$.
Tõesta, et maatriksi $A$ astak on kas $n$ või $n-1$.
\item
Vaatleme vektorruume $\mathbb R^2$, $\mathbb R^3$ ja $c_{00}$ üle $\mathbb R$, kus
\[
c_{00} = \{x = (x_n): \mathbb N \to \mathbb R \ | \ \exists N \in \mathbb N \ \forall n \geq N \ x_n = 0\}.
\] 
Ruumides $\mathbb R^2$, $\mathbb R^3$ olgu normiks harilik eukleidiline norm:
\[
\|(x_1,x_2)\|=\sqrt{x_1^2 + x_2^2},\qquad \|(x_1,x_2,x_3)\|= \sqrt{x_1^2 + x_2^2 + x_3^2}.
\]
Ruum $c_{00}$ olgu varustatud järgmise normiga:
\[
\|x\| = \left( \sum_{n \in \mathbb N} |x_n|^2 \right)^{1/2}.
\]
Iga nimetatud ruumi korral leia vähim võimalik kinniste kerade arv, mis katavad terve ühiksfääri $\{x\colon \|x\|=1\}$, kuid ükski kera ei sisalda nullpunkti, või tõesta, et lõplikust arvust keradest ei piisa.
See tähendab, leia vähim $m \in \mathbb N$, mille korral leiduvad elemendid $x^1, \dots, x^m $ ja raadiused
$r_i \in (0, \|x^m\|)$, $i = 1, \dots, m$ nii, et iga elemendi $y$, $\|y\| = 1$, korral leidub indeks $i \in \{1, \dots, m\}$ omadusega $\|y - x^i\| \leq r_i$.

\item
Olgu $n \in \mathbb N$ ja $c > 0$.
Polünoomi $P$ kõik $n$ nullkohta on erinevad reaalarvud.
Tõesta, et hulk 
\[
\{x \in \mathbb R \colon P(x) \neq 0, \ \frac{P'(x)}{P(x)} > c\}
\]
on lõpliku arvu vahemike ühend, kusjuures nende vahemike pikkuste summa võrdub $\frac n c$.
\item
Olgu $n$-tipulise ($n \in \mathbb N$) täisgraafi $K_n$ iga serv värvitud ühte kolmest värvist. Tõesta, et sellel graafil leidub sidus alamgraaf, mille kõik servad on sama värvi ja mille tippude arv on vähemalt $n/2$.
\end{enumerate}
\newpage
\thispagestyle{empty}
\begin{enumerate}

\item
Let $f: \mathbb R \to \mathbb R$ be integrable and such that $0 < f(z) < \frac{1}{2z}$ for all $z > 0$.
Prove that the function
\[
g(x) := \int_0^x z^2 f(z) dz - \left(\int_0^x zf(z) dz \right)^2
\]
is increasing on $(0, \infty)$.
\item
Every series composed of distinct elements from a set $S \subset \mathbb R$
is convergent. Prove that $S$ is at most countable.

\item
Let $n \in \mathbb N$.
Consider matrix $A$ of size $n \times n$ such that there are only zeroes on the main diagonal and all the other elements are either $1$ or $2018$.
Prove that the rank of $A$ is either $n$ or $n-1$.
\item
Consider the vector spaces $\mathbb R^2$, $\mathbb R^3$, and 
\[
c_{00} = \{x = (x_n): \mathbb N \to \mathbb R \ | \ \exists N \in \mathbb N \ \forall n \geq N \ x_n = 0\}
\] 
Let the spaces $\mathbb R^2$, $\mathbb R^3$ be equipped with the usual Euclidean distance:
\[
\|(x_1,x_2)\|=\sqrt{x_1^2 + x_2^2},\qquad \|(x_1,x_2,x_3)\|= \sqrt{x_1^2 + x_2^2 + x_3^2}.
\]
Let $c_{00}$ be equipped with the norm
\[
\|x\| = \left( \sum_{n \in \mathbb N} |x_n|^2 \right)^{1/2}.
\]
For all these spaces find the minimal finite number of closed balls not containing the origin such that their union contains the unit sphere $\{x\colon \|x\|=1\}$ or prove that it takes infinite number of balls to cover the unit sphere in this way.
That is, find a minimal $m \in \mathbb N$ for which there exist elements $x^1, \dots, x^m $ and radii
$r_i \in (0, \|x^m\|)$, $i = 1, \dots, m$, such that for every element $y$ satisfying $\|y\| = 1$ there exists an index $i \in \{1, \dots, m\}$ with $\|y - x^i\| \leq r_i$.

\item
Let $n \in \mathbb N$ and let $c > 0$.
All the $n$ roots of a polynomial $P$ are distinct real numbers. Prove that the set
\[
\{x \in \mathbb R \colon P(x) \neq 0, \ \frac{P'(x)}{P(x)} > c\}
\]
is a union of a finite number of intervals such that the sum of lengths of these intervals equals $\frac n c$.

\item
Let $n \in \mathbb N$.
In a complete graph with $n$ vertices $K_n$ every edge is colored with one of three colors. Prove that in this graph there exists a connected subgraph with edges of the same color and at least $n/2$ vertices.
\end{enumerate}
\newpage
\textbf{Solutions}

\begin{enumerate}
\item
Note that
\[
g'(x) = x^2 f(x) - 2xf(x)\int_0^x zf(z)dz > x^2 f(x) - xf(x) \int_0^xdz = 0. 
\]
\item
Consider sets 
\[
S^+_n = \{x \in S \ | \ x > \frac 1 n\}
\]
and 
\[
S^-_n = \{x \in S \ | \ x < - \frac 1 n\}.
\]
If any of them is infinite we can construct a divergent series from distinct elements of it. So each of them is finite and 
\[
\{0\} \cup \bigcup_{n \in \mathbb N} (S^+_n \cup S^-_n)
\]
is countable. But the latter set clearly contains $S$.

\item
Let $B = (b_{ij})$ with $b_{ij} = 1$ for all $i,j$.
Note that $A-B$ modulo 2017 is a diagonal matrix with $-1$ on the diagonal. So $|A-B|$ is not 0 modulo 2017 and $\rank(A-B) = n$. Note that rank of a linear transformation $L$ on $\mathbb R^n$ is just the dimension of the image $L(\mathbb R^n)$. Since $(A-B)(\mathbb R^n) \subset A(\mathbb R^n) + B(\mathbb R^n)$,
we have $n = \rank (A-B) \leq \rank A + \rank B = \rank A + 1$.
\item
In $\mathbb R^n$ the minimal number is $n+1$. We cannot cover with $n$ balls because any ball leaves a diametral section of the ball intact and by induction you cannot cover it by $n-1$. The base ($n=1$) is clear.
On the other hand, note that for any half-space $H = H(y, \alpha) = \{x \in \mathbb R^n \ | \ \langle x, y \rangle \geq \alpha \}$ defined by $y \in \mathbb R^n$ and $\alpha > 0$ not containing the origin you can find a large enough ball $B$ not containing the origin such that $S \cap H \subset S \cap B$ ($S$ denotes the sphere). Now you can clearly
cover the sphere by halfspaces $H(e^i, \alpha_i)$, $i=1, \dots, n$ and $H(-(e^1 +\dots +e^n), \alpha)$
for small enough $\alpha_i$ and $\alpha$ (an element $e^i$ is defined by $e^i_k = \delta_{ik}$, i.e., $1$ when $i = k$ and $0$ otherwise).

In $c_{00}$, you cannot cover by a finite number of balls. Take $x^1, \dots, x^m$. We can find $n \in \mathbb N$
such that $x^i_n = 0$ for $i = 1, \dots, m$. Then for any $i$, 
\[
\|x^i - e^n\| = \sqrt{\|x^i\|^2 + 1} > \|x^i\|.
\]
So $e^n \in S$ is not in any ball with center $x^i$ that does not contain the origin.
\item
Take the roots $\{x_1, \dots, x_n \}$ in increasing order. The function
\[
f(x) = \frac{P'(x)}{P(x)} = \frac 1 {x - x_1} + \dots + \frac 1 {x - x_n}
\]
is decreasing on intervals $(-\infty, x_1)$, $(x_1, x_2), \dots, (x_{n-1}, x_n), (x_n, \infty)$ from $\infty$ to $-\infty$ or $0$, because
\[
f'(x) = - \left(\frac 1 {(x - x_1)^2} + \dots + \frac 1 {(x - x_n)^2}\right) < 0.
\]
Note that $f(x) < 0$ on $(-\infty, x_1)$.
The set in question is a union of $n$ intervals $(x_1, y_1), \dots, (x_n, y_n)$ with $y_k \in (x_k, x_{k+1})$
for $k = 1, \dots, n-1$, $y_n \in (x_n, \infty)$,
and $f(y_1) = \dots = f(y_n) = c$. 

Note that
$y_1, \dots, y_n$ are $n$ distinct roots of the polynomial $cP - P'$. Let $P = a_n x^n + \dots a_1 x + a_0$. A Vieta's formula now gives
\[
x_1 + \dots + x_n = -\frac{a_{n-1}}{a_n},
\]
\[
y_1 + \dots + y_n = \frac{na_n - ca_{n-1}}{ca_n} = \frac n c - \frac{a_{n-1}}{a_n}.
\]
\item
Let $A$ be the set of vertices of the original graph.
Find the largest connected single-coloured subgraph \textcolor{blue}{$G_1$} with its set of vertices $A_1$ and assume that $|A_1| < n/2$. Take any $x \in A_1$ and $y \not \in A_1$.
The edge \textcolor{red}{$xy$} is not of the same colour as \textcolor{blue}{$G_1$} by the maximality of \textcolor{blue}{$G_1$}. Let \textcolor{red}{$G_2$} denote the largest connected single-coloured subgraph containing \textcolor{red}{$xy$} and let $A_2$ be its set of vertices. Note that
\begin{itemize}
\item
$x \in A_1 \cap A_2 \neq \emptyset$,
\item
$y \in A_2 \setminus A_1 \neq \emptyset$,
\item
$A_1 \setminus A_2 \neq \emptyset$, because otherwise 
$|A_1| < |A_2|$ contradicts the maximality of \textcolor{blue}{$G_1$},
\item
$A \setminus (A_1 \cup A_2) \neq \emptyset$, because $|A_1 \cup A_2| < 2 \cdot n/2 = n$.
\end{itemize}
Any edge between 
$A_2 \setminus A_1$ and $A_1 \setminus A_2$
must be of the \textcolor{teal}{third color} (by the maximality of \textcolor{blue}{$G_1$} and \textcolor{red}{$G_2$}). \textcolor{teal}{These edges} form a connected subgraph with the set of vertices $A_1 \triangle A_2 := (A_2 \setminus A_1) \cup (A_1 \setminus A_2)$.
The same is true for \textcolor{teal}{edges} between $A_1 \cap A_2$ and $A \setminus (A_1 \cup A_2)$. These form a \textcolor{teal}{connected subgraph} with the set of vertices $A \setminus (A_1 \triangle A_2)$. One of $A \setminus (A_1 \triangle A_2)$ and $A_1 \triangle A_2$ must have at least $n/2$ vertices.
\end{enumerate}
\end{document}
