Middle European Mathematical Olympiad

Let $\mathbb{R}^+$ be the set of positive real numbers. Let $f\colon \mathbb{R}^{+}\to \mathbb{R}^{+}$ be a function such that for all $x,y\in \mathbb{R}^{+}$ it holds that

$$y f^{2025}(x) \geq x f(y).$$

Show that there exists a positive integer $n_0$ such that for all positive integers $n \geq n_0$ and for all $x \in \mathbb{R}^+$ it holds that

$$f^n(x) \geq x.$$

Remark. Here $f^n$ denotes the function $f$ applied $n$ times, this means $f^n(x) = \underbrace{f(f(\ldots f(x)\ldots))}_{n \text{ times}}$.

On an infinite square grid, on which some unit squares are coloured red, a ruby rook is a piece which, in one move, can travel any number of squares in one direction parallel to one of the grid lines (either vertically or horizontally), while remaining on red squares at all times throughout the move.

Starting with an uncoloured infinite square grid, Alice performs the following procedure: First, she colours at most 2025 of the unit squares red. Afterwards, she places some ruby rooks on distinct red unit squares, such that the following two rules are satisfied:

• No ruby rook can reach another ruby rook in one move.
• Every ruby rook can reach every other ruby rook in two moves.

Find the maximum possible number of ruby rooks that Alice can place during this procedure.

Let $ABC$ be a triangle. Its incircle $\omega$ touches the sides $BC, CA$ and $AB$ at points $D, E$ and $F$, respectively. Let $P$ and $Q$ be points on the line $BC$ distinct from $D$ such that $PB = BD$ and $QC = CD$. Prove that the circumcircles of the triangles $PCE$ and $QBF$ and the circle $\omega$ pass through a common point.

A subset $S$ of the integers is called Saxonian if for every three pairwise different elements $a, b, c \in S$ the number $ab + c$ is the square of an integer. Prove that any Saxonian set is finite. Determine the largest possible number of elements that a Saxonian set can have.

Bob has $n$ coins with integer values $$c_1 \geq c_2 \geq \cdots \geq c_n > 0.$$

He is standing in front of a vending machine that offers $n$ candy bars with positive integer costs $b_1, b_2, \ldots, b_n$. Bob notices that for every $i \in \{1, \ldots, n\}$, it holds that $$b_1 + b_2 + \cdots + b_i \geq c_1 + c_2 + \cdots + c_i.$$

Furthermore, the total value of Bob's coins equals the sum of the costs of all the candy bars. The candy bars can be purchased in any order. In order to buy the $i$-th candy bar, Bob has to insert coins of total value at least $b_i$. However, the machine does not give him back any change.

Prove that Bob can buy at least half of the candy bars.

Let $\mathbb{R}^+$ be the set of positive real numbers. Determine all functions $f\colon \mathbb{R}^{+}\to \mathbb{R}^{+}$ such that for all numbers $x,y\in \mathbb{R}^{+}$, we have $$f(xy) + f(x) = f(y)f(xf(y)) + f(x)f(y),$$

and there exists at most one number $a \in \mathbb{R}^+$ such that $f(a) = 1$.

A snake in an $n \times n$ grid is a path composed of straight line segments between centres of adjacent cells, going through the centres of all the $n^2$ grid cells, which visits each cell exactly once. Here two grid cells are considered to be adjacent if they share an edge. Note that all pieces of the snake path are parallel to grid lines. The figure shows an example of a snake in a $4 \times 4$ grid. This snake makes nine $90^\circ$ turns, marked by small black squares.

Let us now consider a snake through the 2025 cells of a $45 \times 45$ grid. What is the maximum possible number of $90^\circ$ turns that such a snake can make?

Let $n$ be a positive integer. In the province of Laplandia there are $100n$ cities, each two connected by a direct road, and each of these roads has a toll station collecting a positive amount of toll revenue. For each road, the revenue of its toll station is split equally between the two cities at the ends of the road (meaning that each of the two cities receives half of the income). For each city, the total toll revenue is given by the sum of the revenues it receives from the $100n - 1$ toll stations on its roads.

According to a new law, the revenues of some of the toll stations will be collected by the federal government instead of by the adjacent cities. The governor of Laplandia is allowed to choose those toll stations. The mayors of the cities demand that for each city, the sum of the remaining revenues it receives from the other toll stations after this change is at least $99\%$ of its former total toll revenue.

Find the largest positive integer $k$, depending on $n$, such that the governor can always choose $k$ toll stations for the federal government to collect the toll revenue, while satisfying the demand of the city mayors.

Let $ABC$ be an acute triangle with $AB < AC$. Denote by $D$ the foot of the perpendicular from $A$ to $BC$. Let $E$ be the point such that $ABEC$ is a parallelogram. Let $M$ be a point inside triangle $ABC$ such that $MB = MC$. Let $F$ be the reflection of point $D$ across the tangent to the circumcircle of triangle $ADM$ at point $M$. Prove that $AF = DE$.

Let $ABC$ be an acute triangle with an interior point $D$ such that $\angle BDC = 180^{\circ} - \angle BAC$. The lines $BD$ and $AC$ intersect at the point $E$, and the lines $CD$ and $AB$ intersect at the point $F$. The points $P \neq E$ and $Q \neq F$ lie on the line $EF$ so that $BP = BE$ and $CQ = CF$. Assume that the segments $AP$ and $AQ$ intersect the circumcircle $\omega$ of $ABC$ at the points $R \neq A$ and $S \neq A$, respectively. Prove that the lines $RF$ and $SE$ intersect on $\omega$.

Let $n$ be a positive integer such that the sum of positive divisors of $n^2 + n + 1$ is divisible by 3. Prove that it is possible to partition the set of positive divisors of $n^2 + n + 1$ into three sets such that the product of all elements in each set is the same.

Determine whether the following statement is true for every polynomial $P$ of degree at least 2 with nonnegative integer coefficients:

There exists a positive integer $m$ such that for infinitely many positive integers $n$ the number $P^n(m)$ has more than $n$ distinct positive divisors.

Remark. Here $P^n$ denotes $P$ applied $n$ times, this means $P^n(x) = \underbrace{P(P(\ldots P(x)\ldots))}_{n \text{ times}}$.

Determine all $k \in \mathbb{N}_0$ for which there exists a function $f \colon \mathbb{N}_0 \to \mathbb{N}_0$ such that $f(2024) = k$ and

$$f(f(n)) \leq f(n + 1) - f(n)$$

for all $n \in \mathbb{N}_0$.

Remark. Here $\mathbb{N}_0$ denotes the set of nonnegative integers.

There is a sheet of paper (like this one) on an infinite blackboard. Marvin secretly chooses a convex 2024-gon $P$ that lies fully on the piece of paper. Tigerin wants to find the vertices of $P$. In each step, Tigerin can draw a line $g$ on the blackboard that is fully outside the piece of paper, then Marvin replies with the line $h$ parallel to $g$ that is the closest to $g$ which passes through at least one vertex of $P$. Prove that there exists a positive integer $n$ such that Tigerin can always determine the vertices of $P$ in at most $n$ steps.

Let $ABC$ be an acute scalene triangle. Choose a circle $\omega$ passing through $B$ and $C$ which intersects segments $AB$ and $AC$ again in points $D \neq A$ and $E \neq A$, respectively. Let $F$ be the intersection of $BE$ and $CD$. Let $G$ be the point on the circumcircle of $ABF$ such that $GB$ is tangent to $\omega$. Similarly, let $H$ be the point on the circumcircle of $ACF$ such that $HC$ is tangent to $\omega$. Prove that there exists a point $T \neq A$, independent of the choice of $\omega$, such that the circumcircle of $AGH$ passes through $T$.

For any positive integer $n$, let $\sigma(n)$ denote the sum of positive divisors of $n$. Determine all polynomials $P$ with integer coefficients such that $P(k)$ is divisible by $\sigma(k)$ for all positive integers $k$.

Consider the two infinite sequences $a_0, a_1, a_2, \ldots$ and $b_0, b_1, b_2, \ldots$ of real numbers such that $a_0 = 0$, $b_0 = 0$ and $$a_{k+1} = b_k, \qquad b_{k+1} = \frac{a_k b_k + a_k + 1}{b_k + 1}$$ for each integer $k \geq 0$. Prove that $a_{2024} + b_{2024} \geq 88$.

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

There are 2024 mathematicians sitting in a row next to the river Tisza. Each of them is working on exactly one research topic, and if two mathematicians are working on the same topic, everyone sitting between them is also working on it.

Marvin is trying to figure out for each pair of mathematicians whether they are working on the same topic. He is allowed to ask each mathematician the following question: "How many of these 2024 mathematicians are working on your topic?" He asks the questions one by one, so he knows all previous answers before he asks the next one.

Determine the smallest positive integer $k$ such that Marvin can always accomplish his goal with at most $k$ questions.

A finite sequence $x_1, x_2, \ldots, x_r$ of positive integers is a palindrome if $x_i = x_{r+1-i}$ for all integers $1 \leq i \leq r$.

Let $a_1, a_2, \ldots$ be an infinite sequence of positive integers. For a positive integer $j \geq 2$, denote by $a[j]$ the finite subsequence $a_1, a_2, \ldots, a_{j-1}$. Suppose that there exists a strictly increasing infinite sequence $b_1, b_2, \ldots$ of positive integers such that for every positive integer $n$, the subsequence $a[b_n]$ is a palindrome and $b_{n+2} \leq b_{n+1} + b_n$. Prove that there exists a positive integer $T$ such that $a_i = a_{i+T}$ for every positive integer $i$.

Let $ABC$ be a triangle with $\angle BAC = 60°$. Let $D$ be a point on the line $AC$ such that $AB = AD$ and $A$ lies between $C$ and $D$. Suppose that there are two points $E \neq F$ on the circumcircle of the triangle $DBC$ such that $AE = AF = BC$. Prove that the line $EF$ passes through the circumcenter of $ABC$.

Let $ABC$ be an acute triangle. Let $M$ be the midpoint of the segment $BC$. Let $I, J, K$ be the incenters of triangles $ABC, ABM, ACM$, respectively. Let $P, Q$ be points on the lines $MK, MJ$, respectively, such that $\angle AJP = \angle ABC$ and $\angle AKQ = \angle BCA$. Let $R$ be the intersection of the lines $CP$ and $BQ$. Prove that the lines $IR$ and $BC$ are perpendicular.

Define glueing of positive integers as writing their base ten representations one after another and interpreting the result as the base ten representation of a single positive integer.

Find all positive integers $k$ for which there exists an integer $N_k$ with the following property: for all $n \geq N_k$, we can glue the numbers $1, 2, \ldots, n$ in some order so that the result is a number divisible by $k$.

Remark. The base ten representation of a positive integer never starts with zero.

Example. Glueing 15, 14, 7 in this order makes 15147.

Let $k$ be a positive integer and $a_1, a_2, \ldots$ be an infinite sequence of positive integers such that $$a_i a_{i+1} \mid k - a_i^2$$ for all integers $i \geq 1$. Prove that there exists a positive integer $M$ such that $a_n = a_{n+1}$ for all integers $n \geq M$.

Let $\mathbb{R}$ denote the set of all real numbers. For each pair $(\alpha, \beta)$ of nonnegative real numbers subject to $\alpha + \beta \geq 2$, determine all functions $f\colon \mathbb{R} \to \mathbb{R}$ satisfying

$$f(x)f(y) \leq f(xy) + \alpha x + \beta y$$

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

Find all integers $n \geq 3$ for which it is possible to draw $n$ chords of one circle such that their $2n$ endpoints are pairwise distinct and each chord intersects precisely $k$ other chords for:

(a) $k = n - 2$,

(b) $k = n - 3$.

Remark. A chord of a circle is a line segment whose both endpoints lie on the circle.

Let $ABC$ be a triangle with incenter $I$. The incircle $\omega$ of $ABC$ is tangent to the line $BC$ at point $D$. Denote by $E$ and $F$ the points satisfying $AI \parallel BE \parallel CF$ and $\angle BEI = \angle CFI = 90°$. Lines $DE$ and $DF$ intersect $\omega$ again at points $E'$ and $F'$, respectively. Prove that $E'F' \perp AI$.

Let $n$ and $m$ be positive integers. We call a set $S$ of positive integers $(n, m)$-good if it satisfies the following three conditions:

(i) We have $m \in S$.

(ii) For all $a \in S$, all of the positive divisors of $a$ are elements of $S$ too.

(iii) For all mutually different numbers $a, b \in S$, we have $a^n + b^n \in S$.

Determine all pairs $(n, m)$ such that the set of all positive integers is the only $(n, m)$-good set.

Let $\mathbb{Z}$ denote the set of all integers and $\mathbb{Z}_{>0}$ denote the set of all positive integers.

(a) A function $f\colon \mathbb{Z}\to \mathbb{Z}$ is called $\mathbb{Z}$-good if it satisfies $f(a^{2} + b) = f(b^{2} + a)$ for all $a,b\in \mathbb{Z}$. Determine the largest possible number of distinct values that can occur among $f(1),f(2),\ldots ,f(2023)$, where $f$ is a $\mathbb{Z}$-good function.

(b) A function $f\colon \mathbb{Z}_{>0}\to \mathbb{Z}_{>0}$ is called $\mathbb{Z}_{>0}$-good if it satisfies $f(a^{2} + b) = f(b^{2} + a)$ for all $a,b\in \mathbb{Z}_{>0}$. Determine the largest possible number of distinct values that can occur among $f(1),f(2),\ldots ,f(2023)$, where $f$ is a $\mathbb{Z}_{>0}$-good function.

Let $a, b, c$ and $d$ be positive real numbers with $abcd = 1$. Prove that

$$\frac {a b + 1}{a + 1} + \frac {b c + 1}{b + 1} + \frac {c d + 1}{c + 1} + \frac {d a + 1}{d + 1} \geq 4,$$

and determine all quadruples $(a,b,c,d)$ for which equality holds.

Find the smallest integer $b$ with the following property: For each way of colouring exactly $b$ squares of an $8 \times 8$ chessboard green, one can place 7 bishops on 7 green squares so that no two bishops attack each other.

Remark. Two bishops attack each other if they are on the same diagonal.

Let $c \geq 4$ be an even integer. In some football league, each team has a home uniform and an away uniform. Every home uniform is coloured in two different colours, and every away uniform is coloured in one colour. A team's away uniform cannot be coloured in one of the colours from the home uniform. There are at most $c$ distinct colours on all of the uniforms. If two teams have the same two colours on their home uniforms, then they have different colours on their away uniforms.

We say a pair of uniforms is clashing if some colour appears on both of them. Suppose that for every team $X$ in the league, there is no team $Y$ in the league such that the home uniform of $X$ is clashing with both uniforms of $Y$. Determine the maximum possible number of teams in the league.

We are given a convex quadrilateral $ABCD$ whose angles are not right. Assume there are points $P, Q, R, S$ on its sides $AB, BC, CD, DA$, respectively, such that $PS \parallel BD$, $SQ \perp BC$, $PR \perp CD$. Furthermore, assume that the lines $PR, SQ$, and $AC$ are concurrent. Prove that the points $P, Q, R, S$ are concyclic.

Let $ABC$ be an acute triangle with $AB < AC$. Let $J$ be the center of the $A$-excircle of $ABC$. Let $D$ be the projection of $J$ on line $BC$. The internal bisectors of angles $BDJ$ and $JDC$ intersect lines $BJ$ and $JC$ at $X$ and $Y$, respectively. Segments $XY$ and $JD$ intersect at $P$. Let $Q$ be the projection of $A$ on line $BC$. Prove that the internal angle bisector of $\measuredangle QAP$ is perpendicular to line $XY$.

Remark. The $A$-excircle of the triangle $ABC$ is the circle outside the triangle which is tangent to the lines $AB$, $AC$, and the line segment $BC$.

Find all positive integers $n$ for which there exist positive integers $a > b$ satisfying

$$n = \frac{4ab}{a - b}.$$

Let $A$ and $B$ be positive integers. Consider a sequence of positive integers $(x_{n})_{n\geq 1}$ such that

$$x_{n+1} = A \cdot \gcd(x_{n}, x_{n-1}) + B \quad \text{for every } n \geq 2.$$

Prove that the sequence attains only finitely many different values.

Remark. We denote by $\gcd(a, b)$ the greatest common divisor of positive integers $a$ and $b$.

Let $\mathbb{R}$ be the set of real numbers. Determine all functions $f\colon \mathbb{R}\to \mathbb{R}$ such that

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

holds for all $x, y \in \mathbb{R}$.

Let $n$ be a positive integer. Anna and Beatrice play a game with a deck of $n$ cards labelled with the numbers $1, 2, \ldots, n$. Initially, the deck is shuffled. The players take turns, starting with Anna. At each turn, if $k$ denotes the number written on the topmost card, then the player first looks at all the cards and then rearranges the $k$ topmost cards. If, after rearranging, the topmost card shows the number $k$ again, then the player has lost and the game ends. Otherwise, the turn of the other player begins. Determine, depending on the initial shuffle, if either player has a winning strategy, and if so, who does.

Let $ABCD$ be a parallelogram with $\angle DAB < 90^{\circ}$. Let $E \neq B$ be the point on the line $BC$ such that $AE = AB$ and let $F \neq D$ be the point on the line $CD$ such that $AF = AD$. The circumcircle of the triangle $CEF$ intersects the line $AE$ again in $P$ and the line $AF$ again in $Q$. Let $X$ be the reflection of $P$ over the line $DE$ and $Y$ the reflection of $Q$ over the line $BF$. Prove that $A, X$ and $Y$ lie on the same line.

Initially, two positive integers $a$ and $b$ with $a \neq b$ are written on a blackboard. At each step, Andrea picks two numbers $x$ and $y$ on the blackboard with $x \neq y$ and writes the number

$$\gcd(x, y) + \operatorname{lcm}(x, y)$$

on the blackboard as well. Let $n$ be a positive integer. Prove that, regardless of the values of $a$ and $b$, Andrea can perform a finite number of steps such that a multiple of $n$ appears on the blackboard.

Remark. If $x$ and $y$ are two positive integers, then $\gcd(x, y)$ denotes their greatest common divisor and $\operatorname{lcm}(x, y)$ their least common multiple.

Given a pair $(a_0, b_0)$ of real numbers, we define two sequences $a_0, a_1, a_2, \ldots$ and $b_0, b_1, b_2, \ldots$ of real numbers by $$a_{n+1} = a_n + b_n \quad \text{and} \quad b_{n+1} = a_n \cdot b_n$$ for all $n = 0, 1, 2, \ldots$. Find all pairs $(a_0, b_0)$ of real numbers such that $a_{2022} = a_0$ and $b_{2022} = b_0$.

Let $k$ be a positive integer and $a_1, a_2, \ldots, a_k$ be nonnegative real numbers. Initially, there is a sequence of $n \geq k$ zeros written on a blackboard. At each step, Nicole chooses $k$ consecutive numbers written on the blackboard and increases the first number by $a_1$, the second one by $a_2$, and so on, until she increases the $k$-th one by $a_k$. After a positive number of steps, Nicole managed to make all the numbers on the blackboard equal. Prove that all the nonzero numbers among $a_1, a_2, \ldots, a_k$ are equal.

Let $n$ be a positive integer. There are $n$ purple and $n$ white cows queuing in a line in some order. Tim wishes to sort the cows by colour, such that all purple cows are at the front of the line. At each step, he is only allowed to swap two adjacent groups of equally many consecutive cows. What is the minimal number of steps Tim needs to be able to fulfill his wish, regardless of the initial alignment of the cows?

Example. For instance, Tim can perform the following three swaps: $$W\underline{PW}\overline{PP}W \longrightarrow \underline{W}\overline{P}PPWW \longrightarrow P\underline{WP}\overline{PW}W \longrightarrow PPWWPW.$$

Let $n$ be a positive integer. We are given a $2n \times 2n$ table. Each cell is coloured with one of $2n^2$ colours such that each colour is used exactly twice. Jana stands in one of the cells. There is a chocolate bar lying in one of the other cells. Jana wishes to reach the cell with the chocolate bar. At each step, she can only move in one of the following two ways. Either she walks to an adjacent cell or she teleports to the other cell with the same colour as her current cell. (Jana can move to an adjacent cell of the same colour by either walking or teleporting.) Determine whether Jana can fulfill her wish, regardless of the initial configuration, if she has to alternate between the two ways of moving and has to start with a teleportation.

Remark. Two cells are adjacent if they share a common edge.

Let $\Omega$ be the circumcircle of a triangle $ABC$ with $\angle CAB = 90^{\circ}$. The medians through $B$ and $C$ meet $\Omega$ again at $D$ and $E$, respectively. The tangent to $\Omega$ at $D$ intersects the line $AC$ at $X$ and the tangent to $\Omega$ at $E$ intersects the line $AB$ at $Y$. Prove that the line $XY$ is tangent to $\Omega$.

Let $ABCD$ be a convex quadrilateral such that $AC = BD$ and the sides $AB$ and $CD$ are not parallel. Let $P$ be the intersection point of the diagonals $AC$ and $BD$. Points $E$ and $F$ lie, respectively, on segments $BP$ and $AP$ such that $PC = PE$ and $PD = PF$. Prove that the circumcircle of the triangle determined by the lines $AB$, $CD$ and $EF$ is tangent to the circumcircle of the triangle $ABP$.

Let $\mathbb{N}$ denote the set of positive integers. Determine all functions $f\colon \mathbb{N}\to \mathbb{N}$ such that $f(1)\leq f(2)\leq f(3)\leq \ldots$ and the numbers $f(n) + n + 1$ and $f(f(n)) - f(n)$ are both perfect squares for every positive integer $n$.

We call a positive integer cheesy if we can obtain the average of the digits in its decimal representation by putting a decimal separator after the leftmost digit. Prove that there are only finitely many cheesy numbers.

Example. For instance, 2250 is cheesy, as the average of the digits is 2.250.

Determine all real numbers $A$ such that every sequence of non-zero real numbers $x_1, x_2, \ldots$ satisfying

$$x_{n+1} = A - \frac{1}{x_n}$$

for every integer $n \geqslant 1$, has only finitely many negative terms.

Let $m$ and $n$ be positive integers. Some squares of an $m \times n$ board are coloured red. A sequence $a_1, a_2, \ldots, a_{2r}$ of $2r \geqslant 4$ pairwise distinct red squares is called a bishop circuit if for every $k \in \{1, \ldots, 2r\}$, the squares $a_k$ and $a_{k+1}$ lie on a diagonal, but the squares $a_k$ and $a_{k+2}$ do not lie on a diagonal (here $a_{2r+1} = a_1$ and $a_{2r+2} = a_2$).

In terms of $m$ and $n$, determine the maximum possible number of red squares on an $m \times n$ board without a bishop circuit.

(Remark. Two squares lie on a diagonal if the line passing through their centres intersects the sides of the board at an angle of $45°$.)