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

\newcommand{\R}{{\mathbb R}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\e}{\varepsilon}
\DeclareMathOperator{\dist}{dist}
\newcommand{\rank}{\operatorname{rank}}
\everymath{\displaystyle}

\begin{document}

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

\begin{enumerate}
\item
Funktsioon $f \in C^2[0,1]$ (kaks korda pidevalt diferentseeruv lõigus $[0,1]$)
rahuldab tingimusi:
\begin{enumerate}
\item $f(0) = f'(0) = 1$,
\item $f''(x) \geq 0$ iga $x \in (0,1)$ korral,
\item $\int_0^1 f(x) dx = \frac{3}{2}$.
\end{enumerate}
Leia kõik sellised funktsioonid $f$.
\item
Olgu $x_1, x_2, \dots, x_n$ nullist erinevad elemendid vektorruumis ja olgu $A$ selline lineaarne teisendus, et
\[
	Ax_1 = x_1
\]
ja
\[
Ax_k = x_k + x_{k-1}, \ k = 2, 3, \dots, n.
\]
Tõesta, et elemendid $x_1, \dots, x_n$ on lineaarselt sõltumatud.
\item
Olgu $P(x) = ax^2 + bx + c$, kus $a,b,c \in \R$. Seejuures $0 \leq P(-1) \leq 1$,
$0 \leq P(0) \leq 1$ ja $0 \leq P(1) \leq 1$. Tõesta, et $P(x) \leq 9 / 8$
iga $x \in [0,1]$ korral.  
\item
Tasandil on antud $n$ punkti. Tõesta, et kehtib üks järgmistest võimalustest:
\begin{itemize}
\item kas kõik need punktid asetsevad ühel ja samal sirgel,
\item või leidub sirge, mis läbib täpselt 2 punkti.
\end{itemize}
\item
Olgu antud $2013 \times 2013$ ruutmaatriksid $A$ ja $B$, kusjuures $AB=0$. Tõesta, et vähemalt üks maatriksidest
$A + A^T$ ja $B + B^T$ on singulaarne.
\item
Tähistame
\[
M := \{x \in \R: \textnormal{rida} \sum_{n=0}^\infty \sin(n! \pi x) \textnormal{ koondub}\}.
\]
Tõesta, et
\begin{itemize}
\item[(a)] $M$ on kõikjal tihe, s.t. suvalise lõigu ja hulga $M$ ühisosa ei ole tühi, (5 punkti)
\item[(b)] $e \in M$, (15 punkti)
\item[(c)] hulga $M$ sees ei leidu ühtegi lõiku. (20 punkti)
\end{itemize}
\end{enumerate}

\newpage
\begin{enumerate}

\item
Find all functions $f \in C^2[0,1]$ (two times continuously differentiable on the interval $[0,1]$)
such that:
\begin{enumerate}
\item $f(0) = f'(0) = 1$,
\item $f''(x) \geq 0$ for all $x \in (0,1)$,
\item $\int_0^1 f(x) dx = \frac{3}{2}$.
\end{enumerate}
\item
Let $x_1, x_2, \dots, x_n$ be nonzero elements in a vector space and let $A$ be a linear transformation such that
\[
	Ax_1 = x_1
\]
and
\[
Ax_k = x_k + x_{k-1}, \ k = 2, 3, \dots, n.
\]
Prove that elements $x_1, \dots, x_n$ are linearly independent.
\item
Let $P(x) = ax^2 + bx + c$, where $a,b,c \in \R$, satisfy $0 \leq P(-1) \leq 1$,
$0 \leq P(0) \leq 1$, and $0 \leq P(1) \leq 1$. Prove that $P(x) \leq 9 / 8$
for all $x \in [0,1]$.  
\item
Take $n$ points on a plane. Prove that one of the following conditions holds:
\begin{itemize}
\item all of these points lie on the same line,
\item there exists a line with exactly two of these points.
\end{itemize}
\item
Let $A$ and $B$ be $2013 \times 2013$ square matrices such that $AB=0$. Prove that at least one of the matrices
$A + A^T$ and $B + B^T$ is not invertible.
\item
Denote
\[
M := \{x \in \R: \textnormal{the series} \sum_{n=0}^\infty \sin(n! \pi x) \textnormal{ converges}\}.
\]
Prove that
\begin{itemize}
\item[(a)] $M$ is dense, i.e., the intersection of any interval and $M$ is not empty, (5 points)
\item[(b)] $e \in M$, (15 points)
\item[(c)] $M$ does not contain any interval. (20 points)
\end{itemize}
\end{enumerate}

\newpage

\setcounter{section}{1}
\section{Solutions}
\begin{enumerate}
\item
By (b) we know that $f'(x) \geq f'(0) = 1$ for all $x \in [0,1]$. Then $f(x) - f(0) = \int_{0}^x f'(y)dy \geq \int_0^x dy = x$,
so that $f(x) \geq 1 + x$. Now $f(x) - 1 - x$ is a continuous function on $[0,1]$ such that
\[
\int_0^1 |f(x) - 1 - x|dx = \int_0^1 f(x)dx - \int_0^1 (1+x) dx = \frac{3}{2} - \frac{3}{2} = 0.
\]
Hence, $|f(x) - 1 - x| = 0$ for all $x \in [0,1]$. That is, $f(x) = x+1$. 
\item
Let us prove it by induction. The case $n=1$ is obvious. Assume the claim is true for $n-1$.
If $x_1, \dots, x_n$ were linearly dependent, then $c_1 x_1 + \dots + c_n x_n = 0$
for some non-zero vector $(c_1, \dots, c_n)$.
Then $c_1 A x_1 + \dots + c_n A x_n = 0$. Substracting the former equation from the latter, and noting that
$Ax_1 - x_1 = 0$ and $Ax_k - x_k = x_{k-1}$ for $k \geq 1$, we get $c_2 x_1 + \dots + c_n x_{n-1} = 0$.
By assumption, $c_2 = c_3 = \dots = c_n = 0$, so that $c_1 x_1 = 0$. But $x_1 \neq 0$ and $c_1 = 0$ contradicts the choice of $c_1$.
\item
Put $Q(x) := P(x) - 1/2$. Then $|Q(-1)|, |Q(0)|, |Q(1)| \leq 1/2$. The Lagrange polynomial for $\{-1,0,1\}$ must coincide with $Q(x)$, so
\[
Q(x) = \frac{x(x-1)}{2} Q(-1) + (1-x^2)Q(0) + \frac{x(x+1)}{2} Q(1).
\]
Now for $x \in [-1,1]$ we have
\[
Q(x) \leq \frac{1}{2} \max_{x \in [-1,1]} \left( \left|\frac{x(x-1)}{2}\right| + \left|1-x^2\right| + \left|\frac{x(x+1)}{2}\right|\right) = \frac{1}{2} \cdot \frac{5}{4} = \frac{5}{8}.
\]
Then $P(x) = \frac{1}{2} + Q(x) \leq \frac{9}{8}$ for all $x \in [-1,1]$.

\item
The case $n \leq 2$ is obvious. Let $n \geq 3$ and assume that for every two points there is a third one on the same line.
Choose a pair consisting of a line defined by two points $A$ and $B$ (which must also have a third point $C$) and of a point $D$ outside this line such that
the distance from $D$ to the line is the least possible (among all the pairs). Let $H$ be a point on this line (which is not necessarily one of the $n$ points) such that
$DH \perp AB$. Of $A$, $B$, $C$ at least two points are on the same side with respect to $H$. Without loss of generality we can assume that $B$ is between
$A$ and $H$. Now the distance from $B$ to the line $AD$ is less than $|DH|$, which contradicts the choice of our pair. Therefore, there is no such pair and all the points
lie on the same line.

\item
\textbf{Lemma 1.} If $A$ and $B$ are matrices of the same size, then $\rank(A+B) \leq \rank A + \rank B$.

\textbf{Lemma 2.} If $A$ and $B$ are square matrices of order $n$, then $\rank A + \rank B \leq \rank(AB) + n$.

By Lemma~2,
\[
\rank A + \rank B \leq \rank(AB) + 2013 = 2013.
\]
Hence, one of the numbers $\rank A$, $\rank B$ is not greater than $\lfloor2013/2\rfloor = 1006$.
Let us assume that $\rank A \leq 1006$, then $\rank A^T = \rank A \leq 1006$. By Lemma~1,
\[
\rank (A+A^T) \leq \rank A + \rank A^T \leq 2012 < 2013.
\]
\item
\begin{enumerate}
\item
In any interval there is a rational point $p/q$, $q > 0$. If $n \geq q$ then
$n!x = p(q-1)(q+1)\dots n$ is an integer, so that $\sin(n!\pi x) = 0$. Hence, the series
\[
\sum_{n=0}^\infty \sin(n!\pi x)
\]
converges.
\item
The Taylor expansion of $e^t$ at $t = 1$ yields
\[
n!e = \sum_{k=0}^\infty \frac{n!}{k!} = \sum_{k=0}^{n-2} \frac{n!}{k!} + (n+1) + \frac{1}{n+1} + \sum_{k=n+2}^\infty \frac{n!}{k!}
\]
for $n \geq 2$. Note that
\[
\sum_{k=0}^{n-2} \frac{n!}{k!} = n(n-1)\sum_{k=0}^{n-2} \frac{(n-2)!}{k!}
\]
is an even number and
\[
\sum_{k=n+2}^\infty \frac{n!}{k!} = \frac{1}{(n+1)(n+2)} + \frac{1}{(n+1)(n+2)(n+3)} + \dots \leq \sum_{m=0}^\infty \frac{1}{(n+1)(n+2)(n+3)^m} 
\]
\[
= \frac{n+3}{(n+1)(n+2)^2} = O\left(\frac{1}{n^2}\right).
\]
Note that $|\sin x - \sin y| \leq |x-y|$, so that $\sin(x+y) = \sin x + z$, where $|z| \leq |y|$. Therefore,
\[
\sin(n!\pi e) = \sin\left(\pi\sum_{k=0}^{n-2} \frac{n!}{k!} + \pi(n+1) + \frac{\pi}{n+1} + \pi \sum_{k=n+2}^\infty \frac{n!}{k!}\right) =
\sin\left(\pi(n+1) + \frac{\pi}{n+1} + \pi \sum_{k=n+2}^\infty \frac{n!}{k!}\right)
\]
\[
 = \sin\left(\pi(n+1) + \frac{\pi}{n+1}\right) + \theta_n = (-1)^{n+1}\sin(\frac{\pi}{n+1}) + \theta_n,
\]
where $|\theta_n| \leq \pi \sum_{k=n+2}^\infty \frac{n!}{k!} =  O\left(\frac{1}{n^2}\right)$.
Now the series
\[
\sum_{n=2}^\infty (-1)^{n+1}\sin(\frac{\pi}{n+1})
\]
converges by the alternating series test and the series
\[
\sum_{n=2}^\infty \theta_n
\]
converges absolutely. Hence, the series
\[
\sum_{n=0}^\infty \sin(n!\pi e) = 2\sin \pi e + \sum_{n=2}^\infty (-1)^{n+1}\sin(\frac{\pi}{n+1}) + \sum_{n=2}^\infty \theta_n
\]
converges as well.
\item
Let us prove that any interval $[a,b]$, $a < b$, contains a point $x \not \in M$.
Take a natural number $n_1$ such that $2/n_1! < b - a$. Then there exists an integer $m_1$ such that
\[
a \leq \frac{m_1}{n_1!} < \frac{(m_1 + 1)}{n_1!} \leq b.
\]
Put 
\[
a_1 := \frac{(m_1 + \frac{1}{3})}{n_1!}, \quad b_1 := \frac{(m_1 + \frac{2}{3})}{n_1!}.
\]
Note that $[a_1, b_1] \subset [a,b]$ and for any $x \in [a_1,b_1]$ one has
\[
\left|\sin n_1! \pi x\right| \geq \sin \frac{\pi}{3} = \frac{\sqrt 3}{2}.
\]
Let us now take $n_2 > n_1$ and $m_2$ such that $2/n_2! < b_1 - a_1$ and
\[
a_1 \leq \frac{m_2}{n_2!} < \frac{(m_2 + 1)}{n_2!} \leq b_1.
\]
Denoting
\[
a_2 := \frac{(m_2 + \frac{1}{3})}{n_2!}, \quad b_2 := \frac{(m_2 + \frac{2}{3})}{n_2!}.
\]
we get $[a_2,b_2] \subset [a_1,b_1]$ and 
$\left|\sin n_2! \pi x\right| \geq \sin \frac{\pi}{3} = \frac{\sqrt 3}{2}$
for any $x \in [a_2, b_2]$.

If we continue in this way, we obtain a system of nested intervals
\[
[a,b] \supset [a_1, b_1] \supset [a_2,b_2] \supset \dots
\]
and an increasing sequence of natural numbers $n_1 < n_2 < \dots$ such that
$\left|\sin n_k! \pi x\right| \geq \sin \frac{\pi}{3} = \frac{\sqrt 3}{2}$
for all $x \in [a_k, b_k]$.

Taking $x \in \bigcap_{k=1}^\infty [a_k,b_k]$ we get $\left|\sin n_k! \pi x\right| \geq \sin \frac{\pi}{3} = \frac{\sqrt 3}{2}$
for $k = 1, 2, \dots$. Thus the series
\[
\sum_{n=0}^\infty \sin(n! \pi x)
\]
diverges and $x \not \in M$.
\end{enumerate}
\end{enumerate}

\end{document}
