Middle European Mathematical Olympiad 2011

Initially, only the integer $44$ is written on a board. An integer $a$ on the board can be replaced with four pairwise different integers $a_1, a_2, a_3, a_4$ such that the arithmetic mean $\frac{1}{4}(a_1 + a_2 + a_3 + a_4)$ of the four new integers is equal to the number $a$. In a step we simultaneously replace all the integers on the board in the above way. After $30$ steps we end up with $n = 4^{30}$ integers $b_1, b_2, \ldots, b_n$ on the board. Prove that $$\frac{b_1^2 + b_2^2 + \ldots + b_n^2}{n} \geq 2011.$$

Let $n \geq 3$ be an integer. John and Mary play the following game: First John labels the sides of a regular $n$-gon with the numbers $1, 2, \ldots, n$ in whatever order he wants, using each number exactly once. Then Mary divides this $n$-gon into triangles by drawing $n - 3$ diagonals which do not intersect each other inside the $n$-gon. All these diagonals are labeled with number $1$. Into each of the triangles the product of the numbers on its sides is written. Let $S$ be the sum of those $n - 2$ products.

Determine the value of $S$ if Mary wants the number $S$ to be as small as possible and John wants $S$ to be as large as possible and if they both make the best possible choices.

In a plane the circles $\mathcal{K}_1$ and $\mathcal{K}_2$ with centers $I_1$ and $I_2$, respectively, intersect in two points $A$ and $B$. Assume that $\angle I_1AI_2$ is obtuse. The tangent to $\mathcal{K}_1$ in $A$ intersects $\mathcal{K}_2$ again in $C$ and the tangent to $\mathcal{K}_2$ in $A$ intersects $\mathcal{K}_1$ again in $D$. Let $\mathcal{K}_3$ be the circumcircle of the triangle $BCD$. Let $E$ be the midpoint of that arc $CD$ of $\mathcal{K}_3$ that contains $B$. The lines $AC$ and $AD$ intersect $\mathcal{K}_3$ again in $K$ and $L$, respectively. Prove that the line $AE$ is perpendicular to $KL$.

Let $k$ and $m$, with $k > m$, be positive integers such that the number $km(k^2 - m^2)$ is divisible by $k^3 - m^3$. Prove that $(k - m)^3 > 3km$.

Find all functions $f\colon \mathbb{R}\to \mathbb{R}$ such that the equality $$y^{2} f(x) + x^{2} f(y) + xy = x y f(x + y) + x^{2} + y^{2}$$ holds for all $x, y \in \mathbb{R}$, where $\mathbb{R}$ is the set of real numbers.

Let $a, b, c$ be positive real numbers such that $$\frac{a}{1 + a} + \frac{b}{1 + b} + \frac{c}{1 + c} = 2.$$ Prove that $$\frac{\sqrt{a} + \sqrt{b} + \sqrt{c}}{2} \geqslant \frac{1}{\sqrt{a}} + \frac{1}{\sqrt{b}} + \frac{1}{\sqrt{c}}.$$

For an integer $n \geq 3$, let $\mathcal{M}$ be the set $\{(x, y) \mid x, y \in \mathbb{Z}, 1 \leq x \leq n, 1 \leq y \leq n\}$ of points in the plane. ($\mathbb{Z}$ is the set of integers.)

What is the maximum possible number of points in a subset $S \subseteq \mathcal{M}$ which does not contain three distinct points being the vertices of a right triangle?

Let $n\geq 3$ be an integer. At a MEMO-like competition, there are $3n$ participants, there are $n$ languages spoken, and each participant speaks exactly three different languages.

Prove that at least $\left\lceil\dfrac{2n}{9}\right\rceil$ of the spoken languages can be chosen in such a way that no participant speaks more than two of the chosen languages.

($\lceil x\rceil$ is the smallest integer which is greater than or equal to $x$.)

Let $ABCDE$ be a convex pentagon with all five sides equal in length. The diagonals $AD$ and $EC$ meet in $S$ with $\angle ASE=60^{\circ}$. Prove that $ABCDE$ has a pair of parallel sides.

Let $ABC$ be an acute triangle. Denote by $B_{0}$ and $C_{0}$ the feet of the altitudes from vertices $B$ and $C$, respectively. Let $X$ be a point inside the triangle $ABC$ such that the line $BX$ is tangent to the circumcircle of the triangle $AXC_{0}$ and the line $CX$ is tangent to the circumcircle of the triangle $AXB_{0}$. Show that the line $AX$ is perpendicular to $BC$.

Let $A$ and $B$ be disjoint nonempty sets with $A\cup B=\{1,2,3,\ldots,10\}$. Show that there exist elements $a\in A$ and $b\in B$ such that the number $a^{3}+ab^{2}+b^{3}$ is divisible by $11$.

We call a positive integer $n$ amazing if there exist positive integers $a,b,c$ such that the equality $$n=(b,c)(a,bc)+(c,a)(b,ca)+(a,b)(c,ab)$$ holds. Prove that there exist $2011$ consecutive positive integers which are amazing.

(By $(m,n)$ we denote the greatest common divisor of positive integers $m$ and $n$.)