International Mathematical Olympiad

Determine all functions $f$ from the set of positive integers to the set of positive integers such that, for all positive integers $a$ and $b$, there exists a non-degenerate triangle with sides of lengths

$$a, f(b) \text{ and } f(b + f(a) - 1).$$

(A triangle is non-degenerate if its vertices are not collinear.)

Let $a_1, a_2, \ldots, a_n$ be distinct positive integers and let $M$ be a set of $n - 1$ positive integers not containing $s = a_1 + a_2 + \cdots + a_n$. A grasshopper is to jump along the real axis, starting at the point $0$ and making $n$ jumps to the right with lengths $a_1, a_2, \ldots, a_n$ in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in $M$.

An acute-angled triangle $ABC$ has orthocentre $H$. The circle passing through $H$ with centre the midpoint of $BC$ intersects the line $BC$ at $A_1$ and $A_2$. Similarly, the circle passing through $H$ with centre the midpoint of $CA$ intersects the line $CA$ at $B_1$ and $B_2$, and the circle passing through $H$ with centre the midpoint of $AB$ intersects the line $AB$ at $C_1$ and $C_2$. Show that $A_1, A_2, B_1, B_2, C_1, C_2$ lie on a circle.

(a) Prove that $$\frac{x^2}{(x-1)^2} + \frac{y^2}{(y-1)^2} + \frac{z^2}{(z-1)^2} \geq 1$$ for all real numbers $x, y, z$, each different from 1, and satisfying $xyz = 1$.

(b) Prove that equality holds above for infinitely many triples of rational numbers $x, y, z$, each different from 1, and satisfying $xyz = 1$.

Prove that there exist infinitely many positive integers $n$ such that $n^2 + 1$ has a prime divisor which is greater than $2n + \sqrt{2n}$.

Find all functions $f: (0, \infty) \to (0, \infty)$ (so, $f$ is a function from the positive real numbers to the positive real numbers) such that $$\frac{(f(w))^2 + (f(x))^2}{f(y^2) + f(z^2)} = \frac{w^2 + x^2}{y^2 + z^2}$$ for all positive real numbers $w, x, y, z$, satisfying $wx = yz$.

Let $n$ and $k$ be positive integers with $k \geq n$ and $k - n$ an even number. Let $2n$ lamps labelled 1, 2, ..., $2n$ be given, each of which can be either on or off. Initially all the lamps are off. We consider sequences of steps: at each step one of the lamps is switched (from on to off or from off to on).

Let $N$ be the number of such sequences consisting of $k$ steps and resulting in the state where lamps 1 through $n$ are all on, and lamps $n + 1$ through $2n$ are all off.

Let $M$ be the number of such sequences consisting of $k$ steps, resulting in the state where lamps 1 through $n$ are all on, and lamps $n + 1$ through $2n$ are all off, but where none of the lamps $n + 1$ through $2n$ is ever switched on.

Determine the ratio $N/M$.

Let $ABCD$ be a convex quadrilateral with $|BA| \neq |BC|$. Denote the incircles of triangles $ABC$ and $ADC$ by $\omega_1$ and $\omega_2$ respectively. Suppose that there exists a circle $\omega$ tangent to the ray $BA$ beyond $A$ and to the ray $BC$ beyond $C$, which is also tangent to the lines $AD$ and $CD$. Prove that the common external tangents of $\omega_1$ and $\omega_2$ intersect on $\omega$.

Real numbers $a_1, a_2, \ldots, a_n$ are given. For each $i$ ($1 \leq i \leq n$) define

$$d_i = \max\{a_j : 1 \leq j \leq i\} - \min\{a_j : i \leq j \leq n\}$$

and let

$$d = \max\{d_i : 1 \leq i \leq n\}.$$

(a) Prove that, for any real numbers $x_1 \leq x_2 \leq \cdots \leq x_n$,

$$\max\{|x_i - a_i| : 1 \leq i \leq n\} \geq \frac{d}{2}. \quad (*)$$

(b) Show that there are real numbers $x_1 \leq x_2 \leq \cdots \leq x_n$ such that equality holds in $(*)$.

Consider five points $A, B, C, D$ and $E$ such that $ABCD$ is a parallelogram and $BCED$ is a cyclic quadrilateral. Let $\ell$ be a line passing through $A$. Suppose that $\ell$ intersects the interior of the segment $DC$ at $F$ and intersects line $BC$ at $G$. Suppose also that $EF = EG = EC$. Prove that $\ell$ is the bisector of angle $DAB$.

In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a clique if each two of them are friends. (In particular, any group of fewer than two competitors is a clique.) The number of members of a clique is called its size.

Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged in two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room.

In triangle $ABC$ the bisector of angle $BCA$ intersects the circumcircle again at $R$, the perpendicular bisector of $BC$ at $P$, and the perpendicular bisector of $AC$ at $Q$. The midpoint of $BC$ is $K$ and the midpoint of $AC$ is $L$. Prove that the triangles $RPK$ and $RQL$ have the same area.

Let $a$ and $b$ be positive integers. Show that if $4ab - 1$ divides $(4a^2 - 1)^2$, then $a = b$.

Let $n$ be a positive integer. Consider

$$S = \{(x, y, z) : x, y, z \in \{0, 1, \ldots, n\}, x + y + z > 0\}$$

as a set of $(n + 1)^3 - 1$ points in three-dimensional space. Determine the smallest possible number of planes, the union of which contains $S$ but does not include $(0,0,0)$.

Let $ABC$ be a triangle with incentre $I$. A point $P$ in the interior of the triangle satisfies $$\angle PBA + \angle PCA = \angle PBC + \angle PCB.$$

Show that $AP \geq AI$, and that equality holds if and only if $P = I$.

Let $P$ be a regular 2006-gon. A diagonal of $P$ is called good if its endpoints divide the boundary of $P$ into two parts, each composed of an odd number of sides of $P$. The sides of $P$ are also called good.

Suppose $P$ has been dissected into triangles by 2003 diagonals, no two of which have a common point in the interior of $P$. Find the maximum number of isosceles triangles having two good sides that could appear in such a configuration.

Determine the least real number $M$ such that the inequality $$\left| ab(a^2 - b^2) + bc(b^2 - c^2) + ca(c^2 - a^2) \right| \leq M(a^2 + b^2 + c^2)^2$$ holds for all real numbers $a$, $b$ and $c$.

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

Let $P(x)$ be a polynomial of degree $n > 1$ with integer coefficients and let $k$ be a positive integer. Consider the polynomial $Q(x) = P(P(\ldots P(P(x)) \ldots))$, where $P$ occurs $k$ times. Prove that there are at most $n$ integers $t$ such that $Q(t) = t$.

Assign to each side $b$ of a convex polygon $P$ the maximum area of a triangle that has $b$ as a side and is contained in $P$. Show that the sum of the areas assigned to the sides of $P$ is at least twice the area of $P$.

Six points are chosen on the sides of an equilateral triangle $ABC$: $A_1$, $A_2$ on $BC$, $B_1$, $B_2$ on $CA$ and $C_1$, $C_2$ on $AB$, such that they are the vertices of a convex hexagon $A_1A_2B_1B_2C_1C_2$ with equal side lengths.

Prove that the lines $A_1B_2$, $B_1C_2$ and $C_1A_2$ are concurrent.

Let $a_1, a_2, \ldots$ be a sequence of integers with infinitely many positive and negative terms. Suppose that for every positive integer $n$ the numbers $a_1, a_2, \ldots, a_n$ leave $n$ different remainders upon division by $n$.

Prove that every integer occurs exactly once in the sequence $a_1, a_2, \ldots$.

Let $x, y, z$ be three positive reals such that $xyz \geq 1$. Prove that $$\frac{x^5 - x^2}{x^5 + y^2 + z^2} + \frac{y^5 - y^2}{x^2 + y^5 + z^2} + \frac{z^5 - z^2}{x^2 + y^2 + z^5} \geq 0.$$

Determine all positive integers relatively prime to all the terms of the infinite sequence $$a_n = 2^n + 3^n + 6^n - 1, \quad n \geq 1.$$

Let $ABCD$ be a fixed convex quadrilateral with $BC = DA$ and $BC$ not parallel with $DA$. Let two variable points $E$ and $F$ lie of the sides $BC$ and $DA$, respectively and satisfy $BE = DF$. The lines $AC$ and $BD$ meet at $P$, the lines $BD$ and $EF$ meet at $Q$, the lines $EF$ and $AC$ meet at $R$.

Prove that the circumcircles of the triangles $PQR$, as $E$ and $F$ vary, have a common point other than $P$.

In a mathematical competition, in which 6 problems were posed to the participants, every two of these problems were solved by more than $\frac{2}{5}$ of the contestants. Moreover, no contestant solved all the 6 problems. Show that there are at least 2 contestants who solved exactly 5 problems each.

Let $ABC$ be an acute-angled triangle with $AB \neq AC$. The circle with diameter $BC$ intersects the sides $AB$ and $AC$ at $M$ and $N$ respectively. Denote by $O$ the midpoint of the side $BC$. The bisectors of the angles $\angle BAC$ and $\angle MON$ intersect at $R$. Prove that the circumcircles of the triangles $BMR$ and $CNR$ have a common point lying on the side $BC$.

Find all polynomials $f$ with real coefficients such that for all reals $a$, $b$, $c$ such that $ab + bc + ca = 0$ we have the following relations $$f(a-b) + f(b-c) + f(c-a) = 2f(a+b+c).$$

Define a "hook" to be a figure made up of six unit squares as shown below in the picture, or any of the figures obtained by applying rotations and reflections to this figure.

Determine all $m \times n$ rectangles that can be covered without gaps and without overlaps with hooks such that

• the rectangle is covered without gaps and without overlaps

• no part of a hook covers area outside the rectangle.

Let $n \geq 3$ be an integer. Let $t_1, t_2, \ldots, t_n$ be positive real numbers such that $$n^2 + 1 > (t_1 + t_2 + \ldots + t_n)\left(\frac{1}{t_1} + \frac{1}{t_2} + \ldots + \frac{1}{t_n}\right).$$

Show that $t_i, t_j, t_k$ are side lengths of a triangle for all $i$, $j$, $k$ with $1 \leq i < j < k \leq n$.

In a convex quadrilateral $ABCD$ the diagonal $BD$ does not bisect the angles $\angle ABC$ and $\angle CDA$. The point $P$ lies inside $ABCD$ and satisfies $$\angle PBC = \angle DBA \text{ and } \angle PDC = \angle BDA.$$

Prove that $ABCD$ is a cyclic quadrilateral if and only if $AP = CP$.

We call a positive integer alternating if every two consecutive digits in its decimal representation are of different parity. Find all positive integers $n$ such that $n$ has a multiple which is alternating.

$S$ is the set $\{1,2,3,\ldots,1000000\}$. Show that for any subset $A$ of $S$ with 101 elements we can find 100 distinct elements $x_i$ of $S$, such that the sets $\{a + x_i | a \in A\}$ are all pairwise disjoint.

Find all pairs $(m,n)$ of positive integers such that $\frac{m^2}{2mn^2 - n^3 + 1}$ is a positive integer.

A convex hexagon has the property that for any pair of opposite sides the distance between their midpoints is $\sqrt{3}/2$ times the sum of their lengths. Show that all the hexagon's angles are equal.

$ABCD$ is cyclic. The feet of the perpendicular from $D$ to the lines $AB, BC, CA$ are $P, Q, R$ respectively. Show that the angle bisectors of $ABC$ and $CDA$ meet on the line $AC$ iff $RP = RQ$.

Given $n > 2$ and reals $x_1 \leq x_2 \leq \cdots \leq x_n$, show that $(\sum_{i,j} |x_i - x_j|)^2 \leq \frac{2}{3}(n^2 - 1)\sum_{i,j}(x_i - x_j)^2$. Show that we have equality iff the sequence is an arithmetic progression.

Show that for each prime $p$, there exists a prime $q$ such that $n^p - p$ is not divisible by $q$ for any positive integer $n$.

$S$ is the set of all $(h,k)$ with $h,k$ non-negative integers such that $h+k<n$. Each element of $S$ is colored red or blue, so that if $(h,k)$ is red and $h'\leq h,k'\leq k$, then $(h',k')$ is also red. A type 1 subset of $S$ has $n$ blue elements with different first member and a type 2 subset of $S$ has $n$ blue elements with different second member. Show that there are the same number of type 1 and type 2 subsets.

$BC$ is a diameter of a circle center $O$. $A$ is any point on the circle with $\angle AOC>60^{\circ}$. $EF$ is the chord which is the perpendicular bisector of $AO$. $D$ is the midpoint of the minor arc $AB$. The line through $O$ parallel to $AD$ meets $AC$ at $J$. Show that $J$ is the incenter of triangle $CEF$.

Find all pairs of integers $m>2,n>2$ such that there are infinitely many positive integers $k$ for which $k^{n}+k^{2}-1$ divides $k^{m}+k-1$.

The positive divisors of the integer $n>1$ are $d_{1}<d_{2}<\ldots<d_{k}$, so that $d_{1}=1,d_{k}=n$. Let $d=d_{1}d_{2}+d_{2}d_{3}+\cdots+d_{k-1}d_{k}$. Show that $d<n^{2}$ and find all $n$ for which $d$ divides $n^{2}$.

Find all real-valued functions on the reals such that $(f(x)+f(y))(f(u)+f(v))=f(xu-yv)+f(xv+yu)$ for all $x,y,u,v$.

$n>2$ circles of radius 1 are drawn in the plane so that no line meets more than two of the circles. Their centers are $O_{1},O_{2},\cdots,O_{n}$. Show that $\sum_{i<j}1/O_{i}O_{j}\leq(n-1)\pi/4$.

Let $ABC$ be an acute-angled triangle with circumcentre $O$. Let $P$ on $BC$ be the foot of the altitude from $A$.

Suppose that $\angle BCA \geq \angle ABC + 30^{\circ}$.

Prove that $\angle CAB + \angle COP < 90^{\circ}$.

Prove that

$$\frac{a}{\sqrt{a^2 + 8bc}} + \frac{b}{\sqrt{b^2 + 8ca}} + \frac{c}{\sqrt{c^2 + 8ab}} \geq 1$$

for all positive real numbers $a, b$ and $c$.

Twenty-one girls and twenty-one boys took part in a mathematical contest.

• Each contestant solved at most six problems.
• For each girl and each boy, at least one problem was solved by both of them.

Prove that there was a problem that was solved by at least three girls and at least three boys.

Let $n$ be an odd integer greater than 1, and let $k_1, k_2, \ldots, k_n$ be given integers. For each of the $n!$ permutations $a = (a_1, a_2, \ldots, a_n)$ of $1, 2, \ldots, n$, let

$$S(a) = \sum_{i=1}^{n} k_i a_i.$$

Prove that there are two permutations $b$ and $c, b \neq c$, such that $n!$ is a divisor of $S(b) - S(c)$.

In a triangle $ABC$, let $AP$ bisect $\angle BAC$, with $P$ on $BC$, and let $BQ$ bisect $\angle ABC$, with $Q$ on $CA$.

It is known that $\angle BAC = 60^{\circ}$ and that $AB + BP = AQ + QB$.

What are the possible angles of triangle $ABC$?

Let $a, b, c, d$ be integers with $a > b > c > d > 0$. Suppose that

$$ac + bd = (b + d + a - c)(b + d - a + c).$$

Prove that $ab + cd$ is not prime.