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

\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{20.05.2016}
\maketitle
\thispagestyle{empty}

\begin{enumerate}
\item
Olgu $A = (a_{ij})$ mittenegatiivsete elementidega $n\times n$ maatriks, kusjuures
\[
\sum_{j=1}^n a_{ij} = 1
\]
kõikide $i = 1, \dots, n$ korral. Olgu $\lambda$ maatriksi $A$ mingi omaväärtus.
Tõesta, et $|\lambda| \leq 1$.
\item 
Olgu $f : \mathbb R \to [-1, 1]$ kaks korda pidevalt diferentseeruv, kusjuures
\[
f(0)^2 + (f'(0))^2 = 4.
\]
Tõesta, et leidub $x_0 \in \mathbb  R$, mille korral
\[
f(x_0) + f''(x_0) = 0.
\]
\item
Nimetame paari $(X, *)$ \emph{auguga rühmoidiks}, kui $X \subset \mathbb N$ on hulk, $*:X \times X \to X \cup \{0\}$
(võib mõelda, et $*$ on tehe hulgal $X$, mille mõned väärtused on defineerimata), $a_0*b_0 = 0$ täpselt ühe paari $(a_0,b_0) \in X \times X$ korral ning leidub $c \in X$ nii, et $a*b = c$ kõikide teiste paaride $(a,b) \in X \times X$ korral (mis erinevad paarist $(a_0, b_0)$). Teiste sõnadega vastava Cayley tabeli elemendid on kõik samad v.a. üks, mis on ``defineerimata''.

Ütleme, et kaks auguga rühmoidi $(X_1, *_1)$ ja $(X_2, *_2)$ on \emph{isomorfsed}, kui leidub bijektiivne kujutus $T : X_1 \cup \{0\} \to X_2 \cup \{0\}$ nii, et $T(0) = 0$ ja  $T(x*_1y) = T(x)*_2T(y)$ kõikide $x, y \in X_1$ korral.

Olgu $n \geq 2$. Kui palju leidub paarikaupa mitteisomorfseid auguga rühmoide $(X, *)$, mille hulgas $X$ on $n$ elementi?
\item
Tõesta, et leidub parajasti üks funktsioon $y:[0,\infty) \to \mathbb R$, mis rahuldab
\[
y(x)^3 + xy(x) = 8
\]
kõikide $x \geq 0$ korral ning arvuta
\[
\int_0^7 y(x)^2 dx.
\]
\item
Leia kõik arvud $n$, mille korral leidub reaalarvuline $n \times n$ maatriks $A$ nii, et
\[
A^2 + 2A + 5I = 0.
\]
\item
\begin{enumerate}
\item
Olgu $f:[0, \infty) \to \mathbb R$ monotoonne funktsioon, kusjuures päratu integraal 
$\int_0^\infty f(x) dx$
koondub. Tõesta, et
\[
\lim_{h \to 0+} h \sum_{n=1}^\infty f(nh) = \int_0^\infty f(x) dx.
\]
\item 
Arvuta
\[
\lim_{t \to 1-} (1-t)\sum_{n=1}^\infty \frac{t^n}{1 + t^n}.
\]
\end{enumerate}
\end{enumerate}
\newpage
\thispagestyle{empty}

\begin{enumerate}
\item
Let $A = (a_{ij})$ be a real $n\times n$ matrix with non-negative entries such that
\[
\sum_{j=1}^n a_{ij} = 1
\]
for all $i = 1, \dots, n$.
Prove that no eigenvalue of $A$ has absolute value greater than $1$.
\item 
Suppose that $f : \mathbb R \to [-1, 1]$ is two times continuously differentiable and that
\[
f(0)^2 + (f'(0))^2 = 4.
\]
Prove that there exists $x_0 \in \mathbb  R$ such that
\[
f(x_0) + f''(x_0) = 0.
\]
\item
Let us call a pair $(X, *)$ a \emph{punctured magma} if $X \subset \mathbb N$ is a set, $*:X \times X \to X \cup \{0\}$
(you may think of $*$ as an operation on $X$ with some values undefined), $a_0*b_0 = 0$ for exactly one pair $(a_0,b_0) \in X \times X$, and there exists $c \in X$ such that $a*b = c$ for all other pairs $(a,b) \in X \times X$ not equal to $(a_0, b_0)$. In other words, all elements of a corresponding Cayley table are the same except for one, which is ``undefined''.

Let us call two punctured magmas $(X_1, *_1)$ and $(X_2, *_2)$ \emph{isomorphic} if there exists a bijection $T : X_1 \cup \{0\} \to X_2 \cup \{0\}$ such that $T(0) = 0$ and  
$
T(x*_1y) = T(x)*_2T(y)
$ for all $x,y \in X_1$.

Let $n \geq 2$. How many mutually non-isomorphic punctured magmas $(X, *)$ with $X$ having $n$ elements are there?
\item
Prove that there exists a unique function $y:[0,\infty) \to \mathbb R$ such that
\[
y(x)^3 + xy(x) = 8
\]
for all $x \geq 0$
and calculate
\[
\int_0^7 y(x)^2 dx.
\]
\item
Find all natural numbers $n$ for which there exists a real $n \times n$ matrix such that
\[
A^2 + 2A + 5I = 0.
\]
\item
\begin{enumerate}
\item
Let $f:[0, \infty) \to \mathbb R$ be a monotone function such that 
$\int_0^\infty f(x) dx$
converges. Prove that
\[
\lim_{h \to 0+} h \sum_{n=1}^\infty f(nh) = \int_0^\infty f(x) dx.
\]
\item 
Calculate
\[
\lim_{t \to 1-} (1-t)\sum_{n=1}^\infty \frac{t^n}{1 + t^n}.
\]
\end{enumerate}
\end{enumerate}
\newpage
\paragraph*{Solutions}
\begin{enumerate}
\item 
Take an eigenvector $x \neq 0$ corresponding to the eigenvalue $\lambda$. Let $x = (x_j)_{j=1}^n$ and let $x_i$
be such that $ |x_i|= \max_{1 \leq j \leq n} |x_j|$. Then $x_i \neq 0$. Since $\lambda x = Ax$, we have
\[
|\lambda|\cdot |x_i| = |\lambda x_i| = \left|\sum_{j=1}^n a_{ij}x_j\right| \leq  \left|\sum_{j=1}^n a_{ij}\right|\cdot \max_{1 \leq j \leq n} |x_j| = 1 \cdot |x_i|
\]
and the claim follows.
\item
Let us denote
\[
F(x) := f(x)^2 + (f'(x))^2.
\]
Then $F$ is continuously differentiable and $F' = 2f'(f + f'')$. So it is enough to find a local extremum point $x$ for $F$ such that $f'(x) \neq 0$. If we take a closed interval $[a,b]$, then $F$ must attain its maximum there. If $0 \in [a,b]$ and $F(a), F(b) \leq F(0) = 4$, then $F$ must attain maximum at the interior point $x$ of $[a, b]$, so it must be a local maximum.  Note that then $f'(x)$ cannot be $0$ because otherwise $F(x) = f(x)^2 \leq 1 < 4$.

To find a suitable $[a,b]$, let us apply the Lagrange mean value theorem to $f$ on intervals $[0,2]$ and $[-2,0]$. We obtain $b \in [0,2]$ such that
\[
|f'(b)| = \frac{|f(2) - f(0)|}2 \leq \frac{|f(2)| + |f(0)|}2 \leq \frac {1 + 1}2 = 1. 
\]
Similarly we get $a \in [-2, 0]$ such that $|f'(a)| \leq 1$. Then 
\[
F(a) = f(a)^2 + (f'(a))^2 \leq 1^2 + 1^2 = 2 < 4
\]
and $F(b) < 4$, as needed.
\item
Let $n \geq 3$. There are only 5 possible cases:
\begin{enumerate}
\item 
For some $a \in X$ we have $a * a = 0$, and $b * c = a$ for all $(b,c)$ different from $(a,a)$.
\item
For some $a \in X$ we have $a * a = 0$, and there exists $b \neq a$ such that $c * d = b$ for all $(c,d)$ different from $(a,a)$.
\item
For different $a,b \in X$ we have $a * b = 0$, and $c * d = a$ for all $(c,d)$ different from $(a,b)$.
\item
For different $a,b \in X$ we have $a * b = 0$, and $c * d = b$ for all $(c,d)$ different from $(a,b)$.
\item
For different $a,b \in X$ we have $a * b = 0$, and there exists $e$ different from both $a$ and $b$ such that $c * d = e$ for all $(c,d)$ different from $(a,b)$.
\end{enumerate}
We claim that magmas belong to the same case if and only if they are isomorphic. (By the way, let us point out that being isomorphic is clearly an equivalence relation.) Clearly, magmas $X_1$ and $X_2$ belonging to the same case are isomorphic (take any bijection connecting elements denoted by the same letters). 

A magma from (a-b) cannot be isomorphic to a magma from (c-e) because $T(a)*T(a) = 0$ means that there would be an element $x$ in the latter magma such that $x * x = 0$, which is a contradiction.

In a (b) magma there are two different elements $x, y$ such that $x*x = x$ and $y*y=y$ but in an (a) magma there is only one, so they are not isomorphic.

An isomorphism between (c-e) magmas must map elements denoted by $a,b$ to the corresponding elements. So a (c) magma (with $a*a=a$) is not isomorphic to a (d-e) magma (with $a*a \neq a$). Similarly a (d) magma is not isomorphic to an (e) magma.
This completes the argument.

If $n = 2$, then the case (e) is not possible. Otherwise, the solution is the same. So in this case, the answer is 4. 
\item
Given a fixed $x \geq 0$ a function $\varphi(y) = y^3 + xy$ is strictly increasing.
So since $\varphi(0) = 0$ and $\varphi(y) \to_{y\to \infty} \infty$, there is a unique solution $y(x)$ to the equation $y^3 + xy = 8$ and $y(x) > 0$.
Since $\varphi'(y) > 0$, the implicit function theorem yields that $y(x)$ is continuously differentiable. Now note that
\[
3y^2y' + y + xy' = 0,
\]
so that 
\[
y' = \frac{-y}{3y^2 + x} < 0.
\]
Thus $y(x)$ is strictly decreasing and therefore has an inverse function $x(y)$. Since $y(0) = 2$ and $y(7) = 1$, we can change the variable in the integral
\[
\int_0^7 y(x)^2 dx = \int_2^1 y^2 x'(y) dy = \int_2^1 \frac{y^2}{y'(x)} dy 
= - \int_1^2 \left(\frac{3y^2 + x}{y}\right)y^2 dy = \int_1^2 (3y^2 + xy) dy.
\]
Since $xy = 8 - y^2$, we have
\[
\int_0^7 y(x)^2 dx = \int_1^2 (8 + 2y^3) dy = 16 - 1/2.
\]
\item
\emph{Answer:} all even natural numbers.


\emph{Solution 1.}
Let $A$ satisfy the equation. Note that any eigenvalue $\lambda$ of $A$ must also satisfy the same equation $\lambda^2 + 2\lambda + 5 = 0$, so $\lambda = -1 \pm 2i$. The characteristic polynomial $|A-\lambda I| = a_n\lambda^n + \dots + a_0$ of $A$ is a polynomial of power $n$ with real coefficients. Its roots are exactly the eigenvalues of $A$. If there are $k$ eigenvalues equal to $-1 + 2i$ and $n - k$ eigenvalues equal to $-1 - 2i$, then $a_{n-1} = -k(-1 +2i) - (n-k)(-1-2i)$. So $a_{n-1}$ is real if and only if $k = n-k$. Hence, $n = 2k$.

Conversely, a calculation shows that the $2 \times 2$ real matrix
\[
A_0 = \left(
\begin{array}{cc}
0 & -5 \\
1 & -2
\end{array}
\right)
\]
is a root of this polynomial. Therefore, any $2n \times 2n$ block diagonal matrix which has $n$ copies of $A_0$ on the diagonal will satisfy this equation as well.

\emph{Solution 2.}(Janno)
Our condition is equivalent to $(A+I)^2 = -4I$. Taking determinant we see that the LHS is always nonnegative but the RHS is so only if $n$ is even. If $n$ is even, take 
\[
A = \begin{pmatrix}
-1 & 0 & 0 & \cdots & \cdots & \cdots & 0 & 2\\
0 & -1 & 0 & \cdots & \cdots & \cdots & 2 & 0\\
\vdots & \vdots & \ddots & \cdots & \cdots & \iddots & \vdots & \vdots \\
0 & \cdots & 0 & -1 & 2 & 0 & \cdots & 0\\
0 & \cdots & 0 & -2 & -1 & 0 & \cdots & 0\\
\vdots & \vdots &  \iddots & \cdots & \cdots & \ddots & \vdots & \vdots \\
0 & -2 & 0 & \cdots & \cdots & \cdots & -1 & 0\\
-2 & 0 & 0 & \cdots & \cdots & \cdots & 0 & -1\\
\end{pmatrix}.
\]

\item
\begin{enumerate}
\item 
By the convergence of the integral, $\lim_{x \to \infty} f(x) = 0$, so $f(x)$ must keep the same sign. Assume, e.g., that $f$ is non-negative and non-increasing. Then
\[
\int_h^{(m+1)h} f(x) dx \leq h (f(h) + f(2h) + \dots + f(mh)) \leq \int_0^{mh} f(x) dx,
\]
so that
\[
\int_h^\infty f(x) dx \leq h \sum_{n=1}^\infty f(nh) \leq \int_0^\infty f(x) dx,
\]
and the claim follows. The other case is done in the same way.
\item
Put 
\[
f(x) = \frac{e^{-x}}{1 + e^{-x}}
\]
and $e^{-h} = t$ in (a).

Then the limit in question is equal to
\[
\int_0^\infty \frac{e^{-x}}{1 + e^{-x}} dx = \int_0^1 \frac{dy}{1+y} = \ln 2.
\]
\end{enumerate}
\end{enumerate}


\end{document}
