International Mathematical Olympiad

Consider nine points in space, no four of which are coplanar. Each pair of points is joined by an edge (that is, a line segment) and each edge is either colored blue or red or left uncolored. Find the smallest value of $n$ such that whenever exactly $n$ edges are colored, the set of colored edges necessarily contains a triangle all of whose edges have the same color.

In the plane let $C$ be a circle, $L$ a line tangent to the circle $C$, and $M$ a point on $L$. Find the locus of all points $P$ with the following property: there exists two points $Q, R$ on $L$ such that $M$ is the midpoint of $QR$ and $C$ is the inscribed circle of triangle $PQR$.

Let $S$ be a finite set of points in three-dimensional space. Let $S_x, S_y, S_z$ be the sets consisting of the orthogonal projections of the points of $S$ onto the $yz$-plane, $zx$-plane, $xy$-plane, respectively. Prove that

$$|S|^2 \leq |S_x| \cdot |S_y| \cdot |S_z|,$$

where $|A|$ denotes the number of elements in the finite set $|A|$. (Note: The orthogonal projection of a point onto a plane is the foot of the perpendicular from that point to the plane.)

For each positive integer $n$, $S(n)$ is defined to be the greatest integer such that, for every positive integer $k \leq S(n)$, $n^2$ can be written as the sum of $k$ positive squares.

(a) Prove that $S(n) \leq n^2 - 14$ for each $n \geq 4$.

(b) Find an integer $n$ such that $S(n) = n^2 - 14$.

(c) Prove that there are infinitely many integers $n$ such that $S(n) = n^2 - 14$.

Given a triangle $ABC$, let $I$ be the center of its inscribed circle. The internal bisectors of the angles $A, B, C$ meet the opposite sides in $A', B', C'$ respectively. Prove that

$$\frac{1}{4} < \frac{AI \cdot BI \cdot CI}{AA' \cdot BB' \cdot CC'} \leq \frac{8}{27}.$$

Let $n > 6$ be an integer and $a_1, a_2, \ldots, a_k$ be all the natural numbers less than $n$ and relatively prime to $n$. If

$$a_2 - a_1 = a_3 - a_2 = \cdots = a_k - a_{k-1} > 0,$$

prove that $n$ must be either a prime number or a power of 2.

Let $S = \{1, 2, 3, \ldots, 280\}$. Find the smallest integer $n$ such that each $n$-element subset of $S$ contains five numbers which are pairwise relatively prime.

Suppose $G$ is a connected graph with $k$ edges. Prove that it is possible to label the edges $1, 2, \ldots, k$ in such a way that at each vertex which belongs to two or more edges, the greatest common divisor of the integers labeling those edges is equal to 1.

[A graph consists of a set of points, called vertices, together with a set of edges joining certain pairs of distinct vertices. Each pair of vertices $u, v$ belongs to at most one edge. The graph $G$ is connected if for each pair of distinct vertices $x, y$ there is some sequence of vertices $x = v_0, v_1, v_2, \ldots, v_m = y$ such that each pair $v_i, v_{i+1}$ ($0 \leq i < m$) is joined by an edge of $G$.]

Let $ABC$ be a triangle and $P$ an interior point of $ABC$. Show that at least one of the angles $\angle PAB$, $\angle PBC$, $\angle PCA$ is less than or equal to $30°$.

An infinite sequence $x_0, x_1, x_2, \ldots$ of real numbers is said to be bounded if there is a constant $C$ such that $|x_i| \leq C$ for every $i \geq 0$.

Given any real number $a > 1$, construct a bounded infinite sequence $x_0, x_1, x_2, \ldots$ such that

$$|x_i - x_j||i - j|^a \geq 1$$

for every pair of distinct nonnegative integers $i, j$.

Chords $AB$ and $CD$ of a circle intersect at a point $E$ inside the circle. Let $M$ be an interior point of the segment $EB$. The tangent line at $E$ to the circle through $D$, $E$, and $M$ intersects the lines $BC$ and $AC$ at $F$ and $G$, respectively. If

$$\frac{AM}{AB} = t,$$

find

$$\frac{EG}{EF}$$

in terms of $t$.

Let $n \geq 3$ and consider a set $E$ of $2n - 1$ distinct points on a circle. Suppose that exactly $k$ of these points are to be colored black. Such a coloring is "good" if there is at least one pair of black points such that the interior of one of the arcs between them contains exactly $n$ points from $E$. Find the smallest value of $k$ so that every such coloring of $k$ points of $E$ is good.

Determine all integers $n > 1$ such that

$$\frac{2^n + 1}{n^2}$$

is an integer.

Let $\mathbb{Q}^+$ be the set of positive rational numbers. Construct a function $f: \mathbb{Q}^+ \to \mathbb{Q}^+$ such that

$$f(xf(y)) = \frac{f(x)}{y}$$

for all $x, y$ in $\mathbb{Q}^+$.

Given an initial integer $n_0 > 1$, two players, $\mathcal{A}$ and $\mathcal{B}$, choose integers $n_1, n_2, n_3, \ldots$ alternately according to the following rules:

Knowing $n_{2k}$, $\mathcal{A}$ chooses any integer $n_{2k+1}$ such that

$$n_{2k} \leq n_{2k+1} \leq n_{2k}^2.$$

Knowing $n_{2k+1}$, $\mathcal{B}$ chooses any integer $n_{2k+2}$ such that

$$\frac{n_{2k+1}}{n_{2k+2}}$$

is a prime raised to a positive integer power.

Player $\mathcal{A}$ wins the game by choosing the number 1990; player $\mathcal{B}$ wins by choosing the number 1. For which $n_0$ does:

(a) $\mathcal{A}$ have a winning strategy?

(b) $\mathcal{B}$ have a winning strategy?

(c) Neither player have a winning strategy?

Prove that there exists a convex 1990-gon with the following two properties:

(a) All angles are equal.

(b) The lengths of the 1990 sides are the numbers $1^2, 2^2, 3^2, \ldots, 1990^2$ in some order.

Prove that the set $\{1,2,\ldots,1989\}$ can be expressed as the disjoint union of subsets $A_i$ ($i = 1, 2, \ldots, 117$) such that:

(i) Each $A_i$ contains 17 elements;

(ii) The sum of all the elements in each $A_i$ is the same.

In an acute-angled triangle $ABC$ the internal bisector of angle $A$ meets the circumcircle of the triangle again at $A_1$. Points $B_1$ and $C_1$ are defined similarly. Let $A_0$ be the point of intersection of the line $AA_1$ with the external bisectors of angles $B$ and $C$. Points $B_0$ and $C_0$ are defined similarly. Prove that:

(i) The area of the triangle $A_0B_0C_0$ is twice the area of the hexagon $AC_1BA_1CB_1$.

(ii) The area of the triangle $A_0B_0C_0$ is at least four times the area of the triangle $ABC$.

Let $n$ and $k$ be positive integers and let $S$ be a set of $n$ points in the plane such that

(i) No three points of $S$ are collinear, and

(ii) For any point $P$ of $S$ there are at least $k$ points of $S$ equidistant from $P$.

Prove that:

$$k < \frac{1}{2} + \sqrt{2n}.$$

Let $ABCD$ be a convex quadrilateral such that the sides $AB$, $AD$, $BC$ satisfy $AB = AD + BC$. There exists a point $P$ inside the quadrilateral at a distance $h$ from the line $CD$ such that $AP = h + AD$ and $BP = h + BC$. Show that:

$$\frac{1}{\sqrt{h}} \geq \frac{1}{\sqrt{AD}} + \frac{1}{\sqrt{BC}}.$$

Prove that for each positive integer $n$ there exist $n$ consecutive positive integers none of which is an integral power of a prime number.

A permutation $(x_1, x_2, \ldots, x_m)$ of the set $\{1, 2, \ldots, 2n\}$, where $n$ is a positive integer, is said to have property $P$ if $|x_i - x_{i+1}| = n$ for at least one $i$ in $\{1, 2, \ldots, 2n-1\}$. Show that, for each $n$, there are more permutations with property $P$ than without.

Consider two coplanar circles of radii $R$ and $r$ ($R > r$) with the same center. Let $P$ be a fixed point on the smaller circle and $B$ a variable point on the larger circle. The line $BP$ meets the larger circle again at $C$. The perpendicular $l$ to $BP$ at $P$ meets the smaller circle again at $A$. (If $l$ is tangent to the circle at $P$ then $A = P$.)

(i) Find the set of values of $BC^2 + CA^2 + AB^2$.

(ii) Find the locus of the midpoint of $BC$.

Let $n$ be a positive integer and let $A_1$, $A_2$, \ldots, $A_{2n+1}$ be subsets of a set $B$. Suppose that

(a) Each $A_i$ has exactly $2n$ elements,

(b) Each $A_i \cap A_j$ ($1 \leq i < j \leq 2n + 1$) contains exactly one element, and

(c) Every element of $B$ belongs to at least two of the $A_i$.

For which values of $n$ can one assign to every element of $B$ one of the numbers $0$ and $1$ in such a way that $A_i$ has $0$ assigned to exactly $n$ of its elements?

A function $f$ is defined on the positive integers by

$$\begin{aligned} f(1) &= 1, \quad f(3) = 3, \\ f(2n) &= f(n), \\ f(4n + 1) &= 2f(2n + 1) - f(n), \\ f(4n + 3) &= 3f(2n + 1) - 2f(n), \end{aligned}$$

for all positive integers $n$.

Determine the number of positive integers $n$, less than or equal to 1988, for which $f(n) = n$.

Show that set of real numbers $x$ which satisfy the inequality

$$\sum_{k=1}^{70} \frac{k}{x-k} \geq \frac{5}{4}$$

is a union of disjoint intervals, the sum of whose lengths is 1988.

$ABC$ is a triangle right-angled at $A$, and $D$ is the foot of the altitude from $A$. The straight line joining the incenters of the triangles $ABD$, $ACD$ intersects the sides $AB$, $AC$ at the points $K$, $L$ respectively. $S$ and $T$ denote the areas of the triangles $ABC$ and $AKL$ respectively. Show that $S \geq 2T$.

Let $a$ and $b$ be positive integers such that $ab + 1$ divides $a^2 + b^2$. Show that

$$\frac{a^2 + b^2}{ab + 1}$$

is the square of an integer.

Let $p_n(k)$ be the number of permutations of the set $\{1, \ldots, n\}$, $n \geq 1$, which have exactly $k$ fixed points. Prove that

$$\sum_{k=0}^{n} k \cdot p_n(k) = n!.$$

(Remark: A permutation $f$ of a set $S$ is a one-to-one mapping of $S$ onto itself. An element $i$ in $S$ is called a fixed point of the permutation $f$ if $f(i) = i$.)

In an acute-angled triangle $ABC$ the interior bisector of the angle $A$ intersects $BC$ at $L$ and intersects the circumcircle of $ABC$ again at $N$. From point $L$ perpendiculars are drawn to $AB$ and $AC$, the feet of these perpendiculars being $K$ and $M$ respectively. Prove that the quadrilateral $AKNM$ and the triangle $ABC$ have equal areas.

Let $x_1, x_2, \ldots, x_n$ be real numbers satisfying $x_1^2 + x_2^2 + \cdots + x_n^2 = 1$. Prove that for every integer $k \geq 2$ there are integers $a_1, a_2, \ldots, a_n$, not all 0, such that $|a_i| \leq k - 1$ for all $i$ and

$$\left| a_1 x_1 + a_1 x_2 + \cdots + a_n x_n \right| \leq \frac{(k - 1) \sqrt{n}}{k^n - 1}.$$

Prove that there is no function $f$ from the set of non-negative integers into itself such that $f(f(n)) = n + 1987$ for every $n$.

Let $n$ be an integer greater than or equal to 3. Prove that there is a set of $n$ points in the plane such that the distance between any two points is irrational and each set of three points determines a non-degenerate triangle with rational area.

Let $n$ be an integer greater than or equal to 2. Prove that if $k^2 + k + n$ is prime for all integers $k$ such that $0 \leq k \leq \sqrt{n/3}$, then $k^2 + k + n$ is prime for all integers $k$ such that $0 \leq k \leq n - 2$.

Let $d$ be any positive integer not equal to 2, 5, or 13. Show that one can find distinct $a$, $b$ in the set $\{2,5,13,d\}$ such that $ab - 1$ is not a perfect square.

A triangle $A_{1}A_{2}A_{3}$ and a point $P_{0}$ are given in the plane. We define $A_{s} = A_{s-3}$ for all $s \geq 4$. We construct a set of points $P_{1}, P_{2}, P_{3}, \ldots$, such that $P_{k+1}$ is the image of $P_{k}$ under a rotation with center $A_{k+1}$ through angle $120^{\circ}$ clockwise (for $k = 0, 1, 2, \ldots$). Prove that if $P_{1986} = P_{0}$, then the triangle $A_{1}A_{2}A_{3}$ is equilateral.

To each vertex of a regular pentagon an integer is assigned in such a way that the sum of all five numbers is positive. If three consecutive vertices are assigned the numbers $x, y, z$ respectively and $y < 0$ then the following operation is allowed: the numbers $x, y, z$ are replaced by $x + y, -y, z + y$ respectively. Such an operation is performed repeatedly as long as at least one of the five numbers is negative. Determine whether this procedure necessarily comes to and end after a finite number of steps.

Let $A$, $B$ be adjacent vertices of a regular $n$-gon ($n \geq 5$) in the plane having center at $O$. A triangle $XYZ$, which is congruent to and initially coincides with $OAB$, moves in the plane in such a way that $Y$ and $Z$ each trace out the whole boundary of the polygon, $X$ remaining inside the polygon. Find the locus of $X$.

Find all functions $f$, defined on the non-negative real numbers and taking non-negative real values, such that:

(i) $f(xf(y))f(y) = f(x + y)$ for all $x, y \geq 0$,

(ii) $f(2) = 0$,

(iii) $f(x) \neq 0$ for $0 \leq x < 2$.

One is given a finite set of points in the plane, each point having integer coordinates. Is it always possible to color some of the points in the set red and the remaining points white in such a way that for any straight line $L$ parallel to either one of the coordinate axes the difference (in absolute value) between the numbers of white point and red points on $L$ is not greater than 1?

A circle has center on the side $AB$ of the cyclic quadrilateral $ABCD$. The other three sides are tangent to the circle. Prove that $AD + BC = AB$.

Let $n$ and $k$ be given relatively prime natural numbers, $k < n$. Each number in the set $M = \{1, 2, \ldots, n-1\}$ is colored either blue or white. It is given that

• (i) for each $i \in M$, both $i$ and $n-i$ have the same color;

• (ii) for each $i \in M, i \neq k$, both $i$ and $|i-k|$ have the same color.

Prove that all numbers in $M$ must have the same color.

For any polynomial $P(x) = a_0 + a_1x + \cdots + a_kx^k$ with integer coefficients, the number of coefficients which are odd is denoted by $w(P)$. For $i = 0, 1, \ldots$, let $Q_i(x) = (1+x)^i$. Prove that if $i_1, i_2, \ldots, i_n$ are integers such that $0 \leq i_1 < i_2 < \cdots < i_n$, then $$w(Q_{i_1} + Q_{i_2} + \cdots + Q_{i_n}) \geq w(Q_{i_1}).$$

Given a set $M$ of 1985 distinct positive integers, none of which has a prime divisor greater than 26. Prove that $M$ contains at least one subset of four distinct elements whose product is the fourth power of an integer.

A circle with center $O$ passes through the vertices $A$ and $C$ of triangle $ABC$ and intersects the segments $AB$ and $BC$ again at distinct points $K$ and $N$, respectively. The circumscribed circles of the triangles $ABC$ and $EBN$ intersect at exactly two distinct points $B$ and $M$. Prove that angle OMB is a right angle.

For every real number $x_1$, construct the sequence $x_1, x_2, \ldots$ by setting $$x_{n+1} = x_n\left(x_n + \frac{1}{n}\right) \text{ for each } n \geq 1.$$ Prove that there exists exactly one value of $x_1$ for which $$0 < x_n < x_{n+1} < 1$$ for every $n$.

Prove that $0 \leq yz + zx + xy - 2xyz \leq 7/27$, where $x, y$ and $z$ are non-negative real numbers for which $x + y + z = 1$.

Find one pair of positive integers $a$ and $b$ such that:

(i) $ab(a + b)$ is not divisible by 7;

(ii) $(a + b)^7 - a^7 - b^7$ is divisible by $7^7$.

Justify your answer.

In the plane two different points $O$ and $A$ are given. For each point $X$ of the plane, other than $O$, denote by $a(X)$ the measure of the angle between $OA$ and $OX$ in radians, counterclockwise from $OA$ $(0 \leq a(X) < 2\pi)$. Let $C(X)$ be the circle with center $O$ and radius of length $OX + a(X)/OX$. Each point of the plane is colored by one of a finite number of colors. Prove that there exists a point $Y$ for which $a(Y) > 0$ such that its color appears on the circumference of the circle $C(Y)$.

Let $ABCD$ be a convex quadrilateral such that the line $CD$ is a tangent to the circle on $AB$ as diameter. Prove that the line $AB$ is a tangent to the circle on $CD$ as diameter if and only if the lines $BC$ and $AD$ are parallel.