BALTIC-WAY 2004

Given a sequence $a_{1}, a_{2}, a_{3}, \ldots$ of non-negative real numbers satisfying the conditions

(1) $a_{n}+a_{2 n} \geq 3 n$

(2) $a_{n+1}+n \leq 2 \sqrt{a_{n} \cdot(n+1)}$

for all indices $n=1,2 \ldots$

(a) Prove that the inequality $a_{n} \geq n$ holds for every $n \in \mathbb{N}$.

(b) Give an example of such a sequence.

Let $P(x)$ be a polynomial with non-negative coefficients. Prove that if $P\left(\frac{1}{x}\right) P(x) \geq 1$ for $x=1$, then the same inequality holds for each positive $x$.

Let $p, q, r$ be positive real numbers and $n \in \mathbb{N}$. Show that if $p q r=1$, then

$$\frac{1}{p^{n}+q^{n}+1}+\frac{1}{q^{n}+r^{n}+1}+\frac{1}{r^{n}+p^{n}+1} \leq 1$$

Let $x_{1}, x_{2}, \ldots, x_{n}$ be real numbers with arithmetic mean $X$. Prove that there is a positive integer $K$ such that the arithmetic mean of each of the lists $\left\{x_{1}, x_{2}, \ldots, x_{K}\right\},\left\{x_{2}, x_{3}, \ldots, x_{K}\right\}$, $\ldots,\left\{x_{K-1}, x_{K}\right\},\left\{x_{K}\right\}$ is not greater than $X$.

Determine the range of the function $f$ defined for integers $k$ by

$$f(k)=(k)_{3}+(2 k)_{5}+(3 k)_{7}-6 k$$

where $(k)_{2 n+1}$ denotes the multiple of $2 n+1$ closest to $k$.

A positive integer is written on each of the six faces of a cube. For each vertex of the cube we compute the product of the numbers on the three adjacent faces. The sum of these products is 1001. What is the sum of the six numbers on the faces?

Find all sets $X$ consisting of at least two positive integers such that for every pair $m, n \in X$, where $n>m$, there exists $k \in X$ such that $n=m k^{2}$.

Let $f$ be a non-constant polynomial with integer coefficients. Prove that there is an integer $n$ such that $f(n)$ has at least 2004 distinct prime factors.

$A$ set $S$ of $n-1$ natural numbers is given ( $n \geq 3$ ). There exists at least two elements in this set whose difference is not divisible by $n$. Prove that it is possible to choose a non-empty subset of $S$ so that the sum of its elements is divisible by $n$.

Is there an infinite sequence of prime numbers $p_{1}, p_{2}, \ldots$ such that $\left|p_{n+1}-2 p_{n}\right|=1$ for each $n \in \mathbb{N}$ ?

An $m \times n$ table is given, in each cell of which a number +1 or -1 is written. It is known that initially exactly one -1 is in the table, all the other numbers being +1 . During a move, it is allowed to choose any cell containing -1 , replace this -1 by 0 , and simultaneously multiply all the numbers in the neighboring cells by -1 (we say that two cells are neighboring if they have a common side). Find all $(m, n)$ for which using such moves one can obtain the table containing zeroes only, regardless of the cell in which the initial -1 stands.

There are $2 n$ different numbers in a row. By one move we can interchange any two numbers or interchange any three numbers cyclically (choose $a, b, c$ and place a instead of $b, b$ instead of $c$ and $c$ instead of $a$ ). What is the minimal number of moves that is always sufficient to arrange the numbers in increasing order?

The 25 member states of the European Union set up a committee with the following rules: (1) the committee should meet daily; (2) at each meeting, at least one member state should be represented; (3) at any two different meetings, a different set of member states should be represented; and (4) at the $n$ 'th meeting, for every $k<n$, the set of states represented should include at least one state that was represented at the k'th meeting. For how many days can the committee have its meetings?

We say that a pile is a set of four or more nuts. Two persons play the following game. They start with one pile of $n \geq 4$ nuts. During a move a player takes one of the piles that they have and split it into two non-empty subsets (these sets are not necessarily piles, they can contain an arbitrary number of nuts). If the player cannot move, he loses. For which values of $n$ does the first player have a winning strategy?

A circle is divided into 13 segments, numbered consecutively from 1 to 13. Five fleas called $A, B, C, D$ and $E$ are sitting in the segments 1,2,3,4 and 5. A flea is allowed to jump to an empty segment five positions away in either direction around the circle. Only one flea jumps at the same time, and two fleas cannot be in the same segment. After some jumps, the fleas are back in the segments 1,2,3,4,5, but possibly in some other order than they started. Which orders are possible?

Through a point $P$ exterior to a given circle pass a secant and a tangent to the circle. The secant intersects the circle at $A$ and $B$, and the tangent touches the circle at $C$ on the same side of the diameter thorugh $P$ as $A$ and $B$. The projection of $C$ on the diameter is $Q$. Prove that $Q C$ bisects $\angle A Q B$.

Consider a rectangle with side lengths 3 and 4 , and pick an arbitrary inner point on each side. Let $x, y, z$ and $u$ denote the side lengths of the quadrilateral spanned by these points. Prove that $25 \leq x^{2}+y^{2}+z^{2}+u^{2} \leq 50$.

A ray emanating from the vertex $A$ of the triangle $A B C$ intersects the side $B C$ at $X$ and the circumcircle of $A B C$ at $Y$. Prove that $\frac{1}{A X}+\frac{1}{X Y} \geq \frac{4}{B C}$.

$D$ is the midpoint of the side $B C$ of the given triangle $A B C . M$ is a point on the side $B C$ such that $\angle B A M=\angle D A C$. $L$ is the second intersection point of the circumcircle of the triangle $C A M$ with the side $A B . K$ is the second intersection point of the circumcircle of the triangle $B A M$ with the side $A C$. Prove that $K L \| B C$.

Three circular arcs $w_{1}, w_{2}, w_{3}$ with common endpoints $A$ and $B$ are on the same side of the line $A B ; w_{2}$ lies between $w_{1}$ and $w_{3}$. Two rays emanating from $B$ intersect these arcs at $M_{1}, M_{2}, M_{3}$ and $K_{1}, K_{2}, K_{3}$, respectively. Prove that $\frac{M_{1} M_{2}}{M_{2} M_{3}}=\frac{K_{1} K_{2}}{K_{2} K_{3}}$.