BALTIC-WAY 1998

Let $\mathbb{Z}^{+}$be the set of all positive integers. Find all functions $f: \mathbb{Z}^{+} \rightarrow \mathbb{Z}^{+}$ satisfying the following conditions for all $x, y \in \mathbb{Z}^{+}$:

$$\begin{aligned} f(x, x) & =x, \\ f(x, y) & =f(y, x), \\ (x+y) f(x, y) & =y f(x, x+y) . \end{aligned}$$

A triple of positive integers $(a, b, c)$ is called quasi-Pythagorean if there exists a triangle with lengths of the sides $a, b, c$ and the angle opposite to the side $c$ equal to $120^{\circ}$. Prove that if $(a, b, c)$ is a quasi-Pythagorean triple then $c$ has a prime divisor greater than 5 .

Find all pairs of positive integers $x, y$ which satisfy the equation

$$2 x^{2}+5 y^{2}=11(x y-11) \text {. }$$

Let $P$ be a polynomial with integer coefficients. Suppose that for $n=1,2,3, \ldots, 1998$ the number $P(n)$ is a three-digit positive integer. Prove that the polynomial $P$ has no integer roots.

Let $a$ be an odd digit and $b$ an even digit. Prove that for every positive integer $n$ there exists a positive integer, divisible by $2^{n}$, whose decimal representation contains no digits other than $a$ and $b$.

Let $P$ be a polynomial of degree 6 and let $a, b$ be real numbers such that $0<a<b$. Suppose that $P(a)=P(-a), P(b)=P(-b)$ and $P^{\prime}(0)=0$. Prove that $P(x)=P(-x)$ for all real $x$.

Let $\mathbb{R}$ be the set of all real numbers. Find all functions $f: \mathbb{R} \rightarrow \mathbb{R}$ satisfying for all $x, y \in \mathbb{R}$ the equation

$$f(x)+f(y)=f(f(x) f(y)) .$$

Let $P_{k}(x)=1+x+x^{2}+\cdots+x^{k-1}$. Show that

$$\sum_{k=1}^{n}\left(\begin{array}{l} n \\ k \end{array}\right) P_{k}(x)=2^{n-1} P_{n}\left(\frac{1+x}{2}\right)$$

for every real number $x$ and every positive integer $n$.

Let the numbers $\alpha, \beta$ satisfy $0<\alpha<\beta<\pi / 2$ and let $\gamma$ and $\delta$ be the numbers defined by the conditions:

(i) $0<\gamma<\pi / 2$, and $\tan \gamma$ is the arithmetic mean of $\tan \alpha$ and $\tan \beta$;

(ii) $0<\delta<\pi / 2$, and $\frac{1}{\cos \delta}$ is the arithmetic mean of $\frac{1}{\cos \alpha}$ and $\frac{1}{\cos \beta}$.

Prove that $\gamma<\delta$.

Let $n \geqslant 4$ be an even integer. A regular $n$-gon and a regular $(n-1)$-gon are inscribed into the unit circle. For each vertex of the $n$-gon consider the distance from this vertex to the nearest vertex of the $(n-1)$-gon, measured along the circumference. Let $S$ be the sum of these $n$ distances. Prove that $S$ depends only on $n$, and not on the relative position of the two polygons.

Let $a, b$ and $c$ be the lengths of the sides of a triangle with circumradius $R$. Prove that

$$R \geqslant \frac{a^{2}+b^{2}}{2 \sqrt{2 a^{2}+2 b^{2}-c^{2}}} .$$

When does equality hold?

In a triangle $A B C, \angle B A C=90^{\circ}$. Point $D$ lies on the side $B C$ and satisfies $\angle B D A=2 \angle B A D$. Prove that

$$\frac{1}{|A D|}=\frac{1}{2}\left(\frac{1}{|B D|}+\frac{1}{|C D|}\right)$$

In a convex pentagon $A B C D E$, the sides $A E$ and $B C$ are parallel and $\angle A D E=\angle B D C$. The diagonals $A C$ and $B E$ intersect at $P$. Prove that $\angle E A D=\angle B D P$ and $\angle C B D=\angle A D P$.

Given a triangle $A B C$ with $|A B|<|A C|$. The line passing through $B$ and parallel to $A C$ meets the external bisector of angle $B A C$ at $D$. The line passing through $C$ and parallel to $A B$ meets this bisector at $E$. Point $F$ lies on the side $A C$ and satisfies the equality $|F C|=|A B|$. Prove that $|D F|=|F E|$.

Given an acute triangle $A B C$. Point $D$ is the foot of the perpendicular from $A$ to $B C$. Point $E$ lies on the segment $A D$ and satisfies the equation

$$\frac{|A E|}{|E D|}=\frac{|C D|}{|D B|}$$

Point $F$ is the foot of the perpendicular from $D$ to $B E$. Prove that $\angle A F C=90^{\circ}$.

Is it possible to cover a $13 \times 13$ chessboard with forty-two tiles of size $4 \times 1$ so that only the central square of the chessboard remains uncovered? (It is assumed that each tile covers exactly four squares of the chessboard, and the tiles do not overlap.)

Let $n$ and $k$ be positive integers. There are $n k$ objects (of the same size) and $k$ boxes, each of which can hold $n$ objects. Each object is coloured in one of $k$ different colours. Show that the objects can be packed in the boxes so that each box holds objects of at most two colours.

Determine all positive integers $n$ for which there exists a set $S$ with the following properties:

(i) $S$ consists of $n$ positive integers, all smaller than $2^{n-1}$;

(ii) for any two distinct subsets $A$ and $B$ of $S$, the sum of the elements of $A$ is different from the sum of the elements of $B$.

Consider a ping-pong match between two teams, each consisting of 1000 players. Each player played against each player of the other team exactly once (there are no draws in ping-pong). Prove that there exist ten players, all from the same team, such that every member of the other team has lost his game against at least one of those ten players.

We say that an integer $m$ covers the number 1998 if $1,9,9,8$ appear in this order as digits of $m$. (For instance, 1998 is covered by 215993698 but not by 213326798 .) Let $k(n)$ be the number of positive integers that cover 1998 and have exactly $n$ digits $(n \geqslant 5)$, all different from 0 . What is the remainder of $k(n)$ in division by 8 ?