Middle European Mathematical Olympiad

Let $ABC$ be an acute triangle and $D$ an interior point of segment $BC$. Points $E$ and $F$ lie in the half-plane determined by the line $BC$ containing $A$ such that $DE$ is perpendicular to $BE$ and $DE$ is tangent to the circumcircle of $ACD$, while $DF$ is perpendicular to $CF$ and $DF$ is tangent to the circumcircle of $ABD$. Prove that the points $A$, $D$, $E$ and $F$ are concyclic.

Let $n \geqslant 3$ be an integer. Zagi the squirrel sits at a vertex of a regular $n$-gon. Zagi plans to make a journey of $n - 1$ jumps such that in the $i$-th jump, it jumps by $i$ edges clockwise, for $i \in \{1, \ldots, n - 1\}$. Prove that if after $\lceil \frac{n}{2} \rceil$ jumps Zagi has visited $\lceil \frac{n}{2} \rceil + 1$ distinct vertices, then after $n - 1$ jumps Zagi will have visited all of the vertices.

(Remark. For a real number $x$, we denote by $\lceil x \rceil$ the smallest integer larger or equal to $x$.)

Determine all functions $f\colon \mathbb{R}\to \mathbb{R}$ such that the inequality

$$f(x^2) - f(y^2) \leqslant (f(x) + y)(x - f(y))$$

holds for all real numbers $x$ and $y$.

Given a positive integer $n$, we say that a polynomial $P$ with real coefficients is $n$-pretty if the equation $P(\lfloor x \rfloor) = \lfloor P(x) \rfloor$ has exactly $n$ real solutions. Show that for each positive integer $n$

(a) there exists an $n$-pretty polynomial;

(b) any $n$-pretty polynomial has a degree of at least $\frac{2n + 1}{3}$.

(Remark. For a real number $x$, we denote by $\lfloor x \rfloor$ the largest integer smaller than or equal to $x$.)

Let $n$, $b$ and $c$ be positive integers. A group of $n$ pirates wants to fairly split their treasure. The treasure consists of $c \cdot n$ identical coins distributed over $b \cdot n$ bags, of which at least $n - 1$ bags are initially empty. Captain Jack inspects the contents of each bag and then performs a sequence of moves. In one move, he can take any number of coins from a single bag and put them into one empty bag. Prove that no matter how the coins are initially distributed, Jack can perform at most $n - 1$ moves and then split the bags among the pirates such that each pirate gets $b$ bags and $c$ coins.

Let $n$ be a positive integer. Prove that in a regular $6n$-gon, we can draw $3n$ diagonals with pairwise distinct ends and partition the drawn diagonals into $n$ triplets so that:

• the diagonals in each triplet intersect in one interior point of the polygon and
• all these $n$ intersection points are distinct.

Let $AD$ be the diameter of the circumcircle of an acute triangle $ABC$. The lines through $D$ parallel to $AB$ and $AC$ meet lines $AC$ and $AB$ in points $E$ and $F$, respectively. Lines $EF$ and $BC$ meet at $G$. Prove that $AD$ and $DG$ are perpendicular.

Let $ABC$ be a triangle and let $M$ be the midpoint of the segment $BC$. Let $X$ be a point on the ray $AB$ such that $2\angle CXA = \angle CMA$. Let $Y$ be a point on the ray $AC$ such that $2\angle AYB = \angle AMB$. The line $BC$ intersects the circumcircle of the triangle $AXY$ at $P$ and $Q$, such that the points $P$, $B$, $C$, and $Q$ lie in this order on the line $BC$. Prove that $PB = QC$.

Find all pairs $(n,p)$ of positive integers such that $p$ is prime and

$$1 + 2 + \cdots + n = 3 \cdot (1^2 + 2^2 + \cdots + p^2).$$

Prove that there are infinitely many positive integers $n$ such that $n^2$ written in base $4$ contains only digits $1$ and $2$.

Let $\mathbb{N}$ be the set of positive integers. Determine all positive integers $k$ for which there exist functions $f\colon \mathbb{N}\to \mathbb{N}$ and $g\colon \mathbb{N}\to \mathbb{N}$ such that $g$ assumes infinitely many values and such that

$$f^{g(n)}(n) = f(n) + k$$

holds for every positive integer $n$.

(Remark. Here, $f^i$ denotes the function $f$ applied $i$ times, i.e., $f^i(j) = \underbrace{f(f(\ldots f(f(j)) \ldots))}_{i \text{ times}}$.)

We call a positive integer $N$ contagious if there exist $1000$ consecutive non-negative integers such that the sum of all their digits is $N$. Find all contagious positive integers.

Let $ABC$ be an acute scalene triangle with circumcircle $\omega$ and incenter $I$. Suppose the orthocenter $H$ of $BIC$ lies inside $\omega$. Let $M$ be the midpoint of the longer arc $BC$ of $\omega$. Let $N$ be the midpoint of the shorter arc $AM$ of $\omega$.

Prove that there exists a circle tangent to $\omega$ at $N$ and tangent to the circumcircles of $BHI$ and $CHI$.

Find all positive integers $n$ for which there exist positive integers $x_1, x_2, \ldots, x_n$ such that

$$\dfrac{1}{x_1^2} + \dfrac{2}{x_2^2} + \dfrac{4}{x_3^2} + \cdots + \dfrac{2^{n-1}}{x_n^2} = 1.$$

Determine all functions $f: \mathbb{R} \to \mathbb{R}$ such that $$f(xf(y) + 2y) = f(xy) + xf(y) + f(f(y))$$ holds for all real numbers $x$ and $y$.

Let $n \geq 3$ be an integer. We say that a vertex $A_i$ ($1 \leq i \leq n$) of a convex polygon $A_1A_2\ldots A_n$ is Bohemian if its reflection with respect to the midpoint of the segment $A_{i-1}A_{i+1}$ (with $A_0 = A_n$ and $A_{n+1} = A_1$) lies inside or on the boundary of the polygon $A_1A_2\ldots A_n$. Determine the smallest possible number of Bohemian vertices a convex $n$-gon can have (depending on $n$).

(A convex polygon $A_1A_2\ldots A_n$ has $n$ vertices with all inner angles smaller than $180°$.)

Let $ABC$ be an acute-angled triangle with $AC > BC$ and circumcircle $\omega$. Suppose that $P$ is a point on $\omega$ such that $AP = AC$ and that $P$ is an interior point of the shorter arc $BC$ of $\omega$. Let $Q$ be the point of intersection of the lines $AP$ and $BC$. Furthermore, suppose that $R$ is a point on $\omega$ such that $QA = QR$ and that $R$ is an interior point of the shorter arc $AC$ of $\omega$. Finally, let $S$ be the point of intersection of the line $BC$ with the perpendicular bisector of the side $AB$. Prove that the points $P$, $Q$, $R$, and $S$ are concyclic.

Determine the smallest positive integer $n$ for which the following statement holds true: From any $n$ consecutive integers one can select a non-empty set of consecutive integers such that their sum is divisible by $2019$.

Determine the smallest and the greatest possible values of the expression $$\left(\frac{1}{a^2 + 1} + \frac{1}{b^2 + 1} + \frac{1}{c^2 + 1}\right)\left(\frac{a^2}{a^2 + 1} + \frac{b^2}{b^2 + 1} + \frac{c^2}{c^2 + 1}\right)$$ provided $a$, $b$, and $c$ are non-negative real numbers satisfying $ab + bc + ca = 1$.

Let $\alpha$ be a real number. Determine all polynomials $P$ with real coefficients such that $$P(2x + \alpha) \leq (x^{20} + x^{19})P(x)$$ holds for all real numbers $x$.

There are $n$ boys and $n$ girls in a school class, where $n$ is a positive integer. The heights of all the children in this class are distinct. Every girl determines the number of boys that are taller than her, subtracts the number of girls that are taller than her, and writes the result on a piece of paper. Every boy determines the number of girls that are shorter than him, subtracts the number of boys that are shorter than him, and writes the result on a piece of paper. Prove that the numbers written down by the girls are the same as the numbers written down by the boys (up to a permutation).

Prove that every integer from $1$ to $2019$ can be represented as an arithmetic expression consisting of up to $17$ symbols $2$ and an arbitrary number of additions, subtractions, multiplications, divisions and brackets. The $2$'s may not be used for any other operation, for example to form multi-digit numbers (such as $222$) or powers (such as $2^2$).

Valid examples: $$\left((2 \times 2 + 2) \times 2 - \frac{2}{2}\right) \times 2 = 22, \quad (2 \times 2 \times 2 - 2) \times \left(2 \times 2 + \frac{2 + 2 + 2}{2}\right) = 42.$$

Let $ABC$ be an acute-angled triangle such that $AB < AC$. Let $D$ be the point of intersection of the perpendicular bisector of the side $BC$ with the side $AC$. Let $P$ be a point on the shorter arc $AC$ of the circumcircle of the triangle $ABC$ such that $DP \parallel BC$. Finally, let $M$ be the midpoint of the side $AB$. Prove that $\angle APD = \angle MPB$.

Let $ABC$ be a right-angled triangle with its right angle at $B$ and circumcircle $c$. Denote by $D$ the midpoint of the shorter arc $AB$ of $c$. Let $P$ be the point on the side $AB$ such that $CP = CD$ and let $X$ and $Y$ be two distinct points on $c$ satisfying $AX = AY = PD$. Prove that the points $X$, $Y$, and $P$ are collinear.

Let $a$, $b$ and $c$ be positive integers satisfying $a < b < c < a + b$. Prove that $c(a - 1) + b$ does not divide $c(b - 1) + a$.

Let $N$ be a positive integer such that the sum of the squares of all positive divisors of $N$ is equal to the product $N(N + 3)$. Prove that there exist two indices $i$ and $j$ such that $N = F_i \cdot F_j$, where $(F_n)_{n=1}^{\infty}$ is the Fibonacci sequence defined by $F_1 = F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for all $n \geq 3$.

Let $\mathbb{Q}^+$ denote the set of all positive rational numbers and let $\alpha \in \mathbb{Q}^+$. Determine all functions $f\colon \mathbb{Q}^{+}\to (\alpha , + \infty)$ satisfying

$$f \left(\frac {x + y}{\alpha}\right) = \frac {f (x) + f (y)}{\alpha}, \quad \text {for all} \, x, y \in \mathbb {Q} ^ {+}.$$

The two figures depicted below consisting of $6$ and $10$ unit squares, respectively, are called staircases.

Consider a $2018 \times 2018$ board consisting of $2018^2$ cells, each being a unit square. Two arbitrary cells were removed from the same row of the board. Prove that the rest of the board cannot be cut (along the cell borders) into staircases (possibly rotated).

Let $ABC$ be an acute-angled triangle with $AB < AC$, and let $D$ be the foot of its altitude from $A$. Let $R$ and $Q$ be the centroids of the triangles $ABD$ and $ACD$, respectively. Let $P$ be a point on the line segment $BC$ such that $P \neq D$ and the points $P, Q, R$ and $D$ are concyclic. Prove that the lines $AP, BQ$ and $CR$ are concurrent.

(a) Prove that for every positive integer $m$ there exists an integer $n \geq m$ such that

$$\left\lfloor \frac {n}{1} \right\rfloor \cdot \left\lfloor \frac {n}{2} \right\rfloor \cdots \left\lfloor \frac {n}{m} \right\rfloor = \binom {n} {m}. \tag{*}$$

(b) Denote by $p(m)$ the smallest integer $n \geq m$ such that the equation (*) holds. Prove that $p(2018) = p(2019)$.

Remark: For a real number $x$, we denote by $\lfloor x \rfloor$ the largest integer not larger than $x$.

Let $a$, $b$ and $c$ be positive real numbers satisfying $abc = 1$. Prove that $$\frac{a^2 - b^2}{a + bc} + \frac{b^2 - c^2}{b + ca} + \frac{c^2 - a^2}{c + ab} \leq a + b + c - 3.$$

Let $P(x)$ be a polynomial of degree $n \geq 2$ with rational coefficients such that $P(x)$ has $n$ pairwise different real roots forming an arithmetic progression. Prove that among the roots of $P(x)$ there are two that are also the roots of some polynomial of degree $2$ with rational coefficients.

A group of pirates had an argument and now each of them holds some other two at gunpoint. All the pirates are called one by one in some order. If the called pirate is still alive, he shoots both pirates he is aiming at (some of whom might already be dead). All shots are immediately lethal. After all the pirates have been called, it turns out that exactly $28$ pirates got killed.

Prove that if the pirates were called in whatever other order, at least $10$ pirates would have been killed anyway.

Let $n$ be a positive integer and $u_1, u_2, \ldots, u_n$ be positive integers not larger than $2^k$, for some integer $k \geq 3$. A representation of a non-negative integer $t$ is a sequence of non-negative integers $a_1, a_2, \ldots, a_n$ such that $$t = a_1 u_1 + a_2 u_2 + \cdots + a_n u_n.$$

Prove that if a non-negative integer $t$ has a representation, then it also has a representation where less than $2k$ of the numbers $a_1, a_2, \ldots, a_n$ are non-zero.

Let $ABC$ be an acute-angled triangle with $AB < AC$, and let $D$ be the foot of its altitude from $A$. Points $B'$ and $C'$ lie on the rays $AB$ and $AC$, respectively, so that points $B'$, $C'$ and $D$ are collinear and points $B$, $C$, $B'$ and $C'$ lie on one circle with center $O$. Prove that if $M$ is the midpoint of $BC$ and $H$ is the orthocenter of $ABC$, then $DHMO$ is a parallelogram.

Let $ABC$ be a triangle. The internal bisector of $\angle ABC$ intersects the side $AC$ at $L$ and the circumcircle of triangle $ABC$ again at $W \neq B$. Let $K$ be the perpendicular projection of $L$ onto $AW$. The circumcircle of triangle $BLC$ intersects line $CK$ again at $P \neq C$. Lines $BP$ and $AW$ meet at point $T$. Prove that $AW = WT$.

Let $a_1, a_2, a_3, \ldots$ be the sequence of positive integers such that $$a_1 = 1 \quad \text{and} \quad a_{k+1} = a_k^3 + 1, \text{ for all positive integers } k.$$

Prove that for every prime number $p$ of the form $3\ell + 2$, where $\ell$ is a non-negative integer, there exists a positive integer $n$ such that $a_n$ is divisible by $p$.

An integer $n$ is called Silesian if there exist positive integers $a$, $b$ and $c$ such that $$n = \frac{a^2 + b^2 + c^2}{ab + bc + ca}.$$

(a) Prove that there are infinitely many Silesian integers.

(b) Prove that not every positive integer is Silesian.

Let $n \geq 2$ be an integer and $x_1, x_2, \ldots, x_n$ be real numbers satisfying

(a) $x_j > -1$ for $j = 1, 2, \ldots, n$ and

(b) $x_1 + x_2 + \cdots + x_n = n$.

Prove the inequality $$\sum_{j=1}^n \frac{1}{1 + x_j} \geq \sum_{j=1}^n \frac{x_j}{1 + x_j^2}$$

and determine when equality holds.

There are $n \geq 3$ positive integers written on a blackboard. A move consists of choosing three numbers $a, b, c$ on the blackboard such that they are the sides of a non-degenerate non-equilateral triangle and replacing them by $a + b - c$, $b + c - a$ and $c + a - b$.

Show that an infinite sequence of moves cannot exist.

Let $ABC$ be an acute-angled triangle with $\measuredangle BAC > 45°$ and with circumcentre $O$. The point $P$ lies in its interior such that the points $A, P, O, B$ lie on a circle and $BP$ is perpendicular to $CP$. The point $Q$ lies on the segment $BP$ such that $AQ$ is parallel to $PO$.

Prove that $\measuredangle QCB = \measuredangle PCO$.

Find all functions $f: \mathbb{N} \to \mathbb{N}$ such that $f(a) + f(b)$ divides $2(a + b - 1)$ for all $a, b \in \mathbb{N}$.

Remark: $\mathbb{N} = \{1, 2, 3, \ldots\}$ denotes the set of positive integers.

Determine all triples $(a, b, c)$ of real numbers satisfying the system of equations $$a^2 + ab + c = 0,$$ $$b^2 + bc + a = 0,$$ $$c^2 + ca + b = 0.$$

Let $\mathbb{R}$ denote the set of real numbers. Determine all functions $f\colon \mathbb{R}\to \mathbb{R}$ such that $$f(x)f(y) = x f(f(y - x)) + x f(2x) + f(x^2)$$ holds for all real numbers $x$ and $y$.

A tract of land in the shape of an $8 \times 8$ square, whose sides are oriented north-south and east-west, consists of $64$ smaller $1 \times 1$ square plots. There can be at most one house on each of the individual plots. A house can only occupy a single $1 \times 1$ square plot.

A house is said to be blocked from sunlight if there are three houses on the plots immediately to its east, west and south.

What is the maximum number of houses that can simultaneously exist, such that none of them is blocked from sunlight?

Remark: By definition, houses on the east, west and south borders are never blocked from sunlight.

A class of high school students wrote a test. Every question was graded as either $1$ point for a correct answer or $0$ points otherwise. It is known that each question was answered correctly by at least one student and the students did not all achieve the same total score.

Prove that there was a question on the test with the following property: The students who answered the question correctly got a higher average test score than those who did not.

Let $ABC$ be an acute-angled triangle with $AB \neq AC$, and let $O$ be its circumcentre. The line $AO$ intersects the circumcircle $\omega$ of $ABC$ a second time in point $D$, and the line $BC$ in point $E$. The circumcircle of $CDE$ intersects the line $CA$ a second time in point $P$. The line $PE$ intersects the line $AB$ in point $Q$. The line through $O$ parallel to $PE$ intersects the altitude of the triangle $ABC$ that passes through $A$ in point $F$.

Prove that $FP = FQ$.

Let $ABC$ be a triangle with $AB \neq AC$. The points $K, L, M$ are the midpoints of the sides $BC, CA, AB$, respectively. The inscribed circle of $ABC$ with centre $I$ touches the side $BC$ at point $D$. The line $g$, which passes through the midpoint of segment $ID$ and is perpendicular to $IK$, intersects the line $LM$ at point $P$.

Prove that $\measuredangle PIA = 90^{\circ}$.

A positive integer $n$ is called a Mozartian number if the numbers $1, 2, \ldots, n$ together contain an even number of each digit (in base $10$).

Prove:

(a) All Mozartian numbers are even.

(b) There are infinitely many Mozartian numbers.

We consider the equation $a^2 + b^2 + c^2 + n = abc$, where $a, b, c$ are positive integers.

Prove:

(a) There are no solutions $(a,b,c)$ for $n = 2017$.

(b) For $n = 2016$, $a$ must be divisible by $3$ for every solution $(a, b, c)$.

(c) The equation has infinitely many solutions $(a, b, c)$ for $n = 2016$.