MathNet 2019-part-03 — 184 problems (EN–VI)

Find all functions $f: \mathbb{R} \mapsto \mathbb{R}$ such that, for all real numbers $x$ and $y$,
$$
f\left(x^{2}+x+f(y)\right)=y+f(x)+f(x)^{2}
$$

Let $p$ be a prime number.

Prove that there exists a prime number $q$ such that $n^{p} \not\equiv p \pmod{q}$ for every $n \in \mathbb{Z}$.

Let $a$ and $b$ be two real numbers such that $a b \geqslant a^{3}+b^{3}$.
Prove that $a+b \leqslant 1$.

A colouring of $\mathbb{Q}$ consists of colouring every rational number either red or blue. A colouring of $\mathbb{Q}$ is called harmonious if, for all rationals $x$ and $y$ of the same colour, the rational $x+y$ also has that same colour.

Find all colourings of $\mathbb{Q}$ that are harmonious.

In a tournament with $n$ players, numbered from 1 to $n$, each pair of players meets exactly once. Each match ends with the victory of one of the two players and the defeat of the other. Let $v_{k}$ be the number of wins of player $k$ during the tournament, and $d_{k}$ his number of losses.

Prove that $\sum_{k=1}^{n} v_{k}^{2}=\sum_{k=1}^{n} d_{k}^{2}$.

Let $ABC$ be a triangle all of whose angles are acute, with $AB \neq AC$. Let $\Gamma$ be the circumcircle of $ABC$, and $D$ the midpoint of the arc $\widehat{BC}$ not containing $A$. Let $E$ and $F$ be points on the segments $[AB]$ and $[AC]$ respectively, such that $AE = AF$. Let $P$ be the intersection point, other than $A$, of $\Gamma$ and the circumcircle of $AEF$.
Let $G$ and $H$ be the intersection points, other than $P$, of $\Gamma$ with the lines $(PE)$ and $(PF)$ respectively. Finally, let $J$ be the intersection point of the lines $(AB)$ and $(DG)$, and let $K$ be the intersection point of the lines $(AC)$ and $(DH)$.
Prove that the midpoint of the segment $[BC]$ lies on the line $(JK)$.

Each square of an $8 \times 8$ board may be coloured white or black, in such a way that every rectangle of size $2 \times 3$ or $3 \times 2$ contains two black squares sharing a side. Determine the minimal number of black squares there can be on the board.

Let $P_{1}, P_{2}, \ldots, P_{2019}$ be nonconstant polynomials with real coefficients such that
$$
P_{1}\left(P_{2}(x)\right)=P_{2}\left(P_{3}(x)\right)=\ldots=P_{2019}\left(P_{1}(x)\right)
$$
for every real number $x$. Prove that $P_{1}=P_{2}=\ldots=P_{2019}$.

Let $\mathbb{Q}^{+}$ denote the set of all positive rational numbers. Determine all functions $f: \mathbb{Q}^{+} \rightarrow \mathbb{Q}^{+}$ with the property
$$
f\left(x^{2} f(y)^{2}\right) = f\left(x^{2}\right) f(y) \tag{*}
$$
for all $x, y \in \mathbb{Q}^{+}$.

Find all pairs $(a, b)$ of positive integers for which there exists a positive integer $n$ such that the numbers of divisors of $n a$ and of $n b$ are equal.

Decide whether there exists a set $M$ of positive integers with the following property: for every positive rational number $r\lt1$ there exists exactly one finite subset $S$ of $M$ such that $\sum_{s \in S} 1 / s = r$, that is, the sum of the reciprocals of all elements of $S$ equals $r$.

Given a positive integer $n$ and a game board consisting of $n+1$ square fields arranged in a row, numbered from left to right from $0$ to $n$. At the start of the game there are $n$ stones on field no. $0$ and the other fields are empty.

A patient player now chooses, for each move, a field with $k \neq 0$ stones and moves one of them at most $k$ fields to the right. The stone must stay on the board. His goal is to bring all $n$ stones to field no. $n$ by a sequence of such moves.

Prove that the player cannot achieve this goal with fewer than $\left\lceil\frac{n}{1}\right\rceil+\left\lceil\frac{n}{2}\right\rceil+\left\lceil\frac{n}{3}\right\rceil+\ldots+\left\lceil\frac{n}{n}\right\rceil$ moves. (Here $\lceil x\rceil$ denotes the smallest integer that is not less than $x$.)

Consider a triangle $ABC$ and a point $P$ in its interior. Let the reflections of $P$ in the sides $\overline{BC}$, $\overline{CA}$ and $\overline{AB}$ be denoted by $A_1$, $B_1$ and $C_1$. Further, let $\Omega$ be the circumcircle of triangle $A_1B_1C_1$, and finally let $A_2$, $B_2$ and $C_2$ be the second intersection points of the lines $A_1P$, $B_1P$ and $C_1P$ with $\Omega$. Prove that the three lines $AA_2$, $BB_2$ and $CC_2$ meet at a point on $\Omega$.

The real numbers $r_{1}, r_{2}, \ldots, r_{2019}$ satisfy the conditions $r_{1}+r_{2}+\ldots+r_{2019}=0$ and $r_{1}^{2}+r_{2}^{2}+\ldots+r_{2019}^{2}=1$. Let $a=\min \left(r_{1}, r_{2}, \ldots, r_{2019}\right)$ and $b=\max \left(r_{1}, r_{2}, \ldots, r_{2019}\right)$. Prove: $a b \leq \frac{-1}{2019}$.

Let a triangle $ABC$ be given. A circle $k$ passes through $A$, meets the sides $\overline{AB}$ and $\overline{AC}$ again at the points $D$ and $E$ respectively, and meets the side $\overline{BC}$ at the points $F$ and $G$, where $F$ lies between $B$ and $G$. The tangent at $F$ to the circle through $B$, $D$ and $F$ and the tangent at $G$ to the circle through $C$, $E$ and $G$ meet at a point $T$. We assume that $A \neq T$. Prove that the lines $AT$ and $BC$ are parallel.

Let $m$ and $n$ be two positive integers. Prove that the integer $m^{2} + \left\lceil \frac{4 m^{2}}{n} \right\rceil$ is not a perfect square.

(Here $\lceil x \rceil$ denotes the smallest integer that is not less than $x$.)

A pirate wants to divide a treasure consisting of 1000 gold coins, each weighing at least 1 g and together weighing exactly 2 kg, into two parts each of whose masses differs from 1 kg by at most 1 g. Prove that this is possible.

Let a triangle $A B C$ with circumcircle $\Omega$ be given, together with points $A_{1}, B_{1}$ and $C_{1}$ on the sides $\overline{B C}, \overline{C A}$ and $\overline{A B}$ such that the three lines $A A_{1}, B B_{1}$ and $C C_{1}$ have a point $P$ in common.
Prove that at most two of the three reflections of $P$ in the points $A_{1}$, $B_{1}$ and $C_{1}$ (point reflections) lie outside $\Omega$.

Let $\varepsilon\gt0$ be given. Show that there exist integers $a, b$ and $c$, not all $0$, such that the inequality $|a \sqrt{2}+b \sqrt{3}+c \sqrt{5}|\lt\varepsilon$ holds.

Prove further that in every triple $(a, b, c) \neq(0,0,0)$ of integers for which this inequality holds, at least one of the absolute values $|a|,|b|,|c|$ is greater than $\varepsilon^{-1 / 3} / \sqrt{30}$.

A grid consists of all points of the form $(m, n)$ where $m$ and $n$ are integers with $|m| \le 2019$, $|n| \le 2019$ and $|m| + |n| \lt 4038$. We call the points $(m, n)$ of the grid with either $|m| = 2019$ or $|n| = 2019$ the *boundary points*. The four lines $x = \pm 2019$ and $y = \pm 2019$ are called *boundary lines*. Two points in the grid are called *neighbours* if the distance between them is equal to 1.
Anna and Bob play a game on this grid.
Anna starts with a token at the point $(0, 0)$. They take turns, with Bob playing first.
1) On each of his turns, Bob deletes at most two boundary points on each boundary line.
2) On each of her turns, Anna makes exactly three *steps*, where a *step* consists of moving her token from its current point to any neighbouring point which has not been deleted.
As soon as Anna places her token on some boundary point which has not been deleted, the game is over and Anna wins.

Does Anna have a winning strategy?