1975 IMO Shortlist

1

There are six ports on a lake. Is it possible to organize a series of routes satisfying the following conditions ? (i) Every route includes exactly three ports; (ii) No two routes contain the same three ports; (iii) The series offers exactly two routes to each tourist who desires to visit two different arbitrary ports.

2

We consider two sequences of real numbers $x_{1} \geq x_{2} \geq \ldots \geq x_{n}$ and $\ y_{1} \geq y_{2} \geq \ldots \geq y_{n}.$ Let $z_{1}, z_{2}, .\ldots, z_{n}$ be a permutation of the numbers $y_{1}, y_{2}, \ldots, y_{n}.$ Prove that $\sum \limits_{i=1}^{n} ( x_{i} -\ y_{i} )^{2} \leq \sum \limits_{i=1}^{n}$ $( x_{i} - z_{i})^{2}.$

3

Find the integer represented by $\left[ \sum_{n=1}^{10^9} n^{-2/3} \right] $. Here $[x]$ denotes the greatest integer less than or equal to $x.$

4

Let $a_1, a_2, \ldots , a_n, \ldots $ be a sequence of real numbers such that $0 \leq a_n \leq 1$ and $a_n - 2a_{n+1} + a_{n+2} \geq 0$ for $n = 1, 2, 3, \ldots$. Prove that \[0 \leq (n + 1)(a_n - a_{n+1}) \leq 2 \qquad \text{ for } n = 1, 2, 3, \ldots\]

5

Let $M$ be the set of all positive integers that do not contain the digit $9$ (base $10$). If $x_1, \ldots , x_n$ are arbitrary but distinct elements in $M$, prove that \[\sum_{j=1}^n \frac{1}{x_j} < 80 .\]

6

When $4444^{4444}$ is written in decimal notation, the sum of its digits is $ A.$ Let $B$ be the sum of the digits of $A.$ Find the sum of the digits of $ B.$ ($A$ and $B$ are written in decimal notation.)

7

Prove that from $x + y = 1 \ (x, y \in \mathbb R)$ it follows that \[x^{m+1} \sum_{j=0}^n \binom{m+j}{j} y^j + y^{n+1} \sum_{i=0}^m \binom{n+i}{i} x^i = 1 \qquad (m, n = 0, 1, 2, \ldots ).\]

8

In the plane of a triangle $ABC,$ in its exterior$,$ we draw the triangles $ABR, BCP, CAQ$ so that $\angle PBC = \angle CAQ = 45^{\circ}$, $\angle BCP = \angle QCA = 30^{\circ}$, $\angle ABR = \angle RAB = 15^{\circ}$. Prove that a.) $\angle QRP = 90\,^{\circ},$ and b.) $QR = RP.$

9

Let $f(x)$ be a continuous function defined on the closed interval $0 \leq x \leq 1$. Let $G(f)$ denote the graph of $f(x): G(f) = \{(x, y) \in \mathbb R^2 | 0 \leq$$ x \leq 1, y = f(x) \}$. Let $G_a(f)$ denote the graph of the translated function $f(x - a)$ (translated over a distance $a$), defined by $G_a(f) = \{(x, y) \in \mathbb R^2 | a \leq x \leq a + 1, y = f(x - a) \}$. Is it possible to find for every $a, \ 0 < a < 1$, a continuous function $f(x)$, defined on $0 \leq x \leq 1$, such that $f(0) = f(1) = 0$ and $G(f)$ and $G_a(f)$ are disjoint point sets ?

10

Determine the polynomials P of two variables so that: a.) for any real numbers $t,x,y$ we have $P(tx,ty) = t^n P(x,y)$ where $n$ is a positive integer, the same for all $t,x,y;$ b.) for any real numbers $a,b,c$ we have $P(a + b,c) + P(b + c,a) + P(c + a,b) = 0;$ c.) $P(1,0) =1.$

11

Let $a_{1}, \ldots, a_{n}$ be an infinite sequence of strictly positive integers, so that $a_{k} < a_{k+1}$ for any $k.$ Prove that there exists an infinity of terms $ a_{m},$ which can be written like $a_m = x \cdot a_p + y \cdot a_q$ with $x,y$ strictly positive integers and $p \neq q.$

12

Consider on the first quadrant of the trigonometric circle the arcs $AM_1 = x_1,AM_2 = x_2,AM_3 = x_3, \ldots , AM_v = x_v$ , such that $x_1 < x_2 < x_3 < \cdots < x_v$. Prove that \[\sum_{i=0}^{v-1} \sin 2x_i - \sum_{i=0}^{v-1} \sin (x_i- x_{i+1}) < \frac{\pi}{2} + \sum_{i=0}^{v-1} \sin (x_i + x_{i+1})\]

13

Let $A_0,A_1, \ldots , A_n$ be points in a plane such that (i) $A_0A_1 \leq \frac{1}{ 2} A_1A_2 \leq \cdots \leq \frac{1}{2^{n-1} } A_{n-1}A_n$ and (ii) $0 < \measuredangle A_0A_1A_2 < \measuredangle A_1A_2A_3 < \cdots < \measuredangle A_{n-2}A_{n-1}A_n < 180^\circ,$ where all these angles have the same orientation. Prove that the segments $A_kA_{k+1},A_mA_{m+1}$ do not intersect for each $k$ and $n$ such that $0 \leq k \leq m - 2 < n- 2.$

14

Let $x_0 = 5$ and $x_{n+1} = x_n + \frac{1}{x_n} \ (n = 0, 1, 2, \ldots )$. Prove that \[45 < x_{1000} < 45. 1.\]

15

Can there be drawn on a circle of radius $1$ a number of $1975$ distinct points, so that the distance (measured on the chord) between any two points (from the considered points) is a rational number?