BALTIC-WAY 2018

A finite collection of positive real numbers (not necessarily distinct) is balanced if each number is less than the sum of the others. Find all $m \geq 3$ such that every balanced finite collection of $m$ numbers can be split into three parts with the property that the sum of the numbers in each part is less than the sum of the numbers in the two other parts.

A $100 \times 100$ table is given. For each $k, 1 \leq k \leq 100$, the $k$-th row of the table contains the numbers $1,2, \ldots, k$ in increasing order (from left to right) but not necessarily in consecutive cells; the remaining $100-k$ cells are filled with zeroes. Prove that there exist two columns such that the sum of the numbers in one of the columns is at least 19 times as large as the sum of the numbers in the other column.

Let $a, b, c, d$ be positive real numbers such that $a b c d=1$. Prove the inequality

$$\frac{1}{\sqrt{a+2 b+3 c+10}}+\frac{1}{\sqrt{b+2 c+3 d+10}}+\frac{1}{\sqrt{c+2 d+3 a+10}}+\frac{1}{\sqrt{d+2 a+3 b+10}} \leq 1 .$$

Find all functions $f:[0,+\infty) \rightarrow[0,+\infty)$, such that for any positive integer $n$ and for any non-negative real numbers $x_{1}, \ldots, x_{n}$

$$f\left(x_{1}^{2}+\cdots+x_{n}^{2}\right)=f\left(x_{1}\right)^{2}+\cdots+f\left(x_{n}\right)^{2} .$$

A polynomial $f(x)$ with real coefficients is called generating, if for each polynomial $\varphi(x)$ with real coefficients there exist a positive integer $k$ and polynomials $g_{1}(x), \ldots, g_{k}(x)$ with real coefficients such that

$$\varphi(x)=f\left(g_{1}(x)\right)+\cdots+f\left(g_{k}(x)\right) .$$

Find all generating polynomials.

Let $n$ be a positive integer. Elfie the Elf travels in $\mathbb{R}^{3}$. She starts at the origin: $(0,0,0)$. In each turn she can teleport to any point with integer coordinates which lies at distance exactly $\sqrt{n}$ from her current location. However, teleportation is a complicated procedure. Elfie starts off normal but she turns strange with her first teleportation. Next time she teleports she becomes normal again, then strange again... etc.

For which $n$ can Elfie travel to any given point with integer coordinates and be normal when she gets there?

On a $16 \times 16$ torus as shown all 512 edges are colored red or blue. A coloring is good if every vertex is an endpoint of an even number of red edges. A move consists of switching the color of each of the 4 edges of an arbitrary cell. What is the largest number of good colorings such that none of them can be converted to another by a sequence of moves?

A graph has $N$ vertices. An invisible hare sits in one of the vertices. A group of hunters tries to kill the hare. In each move all of them shoot simultaneously: each hunter shoots at a single vertex, they choose the target vertices cooperatively. If the hare was in one of the target vertices during a shoot, the hunt is finished. Otherwise the hare can stay in its vertex or jump to one of the neighboring vertices.

The hunters know an algorithm that allows them to kill the hare in at most $N$ ! moves. Prove that then there exists an algorithm that allows them to kill the hare in at most $2^{N}$ moves.

Olga and Sasha play a game on an infinite hexagonal grid. They take turns in placing a stone on a free hexagon of their choice. Olga starts the game. Just before the 2018th stone is placed, a new rule comes into play. A stone may now be placed only on those free hexagons having at least two occupied neighbors.

A player loses when she or he either is unable to make a move, or has filled a pattern of the rhomboid shape as shown (rotated in any possible way). Determine which player, if any, possesses a winning strategy.

The integers from 1 to $n$ are written, one on each of $n$ cards. The first player removes one card. Then the second player removes two cards with consecutive integers. After that the first player removes three cards with consecutive integers. Finally, the second player removes four cards with consecutive integers. What is the smallest value of $n$ for which the second player can ensure that he completes both his moves?

The points $A, B, C, D$ lie, in this order, on a circle $\omega$, where $A D$ is a diameter of $\omega$. Furthermore, $A B=B C=a$ and $C D=c$ for some relatively prime integers $a$ and $c$. Show that if the diameter $d$ of $\omega$ is also an integer, then either $d$ or $2 d$ is a perfect square.

The altitudes $B B_{1}$ and $C C_{1}$ of an acute triangle $A B C$ intersect in point $H$. Let $B_{2}$ and $C_{2}$ be points on the segments $B H$ and $C H$, respectively, such that $B B_{2}=B_{1} H$ and $C C_{2}=C_{1} H$. The circumcircle of the triangle $B_{2} H C_{2}$ intersects the circumcircle of the triangle $A B C$ in points $D$ and $E$. Prove that the triangle $D E H$ is right-angled.

The bisector of the angle $A$ of a triangle $A B C$ intersects $B C$ in a point $D$ and intersects the circumcircle of the triangle $A B C$ in a point $E$. Let $K, L, M$ and $N$ be the midpoints of the segments $A B, B D, C D$ and $A C$, respectively. Let $P$ be the circumcenter of the triangle $E K L$, and $Q$ be the circumcenter of the triangle $E M N$. Prove that $\angle P E Q=\angle B A C$.

A quadrilateral $A B C D$ is circumscribed about a circle $\omega$. The intersection point of $\omega$ and the diagonal $A C$, closest to $A$, is $E$. The point $F$ is diametrically opposite to the point $E$ on the circle $\omega$. The tangent to $\omega$ at the point $F$ intersects lines $A B$ and $B C$ in points $A_{1}$ and $C_{1}$, and lines $A D$ and $C D$ in points $A_{2}$ and $C_{2}$, respectively. Prove that $A_{1} C_{1}=A_{2} C_{2}$.

Two circles in the plane do not intersect and do not lie inside each other. We choose diameters $A_{1} B_{1}$ and $A_{2} B_{2}$ of these circles such that the segments $A_{1} A_{2}$ and $B_{1} B_{2}$ intersect. Let $A$ and $B$ be the midpoints of the segments $A_{1} A_{2}$ and $B_{1} B_{2}$, and $C$ be the intersection point of these segments. Prove that the orthocenter of the triangle $A B C$ belongs to a fixed line that does not depend on the choice of the diameters.

Let $p$ be an odd prime. Find all positive integers $n$ for which $\sqrt{n^{2}-n p}$ is a positive integer.

Prove that for any positive integers $p, q$ such that $\sqrt{11}>\frac{p}{q}$, the following inequality holds:

$$\sqrt{11}-\frac{p}{q}>\frac{1}{2 p q}$$

Let $n \geq 3$ be an integer such that $4 n+1$ is a prime number. Prove that $4 n+1$ divides $n^{2 n}-1$.

An infinite set $B$ consisting of positive integers has the following property. For each $a, b \in B$ with $a>b$ the number $\frac{a-b}{(a, b)}$ belongs to $B$. Prove that $B$ contains all positive integers. Here $(a, b)$ is the greatest common divisor of numbers $a$ and $b$.

Find all the triples of positive integers $(a, b, c)$ for which the number

$$\frac{(a+b)^{4}}{c}+\frac{(b+c)^{4}}{a}+\frac{(c+a)^{4}}{b}$$

is an integer and $a+b+c$ is a prime.