Middle European Mathematical Olympiad

Find all surjective functions $f: \mathbb{N} \to \mathbb{N}$ such that for all positive integers $a$ and $b$, exactly one of the following equations is true: $$f(a) = f(b),$$ $$f(a + b) = \min\{f(a), f(b)\}.$$

Remarks: $\mathbb{N}$ denotes the set of all positive integers. A function $f: X \to Y$ is said to be surjective if for every $y \in Y$ there exists $x \in X$ such that $f(x) = y$.

Let $n \geq 3$ be an integer. An inner diagonal of a simple $n$-gon is a diagonal that is contained in the $n$-gon. Denote by $D(P)$ the number of all inner diagonals of a simple $n$-gon $P$ and by $D(n)$ the least possible value of $D(Q)$, where $Q$ is a simple $n$-gon. Prove that no two inner diagonals of $P$ intersect (except possibly at a common endpoint) if and only if $D(P) = D(n)$.

Remark: A simple $n$-gon is a non-self-intersecting polygon with $n$ vertices. A polygon is not necessarily convex.

Let $ABCD$ be a cyclic quadrilateral. Let $E$ be the intersection of lines parallel to $AC$ and $BD$ passing through points $B$ and $A$, respectively. The lines $EC$ and $ED$ intersect the circumcircle of $AEB$ again at $F$ and $G$, respectively. Prove that points $C$, $D$, $F$, and $G$ lie on a circle.

Find all pairs of positive integers $(m,n)$ for which there exist relatively prime integers $a$ and $b$ greater than $1$ such that $$\frac{a^m + b^m}{a^n + b^n}$$ is an integer.

Prove that for all positive real numbers $a$, $b$, $c$ such that $abc = 1$ the following inequality holds: $$\frac{a}{2b + c^2} + \frac{b}{2c + a^2} + \frac{c}{2a + b^2} \leq \frac{a^2 + b^2 + c^2}{3}.$$

Determine all functions $f: \mathbb{R}\backslash\{0\} \to \mathbb{R}\backslash\{0\}$ such that $$f(x^2 y f(x)) + f(1) = x^2 f(x) + f(y)$$ holds for all nonzero real numbers $x$ and $y$.

There are $n$ students standing in line in positions $1$ to $n$. While the teacher looks away, some students change their positions. When the teacher looks back, they are standing in line again. If a student who was initially in position $i$ is now in position $j$, we say the student moved for $|i - j|$ steps. Determine the maximal sum of steps of all students that they can achieve.

Let $N$ be a positive integer. In each of the $N^2$ unit squares of an $N \times N$ board, one of the two diagonals is drawn. The drawn diagonals divide the $N \times N$ board into $K$ regions. For each $N$, determine the smallest and the largest possible values of $K$.

Example with $N = 3$, $K = 7$

Let $ABC$ be an acute triangle with $AB > AC$. Prove that there exists a point $D$ with the following property: whenever two distinct points $X$ and $Y$ lie in the interior of $ABC$ such that the points $B$, $C$, $X$, and $Y$ lie on a circle and $$\angle AXB - \angle ACB = \angle CYA - \angle CBA$$ holds, the line $XY$ passes through $D$.

Let $I$ be the incentre of triangle $ABC$ with $AB > AC$ and let the line $AI$ intersect the side $BC$ at $D$. Suppose that point $P$ lies on the segment $BC$ and satisfies $PI = PD$. Further, let $J$ be the point obtained by reflecting $I$ over the perpendicular bisector of $BC$, and let $Q$ be the other intersection of the circumcircles of the triangles $ABC$ and $APD$. Prove that $\angle BAQ = \angle CAJ$.

Find all pairs of positive integers $(a,b)$ such that $$a! + b! = a^b + b^a.$$

Let $n \geq 2$ be an integer. Determine the number of positive integers $m$ such that $m \leq n$ and $m^2 + 1$ is divisible by $n$.

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

Prove that $$2(a + b + c) \geq \sqrt[3]{7a^2b + 1} + \sqrt[3]{7b^2c + 1} + \sqrt[3]{7c^2a + 1}.$$

Find all triples $(a,b,c)$ for which equality holds.

Let $n$ be a positive integer. On a board consisting of $4n \times 4n$ squares, exactly $4n$ tokens are placed so that each row and each column contains one token. In a step, a token is moved horizontally or vertically to a neighbouring square. Several tokens may occupy the same square at the same time. The tokens are to be moved to occupy all the squares of one of the two diagonals.

Determine the smallest number $k(n)$ such that for any initial situation, we can do it in at most $k(n)$ steps.

Let $ABC$ be an isosceles triangle with $AC = BC$. Let $N$ be a point inside the triangle such that $2\angle ANB = 180° + \angle ACB$. Let $D$ be the intersection of the line $BN$ and the line parallel to $AN$ that passes through $C$. Let $P$ be the intersection of the angle bisectors of the angles $CAN$ and $ABN$.

Show that the lines $DP$ and $AN$ are perpendicular.

Let $a$ and $b$ be positive integers. Prove that there exist positive integers $x$ and $y$ such that $$\binom{x + y}{2} = ax + by.$$

Find all functions $f\colon\mathbb{R}\to\mathbb{R}$ such that $$f(xf(x)+2y)=f(x^{2})+f(y)+x+y-1$$ for all $x$, $y\in\mathbb{R}$.

Let $x$, $y$, $z$, $w\in\mathbb{R}\setminus\{0\}$ such that $x+y\neq 0$, $z+w\neq 0$, and $xy+zw\geq 0$. Prove the inequality $$\left(\frac{x+y}{z+w}+\frac{z+w}{x+y}\right)^{-1}+\frac{1}{2}\geq\left(\frac{x}{z}+\frac{z}{x}\right)^{-1}+\left(\frac{y}{w}+\frac{w}{y}\right)^{-1}.$$

There are $n\geq 2$ houses on the northern side of a street. Going from the west to the east, the houses are numbered from $1$ to $n$. The number of each house is shown on a plate. One day the inhabitants of the street make fun of the postman by shuffling their number plates in the following way: for each pair of neighbouring houses, the current number plates are swapped exactly once during the day.

How many different sequences of number plates are possible at the end of the day?

Consider finitely many points in the plane with no three points on a line. All these points can be coloured red or green such that any triangle with vertices of the same colour contains at least one point of the other colour in its interior.

What is the maximal possible number of points with this property?

Let $ABC$ be an acute triangle. Construct a triangle $PQR$ such that $AB = 2PQ$, $BC = 2QR$, $CA = 2RP$, and the lines $PQ$, $QR$, and $RP$ pass through the points $A$, $B$, and $C$, respectively. (All six points $A$, $B$, $C$, $P$, $Q$, and $R$ are distinct.)

Let $K$ be a point inside an acute triangle $ABC$, such that $BC$ is a common tangent of the circumcircles of $AKB$ and $AKC$. Let $D$ be the intersection of the lines $CK$ and $AB$, and let $E$ be the intersection of the lines $BK$ and $AC$. Let $F$ be the intersection of the line $BC$ and the perpendicular bisector of the segment $DE$. The circumcircle of $ABC$ and the circle $k$ with centre $F$ and radius $FD$ intersect at points $P$ and $Q$.

Prove that the segment $PQ$ is a diameter of $k$.

The numbers from $1$ to $2013^{2}$ are written row by row into a table consisting of $2013 \times 2013$ cells. Afterwards, all columns and all rows containing at least one of the perfect squares $1,4,9,\ldots,2013^{2}$ are simultaneously deleted.

How many cells remain?

The expression $$\pm \square \pm \square \pm \square \pm \square \pm \square \pm \square$$ is written on the blackboard. Two players, $A$ and $B$, play a game, taking turns. Player $A$ takes the first turn. In each turn, the player on turn replaces a symbol $\square$ by a positive integer. After all the symbols $\square$ are replaced, player $A$ replaces each of the signs $\pm$ by either $+$ or $-$, independently of each other. Player $A$ wins if the value of the expression on the blackboard is not divisible by any of the numbers $11, 12, \ldots, 18$. Otherwise, player $B$ wins.

Determine which player has a winning strategy.

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$.)

Find all functions $f\colon \mathbb{R}\to \mathbb{R}$ such that for all $x,y\in \mathbb{R}$, we have $$f(x + y) + f(x)f(y) = f(xy) + (y + 1)f(x) + (x + 1)f(y).$$

All positive divisors of a positive integer $N$ are written on a blackboard. Two players $A$ and $B$ play the following game taking alternate moves. In the first move, the player $A$ erases $N$. If the last erased number is $d$, then the next player erases either a divisor of $d$ or a multiple of $d$. The player who cannot make a move loses. Determine all numbers $N$ for which $A$ can win independently of the moves of $B$.

We are given a cyclic quadrilateral $ABCD$ with a point $E$ on the diagonal $AC$ such that $AD = AE$ and $CB = CE$. Let $M$ be the center of the circumcircle $k$ of the triangle $BDE$. The circle $k$ intersects the line $AC$ in the points $E$ and $F$. Prove that the lines $FM$, $AD$, and $BC$ meet at one point.

Find all positive integers $n$ which satisfy the following two conditions:

(i) $n$ has at least four different positive divisors;

(ii) for any divisors $a$ and $b$ of $n$ satisfying $1 < a < b < n$, the number $b - a$ divides $n$.

Three strictly increasing sequences $$a_1, a_2, a_3, \ldots, \qquad b_1, b_2, b_3, \ldots, \qquad c_1, c_2, c_3, \ldots$$ of positive integers are given. Every positive integer belongs to exactly one of the three sequences. For every positive integer $n$, the following conditions hold:

(i) $c_{a_n} = b_n + 1$;

(ii) $a_{n+1} > b_n$;

(iii) the number $c_{n+1}c_n - (n+1)c_{n+1} - nc_n$ is even.

Find $a_{2010}$, $b_{2010}$, and $c_{2010}$.

For each integer $n \geq 2$, determine the largest real constant $C_n$ such that for all positive real numbers $a_1, \ldots, a_n$, we have $$\frac{a_1^2 + \cdots + a_n^2}{n} \geq \left(\frac{a_1 + \cdots + a_n}{n}\right)^2 + C_n \cdot (a_1 - a_n)^2.$$

In each vertex of a regular $n$-gon there is a fortress. At the same moment each fortress shoots at one of the two nearest fortresses and hits it. The result of the shooting is the set of the hit fortresses; we do not distinguish whether a fortress was hit once or twice. Let $P(n)$ be the number of possible results of the shooting. Prove that for every positive integer $k \geq 3$, $P(k)$ and $P(k + 1)$ are relatively prime.

Let $n$ be a positive integer. A square $ABCD$ is partitioned into $n^2$ unit squares. Each of them is divided into two triangles by the diagonal parallel to $BD$. Some of the vertices of the unit squares are colored red in such a way that each of these $2n^2$ triangles contains at least one red vertex. Find the least number of red vertices.

The incircle of the triangle $ABC$ touches the sides $BC$, $CA$, and $AB$ in the points $D$, $E$, and $F$, respectively. Let $K$ be the point symmetric to $D$ with respect to the incenter. The lines $DE$ and $FK$ intersect at $S$. Prove that $AS$ is parallel to $BC$.

Let $A$, $B$, $C$, $D$, $E$ be points such that $ABCD$ is a cyclic quadrilateral and $ABDE$ is a parallelogram. The diagonals $AC$ and $BD$ intersect at $S$ and the rays $AB$ and $DC$ intersect at $F$. Prove that $\angle AFS = \angle ECD$.

For a nonnegative integer $n$, define $a_n$ to be the positive integer with decimal representation $$1\underbrace{0\ldots 0}_{n}2\underbrace{0\ldots 0}_{n}2\underbrace{0\ldots 0}_{n}1.$$

Prove that $a_n/3$ is always the sum of two positive perfect cubes but never the sum of two perfect squares.

We are given a positive integer $n$ which is not a power of $2$. Show that there exists a positive integer $m$ with the following two properties:

(i) $m$ is the product of two consecutive positive integers;

(ii) the decimal representation of $m$ consists of two identical blocks of $n$ digits.

Find all functions $f\colon \mathbb{R}\to \mathbb{R}$ such that

$$f (x f (y)) + f (f (x) + f (y)) = y f (x) + f (x + f (y))$$

for all $x,y\in \mathbb{R}$, where $\mathbb{R}$ denotes the set of real numbers.

Suppose that we have $n \geqslant 3$ distinct colours. Let $f(n)$ be the greatest integer with the property that every side and every diagonal of a convex polygon with $f(n)$ vertices can be coloured with one of $n$ colours in the following way:

• at least two distinct colours are used, and

• any three vertices of the polygon determine either three segments of the same colour or of three different colours.

Show that $f(n) \leqslant (n - 1)^2$ with equality for infinitely many values of $n$.