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

\newcommand{\Mat}{\operatorname{Mat}}
\newcommand{\e}{\varepsilon}
\everymath{\displaystyle}

\begin{document}
\title{Matemaatika võistlus}
\date{Tartu, 19.10.2018}
\maketitle
\thispagestyle{empty}

\begin{enumerate}

\item
Rahuldagu tõkestatud jada $(x_n)_{n=1}^\infty \subset \mathbb R$ tingimust $x_n - 2x_{n+1} + x_{n+2} \to 0$. Tõesta, et $x_n - x_{n+1} \to 0$. 


\item
Rahuldagu funktsioon $f: [0,1] \to \mathbb R$ võrratust
\[
f\left(\frac{x+y}2\right) \leq f(x) + f(y)
\]
kõikide $x, y \in [0,1]$ korral ning olgu $f(0) = f(1) = 0$.
\begin{enumerate}
\item
Tõesta, et $f(x) \geq 0$ iga $x \in [0,1]$ korral.
\item
Tõesta, et $f(x) = 0$ lõpmata paljudes punktides $x \in [0,1]$.
\item
Tuua näide ülesande tingimust rahuldavast mittekonstantsest funktsioonist $f$.
\end{enumerate}

\item
Olgu $p > 2$ algarv. Leia arvude 
\[
1 + \sum_{n=1}^{\frac{p-1}{2}} \binom{2n}{n} c^n, \quad c \in \mathbb N,
\]
kõik võimalikud jäägid jagamisel arvuga $p$.

\item
Olgu $n \in \mathbb N$, olgu $P_1, \dots, P_n$ nullist erinevad reaalarvuliste kordajatega polünoomid vastavalt astmetega
$m_1, \dots, m_n$ ning olgu $a_1, \dots, a_n$ paarikaupa erinevad reaalarvud. Tõesta, et võrrandil
\[
P_1(x)e^{a_1 x} + P_2(x)e^{a_2 x}  + \dots + P_n(x)e^{a_n x} = 0
\] 
on ülimalt $m_1 + \dots + m_n + n - 1$ reaalarvulist lahendit.
\item
Kehtigu reaalarvuliste $n \times n$ ruutmaatriksite $A$, $B$ ja $C$ korral
$A^3 = -I$ ja $BA^2 + BA = C^6 + C + I$ (siin $I$ on ühikmaatriks) ning olgu $C$ sümmeetriline.
Tõesta, et $n$ ei saa olla paaritu. 
\end{enumerate}
\newpage

\title{Math competition}
\date{Tartu, 19.10.2018}
\maketitle
\thispagestyle{empty}

\begin{enumerate}

\item
A bounded sequence $(x_n)_{n=1}^\infty \subset \mathbb R$ is such that $x_n - 2x_{n+1} + x_{n+2} \to 0$. Prove that $x_n - x_{n+1} \to 0$. 

\item
The function $f: [0,1] \to \mathbb R$ is such that
\[
f\left(\frac{x+y}2\right) \leq f(x) + f(y)
\]
for all $x, y \in [0,1]$ and also $f(0) = f(1) = 0$.
\begin{enumerate}
\item
Prove that $f(x) \geq 0$ for all $x \in [0,1]$.
\item
Prove that $f(x) = 0$ for infinitely many $x \in [0,1]$.
\item
Provide an example of a non-constant function $f$.
\end{enumerate}

\item
Let $p > 2$ be a prime number. Find all possible residues modulo $p$ of numbers 
\[
1 + \sum_{n=1}^{\frac{p-1}{2}} \binom{2n}{n} c^n, \quad c \in \mathbb N.
\]

\item
Let $n \in \mathbb N$, let $P_1, \dots, P_n$ be non-zero polynomials with real coefficients of degrees
$m_1, \dots, m_n$ respectively, and let $a_1, \dots, a_n$ be pairwise distinct real numbers. Prove that the equation
\[
P_1(x)e^{a_1 x} + P_2(x)e^{a_2 x}  + \dots + P_n(x)e^{a_n x} = 0
\]
has at most $m_1 + \dots + m_n + n - 1$ real solutions.
\item
Real $n \times n$ matrices $A$, $B$, and $C$ are such that 
$A^3 = -I$ and $BA^2 + BA = C^6 + C + I$ (here $I$ denotes a unit matrix). Also, $C$ is symmetric.
Prove that $n$ cannot be odd. 
\end{enumerate}
\newpage
\begin{enumerate}
\item
Denote $a_n := x_n - x_{n+1}$ and assume that $a_n \not \to 0$. We can find $\e > 0$ and a subsequence of $(a_n)$
which lies outside of $(-\e, \e)$. In that, since $(a_n)$ is bounded, we can find a further subsequence, which converges to some $a \neq 0$. In that, we can find a subsequence $(a_{n_k})$ such that $x_{n_k}$ goes to some $x \in \mathbb R$. 
So $x_{n_k + 1} = x_{n_k} - a_{n_k} \to x - a$.
But since $a_{n} - a_{n + 1} \to 0$, not only $a_{n_k} \to a$ but also $a_{n_k + m} \to a$ for any $m \in \mathbb N$. It follows that $x_{n_k + m} \to x - ma$ for any $m \in \mathbb N$. This contradicts the boundedness of $(x_n)$.
\item
\begin{enumerate}
\item
Assume $f(x) < 0$ for some $x \in [0,1]$. We have
\[
f(\frac x 2) \leq f(\frac x 4) + f(\frac{3x}4) \leq f(0) + f(\frac x 2) + f(\frac x 2) + f(x) < 2f(\frac x 2),
\]
so $f(\frac x 2) > 0$. But 
\[
f(\frac x 2) \leq f(0) + f(x) < 0.
\]
\item
It follows that if $f(x) = f(y) = 0$, then also $f(\frac{x+y}2) = 0$. Starting from $f(0) = f(1) = 0$, we arrive
at $f(x) = 0$ for any $x = a_1 + a_2 2^{-1} + a_3 2^{-2} + \dots + a_n 2^{-n}$ for some $n \in \mathbb N$ and $(a_i) \in \{0, 1\}^n$.
\item
Denote the set of all $x$ as above by $A$. Put $f(y) = 0$ if $y \in A$ and $f(y) = 1$ otherwise.

Clearly, $A$ is closed under operation $x,y \mapsto \frac{x+y}2$. So the inequality is satisfied for all $x,y \in A$. If one of $x,y$ is not in $A$, then also $f(x) + f(y) \geq 1 + 0 = 1 \geq f(\frac{x+y}2)$.
 
\end{enumerate}
\item
Note that the binomial expansion
\[
(1+a)^{\frac{p-1}2} = 1 + \sum_{n=1}^{\frac{p-1}{2}} \binom{\frac{p-1}{2}}{n} a^n
\]
looks very similar to the expression in question. So let us compare $\binom{2n}{n}$ to $\binom{\frac{p-1}{2}}{n}$ modulo $p$. But first note that $(-2)(\frac{p-1}{2} - i) = 2i - (p-1) \equiv 2i + 1$. We have
\[
\binom{2n}{n} = \frac{(2n)!}{(n!)^2} = \frac{2^n(1 \cdot 3 \cdot \dots \cdot (2n-1))}{n!}
\equiv \frac{(-4)^n\frac{p-1}{2}(\frac{p-1}{2} - 1)\cdot \dots \cdot (\frac{p-1}{2} - (n-1))}{n!} = (-4)^n \binom{\frac{p-1}{2}}{n}
\]
(the congruence is legal, because clearly  $n!$ is invertible modulo $p$). Thus 
\[
1 + \sum_{n=1}^{\frac{p-1}{2}} \binom{2n}{n} c^n \equiv 1 + \sum_{n=1}^{\frac{p-1}{2}} \binom{\frac{p-1}{2}}{n} (-4)^n c^n = (1-4c)^{\frac{p-1}{2}} \equiv (4(4^{-1} - c))^{\frac{p-1}{2}} \equiv (4^{-1} - c)^{\frac{p-1}{2}},
\]
because $4^{\frac{p-1}{2}} = 2^{p-1} \equiv 1$. So the question reduces to finding the possible values of $b^{\frac{p-1}{2}}$ modulo $p$ when $b$ runs in $\mathbb N$. By Euler's criterion these are $-1$, $0$, and $1$.

\item
We prove by induction on $n$. Base $n=1$ is clear. Denote 
\[
g(x) := P_1(x)e^{a_1 x} + P_2(x)e^{a_2 x}  + \dots + P_n(x)e^{a_n x}.
\]
Assume that $g(x)$ has $N$ real zeroes. Then $e^{-a_n x} g(x)$ has as many and $(e^{-a_n x} g(x))'$ has at least $N-1$. Continuing in this fashion, we get that $(e^{-a_n x} g(x))^{(m_n+1)}$ has at least $N - m_n - 1$ real zeroes. But $(e^{-a_n x} g(x))^{(m_n+1)} = (e^{-a_n x} g(x) - P_n(x))^{(m_n+1)}$. The latter function satisfies the induction hypothesis for $n-1$ (the degrees of the new polynomials do not exceed those of $P_1, \dots, P_{n-1}$). So 
\[
N - m_n - 1 \leq m_1 + \dots + m_{n-1} + n - 2,
\]
from which the claim follows.
\item
Since $C$ is symmetric, it is diagonalizable. So it cannot be singular, because the polynomial $x^6 + x + 1$
does not have real roots. So $BA(A+I)$ is regular and so is $A+I$. But $(A^2 - A + I)(A+I) = A^3 + I = 0$ and hence $A^2 - A + I = 0$. The polynomial $x^2 - x + 1$ does not have real roots. So $A$ does not have real eigenvalues. But any matrix of odd order must have at least one real eigenvalue (by the intermediate value theorem applied to the characteristic polynomial).
\end{enumerate}
\newpage
Kommentaarid ja osalised hindamisskeemid:
\begin{enumerate}
\item
Paljudel oli arutelu, et $a_n - a_{n+1} \to 0$ annab, et $(a_n)$ on Cauchy (ja seega koondub), tihti järgmise ``tõestusega'': $|a_n - a_{n+p}| \leq |a_n - a_{n+1}| + |a_{n+1} - a_{n+2}| + \dots + |a_{n+p-1} - a_{n+p}| \to 0$.

See on vale. Lihtsaks kontranäideks on harmoonilise rea osasummad $S_n = 1 + \dots + \frac 1 n \to \infty$.
Veelgi enam, selle näite põhjal saab natuke mõeldes konstrueerida ka tõkestatud mittekoonduva jada sama omadusega. 

Skeem: 
\begin{itemize}
\item[7p:] Tehtud eeldusel või valesti tõestades, et $(a_n)$ koondub.
\item[6p:] Sama, aga pole aru saadud, et see eeldus on tehtud.
\item[1p:] Tehtud eeldusel, et $(x_n)$ koondub.
\end{itemize}

\item
Osa a) palju lihtsam tõestus on muidugi võtta $x=y$.

Skeem: 20p = a) 7p + b) 7p + c) 6p.

\item
Skeem: 3p õige vastuse eest. Triinule lisaks 2p avaldiseni $(-1)^{\frac{p-1}2}$ jõudmise eest, kust oleks võinud tekkida idee vaadata lahenduses toodud binoomvalemit.

\item
Skeem: 3p punkti tuletise $(e^{ax} P(x))'$ vaatamise eest, mis on oluline samm õiges suunas.

\item
Skeem: 2p maatriksi $C$ omaväärtuste vaatamise eest. 
\end{enumerate}
\end{document}
