\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}
\DeclareMathOperator{\rank}{rank}

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

\begin{enumerate}
\item
Olgu $p$ algarv. On teada, et ükski täisarvudest $a_1, \dots, a_{p-1}$ ei jagu arvuga $p$.
Kas alati iga $r = 1, \dots, p-1$ jaoks  leidub selline indeksite hulk $I \subseteq \{1, \dots, p-1\}$ nii, et
summa $\sum_{i \in I} a_i$ jagamisel arvuga $p$ annab jäägi $r$?

\item
Olgu funktsioon $f: [0,1] \to [0,1]$ pidev ja mittekahanev lõigus $[0,1]$ ja diferentseeruv vahemikus $(0,1)$,
kusjuures $f'(x) < 1$ iga $x \in (0,1)$ korral. 
Tähistame $A_0 = [0,1]$ ja $A_{n+1} = f(A_n)$ iga $n = 0, 1, \dots$ jaoks. 
Tõesta, et $\sup_{x,y \in A_n} |x-y| \to 0$.

\item
Olgu $n$ ja $m$ positiivsed täisarvud ning olgu $A_1, \dots, A_m$ idempotentsed $(n \times n)$-maatriksid (st $A^2 = A$). 
Tähistagu $I$ samasusteisendust.
Tõesta, et 
\[
\sum_{i=1}^m \dim\ker A_i \geq \operatorname{rank}(I - A_1 A_2\ldots  A_m).
\]
(Siin $\dim$ tähendab vektorruumi mõõdet; $\ker A = A^{-1}(0)$ on maatriksi nullruum; $\rank$ on maatriksi astak.)


\item
Ühe keele tähestik koosneb $n$ tähest, kusjuures kõik sõnad on lõplikud ning ükski sõna ei ole mingi teise sõna alguseks. Tähistagu $a_k$ selle keele nende sõnade arvu, mille pikkus on $k \in \mathbb N$. Tõesta, et
\[
\sum_{k \geq 1} \frac{a_k}{n^k} \leq 1.
\]

\item
Olgu $x > 0$. Tõesta, et
\[
\lim_{n \to \infty} \frac{1^{x-1} + 2^{x-1} + \dots + n^{x-1}}{n^x} = \frac 1 x.
\]


\end{enumerate}
\newpage

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

\begin{enumerate}
\item
Let $p$ be a prime number, which does not divide any of the integers $a_1, \dots, a_{p-1}$.
Is it always true, that for any $r = 1, \dots, p-1$ one can find a subset $I \subseteq \{1, \dots, p-1\}$ of indices such that the remainder of $\sum_{i \in I} a_i$ when divided by $p$ is $r$?

\item
Let $f: [0,1] \to [0,1]$ be continuous function non-decreasing on $[0,1]$ and differentiable on $(0,1)$ such that $f'(x) < 1$ for all $x \in (0,1)$. 
Denote $A_0 = [0,1]$ and $A_{n+1} = f(A_n)$ for all $n = 0, 1, \dots$. 
Show that $\sup_{x,y \in A_n} |x-y| \to 0$.

\item
Let $n$ and $m$ be positive integers and let $A_1, \dots, A_m$ be idempotent $(n \times n)$-matrices (i.e. $A^2 = A$). 
Let $I$ denote the identity.
Prove that
\[
\sum_{i=1}^m \dim\ker A_i \geq \operatorname{rank}(I - A_1 A_2\ldots  A_m).
\]
(Here $\dim$ denotes the dimension of a vector space; $\ker A = A^{-1}(0)$ is a kernel of a matrix; $\rank$ is the rank of a matrix.)


\item
Some language uses $n$ letters. Every its word is finite and no word is a prefix of any other word. Let $a_k$ denote the number of words of length $k \in \mathbb N$. Prove that
\[
\sum_{k \geq 1} \frac{a_k}{n^k} \leq 1.
\]

\item
Let $x > 0$. Prove that
\[
\lim_{n \to \infty} \frac{1^{x-1} + 2^{x-1} + \dots + n^{x-1}}{n^x} = \frac 1 x.
\]
\end{enumerate}

\newpage
\paragraph{Solutions}
\begin{enumerate}
\item
Clearly (e.g., by induction), it is enough to show that given $k < p-1$ different nonzero elements  $r_1, \dots, r_k$ of $\mathbb Z_p$ and some other nonzero $n \in \mathbb Z_p$, one of $r_i+n$ or $n$ itself would differ from all the $r_i$'s.

Try $n$, if $n$ is among $r_i$'s, try $2n$ and so on. Since all $n, 2n, \dots, (p-1)n$ are different, this can only continue until $kn$. Then $(k+1)n$ will fit the requirements.

\item
Since $f$ is non-decreasing, the sequence $(f^n(0))$ is bounded and non-decreasing, while $(f^n(1))$ is bounded and non-increasing. Moreover, each consists of (lower or, respectively, upper) bounds for the other. Take $m := \lim f^n(0)$ and $M := \lim f^n(1)$. Clearly $m \leq M$. Since $f$ is continuous they are both fixed points: indeed, e.g., $f(m) = \lim f(f^n(0)) = \lim f^{n+1}(0) = m$. If $M \neq m$, then the mean value theorem gives $\xi \in (m, M)$ such that
\[
M - m = f(M) - f(m) = f'(\xi)(M - m) < M - m.
\]
So, $\sup_{x,y \in A_n} |x - y|= f^n(1) - f^n(0) \to 0$.
\item
If $A$ is idempotent, then $I-A$ is idempotent and the vector space $V := \mathbb R^n$ can be decomposed as $V = A(V) + (I-A)(V)$ with $A(V) \cap (I-A)(V) = \{0\}$. In particular $\rank A = \dim A(V) = n - \dim(I-A)(V) = n - \rank(I-A)$.

So 
\[
\rank(I-A_1) = n - \rank A_1 = n - (n - \dim \ker A_1) = \dim \ker A_1.  
\]
By induction (using $\rank(A+B) \leq \rank A + \rank B$ and $\rank(AB) \leq \rank A$), we get that
\begin{align*}
\sum_{ i < n} \dim \ker A_i + \dim \ker A_n &\geq
\rank (I - \prod_{i < n} A_i) + \rank(I - A_n)\\
&
\geq \rank ((I - \prod_{i < n} A_i)A_n + I - A_n)\\
&= \rank(I - \prod_{i \leq n} A_i).
\end{align*}

\item
Consider first all possible words (perhaps not in the language) of length $m$: their number is $n^m$. Given a language word of length $k \leq m$, we can have exactly $n^{m-k}$ possible words of length $m$ containing the given word as a prefix. By the assumption none of these possible words contains any other language word as a prefix. Thus, we have
\[
\sum_{1 \leq k \leq m} a_k n^{m-k} \leq n^m.
\]
Dividing by $n^m$, we obtain
\[
\sum_{1 \leq k \leq m} a_k n^{-k} \leq 1,
\]
from where the claim follows after taking the limit on $m$.

\item
One way to do it is to take $f(t) = t^{x-1}$ in the general result below.

Let $f: [0,1] \to \mathbb R$ be monotone on $(0,1)$ such that the (maybe improper) integral $\int_0^1 f(t)dt$ exists. Then
\[
\lim_{n\to \infty} \frac{f(\frac 1 n) + f(\frac 2 n) + \dots + f(\frac{n-1}{n})}{n} =  \int_0^1 f(t)dt.
\] 

Indeed, assume, e.g., that $f$ is non-decreasing. Then 
\[
\int_0^{1 - \frac 1 n} f(t)dt \leq 
\frac{f(\frac 1 n) + f(\frac 2 n) + \dots + f(\frac{n-1}{n})}{n}
\leq \int_{\frac 1 n}^{1} f(t)dt.
\]
\end{enumerate}
\end{document}
