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

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

\begin{enumerate}
\item % 1.4.5
Tõesta, et paaritu täisarvu $n$ korral
\[
\int_0^{2\pi} \sin(\sin x + nx) + \cos(\cos x + nx) dx = 0.
\]
\item % 2.3.5
Olgu $P$ ja $Q$ erinevad reaalmuutuja polünoomid ning kehtigu polünoomide võrdus $P(Q(x)) = Q(P(x))$ iga $x \in \mathbb R$ korral.
Tõesta, et polünoom $P(P(x)) - Q(Q(x))$ jagub polünoomiga $P(x) - Q(x)$.
\item
Olgu $f \in C^{\infty}(\R)$ (lõpmata palju kordi diferentseeruv funktsioon), kusjuures $f(0) = 0$, $f^{(k)}(0) = 0$ ja $f^{(k)}(x) \geq 0$
kõikide $k \in \mathbb N$ ja $x > 0$ korral. Tõesta, et $f(x) = 0$
iga $x > 0$ korral.
\item % 1.7.1
Jada $(x_n)$ on defineeritud seostega $x_1 = a > 1$ ja
$x_{n+1} = x_n^2 - x_n + 1$, $n \geq 1$.
Leia
\[
\sum_{n=1}^\infty \frac 1 {x_n}.
\]
\item % 1.3.33
Olgu funktsioon $f$ pidevalt diferentseeruv vahemikus $(0,\infty)$.
\begin{enumerate}
\item On teada, et $f(x) + f'(x) \to A$ protsessis $x \to \infty$.
Tõesta, et $f(x) \to A$ protsessis $x \to \infty$.
\item On teada, et $f(x) - f'(x) \to A$ protsessis $x \to \infty$.
Kas võib väita, et $f(x) \to A$ protsessis $x \to \infty$?
\end{enumerate}
\item % SL6
Olgu $a_1 < a_2 < \ldots < a_n$ ja $b_1 < b_2 < \ldots < b_n$
reaalarvud. Tõesta, et
\[
\begin{vmatrix}
e^{a_1b_1} & e^{a_1b_2} & \ldots & e^{a_1b_n}\\
e^{a_2b_1} & e^{a_2b_2} & \ldots & e^{a_2b_n}\\
\vdots & \vdots & \ddots & \vdots\\
e^{a_nb_1} & e^{a_nb_2} & \ldots & e^{a_nb_n}
\end{vmatrix}
> 0.
\]
\begin{comment}
\item %4.1.3
Leia vähemalt üks täisarvude kolmik $(x,y,z)$, mille korral $x,y,z > 50$ ja
\[
x^2 + y^2 + z^2 = 3xyz.
\]
\end{comment}
\end{enumerate}
\newpage
\thispagestyle{empty}

\begin{enumerate}
\item % 1.4.5
Let $n$ be an odd integer. Prove the equality
\[
\int_0^{2\pi} \sin(\sin x + nx) + \cos(\cos x + nx) dx = 0.
\]
\item % 2.3.5
Let $P$ and $Q$ be different polynomials with real coefficients such that $P(Q(x)) = Q(P(x))$ for all $x \in \mathbb R$.
Prove that the polynomial $P(P(x)) - Q(Q(x))$ is divisible by the polynomial $P(x) - Q(x)$.
\item
Let $f \in C^{\infty}(\R)$ be a smooth function such that $f(0) = 0$, $f^{(k)}(0) = 0$, and $f^{(k)}(x) \geq 0$
for all $k \in \mathbb N$ and $x > 0$. Prove that$f(x) = 0$ for all $x > 0$.
\item % 1.7.1
The sequence $(x_n)$ is defined by the relations $x_1 = a > 1$ and
$x_{n+1} = x_n^2 - x_n + 1$, $n \geq 1$.
Find
\[
\sum_{n=1}^\infty \frac 1 {x_n}.
\]
\item % 1.3.33
Let the function $f$ be continuously differentiable on the interval $(0,\infty)$.
\begin{enumerate}
\item Assume $f(x) + f'(x) \to A$ for $x \to \infty$.
Prove that $f(x) \to A$ for $x \to \infty$.
\item Assume $f(x) - f'(x) \to A$ for $x \to \infty$.
Is it possible to claim $f(x) \to A$ for $x \to \infty$?
\end{enumerate}
\item % SL6
Let $a_1 < a_2 < \ldots < a_n$ and $b_1 < b_2 < \ldots < b_n$
be real numbers. Prove that
\[
\begin{vmatrix}
e^{a_1b_1} & e^{a_1b_2} & \ldots & e^{a_1b_n}\\
e^{a_2b_1} & e^{a_2b_2} & \ldots & e^{a_2b_n}\\
\vdots & \vdots & \ddots & \vdots\\
e^{a_nb_1} & e^{a_nb_2} & \ldots & e^{a_nb_n}
\end{vmatrix}
> 0.
\]
\begin{comment}
\item %4.1.3
Leia vähemalt üks täisarvude kolmik $(x,y,z)$, mille korral $x,y,z > 50$ ja
\[
x^2 + y^2 + z^2 = 3xyz.
\]
\end{comment}
\end{enumerate}
\newpage
\paragraph*{Solutions}
\begin{enumerate}
\item 
\emph{($\sim$ Kiev NU)}
Substitute $x = y + \pi$ and note that
$\sin(y+\pi) = - \sin y$,
$\cos(y+\pi) = - \cos y$,
$\sin(ny + n\pi) = (-1)^n\sin(ny)$,
$\cos(ny + n\pi) = (-1)^n\cos(ny)$. We have
\begin{align*}
A := \int_0^{2\pi} \sin(\sin x + nx) + \cos(\cos x + nx) \, dx\\ 
=\int_0^{2\pi} \sin(\sin x)\cos(nx) + \cos(\sin x)\sin(nx)\\
+\cos(\cos x)\cos(nx) - \sin(\cos x)\sin(nx) \, dx\\
=\int_{-\pi}^{\pi} \sin(-\sin y)(-1)^n\cos(ny) + \cos(-\sin y)(-1)^n\sin(ny)\\
+\cos(-\cos y)(-1)^n\cos(ny) - \sin(-\cos y)(-1)^n\sin(ny) \, dy
\end{align*}
In the latter integral three summands are odd functions of $y$ (hence their integral with symmetric bounds is $0$) and one is even. So
\[
A = (-1)^n\int_{-\pi}^{\pi} \cos(\cos y)\cos(ny) \, dy = 2\cdot (-1)^n\int_0^\pi \cos(\cos y)\cos(ny) \, dy.
\]
Again, substitute
$y = z + \pi / 2$ and note that
$\cos(z + \pi / 2) = -\sin z$ and
$\cos(nz + n\pi / 2) = (-1)^{\frac{n+1} 2} \sin(nz)$. 
We have
\[
A = 2\cdot (-1)^n\int_{-\pi /2}^{\pi /2} \cos(-\sin z)(-1)^{\frac{n+1} 2}\sin(nz) \, dz = 0
\]
as it is an integral with symmetric bounds of an odd function.
\item
\emph{(MSU MechMath)}
Note that if $P,Q,R$ are polynomials, then
$P(Q(x)) - P(R(x))$ is divisible by $Q(x) - R(x)$
because so is $Q(x)^n - R(x)^n$ for all $n \in \mathbb N$. Hence,
\[
P(P(x)) - Q(Q(x)) = (P(P(x)) - P(Q(x))) + (Q(P(x)) - Q(Q(x)))
\]
is divisible by $P(x) - Q(x)$.
\item
\emph{(Yugoslavia)}
Take $x > 0$. Taylor expansion at $0$ gives
\[
f(x) = \frac{f^{(k)}(\theta)}{k!} x^k, \quad 0 \leq \theta \leq x.
\]
Since $f^{(k)}$ is non-decreasing on $[0, \infty)$,
we have
\[
\frac{f^{(k)}(x)}{k!} x^k \geq f(x).
\]
Taylor expansion at $x$ gives
\[
f(2x) = \sum_{k=0}^{n-1} \frac{f^{(k)}(x)}{k!} x^k + \frac{f^{(n)}(\theta)}{n!} x^n \geq
 \sum_{k=0}^{n-1} \frac{f^{(k)}(x)}{k!} x^k \geq
 nf(x)
\]
for some $\theta \in [x, 2x]$.
The latter inequality can hold for all $n$ only if $f(x) = 0$.
\item
\emph{(Math.Battle)}

\emph{Answer:} $\frac 1 {a-1}.$

Clearly, $(x_n)$ is non-decreasing. Assume that
$c = \lim x_n < \infty$. Then $c^2 - 2c + 1 = 0$,
so that $c = 1$, which contradicts $a > 1$.
Therefore, $x_n \to \infty$.
Now
\[
\frac 1 {x_1-1} = \frac 1 {x_1} + \frac 1 {x_1^2 - x_1} = \frac 1 {x_1} + \frac 1 {x_2 - 1} = \ldots = 
\sum_{n=1}^N \frac 1 {x_n} + \frac 1 {x_{N+1} - 1},
\]
so that
\[
\frac 1 {a-1} - \sum_{n=1}^N \frac 1 {x_n}
= \frac 1 {x_{N+1} - 1} \mathop{\xrightarrow{\hspace{2cm}}}_{N\to \infty} 0.
\]
\item
\emph{(USSR tour)}
\begin{enumerate}
\item
Fix $\e > 0$. There exists $x_0$ such that
$|f(x) + f'(x) - A| < \e$, i.e.,
\[
-f(x) + A - \e < f'(x) < -f(x) + A + \e
\]
for all $x \geq x_0$.	

Let $f_1$ and $f_2$ be solutions to differential equations $f'(x) = -f(x) + A - \e$ and 
$f'(x) = -f(x) + A + \e$, respectively, such that
$f(x_0) = f_1(x_0) = f_2(x_0)$.
Then $f_1(x) \leq f(x) \leq f_2(x)$ for all $x \geq x_0$.
Indeed, put $g(x) = f(x) - f_1(x)$.
Then $g(x_0) = 0$ and $g'(x) \geq -g(x)$ for all 
$x \geq x_0$. Assume that $g(x) < 0$ for some
$x > x_0$. Let $g$ attain its minimum value in $[0,x]$ at $\theta \in (0, x]$. Then $g(\theta) < 0$ and $g'(\theta) \geq -g(\theta) > 0$,
so that $g(\theta - \delta) < g(\theta)$ for some small $\delta > 0$, a contradiction. That is,
$f(x) \geq f_1(x)$ for all $x \geq x_0$. Similarly, $f(x) \leq f_2(x)$ for all $x \geq x_0$.

By solving the differential equations we obtain
\[
c_1 e^{-x} + A - \e \leq f(x) \leq c_2 e^{-x} + A + \e
\]
for some constants $c_1, c_2$ and all $x \geq x_0$. Hence, there exists $x_1$
such that
\[
A - 2\e \leq f(x) \leq A + 2\e
\]
for all $x \geq x_1$.
\item
No. Take any $A \in \mathbb R$
and put $f(x) = e^x + A$. Then $f(x) - f'(x) = A$
for all $x \in \mathbb R$ but $f(x) \to \infty$
when $x \to \infty$.
\end{enumerate}
\item
\emph{(G\'eza K\'os, Budapest)}
Denote the determinant by $D$. Apply induction on $n$. For $n = 1$ the statement is obvious.
Suppose $n > 1$ and assume the statement is true
for all smaller values.

Let $c_i = a_i - a_1$. Then
\[
D = 
\begin{vmatrix}
e^{a_1b_1} & e^{a_1b_2} & \ldots & e^{a_1b_n}\\
e^{a_1b_1}e^{c_2b_1} & e^{a_1b_2}e^{c_2b_2} & \ldots & e^{a_1b_n}e^{c_2b_n}\\
\vdots & \vdots & \ddots & \vdots\\
e^{a_1b_1}e^{c_nb_1} & e^{a_1b_2}e^{c_nb_2} & \ldots & e^{a_1b_n}e^{c_nb_n}
\end{vmatrix}
= e^{a_1(b_1 + b_2 + \ldots + b_n)}
\begin{vmatrix}
1 & 1 & \ldots & 1\\
e^{c_2b_1} & e^{c_2b_2} & \ldots & e^{c_2b_n}\\
\vdots & \vdots & \ddots & \vdots\\
e^{c_nb_1} & e^{c_nb_2} & \ldots & e^{c_nb_n}
\end{vmatrix},
\]
and it is sufficient to prove that the last determinant $D_1$ is positive.

Eliminate the first row by multiplying with 
\[
\begin{pmatrix}
1 & -1 & 0 & \ldots & 0 & 0\\
0 & 1 & -1 & \ldots & 0 & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
0 & 0 & 0 & \ldots & 1 & -1\\
0 & 0 & 0 & \ldots & 0 & 1\\
\end{pmatrix},
\] so that
\begin{align*}
D_1 &= 
\begin{vmatrix}
1 & 0 & 0 & \ldots & 1\\
e^{c_2b_1} & e^{c_2b_2} - e^{c_2b_1} & e^{c_2b_3} - e^{c_2b_2} & \ldots & e^{c_2b_n} - e^{c_2b_{n-1}}\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
e^{c_nb_1} & e^{c_nb_2} - e^{c_nb_1} & 
e^{c_nb_3} - e^{c_nb_2} & \ldots & e^{c_nb_n} - e^{c_nb_{n-1}}
\end{vmatrix}\\
&= \begin{vmatrix}
e^{c_2b_2} - e^{c_2b_1} & e^{c_2b_3} - e^{c_2b_2} & \ldots & e^{c_2b_n} - e^{c_2b_{n-1}}\\
\vdots & \vdots & \ddots & \vdots\\
e^{c_nb_2} - e^{c_nb_1} & 
e^{c_nb_3} - e^{c_nb_2} & \ldots & e^{c_nb_n} - e^{c_nb_{n-1}}
\end{vmatrix}.
\end{align*}
Consider the function
\[
f(t) = 
\begin{vmatrix}
e^{c_2t} & e^{c_2b_3} - e^{c_2b_2} & \ldots & e^{c_2b_n} - e^{c_2b_{n-1}}\\
\vdots & \vdots & \ddots & \vdots\\
e^{c_nt} & 
e^{c_nb_3} - e^{c_nb_2} & \ldots & e^{c_nb_n} - e^{c_nb_{n-1}}
\end{vmatrix}.
\]
By Lagrange's mean value theorem there exists
$\xi_1 \in (b_1, b_2)$ such that
$f(b_1) - f(b_2) = (b_2 - b_1)f'(t)$, i.e.,
\[
\begin{vmatrix}
e^{c_2b_2} - e^{c_2b_1} & e^{c_2b_3} - e^{c_2b_2} & \ldots & e^{c_2b_n} - e^{c_2b_{n-1}}\\
\vdots & \vdots & \ddots & \vdots\\
e^{c_nb_2} - e^{c_nb_1} & 
e^{c_nb_3} - e^{c_nb_2} & \ldots & e^{c_nb_n} - e^{c_nb_{n-1}}
\end{vmatrix}
= (b_2 - b_1)
\begin{vmatrix}
c_2e^{c_2\xi_1} & e^{c_2b_3} - e^{c_2b_2} & \ldots & e^{c_2b_n} - e^{c_2b_{n-1}}\\
\vdots & \vdots & \ddots & \vdots\\
c_ne^{c_n\xi_1} & 
e^{c_nb_3} - e^{c_nb_2} & \ldots & e^{c_nb_n} - e^{c_nb_{n-1}}
\end{vmatrix}.
\]
Repeating the same argument for each column, we can find real numbers $\xi_i \in (b_i, b_{i+1})$, 
$1 \leq i \leq n-1$, such that
\begin{align*}
\begin{vmatrix}
e^{c_2b_2} - e^{c_2b_1} & e^{c_2b_3} - e^{c_2b_2} & \ldots & e^{c_2b_n} - e^{c_2b_{n-1}}\\
\vdots & \vdots & \ddots & \vdots\\
e^{c_nb_2} - e^{c_nb_1} & 
e^{c_nb_3} - e^{c_nb_2} & \ldots & e^{c_nb_n} - e^{c_nb_{n-1}}
\end{vmatrix}
&=&
\left(\prod_{i=1}^{n-1} (b_{i+1} - b_i)\right)
\begin{vmatrix}
c_2e^{c_2\xi_1} & c_2 e^{c_2\xi_2} & \ldots & c_2e^{c_2\xi_{n-1}}\\
\vdots & \vdots & \ddots & \vdots\\
c_ne^{c_n\xi_1} & 
c_ne^{c_n\xi_2} & \ldots & c_ne^{c_n\xi_{n-1}}
\end{vmatrix}\\
&=&
\left(\prod_{i=1}^{n-1} c_{i+1}(b_{i+1} - b_i)\right)
\begin{vmatrix}
e^{c_2\xi_1} & e^{c_2\xi_2} & \ldots & e^{c_2\xi_{n-1}}\\
\vdots & \vdots & \ddots & \vdots\\
e^{c_n\xi_1} & 
e^{c_n\xi_2} & \ldots & e^{c_n\xi_{n-1}}
\end{vmatrix}.
\end{align*}
The latter determinant is positive by the induction hypothesis.
\end{enumerate}


\end{document}
