Middle European Mathematical Olympiad 2025

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