\documentclass[a4paper,12pt]{article}
\pagestyle{plain}

\usepackage{latexsym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[ansinew]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[estonian]{babel}
\usepackage{a4}
\usepackage{amsxtra}
\usepackage{amsthm}
\usepackage{amsopn}
\usepackage{eufrak}


\input cyracc.def
\font\strcyr=wncyr10 at 12pt
\def\cyr{\strcyr\cyracc}
\font\itcyr=wncyi10 at 12pt
\def\cyrit{\itcyr\cyracc}

\renewcommand{\thesection}{\hspace{-0.6cm}}
\renewcommand{\thesubsection}{\hspace{-0.6cm}}

\newtheorem*{teoreem}{Teoreem}
\newtheorem*{fakt}{Fakt}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem*{lause}{Lause}
%\newtheorem{jareldus}[teoreem]{Järeldus}
\newtheorem*{lemma*}{Lemma}
\newtheorem{naide}{Näide}


\theoremstyle{definition}
\newtheorem*{definitsioon}{Definitsioon}
\theoremstyle{remark}
\newtheorem{markus}{Märkus}


\def\N{{\mathbb
N}}
\def\R{{\mathbb R}}

\def\C{{\mathbb C}}

\def\K{{\mathbb K}}

\def\Z{{\mathbb Z}}

\def\Q{{\mathbb Q}}

\newcommand{\conv}{\textnormal{conv}}
\newcommand{\absconv}{\textnormal{absconv}}

\newcommand{\calB}{{\mathcal
B}}
\newcommand{\calK}{{\mathcal
K}}
\newcommand{\calW}{{\mathcal W}}
\newcommand{\calL}{{\mathcal
L}}
\newcommand{\calT}{{\mathcal T}}
\newcommand{\calP}{{\mathcal
P}}
\newcommand{\calF}{{\mathcal F}}
\newcommand{\calA}{{\mathcal
A}}
\newcommand{\calR}{{\mathcal R}}
\newcommand{\calN}{{\mathcal
N}}

\newcommand{\ran}{{\rm
ran} \ }

\newcommand{\g}{\mathfrak}

\newcommand{\emf}[1]{\textbf{#1}}

\newcommand{\ext}{\hbox{ext}\,}
\newcommand{\strexp}{\hbox{str.exp.}\,}
\newcommand{\la}{\leftarrow}
\newcommand{\ra}{\rightarrow}
\newcommand{\lra}{\longrightarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\La}{\Leftarrow}
\newcommand{\Lra}{\Leftrightarrow}
\newcommand{\al}{\alpha}
\newcommand{\e}{\epsilon}
\newcommand{\ph}{\varphi}
\newcommand{\eq}{\Longleftrightarrow}
\newcommand{\xast}{x^{\ast}}
\newcommand{\uast}{u^{\ast}}
\newcommand{\yast}{y^{\ast}}
\newcommand{\Yast}{Y^{\ast}}
\newcommand{\zast}{z^{\ast}}
\newcommand{\Zast}{Z^{\ast}}
\newcommand{\Xast}{X^{\ast}}
\newcommand{\Zastast}{Z^{\ast\ast}}
\newcommand{\zastast}{z^{\ast\ast}}
\newcommand{\aast}{a^{\ast}}
\newcommand{\Xastast}{X^{\ast\ast}}
\newcommand{\Yastast}{Y^{\ast\ast}}
\newcommand{\Tastast}{T^{\ast\ast}}
\newcommand{\Sastast}{S^{\ast\ast}}
\newcommand{\Jastast}{J^{\ast\ast}}
\newcommand{\xastast}{x^{\ast\ast}}
\newcommand{\yastast}{y^{\ast\ast}}
\newcommand{\bastast}{b^{\ast\ast}}
\newcommand{\Past}{P^{\ast}}
\newcommand{\Jast}{J^{\ast}}
\newcommand{\Tast}{T^{\ast}}
\newcommand{\Sast}{S^{\ast}}
\newcommand{\w}{w^{\ast}}
\newcommand{\Weakstop}{\mathcal{W}_{w^\ast}}
\newcommand{\Kw}{\mathcal{K}_{w^\ast}}
\newcommand{\Lw}{\mathcal{L}_{w^\ast}}

\newcommand{\jast}{j^{\ast}}

\newcommand{\Tt}{{\tilde{T}^{\ast}}}
\newcommand{\Ttt}{(\mathop{\tilde{T}^{\ast}})^{\ast}}

\newcommand{\cir}{\diamond}
\newcommand{\Tc}{T^{\cir}}
\newcommand{\Sc}{S^{\cir}}


\newcommand{\ol}{\overline}
\newcommand{\n}[1]{\left\|#1\right\|}
\newcommand{\abs}[1]{\left|#1\right|}

\newcommand{\too}{\mathop{\longrightarrow}}

\newcommand{\sign}{\mbox{sign} \, }
\newcommand{\im}{\mbox{im}}
\newcommand{\id}{\mbox{id}}

\renewcommand{\Re}{\mathit{Re}}
\renewcommand{\Im}{\mathit{Im}}

\newenvironment{toestus}{\begin{proof}[Tõestus]}{\end{proof}}


\renewcommand{\labelenumi}{$\rm \arabic{enumi})$}

\newcommand{\nim}{nimetatakse~}

\sloppy

\setlength{\parskip}{0.3ex}

\hyphenation{Vii-ma-sed}
\begin{document}
\title{Matemaatika-informaatikateaduskonna üliõpilaste matemaatikaolümpiaad}
\maketitle
\begin{enumerate}
%\item 
%
%Tõesta, et leidub lõpmatult palju positiivseid arvusid $x$, mille korral
%summa 
%\[
%\sum_{n=1}^{\infty} \frac{(-1)^{n+1}}{n+x}
%\]
%on ratsionaalarv.

\item
Tõesta, et
\[
\lim_{t \to 0+}\left(\sum_{n=1}^\infty \frac{e^{-n^2 t}}{n}\right) \:/ \ln t = -\frac{1}{2}.
\]

\item 

Olgu $P(x)$ trigonomeetriline polünoom astmega $n$, s.t.\newline
$P(x) = \sum_{k=0}^{n} a_k \sin(kx + \varphi_k)$.
Tõesta võrratus
\[
\abs{P(x)} \leq \frac{1}{\pi} \int_0^{2\pi} \abs{P(t)}^2 dt + \frac{2n + 1}{8}.
\]
\item 

Olgu $P$ polünoom, kusjuures $\deg P \leq 2n$ ja $\abs{P(k)} \leq 1$ iga $k \in \mathbb{Z} \cap [-n, n]$ korral.
Tõesta, et iga $x \in [-n, n]$ korral $\abs{P(x)} \leq 2^{2n}$.

\item

Tähistagu $M_n$ kõikide kompleksete $n\times n$-maatriksite hulka.
Olgu $A \in M_n$ regulaarne. Näita, et järgmised tingimused on samaväärsed:
\begin{enumerate}
\item $A$ ja $-A$ on sarnased.
\item Leiduvad maatriksid $B, \, C \in M_n$ nii, et $A =B+C$ ja 
$B^2 + C^2 = 0$.
\end{enumerate}

\item Tõesta võrratus
\[
\int_0^1\sqrt{1 + x^2 \ln^2(1+x)} dx \geq \sqrt{\frac{17}{16}}.
\]

\item

Olgu $F: \R^2 \to \R$ pidev funktsioon, kusjuures kõikide  $u, v, w$ korral
\[
F(u,0) = u, \ F(u,u) = 0, F(F(u,w),F(v,w)) = F(u,v).
\]
Tõesta, et leidub rangelt monotoonne funktsioon $f : \R \to \R$ nii, et
\[
f(x-y) = F(f(x), f(y))
\]
kõikide $x, y \in \R$ korral.
\end{enumerate}

\newpage

\textbf{Solutions}

\begin{enumerate}
\item Since the function $\frac{e^{-n^2t}}{n}$
with argument $t$ is nonnegative and decreasing, we can conclude (as in the proof of integral test for convergence) that
\[
0 \leq \sum_{n=1}^\infty \frac{e^{-n^2t}}{n} - \int_1^\infty \frac{e^{-x^2t}}{x} dx \leq e^{-t}  \leq 1.
\]
This implies that 
\[
\lim_{t \to 0+}\left(\sum_{n=1}^\infty \frac{e^{-n^2 t}}{n}\right) \:/ \ln t
= \lim_{t \to 0+}\left(\int_1^\infty \frac{e^{-x^2 t}}{x} dx\right) \:/ \ln t.
\]
Compute 
\[
\int_1^\infty \frac{e^{-x^2 t}}{x} dx = \int_{\sqrt t}^\infty \frac{e^{-y^2 }}{y} dy = \int_{\sqrt t}^1 \frac{dx}{x} + \int_{\sqrt t}^1 \frac{e^{-x^2} - 1}{x} dx + \int_1^\infty \frac{e^{-x^2 }}{x} dx
\]
and observe that the latter two integrals have finite limits when $t \to 0+$.
Therefore
\[
\lim_{t \to 0+}\left(\sum_{n=1}^\infty \frac{e^{-n^2 t}}{n}\right) \:/ \ln t
= \lim_{t \to 0+}\left( \int_{\sqrt t}^1 \frac{dx}{x}\right) \:/ \ln t
= \lim_{t \to 0+}\frac{-\ln \sqrt t}{\ln t} = -\frac{1}{2}.
\]
\item Observe that
\[
\frac{1}{\pi} \int_0^{2\pi} \abs{P(t)}^2 dt = 2a_0^2 + a_1^2 + \dots + a_n^2 \geq 
\]
\[
\geq \left(\abs{a_0} - \frac{1}{8}\right) + \left(\abs{a_1} - \frac{1}{4}\right)
+ \dots + \left(\abs{a_n} - \frac{1}{4}\right) = 
\]
\[
= \abs{a_0} + \abs{a_1} + \dots + \abs{a_n} - \frac{2n+1}{8} \geq
\]
\[
\sum_{k=0}^n\abs{a_k \sin(kx + \phi_k)} - \frac{2n+1}{8} \geq \abs{P(x)} -\frac{2n+1}{8}
\]
for any $x \in \R$. (We used inequalities
\[
2u^2 - u + \frac{1}{8} = 2(u-\frac{1}{4})^2 \geq 0, \ u^2 - u + \frac{1}{4} = (u-\frac{1}{2})^2 \geq 0.)
\]
\item
According to Lagrange formula we have
\[
P(x) = \sum_{k=-n}^n P(k) \prod_{i \neq k} \frac{x-i}{k-i}.
\]
Since $\abs{P(k)} \leq 1$ for $k \in [-n,n] \cap \mathbb{Z}$ we get
\[
\abs{P(x)} \leq \sum_{k=-n}^n \abs{P(k)}\prod_{i \neq k} \frac{\abs{x-i}}{\abs{k-i}}
\leq 
\sum_{k=-n}^n \prod_{i \neq k} \frac{\abs{x-i}}{\abs{k-i}}.
\]
For every $x \in [-n,n]$ the inequality
\[
\prod_{i \neq k} \abs{x-i} \leq (2n)!
\]
holds. Indeed, in the case $x \geq k$ one gets
\[
\prod_{i \neq k} \abs{x-i} = \left(\prod_{i > k} \abs{x-i} \right)\left(\prod_{i < k} \abs{x-i}\right)
\leq (n-k)!((n-k+1)\dots 2n) = (2n)!.
\]
The case $x < k$ is done similarly.
Hence
\[
\prod_{i \neq k} \frac{\abs{x-i}}{\abs{k-i}} \leq (2n)!\prod_{i \neq k} \frac{1}{\abs{k-i}} \leq (2n)! \frac{1}{(k+n)!(n-k)!},
\]
so
\[
\abs{P(x)} \leq \sum_{k=-n}^n \frac{(2n)!}{(k+n)!(n-k)!} = \sum_{k=0}^{2n} \frac{(2n)!}{k!(2n-k)!} = \sum_{k=0}^{2n} C^k_{2n} = 2^{2n},
\]
as needed.

\item
(1) $\Ra$ (2). If $A$ is a block matrix of the form 
$\left(\begin{array}{cc}
A_1&0\\
0&A_2
\end{array}
\right)$,
where $A_1, A_2$ are square matrices similar to $-A_1, -A_2$,
respectively, and condition (2) is satisfied for $A_1, A_2$,
then it is clearly satisfied for $A$. We may assume that $A$
is in Jordan normal form. The condition (1) means that for any $k \in \N$, 
$\alpha \in \C$ the number of Jordan cells of size $k$ corresponding to eigenvalues $\alpha$ and $-\alpha$ is the same. $A$ is non-degenerate, so
$A$ does not contain nilpotent Jordan cells. Thus we reduce to the case 
$A = \left(\begin{array}{cc}
\alpha E + J&0\\
0&-\alpha E + J
\end{array}
\right)$.

Here $\alpha \in \C \setminus \{0\}$, $E$ is the identity matrix, $J$ is the 
nilpotent Jordan cell of the same size $m = \frac{n}{2}$. One obviously
can choose a basis $u_1, \dots, u_m, v_1, \dots, v_m$ of $\C^{2n}$ such that
\[
Au_i = \alpha u_i + u_{i+1}, \, Av_i = \alpha v_i + v_{i+1}, \, i = \overline{1, m-1}, \, Au_m = \alpha u_m, Av_m = -\alpha v_m.
\]

Put $x_i = u_i + v_i$, $y_i = u_i - v_i$. One immediately obtains
\[
Ax_i = \alpha y_i + x_{i+1}, \, Ay_i = \alpha x_i + y_{i+1}, \, i = \overline{1, m-1}, \, Ax_m = \alpha y_m, Ay_m = \alpha x_m.
\]

Let us define $B, C \in M_n$ by the following equations
\[
Bx_i = Ax_i, \, By_i = 0, \, Cx_i = 0, \, Cy_i = Ay_i, \ \textnormal{for odd } i,
\]
\[
Bx_i = 0, \, By_i = Ay_i, \, Cx_i = Ax_i, \, Cy_i = 0, \ \textnormal{for even } i.
\]

It is checked directly that $A = B + C$ and $B^2 = C^2 = 0$.

(2) $\Ra$ (1). Put $V = \C^n$, $V_1 = \im(B)$, $V_2 = \im(C)$. There is a linear map $\phi : V_1 \oplus V_2 \mapsto V$, $(v_1, v_2) \mapsto v_1 + v_2$.
The image of $\phi$ clearly contains $\im(A)$ and, since $A$ is non-degenerate,
coincides with $V$. From the other hand, $\im(B) \subset \ker(B)$, and so $\dim V_1 \leq \dim \frac{V}{2}$. Analogously, $\dim V_2 \leq \dim \frac{V}{2}$.
We conclude, that $V = V_1 \oplus V_2$. It follows directly from the construction that $B(V_1) = 0, \, C(V_2) = 0, \, B(V_2) = V, \, C(V_1) = V_2$.
Denote by $I$ the linear transformation of $V$ such that $I|_{V_1} = \id$, 
$I|_{V_2} = -\id$. One checks directly that $IB = -B, \, BI = B, \, IC = C, \, CI = -C.$ Thus $IAI^{-1} =-A$.

\item

Given integral can be viewed as the length of a curve defined by
the function $F(x) = \int x \ln(1+x) dx$ on interval $[0,1]$. After
computing
\[
F(x) =  \int x \ln(1+x) dx = \frac{1}{4}(2(x^2-1)\ln(x+1) - (x-2)x)
\]
notice that $F$ is monotone, $F(0) = 0$ and $F(1) = 	\frac{1}{4}$.
Hence, the length of the curve defined by F is not less than the distance between
$(0,0)$ and $(1, \frac{1}{4})$, which is $\sqrt{\frac{1}{4^2}+1^2} = \sqrt{\frac{17}{16}}$.

\item

Define a function $\ph(x) \equiv F(0,x)$. It is obviously continuous. We have 
\begin{equation}
\label{phiinv}
\ph(\ph(x))=F(0,F(0,x))=F(F(x,x),F(0,x))=F(x,0)=x
\end{equation}
for all $x \in \R$, hence $\ph$ is bijective. Therefore $\ph$ is strictly monotone. Also check that
$\ph(F(x,y)) \equiv F(y,x)$.
\\

\noindent
Consider equation $y = F(t,x)$ and try to find solutions to it. It is easy to observe that
\begin{equation}
\label{sols}
y = F(t,x) \eq t = F(y, \ph(x) ) \eq x = F( \ph(y), \ph(t) ) .
\end{equation}


\noindent
Now for every $y \in \R$ consider functions $F^y (x) \equiv F(y,x)$ and $F_y (x) \equiv F(x,y)$.
Using (\ref{sols}) it is easy to check that these functions are bijective. Hence, strictly monotone.
\\

\noindent
Assume $\ph$ is increasing. Then it is easy to check that $\ph(x) \equiv x$, which means
$F(x,y) \equiv F(y,x)$ and $F_y = F^y$. Take $x_0 > y_0 > 0$. Then $F_{y_0}(0) = y_0 > 0 = F_{y_0}(y_0)$, 
which means $F_{y_0}$ is decreasing. Hence $F(x_0,y_0) = F_{y_0}(x_0) < 0$. Likewise $F_{x_0}$ is decreasing
and $F(x_0,y_0) = F_{x_0}(y_0) > F_{x_0}(x_0) = 0$, which is a contradiction.
\\

\noindent
Thus $\ph$ is decreasing. Note that $\ph(0)=0$. 	
Now as $F_y(y) = 0 > \ph(y) = F_y(0)$ iff $y > 0$ we see that the functions $F_y$ ($y \in \R$)
are increasing. Similarly the functions
$F^y$ ($y \in \R$) are decreasing.
\\

\noindent
If function $f$ satisfying 
\begin{equation}
\label{minus}
f(x-y) \equiv F(f(x), f(y)),
\end{equation} 
exists then due to (\ref{sols}) we get 
$$f(x) \equiv F(f(x-y),\ph(f(y)))$$
and particularly
$$f(2x) \equiv F(f(x),\ph(f(x))).$$
More generally, for arbitrary constant $n \in \N$ holds
$$f(nx) \equiv F(f(x),\ph(f((n-1)x))).$$
\\

\noindent
This gives us an idea to define \emph{"multiplying"} functions as following:
\[
\psi_0(x) \equiv 0,
\]
\[
\psi_n(x) \equiv F(x,\ph(\psi_{n-1}(x)))
\]
for each $n \in \Z^+$. Next we define $\psi_{-n} := \ph \psi_n$ for $n \in \Z^+$ or equivalently
\[
\psi_{-n}(x) \equiv \ph(\psi_n(x)).
\] 
Applying (\ref{phiinv}) to the latter when necessary we get the same equality $\psi_{-n}=\ph\psi_n$
for every $n \in \Z$.
Observe that for a function $f$ satisfying (\ref{minus}) then holds
\[
\psi_n(f(x)) \equiv f(nx).
\]

\noindent
Now we show that for all $n,m \in \Z$ holds
\begin{equation}
\label{intplus}
\psi_{n+m}(x) \equiv F( \psi_m(x), \psi_{-n}(x) ).
\end{equation}   
Assume first $n,m \geq 0$. We show (\ref{intplus}) with induction by $m$. In cases $m=0$ and $m=1$ the assertion
is true. Assuming that (\ref{intplus}) holds for $m=\mu \geq 1$ we show that it also holds for $m=\mu + 1$:
$$\psi_{n + \mu + 1}(x) \equiv F( \psi_{\mu}(x), \psi_{-n-1}(x)),$$
whereas 
$$\psi_{-n-1}(x) \equiv \ph(\psi_{n+1}(x)) \equiv \ph(F(x,\psi_{-n})) \equiv F(\psi_{-n},x)$$
and induction hypothesis $\psi_{\mu+1}(x) \equiv F(\psi_{\mu}(x),\psi_{-1}(x))$ implies with respect to (\ref{sols})
$$\psi_{\mu}(x) \equiv F(\psi_{\mu+1}(x),x).$$
Therefore, indeed
$$\psi_{n+\mu + 1}(x) \equiv F( F(\psi_{\mu+1}(x),x), F(\psi_{-n}(x),x) ) \equiv F( \psi_{\mu+1}(x), \psi_{-n}(x) ).$$
Now consider $n \geq 0$, $-n < m < 0$. Then $-m > 0$ and $m+n < 0$. Therefore holds 
$\psi_n(x) \equiv F(\psi_{-m}(x), \psi_{-m-n}(x))$, which gives 
$\psi_{m+n}(x) \equiv F(\psi_m(x), \psi_{-n}(x))$.
If $n \geq 0$, $m < -n$ we have $m+n < 0$ and thus $\psi_{-m}(x) \equiv F(\psi_n(x),\psi_{m+n}(x))$, which gives
$\psi_{m+n}(x) \equiv F(\psi_m(x), \psi_{-n}(x))$. 

Equation (\ref{intplus}) means that $\psi$ as a function of its subscript satisfies (\ref{minus}) for integer arguments, and is therefore \emph{multiplying} for itself. Hence $\psi_n\psi_m \equiv \psi_{nm}$ for all $n,m \in \Z$. Also observe that by definition $\psi_n$ is bijective whenever $n \neq 0$. This allows us to define $\psi_{n^{-1}} := \psi_n^{-1}$ for $n \neq 0$.
It is now clear that we can define $\psi_q$ for any $q \in \Q$ with all the same properties.

Denote $f_x(q) = \psi_q(x)$ for $x \in \R$, $q \in \Q$. Using the fact that
functions $\ph$ and $F^y$ are strictly monotone it is easy to check that $f_x$ is increasing if $x > 0$. Fix such an $x$ and let $q, q_i$ denote exclusively elements of $\Q$.

Next, define $f_x(r) = \inf_{q > r} f_x(q) $ for $r \in \R \setminus \Q$.
Then $f_x(q_1) < f_x(r) < f_x(q_2)$ for all $q_1 < r < q_2$.
Indeed, e.g. if there was $q_0 > r$ such that 
$q_0 = \inf_{q > r} f_x(q)$ then the same equality would hold for 
any $q \in (r, q_0) \cap \Q$, a contradiction since $f_x$ is strictly monotone on $\Q$. Also observe that $f_x(r) = \inf_{q \geq r} f_x(q)$ holds for any
$r \in \R$.

We only need to check condition (\ref{minus}) now. Take $r_1, r_2 \in \R$.
Then 
\[
F(f_x(r_1), f_x(r_2)) = F(\inf_{q_1 \geq r_1} f_x(q_1), \inf_{q_2 \geq r_2} f_x(q_2))
= \inf_{q_1 \geq r_1} \sup_{q_2 \geq r_2} F(f_x(q_1), f_x(q_2))
\]
\[
= \inf_{q_1 \geq r_1} \sup_{q_2 \geq r_2} f_x(q_1 - q_2) = \inf_{q_1 \geq r_1} \sup_{q_2 \geq r_2} \ph(f_x(q_2-q_1)) = \inf_{q_1 \geq r_1} \ph(\inf_{q_2 \geq r_2} f_x(q_2-q_1))
\]
\[
= \inf_{q_1 \geq r_1} \ph(f_x(r_2-q_1)) = \inf_{q_1 \geq r_1} f_x(q_1-r_2) = f_x(r_1 - r_2).
\]
Hereby we used the facts that functions $\ph$, $F_y$ and $F^y$ are continuous and strictly monotone, as well as equality $f_x(-r) = \ph(f_x(r))$.
\end{enumerate}
\end{document}
