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

\newcommand{\R}{{\mathbb R}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\e}{\varepsilon}
\DeclareMathOperator{\dist}{dist}
\DeclareMathOperator{\Mat}{Mat}
\newcommand{\rank}{\operatorname{rank}}
\everymath{\displaystyle}

\begin{document}

\title{Tartu Ülikooli üliõpilaste matemaatikaolümpiaad}
\date{15.05.2015}
\maketitle
\thispagestyle{empty}

\begin{enumerate}

\item
Olgu $f : \R \to \R$.
Tõesta, et järgmised väited on samaväärsed:
\begin{enumerate}
\item $f$ on diferentseeruv ja $f'$ on perioodiline;
\item $f(x) = g(x) + c\cdot x$ iga $x \in \R$ korral, kus $c \in \R$ ning $g : \R \to \R$ on diferentseeruv ja perioodiline.
\end{enumerate}

\emph{Info:} funktsioon $h :\R \to \R$ on \emph{perioodiline},
kui leidub $p > 0$ nii, et $h(x + p) = h(x)$ iga $x \in \R$ korral.
\item 
Milliste positiivsete täisarvude $n$ korral kehtib järgmine väide?
Kui $P$ on reaalsete kordajatega $n$-muutuja polünoom ning 
$P(x) > 0$ iga $x\in \R^n$ korral, siis leidub $\varepsilon > 0$ nii, et $P(x) > \varepsilon$ iga $x \in \R^n$ korral.
\item
Leia kõik funktsioonid $f : \R \to \R$, mille puhul 
\[
f(x + f(x) + f(y)) = f(y +f(x)) + x + f(y) - f(f(y))
\]
kõikide $x$, $y \in \R$ korral.
\item
Olgu $n$ positiivne täisarv.
Leia kõik maatriksid $A \in \Mat_n(\R)$, mille puhul 
\[
A^2 B + B A^2 = 2ABA
\]
kõikide $B \in \Mat_n(\R)$ korral.
\item
Kehtigu maatriksite $A$, $B \in \Mat_3(\Z)$ ja mingi positiivse täisarvu $k$ korral võrdus
\[
AB = 
\begin{pmatrix}
1 & 2k & k(2k+1)\\
0 & 1 & 2k\\
0 & 0 & 1
\end{pmatrix}.
\]
Tõesta, et leidub $C \in \Mat_3(\Z)$ nii, et $BA = C^k$.
\item
Olgu antud täisarv $n \geq 2$. Kas sümmeetrilises rühmas $S_n$ on rohkem elemente paaris- või paaritu järguga?

\emph{Info ülesande lahenduseks:}
\begin{enumerate}
\item 
Rühma elemendi $a$ \emph{järk} on vähim positiivne täisarv $k$ nii, et $a^k = 1$ (siin $1$ on rühma ühikelement) või lõpmatus, kui sellist arvu ei leidu.
Lõplikus rühmas igal elemendil on lõplik järk.
\item
\emph{Sümmeetriline rühm} $S_n$ koosneb kõikidest hulga $\{1, 2, \dots, n\}$
\emph{permutatsioonidest} ehk selle hulga bijektiivsetest teisendustest, kusjuures rühma korrutamine on defineeritud kui teisenduste kompositsioon ehk järjest rakendamine. Nii et kahe permutatsiooni $\sigma_1, \sigma_2 \in S_n$ puhul $(\sigma_1 \sigma_2) (x) = \sigma_1(\sigma_2(x))$ iga $x \in \{1, \dots, n\}$ korral.
Selle tehte suhtes $S_n$ on tõepoolest rühm (ehk tehe on assotsiatiivne, leidub ühikelement (tähistatakse $id$), ning igal elemendil leidub pöördelement).
\item
Konkreetset permutatsiooni võib tähistada näiteks Cauchy kahe rea notatsiooniga
\[
\sigma = 
\begin{pmatrix}
1 & 2 & \dots & n\\
\sigma(1) & \sigma(2) & \dots & \sigma(n)
\end{pmatrix}.
\]
Teine võimalus on esitada sõltumate tsüklite korrutisena. Näiteks,
\[
(1 5)(3 4) =
\begin{pmatrix}
1 & 2 & 3 & 4 & 5\\
5 & 2 & 4 & 3 & 1
\end{pmatrix}
\quad \mbox{ja} \quad
(1 2 5)(3 4) = 
\begin{pmatrix}
1 & 2 & 3 & 4 & 5\\
2 & 5 & 4 & 3 & 1
\end{pmatrix}.
\]
\item
Permutatsiooni, kus ainult kaks arvu on omavahel vahetatud, nimetatakse \emph{transpositsiooniks}. Ta on esitatav kujul $(k l)$.
Iga permutatsioon on esitatav (mitmel viisil) transpositsioonide korrutisena, kusjuures ühe permutatsiooni kõikides sellistes esitustes on transpositsioonide arvud sama paarsusega. Selle invariantse paarsuse järgi nimetatakse permutatsiooni kas paaris- või paarituks. 
NB! Permutatsiooni enda paarsus ja permutatsiooni järgu paarsus on erinevad mõisted.
\item
Rühmas $S_n$ on paarispermutatsioone täpselt sama palju kui paarituid.
\end{enumerate}
\end{enumerate}
\newpage
\paragraph*{Solutions}
\begin{enumerate}
\item
(b) $\Rightarrow$ (a) is clear because $f'(x) = g'(x) + c$.

(a) $\Rightarrow$ (b). If $f'(x+p) = f'(x)$ for all $x$, then 
$(f(x+p) - f(x))' = 0$ and there exists a constant $d \in \R$ such that $f(x+p) - f(x) = d$ for all $x$. Defining $g$ by $f(x) = g(x) + cx$ for any $c$, we see that $g$ is  differentiable and $g(x+p) - g(x) + cp = d$ for all $x$. So $g$ is periodic whenever $c = \frac d p $.
\item
\emph{Answer:} $n = 1$.

\emph{Solution:}
Case $n = 1$. Since $P$ is everywhere positive, it has an even degree. So $\lim_{x \to \pm \infty} P(x) = \infty$ and there exists $M > 0$ such that $P(x) > 1$ whenever $|x| > M$. On the other hand, $P$ is a continous function and attains its minimum $P(x_0)$ on the compact set $[-M, M]$. But $P(x_0) > 0$ by the assumption, so $\varepsilon = \min(1, P(x_0))$ has the required property.

Case $n \geq 2$. Consider the polynomial $P(x,y, \dots) = x^2 + (xy -1)^2$. It is everywhere positive, since the summands cannot be both zero at the same time. On the other hand, for $x > 0$ we have \[
P(x, \frac 1 x, \dots) =  x^2 \to_{x \to 0} 0.
\]
\item
Let us first show that $f$ is injective. Assume $f(a) = f(b)$.
Now by substituting $y$ by both $a$ and $b$ and comparing the resulting equations we get
\[
f(a + f(x)) = f(b + f(x)) \quad \forall x \in \R. 
\]
By doing the same thing for $x$ we get
\[
a-b = f(a + f(a) + f(y)) - f(b + f(a) + f(y)) \quad \forall y \in \R.
\]
For $a=b$, it is now enough to find $x_0, y_0 \in \R$ such that
$f(a) + f(y_0) = f(x_0)$.
These numbers can be clearly obtained by putting $x = f(a) - f(y) + f(f(y))$ in the main equation. So $f$ is injective.

Setting $x = y = 0$, we get $f(2f(0)) = f(0)$ and the injectivity yields $f(0) = 0$. Now setting $x = 0$. we get $f(f(y)) = f(y)$ for all $y \in \R$ and the injectivity implies $f(y) = y$ for all $y \in \R$. This function clearly satisfies the original equation.
\item
Let us first try the case when $n = 2$. Put $A = (a_{ij})$ and $B = \begin{pmatrix}
0 & 0\\
1 & 0
\end{pmatrix}$. Then $AB = 
\begin{pmatrix}
a_{12} & 0\\
a_{22} & 0
\end{pmatrix}$
and $A^2 B = 
\begin{pmatrix}
a_{11}a_{12} + a_{12}a_{22} & 0\\
a_{21}a_{12} + a^2_{22} & 0
\end{pmatrix}.$
%We see that $(A^2B)_{12} = 0$. 
%Similarly, $(BA^2)_{12} = 0$. 
Similarly, $BA^2 = \begin{pmatrix}
0 & 0\\
a^2_{11} + a_{12}a_{21} & a_{11}a_{12} + a_{12}a_{22}
\end{pmatrix}$.
%So $(A^2B + BA^2)_{12} = 0$. 
On the other hand, $ABA = \begin{pmatrix}
a_{12}a_{11} & a^2_{12}\\
a_{22}a_{11} & a_{22}a_{12}
\end{pmatrix}$, so the equality yields $a_{12} = 0$. Then the other corner gives $a_{11}^2 + a_{22}^2 = 2a_{22}a_{11}$ and $a_{11} = a_{22}$. That is, $A$ must be in the form $\lambda E$ for some $\lambda \in \R$, where $E$ is the identity matrix. This form also fits the original equality.

Trying the same approach in the general case (with $b_{n1} = 1$ and $b_{ij} = 0$ otherwise) would similarly yield that $a_{1n} = 0$. In fact, this also works for any pair of distinct indices $k, l$.

Recall that $a_{ij} = e_iAe_j^T$ for all $i,j$, where $e_i$ is the $i$-th row of the identity matrix. In particular $E = (\delta_{ij}) = (e_ie_j^T)$.

For distinct $k$ and $l$, let $b_{kl} = 1$ and $b_{ij} = 0$ otherwise. It means that $B = e_k^Te_l$, 
 We want to show that $a_{lk} = 0$. For that, let us calculate the element in the same position on both sides of the equation. The first summand of the left hand side gives
\[
e_l A^2 B e_k^T = e_l A^2 e_k^T e_l e_k^T = 0,
\]
because $e_l e_k^T = \delta_{lk} = 0$. The second summand is similar and we get $0$ on the left hand side. The right hand side gives
\[
2e_l ABA e_k^T = 2e_l A e^T_k e_l A e_k^T  = 2 a^2_{lk}.
\]
Thus $a_{lk} = 0$. Since $k$ and $l$ were arbitrary, this means that $A$ must be a diagonal matrix. 

Let us fix $k$,$l$, and $B$ as before and check the $kl$ element of both sides. LHS gives
\[
e_kA^2e_k^Te_le_l^T + e_k e_k^T e_l A^2 e_l^T = e_kA^2e_k^T + e_lA^2e_l^T = (A^2)_{kk} + (A^2)_{ll},
\]
because $e_i e_i^T = \delta_{ii} = 1$. But $(A^2)_{ii} = a^2_{ii}$, since $A$ is diagonal. So we get $a^2_{kk} + a^2_{ll}$.

RHS gives
\[
2e_kAe_k^Te_lAe^T_l = 2 a_{kk} a_{ll}.
\]
So $a^2_{kk} + a^2_{ll} = 2 a_{kk} a_{ll}$, that is 
$(a_{kk} - a_{ll})^2 = 0$ and $a_{kk} = a_{ll}$. Since $k$ and $l$ were arbitrary we see that $A$ is of the form $\lambda E$.
\item
Let 
\[
M = 
\begin{pmatrix}
1 & 2 & 3\\
0 & 1 & 2\\
0 & 0 & 1
\end{pmatrix}.
\]
It can be easily seen (e.g., by induction) that $AB = M^k$. Since $|AB| = 1 \neq 0$, also $|A| \neq 0$. Now $BA = A^{-1}ABA = A^{-1}M^kA = (A^{-1}MA)^k$.
\item
Let us note that an odd permutation must have an even order. Indeed, let a permutation $\sigma$ be represented as a product of $k$ transpositions, where $k$ is odd. Then $\sigma^{n}$ is represented as a product of $kn$ transpositions. If $\sigma^n = id$, then $kn$ must be even, because $id$ is an even permutation, so $n$ must be even.

Therefore, by (e), at least half of permutations must have an even order.

On the other hand, if $n \geq 4$, then there also are even permutations with an even order, e.g., $(1 2)(3 4)$.
So in this case, there are more permutations with an even order.

For $n=2$ and $n=3$, it is easily checked that the numbers are equal. Even order: $(1 2)$, $(1 3)$, $(2 3)$. Odd order: $id$, $(1 2 3)$, $(1 3 2)$.
\end{enumerate}

\end{document}
