[Shortlists] International Mathematical Olympiad 2003

Geometry

1. Let $ABCD$ be a cyclic quadrilateral. Let $P$, $Q$, $R$ be the feet of the perpendiculars from $D$ to the lines $BC$, $CA$, $AB$, respectively. Show that $PQ=QR$ if and only if the bisectors of $\angle ABC$ and $\angle ADC$ are concurrent with $AC$.
2. Given three fixed pairwisely distinct points $A$, $B$, $C$ lying on one straight line in this order. Let $G$ be a circle passing through $A$ and $C$ whose center does not lie on the line $AC$. The tangents to $G$ at $A$ and $C$ intersect each other at a point $P$. The segment $PB$ meets the circle $G$ at $Q$. Show that the point of intersection of the angle bisector of the angle $AQC$ with the line $AC$ does not depend on the choice of the circle $G$.
3. Let $ABC$ be a triangle, and $P$ a point in the interior of this triangle. Let $D$, $E$, $F$ be the feet of the perpendiculars from the point $P$ to the lines $BC$, $CA$, $AB$, respectively. Assume that $AP^{2}+PD^{2}$ $=BP^{2}+PE^{2}$ $=CP^{2}+PF^{2}$. Furthermore, let $I_{a}$, $I_{b}$, $I_{c}$ be the excenters of triangle $ABC$. Show that the point $P$ is the circumcenter of triangle $I_{a}I_{b}I_{c}$.
4. Let $\Gamma_1$, $\Gamma_2$, $\Gamma_3$, $\Gamma_4$ be distinct circles such that $\Gamma_1$, $\Gamma_3$ are externally tangent at $P$, and $\Gamma_2$, $\Gamma_4$ are externally tangent at the same point $P$. Suppose that $\Gamma_1$ and $\Gamma_2$; $\Gamma_2$ and $\Gamma_3$; $\Gamma_3$ and $\Gamma_4$; $\Gamma_4$ and $\Gamma_1$ meet at $A$, $B$, $C$, $D$, respectively, and that all these points are different from $P$. Prove that \[ \frac{AB\cdot BC}{AD\cdot DC}=\frac{PB^2}{PD^2}. \]
5. Let $ABC$ be an isosceles triangle with $AC=BC$, whose incentre is $I$. Let $P$ be a point on the circumcircle of the triangle $AIB$ lying inside the triangle $ABC$. The lines through $P$ parallel to $CA$ and $CB$ meet $AB$ at $D$ and $E$, respectively. The line through $P$ parallel to $AB$ meets $CA$ and $CB$ at $F$ and $G$, respectively. Prove that the lines $DF$ and $EG$ intersect on the circumcircle of the triangle $ABC$.
6. Each pair of opposite sides of a convex hexagon has the following property: the distance between their midpoints is equal to $\dfrac{\sqrt{3}}{2}$ times the sum of their lengths. Prove that all the angles of the hexagon are equal.
7. Let $ABC$ be a triangle with semiperimeter $s$ and inradius $r$. The semicircles with diameters $BC$, $CA$, $AB$ are drawn on the outside of the triangle $ABC$. The circle tangent to all of these three semicircles has radius $t$. Prove that \[\frac{s}{2}<t\le\frac{s}{2}+\left(1-\frac{\sqrt{3}}{2}\right)r. \]

Number Theory

1. Let $m$ be a fixed integer greater than $1$. The sequence $x_0$, $x_1$, $x_2$, $\ldots$ is defined as follows: $x_i= 2^i$ if $0 \leq i\leq m-1$, $x_i = \sum_{j=1}^{m}x_{i-j},$ if $i\geq m$. Find the greatest $k$ for which the sequence contains $k$ consecutive terms divisible by $m$ .
2. Each positive integer $a$ is subjected to the following procedure, yielding the number $d = d\left(a\right)$:
   a) The last digit of $a$ is moved to the first position. The resulting number is called $b$.
   b) The number $b$ is squared. The resulting number is called $c$.
   c) The first digit of $c$ is moved to the last position. The resulting number is called $d$. (All numbers are considered in the decimal system.) For instance, $a = 2003$ gives $b = 3200$, $c = 10240000$ and $d = 02400001$ $= 2400001$ $= d\left(2003\right)$.  Find all integers a such that $d\left( a\right) =a^2$.
3. Determine all pairs of positive integers $(a,b)$ such that \[ \dfrac{a^2}{2ab^2-b^3+1} \] is a positive integer.
4. Let $ b$ be an integer greater than $ 5$. For each positive integer $ n$, consider the number \[ x_n = \underbrace{11\cdots1}_{n - 1}\underbrace{22\cdots2}_{n}5, \] written in base $ b$. Prove that the following condition holds if and only if $ b = 10$: there exists a positive integer $ M$ such that for any integer $ n$ greater than $ M$, the number $ x_n$ is a perfect square.
5. An integer $n$ is said to be good if $|n|$ is not the square of an integer. Determine all integers $m$ with the following property: $m$ can be represented, in infinitely many ways, as a sum of three distinct good integers whose product is the square of an odd integer.
6. Let $p$ be a prime number. Prove that there exists a prime number $q$ such that for every integer $n$, the number $n^p-p$ is not divisible by $q$.
7. The sequence $a_0$, $a_1$, $a_2,$ $\ldots$ is defined as follows: $$a_0=2, \quad a_{k+1}=2a_k^2-1 \quad$ for $k \geq 0.$$ Prove that if an odd prime $p$ divides $a_n$, then $2^{n+3}$ divides $p^2-1$.
8. Let $p$ be a prime number and let $A$ be a set of positive integers that satisfies the following conditions: (1) the set of prime divisors of the elements in $A$ consists of $p-1$ elements; (2) for any nonempty subset of $A$, the product of its elements is not a perfect $p$-th power. What is the largest possible number of elements in $A$ ?

Algebra

1. Let $a_{ij}$ (with the indices $i$ and $j$ from the set $\left\{1,\ 2,\ 3\right\}$) be real numbers such that $a_{ij}>0$ for $i = j$; $a_{ij}<0$ for $i\neq j$. Prove the existence of positive real numbers $c_{1}$, $c_{2}$, $c_{3}$ such that the numbers $$a_{11}c_{1}+a_{12}c_{2}+a_{13}c_{3},$$ $$a_{21}c_{1}+a_{22}c_{2}+a_{23}c_{3},$$ $$a_{31}c_{1}+a_{32}c_{2}+a_{33}c_{3}$$ are either all negative, or all zero, or all positive.
2. Find all nondecreasing functions $f: \mathbb{R}\rightarrow\mathbb{R}$ such that
   • $f(0) = 0, f(1) = 1;$
   • $f(a) + f(b) = f(a)f(b) + f(a + b - ab)$ for all real numbers $a, b$ such that $a < 1 < b$.
3. Consider two monotonically decreasing sequences $ \left( a_k\right)$ and $ \left( b_k\right)$, where $ k \geq 1$, and $ a_k$ and $ b_k$ are positive real numbers for every k. Now, define the sequences $$ c_k = \min \left( a_k, b_k \right)$$ $$ A_k = a_1 + a_2 + ... + a_k$$ $$ B_k = b_1 + b_2 + ... + b_k$$ $$ C_k = c_1 + c_2 + ... + c_k$$ for all natural numbers k.
   a) Do there exist two monotonically decreasing sequences $ \left( a_k\right)$ and $ \left( b_k\right)$ of positive real numbers such that the sequences $ \left( A_k\right)$ and $ \left( B_k\right)$ are not bounded, while the sequence $ \left( C_k\right)$ is bounded?
   b) Does the answer to problem (a) change if we stipulate that the sequence $ \left( b_k\right)$ must be $ \displaystyle b_k = \frac {1}{k}$ for all k ?
4. Let $n$ be a positive integer and let $x_1\le x_2\le\cdots\le x_n$ be real numbers. Prove that \[ \left(\sum_{i,j=1}^{n}|x_i-x_j|\right)^2\le\frac{2(n^2-1)}{3}\sum_{i,j=1}^{n}(x_i-x_j)^2. \] Show that the equality holds if and only if $x_1, \ldots, x_n$ is an arithmetic sequence.
5. Let $\mathbb{R}^+$ be the set of all positive real numbers. Find all functions $f: \mathbb{R}^+ \to \mathbb{R}^+$ that satisfy the following conditions: - $f(xyz)+f(x)+f(y)+f(z)=f(\sqrt{xy})f(\sqrt{yz})f(\sqrt{zx})$ for all $x,y,z\in\mathbb{R}^+$; - $f(x)<f(y)$ for all $1\le x<y$.
6. Let $n$ be a positive integer and let $(x_1,\ldots,x_n)$, $(y_1,\ldots,y_n)$ be two sequences of positive real numbers. Suppose $(z_2,\ldots,z_{2n})$ is a sequence of positive real numbers such that $z_{i+j}^2 \geq x_iy_j$ for all $1\le i,j \leq n$. Let $M=\max\{z_2,\ldots,z_{2n}\}$. Prove that \[ \left( \frac{M+z_2+\dots+z_{2n}}{2n} \right)^2 \ge \left( \frac{x_1+\dots+x_n}{n} \right) \left( \frac{y_1+\dots+y_n}{n} \right). \]
   

Combinatorics

1. Let $A$ be a $101$-element subset of the set $S=\{1,2,\ldots,1000000\}$. Prove that there exist numbers $t_1$, $t_2, \ldots, t_{100}$ in $S$ such that the sets \[ A_j=\{x+t_j\mid x\in A\},\qquad j=1,2,\ldots,100 \] are pairwise disjoint.
2. Let $D_1$, $D_2$, ..., $D_n$ be closed discs in the plane. (A closed disc is the region limited by a circle, taken jointly with this circle.) Suppose that every point in the plane is contained in at most $2003$ discs $D_i$. Prove that there exists a disc $D_k$ which intersects at most $7\cdot 2003 - 1 = 14020$ other discs $D_i$.
3. Let $n \geq 5$ be an integer. Find the maximal integer $k$ such that there exists a polygon with $n$ vertices (convex or not, but not self-intersecting!) having $k$ internal $90^{\circ}$ angles.
4. Given $n$ real numbers $x_1$, $x_2$, ..., $x_n$, and $n$ further real numbers $y_1$, $y_2$, ..., $y_n$. The entries $a_{ij}$ (with $1\leq i,\;j\leq n$) of an $n\times n$ matrix $A$ are defined as follows: $$a_{ij}=\left\{ \begin{array}{c} 1\text{ if }x_{i}+y_{j}\geq 0; \\ 0\text{ if }x_{i}+y_{j}<0. \end{array} \right.$$ Further, let $B$ be an $n\times n$ matrix whose elements are numbers from the set $\left\{0;\ 1\right\}$ satisfying the following condition: The sum of all elements of each row of $B$ equals the sum of all elements of the corresponding row of $A$; the sum of all elements of each column of $B$ equals the sum of all elements of the corresponding column of $A$. Show that in this case, $A = B$.
5. Regard a plane with a Cartesian coordinate system; for each point with integer coordinates, draw a circular disk centered at this point and having the radius $\frac{1}{1000}$.
   a) Prove the existence of an equilateral triangle whose vertices lie in the interior of different disks;
   b) Show that every equilateral triangle whose vertices lie in the interior of different disks has a sidelength > 96.
6. Let $f(k)$ be the number of all non-negative integers $n$ satisfying the following conditions
   
   • The integer $n$ has exactly $k$ digits in the decimal representation (where the first digit is not necessarily non-zero!), i. e. we have $0 \leq n <10^k$.
   • These $k$ digits of n can be permuted in such a way that the resulting number is divisible by $11$.
   Show that for any positive integer number $m,$ we have $$f\left(2m\right) = 10 f\left(2m - 1\right).$$

[DOWNLOAD SOLUTIONS ##download##]