2013 Ukraine Team Selection Test

Day 1

1

Let $ABC$ be an isosceles triangle $ABC$ with base $BC$ insribed in a circle. The segment $AD$ is the diameter of the circle, and point $P$ lies on the smaller arc $BD$. Line $DP$ intersects rays $AB$ and $AC$ at points $M$ and $N$, and the lines $BP$ and $CP$ intersects the line $AD$ at points $Q$ and $R$. Prove that the midpoint of the segment $MN$ lies on the circumscribed circle of triangle $PQR$.

2

The teacher reported to Peter an odd integer $m \le 2013$ and gave the guy a homework. Petrick should star the cells in the $2013 \times 2013$ table so to make the condition true: if there is an asterisk in some cell in the table, then or in row or column containing this cell should be no more than $m$ stars (including this one). Thus in each cell of the table the guy can put at most one star. The teacher promised Peter that his assessment would be just the number of stars that the guy will be able to place. What is the greatest number will the stars be able to place in the table Petrick?

3

For a nonnegative integer $n$ define $\operatorname{rad}(n)=1$ if $n=0$ or $n=1$, and $\operatorname{rad}(n)=p_1p_2\cdots p_k$ where $p_1<p_2<\cdots <p_k$ are all prime factors of $n$. Find all polynomials $f(x)$ with nonnegative integer coefficients such that $\operatorname{rad}(f(n))$ divides $\operatorname{rad}(f(n^{\operatorname{rad}(n)}))$ for every nonnegative integer $n$.

Day 2

4

Call admissible a set $A$ of integers that has the following property: If $x,y \in A$ (possibly $x=y$) then $x^2+kxy+y^2 \in A$ for every integer $k$. Determine all pairs $m,n$ of nonzero integers such that the only admissible set containing both $m$ and $n$ is the set of all integers. Proposed by Warut Suksompong, Thailand

5

For positive $x, y$, and $z$ that satisfy the condition $xyz = 1$, prove the inequality $$\sqrt[3]{\frac{x+y}{2z}}+\sqrt[3]{\frac{y+z}{2x}}+\sqrt[3]{\frac{z+x}{2y}}\le \frac{5(x+y+z)+9}{8}$$

6

Six different points $A, B, C, D, E, F$ are marked on the plane, no four of them lie on one circle and no two segments with ends at these points lie on parallel lines. Let $P, Q,R$ be the points of intersection of the perpendicular bisectors to pairs of segments $(AD, BE)$, $(BE, CF)$ ,$(CF, DA)$ respectively, and $P', Q' ,R'$ are points the intersection of the perpendicular bisectors to the pairs of segments $(AE, BD)$, $(BF, CE)$ , $(CA, DF)$ respectively. Show that $P \ne P', Q \ne Q', R \ne R'$, and prove that the lines $PP', QQ'$ and $RR'$ intersect at one point or are parallel.

Day 3

7

$2013$ users have registered on the social network "Graph". Some users are friends, and friendship in "Graph" is mutual. It is known that among network users there are no three, each of whom would be friends. Find the biggest one possible number of pairs of friends in "Graph".

8

Let $ABC$ be a triangle with $AB \neq AC$ and circumcenter $O$. The bisector of $\angle BAC$ intersects $BC$ at $D$. Let $E$ be the reflection of $D$ with respect to the midpoint of $BC$. The lines through $D$ and $E$ perpendicular to $BC$ intersect the lines $AO$ and $AD$ at $X$ and $Y$ respectively. Prove that the quadrilateral $BXCY$ is cyclic.

9

Determine all functions $f:\Bbb{R}\to\Bbb{R}$ such that \[ f^2(x+y)=f^2(x)+2f(xy)+f^2(y), \] for all $x,y\in \Bbb{R}.$

Day 4

10

Let $\mathbb{Z}$ and $\mathbb{Q}$ be the sets of integers and rationals respectively. a) Does there exist a partition of $\mathbb{Z}$ into three non-empty subsets $A,B,C$ such that the sets $A+B, B+C, C+A$ are disjoint? b) Does there exist a partition of $\mathbb{Q}$ into three non-empty subsets $A,B,C$ such that the sets $A+B, B+C, C+A$ are disjoint? Here $X+Y$ denotes the set $\{ x+y : x \in X, y \in Y \}$, for $X,Y \subseteq \mathbb{Z}$ and for $X,Y \subseteq \mathbb{Q}$.

11

Specified natural number $a$. Prove that there are an infinite number of prime numbers $p$ such that for some natural $n$ the number $2^{2^n} + a$ is divisible by $p$.

12

$4026$ points were noted on the plane, not three of which lie on a straight line. The $2013$ points are the vertices of a convex polygon, and the other $2013$ vertices are inside this polygon. It is allowed to paint each point in one of two colors. Coloring will be good if some pairs of dots can be combined segments with the following conditions: $\bullet$ Each segment connects dots of the same color. $\bullet$ No two drawn segments intersect at their inner points. $\bullet$ For an arbitrary pair of dots of the same color, there is a path along the lines from one point to another. Please note that the sides of the convex $2013$ rectangle are not automatically drawn segments, although some (or all) can be drawn as needed. Prove that the total number of good colors does not depend on the specific locations of the points and find that number.