BALTIC-WAY 2005

Let $a_{0}$ be a positive integer. Define the sequence $a_{n}, n \geq 0$, as follows: If

$$a_{n}=\sum_{i=0}^{j} c_{i} 10^{i}$$

where $c_{i}$ are integers with $0 \leq c_{i} \leq 9$, then

$$a_{n+1}=c_{0}^{2005}+c_{1}^{2005}+\cdots+c_{j}^{2005} .$$

Is it possible to choose $a_{0}$ so that all the terms in the sequence are distinct?

Let $\alpha, \beta$ and $\gamma$ be three angles with $0 \leq \alpha, \beta, \gamma<90^{\circ}$ and $\sin \alpha+\sin \beta+\sin \gamma=1$. Show that

$$\tan ^{2} \alpha+\tan ^{2} \beta+\tan ^{2} \gamma \geq \frac{3}{8}$$

Consider the sequence $a_{k}$ defined by $a_{1}=1, a_{2}=\frac{1}{2}$,

$$a_{k+2}=a_{k}+\frac{1}{2} a_{k+1}+\frac{1}{4 a_{k} a_{k+1}} \text { for } k \geq 1$$

Prove that

$$\frac{1}{a_{1} a_{3}}+\frac{1}{a_{2} a_{4}}+\frac{1}{a_{3} a_{5}}+\cdots+\frac{1}{a_{98} a_{100}}<4$$

Find three different polynomials $P(x)$ with real coefficients such that $P\left(x^{2}+1\right)=P(x)^{2}+1$ for all real $x$.

Let $a, b, c$ be positive real numbers with $a b c=1$. Prove that

$$\frac{a}{a^{2}+2}+\frac{b}{b^{2}+2}+\frac{c}{c^{2}+2} \leq 1$$

Let $K$ and $N$ be positive integers with $1 \leq K \leq N$. A deck of $N$ different playing cards is shuffled by repeating the operation of reversing the order of the $K$ topmost cards and moving these to the bottom of the deck. Prove that the deck will be back in its initial order after a number of operations not greater than $4 \cdot N^{2} / K^{2}$.

A rectangular array has $n$ rows and six columns, where $n>2$. In each cell there is written either 0 or 1 . All rows in the array are different from each other. For each pair of rows $\left(x_{1}, x_{2}, \ldots, x_{6}\right)$ and $\left(y_{1}, y_{2}, \ldots, y_{6}\right)$, the row $\left(x_{1} y_{1}, x_{2} y_{2}, \ldots, x_{6} y_{6}\right)$ can also be found in the array. Prove that there is a column in which at least half of the entries are zeroes.

Consider a grid of $25 \times 25$ unit squares. Draw with a red pen contours of squares of any size on the grid. What is the minimal number of squares we must draw in order to colour all the lines of the grid?

A rectangle is divided into $200 \times 3$ unit squares. Prove that the number of ways of splitting this rectangle into rectangles of size $1 \times 2$ is divisible by 3 .

Let $m=30030=2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13$ and let $M$ be the set of its positive divisors which have exactly two prime factors. Determine the minimal integer $n$ with the following property: for any choice of numbers from $M$, there exist three numbers $a, b, c$ among them satisfying $a \cdot b \cdot c=m$.

Let the points $D$ and $E$ lie on the sides $B C$ and $A C$, respectively, of the triangle $A B C$, satisfying $B D=A E$. The line joining the circumcentres of the triangles $A D C$ and $B E C$ meets the lines $A C$ and $B C$ at $K$ and $L$, respectively. Prove that $K C=L C$.

Let $A B C D$ be a convex quadrilateral such that $B C=A D$. Let $M$ and $N$ be the midpoints of $A B$ and $C D$, respectively. The lines $A D$ and $B C$ meet the line $M N$ at $P$ and $Q$, respectively. Prove that $C Q=D P$.

What is the smallest number of circles of radius $\sqrt{2}$ that are needed to cover a rectangle

(a) of size $6 \times 3$ ?

(b) of size $5 \times 3$ ?

Let the medians of the triangle $A B C$ meet at $M$. Let $D$ and $E$ be different points on the line $B C$ such that $D C=C E=A B$, and let $P$ and $Q$ be points on the segments $B D$ and $B E$, respectively, such that $2 B P=P D$ and $2 B Q=Q E$. Determine $\angle P M Q$.

Let the lines $e$ and $f$ be perpendicular and intersect each other at $O$. Let $A$ and $B$ lie on $e$ and $C$ and $D$ lie on $f$, such that all the five points $A, B, C, D$ and $O$ are distinct. Let the lines $b$ and $d$ pass through $B$ and $D$ respectively, perpendicularly to $A C$; let the lines $a$ and $c$ pass through $A$ and $C$ respectively, perpendicularly to $B D$. Let $a$ and $b$ intersect $a t X$ and $c$ and $d$ intersect at $Y$. Prove that $X Y$ passes through $O$.

Let $p$ be a prime number and let $n$ be a positive integer. Let $q$ be a positive divisor of $(n+1)^{p}-n^{p}$. Show that $q-1$ is divisible by $p$.

A sequence $\left(x_{n}\right), n \geq 0$, is defined as follows: $x_{0}=a, x_{1}=2$ and $x_{n}=2 x_{n-1} x_{n-2}-$ $x_{n-1}-x_{n-2}+1$ for $n>1$. Find all integers a such that $2 x_{3 n}-1$ is a perfect square for all $n \geq 1$.

Let $x$ and $y$ be positive integers and assume that $z=4 x y /(x+y)$ is an odd integer. Prove that at least one divisor of $z$ can be expressed in the form $4 n-1$ where $n$ is a positive integer.

Is it possible to find 2005 different positive square numbers such that their sum is also a square number?

Find all positive integers $n=p_{1} p_{2} \cdots p_{k}$ which divide $\left(p_{1}+1\right)\left(p_{2}+1\right) \cdots\left(p_{k}+1\right)$, where $p_{1} p_{2} \cdots p_{k}$ is the factorization of $n$ into prime factors (not necessarily distinct).