ISL 1988

An integer sequence is defined by $${ a_n = 2 a_{n-1} + a_{n-2}}, (n > 1), a_0 = 0, a_1 = 1.$$ Prove that $2^k$ divides $a_n$ if and only if $2^k$ divides $n$ .

$n$ points are given on the surface of a sphere. Show that the surface can be divided into $n$ congruent regions such that each of them contains exactly one of the given points.

In a multiple choice test there were 4 questions and 3 possible answers for each question. A group of students was tested and it turned out that for any three of them there was a question which the three students answered differently. What is the maximum number of students tested?

A sequence of numbers $a_n, n = 1,2, \ldots,$ is defined as follows: $a_1 = \frac{1}{2}$ and for each $n \geq 2$ $$a_n = \frac{2 n - 3}{2 n} a_{n-1}.$$ Prove that $\sum^n_{k=1} a_k < 1$ for all $n \geq 1.$

i.) Let $ABC$ be a triangle with $AB = 12$ and $AC = 16.$ Suppose $M$ is the midpoint of side $BC$ and points $E$ and $F$ are chosen on sides $AC$ and $AB$ , respectively, and suppose that lines $EF$ and $AM$ intersect at $G.$ If $AE = 2 \cdot AF$ then find the ratio

$$\frac{EG}{GF}$$

ii.) Let $E$ be a point external to a circle and suppose that two chords $EAB$ and $EDC$ meet at angle of $40^{\circ}.$ If $AB = BC = CD$ find the size of angle $ACD.$

i.) Four balls of radius 1 are mutually tangent, three resting on the floor and the fourth resting on the others. A tedrahedron, each of whose edges has length $s,$ is circumscribed around the balls. Find the value of $s.$

ii.) Suppose that $ABCD$ and $EFGH$ are opposite faces of a retangular solid, with $\angle DHC = 45^{\circ}$ and $\angle FHB = 60^{\circ}.$ Find the cosine of $\angle BHD.$

i.) The polynomial $x^{2 \cdot k} + 1 + (x+1)^{2 \cdot k}$ is not divisible by $x^2 + x + 1.$ Find the value of $k.$

ii.) If $p,q$ and $r$ are distinct roots of $x^3 - x^2 + x - 2 = 0$ the find the value of $p^3 + q^3 + r^3.$

iii.) If $r$ is the remainder when each of the numbers 1059, 1417 and 2312 is divided by $d,$ where $d$ is an integer greater than one, then find the value of $d-r.$

iv.) What is the smallest positive odd integer $n$ such that the product of

$$2^{\frac{1}{7}}, 2^{\frac{3}{7}}, \ldots, 2^{\frac{2 \cdot n + 1}{7}}$$

is greater than 1000?

i.) Let $g(x) = x^5 + x^4 + x^3 + x^2 + x + 1.$ What is the remainder when the polynomial $g(x^{12}$ is divided by the polynomial $g(x)$ ?

ii.) If $k$ is a positive number and $f$ is a function such that, for every positive number $x, f(x^2 + 1 )^{\sqrt{x}} = k.$ Find the value of

$$f( \frac{9 +y^2}{y^2})^{\sqrt{ \frac{12}{y} }}$$ for every positive number $y.$

iii.) The function $f$ satisfies the functional equation $f(x) + f(y) = f(x+y) - x \cdot y - 1$ for every pair $x,y$ of real numbers. If $f(1) = 1,$ then find the numbers of integers $n,$ for which $f(n) = n.$

i.) Consider a circle $K$ with diameter $AB;$ with circle $L$ tangent to $AB$ and to $K$ and with a circle $M$ tangent to circle $K,$ circle $L$ and $AB.$ Calculate the ration of the area of circle $K$ to the area of circle $M.$

ii.) In triangle $ABC, AB = AC$ and $\angle CAB = 80^{\circ}.$ If points $D,E$ and $F$ lie on sides $BC, AC$ and $AB,$ respectively and $CE = CD$ and $BF = BD,$ then find the size of $\angle EDF.$

i.) Calculate $x$ if $$x = \frac{(11 + 6 \cdot \sqrt{2}) \cdot \sqrt{11 - 6 \cdot \sqrt{2}} - (11 - 6 \cdot \sqrt{2}) \cdot \sqrt{11 + 6 \cdot \sqrt{2}}}{(\sqrt{\sqrt{5} + 2} + \sqrt{\sqrt{5} - 2}) - (\sqrt{\sqrt{5}+1})}$$

ii.) For each positive number $x,$ let $$k = \frac{\left( x + \frac{1}{x} \right)^6 - \left( x^6 + \frac{1}{x^6} \right) - 2}{\left( x + \frac{1}{x} \right)^3 - \left( x^3 + \frac{1}{x^3} \right)}$$ Calculate the minimum value of $k.$

Find all plane triangles whose sides have integer length and whose incircles have unit radius.

Let $-1 < x < 1.$ Show that $$\sum^{6}_{k=0} \frac{1 - x^2}{1 - 2 \cdot x \cdot \cos \left( \frac{2 \cdot \pi \cdot k }{7} \right) + x^2} = \frac{7 \cdot \left( 1 + x^7 \right)}{\left( 1 - x^7 \right)}.$$ Deduce that $$\csc^2\left( x + \frac{\pi}{7} \right) + \csc^2\left(2 \cdot x + \frac{\pi}{7} \right) + \csc^2\left(3 \cdot x + \frac{\pi}{7} \right) = 8.$$

Let $g(n)$ be defined as follows: $$g(1) = 0, g(2) = 1$$ and $$g(n+2) = g(n) + g(n+1) + 1, n \geq 1.$$ Prove that if $n > 5$ is a prime, then $n$ divides $g(n) \cdot (g(n) + 1).$

$A_1, A_2, \ldots, A_{29}$ are $29$ different sequences of positive integers. For $1 \leq i < j \leq 29$ and any natural number $x,$ we define $N_i(x) =$ number of elements of the sequence $A_i$ which are less or equal to $x,$ and $N_{ij}(x) =$ number of elements of the intersection $A_i \cap A_j$ which are less than or equal to $x.$ It is given for all $1 \leq i \leq 29$ and every natural number $x,$ $$N_i(x) \geq \frac{x}{e},$$ where $e = 2.71828 \ldots$ Prove that there exist at least one pair $i,j$ ( $1 \leq i < j \leq 29$ ) such that $$N_{ij}(1988) > 200.$$

Prove that the numbers $A,B$ and $C$ are equal, where:

• $A=$ number of ways that we can cover a $2 \times n$ rectangle with $2 \times 1$ retangles.

• $B=$ number of sequences of ones and twos that add up to $n$

• $C= \sum^m_{k=0} \binom{m + k}{2 \cdot k}$ if $n = 2 \cdot m,$ and

• $C= \sum^m_{k=0} \binom{m + k + 1}{2 \cdot k + 1}$ if $n = 2 \cdot m + 1.$

The positive integer $n$ has the property that, in any set of $n$ integers, chosen from the integers $1,2, \ldots, 1988,$ twenty-nine of them form an arithmetic progression. Prove that $n > 1788.$

$ABCD$ is a quadrilateral. $A'BCD'$ is the reflection of $ABCD$ in $BC,$ $A''B'CD'$ is the reflection of $A'BCD'$ in $CD'$ and $A''B''C'D'$ is the reflection of $A''B'CD'$ in $D'A''.$ Show that; if the lines $AA''$ and $BB''$ are parallel, then ABCD is a cyclic quadrilateral.

Given $n$ points $A_1, A_2, \ldots, A_n,$ no three collinear, show that the $n$ - gon $A_1 A_2 \ldots A_n,$ is inscribed in a circle if and only if

$A_1 A_2 \cdot A_3 A_n \cdot \ldots \cdot A_{n-1} A_n + A_2 A_3 \cdot A_4 A_n \cdot \ldots A_{n-1} A_n \cdot A_1 A_n + \ldots$ $+ A_{n-1} A_{n-2} \cdot A_1 A_n \cdot \ldots \cdot A_{n-3} A_n$ $= A_1 A_{n-1} \cdot A_2 A_n \cdot \ldots \cdot A_{n-2} A_n$ ,

where $XY$ denotes the length of the segment $XY.$

Suppose $\alpha_i > 0, \beta_i > 0$ for $1 \leq i \leq n, n > 1$ and that $$\sum^n_{i=1} \alpha_i = \sum^n_{i=1} \beta_i = \pi.$$ Prove that $$\sum^n_{i=1} \frac{\cos(\beta_i)}{\sin(\alpha_i)} \leq \sum^n_{i=1} \cot(\alpha_i).$$

Given a set of 1988 points in the plane. No four points of the set are collinear. The points of a subset with 1788 points are coloured blue, the remaining 200 are coloured red. Prove that there exists a line in the plane such that each of the two parts into which the line divides the plane contains 894 blue points and 100 red points.

$S$ is the set of all sequences $\{a_i| 1 \leq i \leq 7, a_i = 0 \text{ or } 1\}.$ The distance between two elements $\{a_i\}$ and $\{b_i\}$ of $S$ is defined as $$\sum^7_{i = 1} |a_i - b_i|.$$ $T$ is a subset of $S$ in which any two elements have a distance apart greater than or equal to 3. Prove that $T$ contains at most 16 elements. Give an example of such a subset with 16 elements.

For a convex polygon $P$ in the plane let $P'$ denote the convex polygon with vertices at the midpoints of the sides of $P.$ Given an integer $n \geq 3,$ determine sharp bounds for the ratio

$$\frac{\text{area } P'}{\text{area } P},$$ over all convex $n$ -gons $P.$

In $3$ -dimensional space there is given a point $O$ and a finite set $A$ of segments with the sum of lengths equal to $1988$ . Prove that there exists a plane disjoint from $A$ such that the distance from it to $O$ does not exceed $574$ .

Given integers $a_1, \ldots, a_{10},$ prove that there exist a non-zero sequence $\{x_1, \ldots, x_{10}\}$ such that all $x_i$ belong to $\{-1,0,1\}$ and the number $\sum^{10}_{i=1} x_i \cdot a_i$ is divisible by 1001.

Let $x = p, y = q, z = r, w = s$ be the unique solution of the system of linear equations $$x + a_i \cdot y + a^2_i \cdot z + a^3_i \cdot w = a^4_i, i = 1,2,3,4.$$ Express the solutions of the following system in terms of $p,q,r$ and $s:$ $$x + a^2_i \cdot y + a^4_i \cdot z + a^6_i \cdot w = a^8_i, i = 1,2,3,4.$$ Assume the uniquness of the solution.

Find all positive integers $x$ such that the product of all digits of $x$ is given by $x^2 - 10 \cdot x - 22.$

The Fibonacci sequence is defined by $$a_{n+1} = a_n + a_{n-1}, n \geq 1, a_0 = 0, a_1 = a_2 = 1.$$ Find the greatest common divisor of the 1960-th and 1988-th terms of the Fibonacci sequence.

Let $C$ be a cube with edges of length 2. Construct a solid with fourteen faces by cutting off all eight corners at $C,$ keeping the new faces perpendicular to the diagonals of the cube, and keeping the newly formed faces indentical. If at the conclusion of this process the fourteen faces so have the same area, find the area of each of face of the new solid.

For each positive integer $k$ and $n,$ let $S_k(n)$ be the base $k$ digit sum of $n.$ Prove that there are at most two primes $p$ less than $20,000$ for which $S_{31}(p)$ are composite numbers with at least two distinct prime divisors.

In a group of $n$ people, each one knows exactly three others. They are seated around a table. We say that the seating is $perfect$ if everyone knows the two sitting by their sides. Show that, if there is a perfect seating $S$ for the group, then there is always another perfect seating which cannot be obtained from $S$ by rotation or reflection.

$ABC$ is a triangle, with inradius $r$ and circumradius $R.$ Show that: $$\sin \left( \frac{A}{2} \right) \cdot \sin \left( \frac{B}{2} \right) + \sin \left( \frac{B}{2} \right) \cdot \sin \left( \frac{C}{2} \right) + \sin \left( \frac{C}{2} \right) \cdot \sin \left( \frac{A}{2} \right) \leq \frac{5}{8} + \frac{r}{4 \cdot R}.$$

The quadrilateral $A_1A_2A_3A_4$ is cyclic, and its sides are $a_1 = A_1A_2, a_2 = A_2A_3, a_3 = A_3A_4$ and $a_4 = A_4A_1.$ The respective circles with centres $I_i$ and radii $r_i$ are tangent externally to each side $a_i$ and to the sides $a_{i+1}$ and $a_{i-1}$ extended. ( $a_0 = a_4$ ). Show that $$\prod^4_{i=1} \frac{a_i}{r_i} = 4 \cdot (\csc (A_1) + \csc (A_2) )^2.$$

Consider $h+1$ chess boards. Number the squares of each board from 1 to 64 in such a way that when the perimeters of any two boards of the collection are brought into coincidence in any possible manner, no two squares in the same position have the same number. What is the maximum value of $h?$

A two-person game is played with nine boxes arranged in a $3 \times 3$ square and with white and black stones. At each move a player puts three stones, not necessarily of the same colour, in three boxes in either a horizontal or a vertical line. No box can contain stones of different colours: if, for instance, a player puts a white stone in a box containing black stones the white stone and one of the black stones are removed from the box. The game is over when the centrebox and the cornerboxes contain one black stone and the other boxes are empty. At one stage of a game $x$ boxes contained one black stone each and the other boxes were empty. Determine all possible values for $x.$

Let $S$ be an infinite set of integers containing zero, and such that the distances between successive number never exceed a given fixed number. Consider the following procedure: Given a set $X$ of integers we construct a new set consisting of all numbers $x \pm s,$ where $x$ belongs to $X$ and s belongs to $S.$ Starting from $S_0 = \{0\}$ we successively construct sets $S_1, S_2, S_3, \ldots$ using this procedure. Show that after a finite number of steps we do not obtain any new sets, i.e. $S_k = S_{k_0}$ for $k \geq k_0.$

It is proposed to partition a set of positive integers into two disjoint subsets $A$ and $B$ subject to the conditions

i.) 1 is in $A$ ii.) no two distinct members of $A$ have a sum of the form $2^k + 2, k = 0,1,2, \ldots;$ and iii.) no two distinct members of B have a sum of that form.

Show that this partitioning can be carried out in unique manner and determine the subsets to which 1987, 1988 and 1989 belong.

There are $n \geq 3$ job openings at a factory, ranked $1$ to $n$ in order of increasing pay. There are $n$ job applicants, ranked from $1$ to $n$ in order of increasing ability. Applicant $i$ is qualified for job $j$ if and only if $i \geq j.$ The applicants arrive one at a time in random order. Each in turn is hired to the highest-ranking job for which he or she is qualified AND which is lower in rank than any job already filled. (Under these rules, job $1$ is always filled, and hiring terminates thereafter.) Show that applicants $n$ and $n - 1$ have the same probability of being hired.

The triangle $ABC$ has a right angle at $C.$ The point $P$ is located on segment $AC$ such that triangles $PBA$ and $PBC$ have congruent inscribed circles. Express the length $x = PC$ in terms of $a = BC, b = CA$ and $c = AB.$

Let $a,b,c$ be integers different from zero. It is known that the equation $a \cdot x^2 + b \cdot y^2 + c \cdot z^2 = 0$ has a solution $(x,y,z)$ in integer numbers different from the solutions $x = y = z = 0.$ Prove that the equation $$a \cdot x^2 + b \cdot y^2 + c \cdot z^2 = 1$$ has a solution in rational numbers.

In a row written in increasing order all the irreducible positive rational numbers, such that the product of the numerator and the denominator is less than 1988. Prove that any two adjacent fractions $\frac{a}{b}$ and $\frac{c}{d},$ $\frac{a}{b} < \frac{c}{d},$ satisfy the equation $b \cdot c - a \cdot d = 1.$

Seven circles are given. That is, there are six circles inside a fixed circle, each tangent to the fixed circle and tangent to the two other adjacent smaller circles. If the points of contact between the six circles and the larger circle are, in order, $A_1, A_2, A_3, A_4, A_5$ and $A_6$ prove that $$A_1 A_2 \cdot A_3 A_4 \cdot A_5 A_6 = A_2 A_3 \cdot A_4 A_5 \cdot A_6 A_1.$$

We match sets $M$ of points in the coordinate plane to sets $M*$ according to the rule that $(x*,y*) \in M*$ if and only if $x \cdot x* + y \cdot y* \leq 1$ whenever $(x,y) \in M.$ Find all triangles $Q$ such that $Q*$ is the reflection of $Q$ in the origin.

Does there exist a number $\alpha, 0 < \alpha < 1$ such that there is an infinite sequence $\{a_n\}$ of positive numbers satisfying $$1 + a_{n+1} \leq a_n + \frac{\alpha}{n} \cdot \alpha_n, n = 1,2, \ldots?$$

A regular 14-gon with side $a$ is inscribed in a circle of radius one. Prove $$\frac{2-a}{2 \cdot a} > \sqrt{3 \cdot \cos \left( \frac{\pi}{7} \right)}.$$

Let $p \geq 2$ be a natural number. Prove that there exist an integer $n_0$ such that $$\sum^{n_0}_{i=1} \frac{1}{i \cdot \sqrt[p]{i + 1}} > p.$$

Given a natural number $n,$ find all polynomials $P(x)$ of degree less than $n$ satisfying the following condition $$\sum^n_{i=0} P(i) \cdot (-1)^i \cdot \binom{n}{i} = 0.$$

Let $n+1, n \geq 1$ positive integers be formed by taking the product of $n$ given prime numbers (a prime number can appear several times or also not appear at all in a product formed in this way.) Prove that among these $n+1$ one can find some numbers whose product is a perfect square.