BALTIC-WAY 2013

Let $n$ be a positive integer. Assume that $n$ numbers are to be chosen from the table

$$\begin{array}{cccc} 0 & 1 & \cdots & n-1 \\ n & n+1 & \cdots & 2 n-1 \\ \vdots & \vdots & \ddots & \vdots \\ (n-1) n & (n-1) n+1 & \cdots & n^{2}-1 \end{array}$$

with no two of them from the same row or the same column. Find the maximal value of the product of these $n$ numbers.

Let $k$ and $n$ be positive integers and let $x_{1}, x_{2}, \ldots, x_{k}, y_{1}, y_{2}, \ldots, y_{n}$ be distinct integers. A polynomial $P$ with integer coefficients satisfies

$$P\left(x_{1}\right)=P\left(x_{2}\right)=\ldots=P\left(x_{k}\right)=54$$

and

$$P\left(y_{1}\right)=P\left(y_{2}\right)=\ldots=P\left(y_{n}\right)=2013 .$$

Determine the maximal value of $k n$.

Let $\mathbb{R}$ denote the set of real numbers. Find all functions $f: \mathbb{R} \rightarrow \mathbb{R}$ such that

$$f(x f(y)+y)+f(-f(x))=f(y f(x)-y)+y \text { for all } x, y \in \mathbb{R}$$

Prove that the following inequality holds for all positive real numbers $x, y, z$ :

$$\frac{x^{3}}{y^{2}+z^{2}}+\frac{y^{3}}{z^{2}+x^{2}}+\frac{z^{3}}{x^{2}+y^{2}} \geq \frac{x+y+z}{2}$$

Numbers 0 and 2013 are written at two opposite vertices of a cube. Some real numbers are to be written at the remaining 6 vertices of the cube. On each edge of the cube the difference between the numbers at its endpoints is written. When is the sum of squares of the numbers written on the edges minimal?

Santa Claus has at least $n$ gifts for $n$ children. For $i \in\{1,2, \ldots, n\}$, the $i$-th child considers $x_{i}>0$ of these items to be desirable. Assume that

$$\frac{1}{x_{1}}+\ldots+\frac{1}{x_{n}} \leq 1$$

Prove that Santa Claus can give each child a gift that this child likes.

A positive integer is written on a blackboard. Players $A$ and $B$ play the following game: in each move one has to choose a divisor $m$ of the number $n$ written on the blackboard for which $1<m<n$ and replace $n$ with $n-m$. Player $A$ makes the first move, players move alternately. The player who can't make a move loses the game. For which starting numbers is there a winning strategy for player $B$ ?

There are $n$ rooms in a sauna, each has unlimited capacity. No room may be attended by a female and a male simultaneously. Moreover, males want to share a room only with males that they don't know and females want to share a room only with females that they know. Find the biggest number $k$ such that any $k$ couples can visit the sauna at the same time, given that two males know each other if and only if their wives know each other.

In a country there are 2014 airports, no three of them lying on a line. Two airports are connected by a direct flight if and only if the line passing through them divides the country in two parts, each with 1006 airports in it. Show that there are no two airports such that one can travel from the first to the second, visiting each of the 2014 airports exactly once.

A white equilateral triangle is split into $n^{2}$ equal smaller triangles by lines that are parallel to the sides of the triangle. Denote a line of triangles to be all triangles that are placed between two adjacent parallel lines that form the grid. In particular, a triangle in a corner is also considered to be a line of triangles. We are to paint all triangles black by a sequence of operations of the following kind: choose a line of triangles that contains at least one white triangle and paint this line black (a possible situation with $n=6$ after four operations is shown in Figure 1; arrows show possible next operations in this situation). Find the smallest and largest possible number of operations.

In an acute triangle $A B C$ with $A C>A B$, let $D$ be the projection of $A$ on $B C$, and let $E$ and $F$ be the projections of $D$ on $A B$ and $A C$, respectively. Let $G$ be the intersection point of the lines $A D$ and $E F$. Let $H$ be the second intersection point of the line $A D$ and the circumcircle of triangle $A B C$. Prove that

$$A G \cdot A H=A D^{2}$$

A trapezoid $A B C D$ with bases $A B$ and $C D$ is such that the circumcircle of the triangle $B C D$ intersects the line $A D$ in a point $E$, distinct from $A$ and $D$. Prove that the circumcircle of the triangle $A B E$ is tangent to the line $B C$.

All faces of a tetrahedron are right-angled triangles. It is known that three of its edges have the same length $s$. Find the volume of the tetrahedron.

Circles $\alpha$ and $\beta$ of the same radius intersect in two points, one of which is $P$. Denote by $A$ and $B$, respectively, the points diametrically opposite to $P$ on each of $\alpha$ and $\beta$. A third circle of the same radius passes through $P$ and intersects $\alpha$ and $\beta$ in the points $X$ and $Y$, respectively. Show that the line $X Y$ is parallel to the line $A B$.

Four circles in a plane have a common center. Their radii form a strictly increasing arithmetic progression. Prove that there is no square with each vertex lying on a different circle.

We call a positive integer $n$ delightful if there exists an integer $k, 1<k<n$, such that

$$1+2+\cdots+(k-1)=(k+1)+(k+2)+\cdots+n$$

Does there exist a delightful number $N$ satisfying the inequalities

$$2013^{2013}<\frac{N}{2013^{2013}}<2013^{2013}+4 ?$$

Let $c$ and $n>c$ be positive integers. Mary's teacher writes $n$ positive integers on a blackboard. Is it true that for all $n$ and $c$ Mary can always label the numbers written by the teacher by $a_{1}, \ldots, a_{n}$ in such an order that the cyclic product $\left(a_{1}-a_{2}\right) \cdot\left(a_{2}-a_{3}\right) \cdot \ldots \cdot\left(a_{n-1}-a_{n}\right) \cdot\left(a_{n}-a_{1}\right)$ would be congruent to either 0 or $c$ modulo $n$ ?

Find all pairs $(x, y)$ of integers such that $y^{3}-1=x^{4}+x^{2}$.

Let $a_{0}$ be a positive integer and $a_{n}=5 a_{n-1}+4$, for all $n \geq 1$. Can $a_{0}$ be chosen so that $a_{54}$ is a multiple of 2013?

Find all polynomials $f$ with non-negative integer coefficients such that for all primes $p$ and positive integers $n$ there exist a prime $q$ and a positive integer $m$ such that $f\left(p^{n}\right)=q^{m}$.