ISL 1989

Prove the identity

$$1 + \frac{1}{2} - \frac{2}{3} + \frac{1}{4} + \frac{1}{5} - \frac{2}{6} + \ldots + \frac{1}{478} + \frac{1}{479} - \frac{2}{480} = 2 \cdot \sum^{159}_{k=0} \frac{641}{(161+k) \cdot (480-k)}.$$

Connecting the vertices of a regular $n$ -gon we obtain a closed (not necessarily convex) $n$ -gon. Show that if $n$ is even, then there are two parallel segments among the connecting segments and if $n$ is odd then there cannot be exactly two parallel segments.

A sequence of real numbers $x_0, x_1, x_2, \ldots$ is defined as follows: $x_0 = 1989$ and for each $n \geq 1$

$$x_n = - \frac{1989}{n} \sum^{n-1}_{k=0} x_k.$$

Calculate the value of $\sum^{1989}_{n=0} 2^n x_n.$

Alice has two urns. Each urn contains four balls and on each ball a natural number is written. She draws one ball from each urn at random, notes the sum of the numbers written on them, and replaces the balls in the urns from which she took them. This she repeats a large number of times. Bill, on examining the numbers recorded, notices that the frequency with which each sum occurs is the same as if it were the sum of two natural numbers drawn at random from the range 1 to 4. What can he deduce about the numbers on the balls?

Let $f(x) = a \sin^2x + b \sin x + c,$ where $a, b,$ and $c$ are real numbers. Find all values of $a, b$ and $c$ such that the following three conditions are satisfied simultaneously:

(i) $f(x) = 381$ if $\sin x = \frac{1}{2}.$ (ii) The absolute maximum of $f(x)$ is $444.$ (iii) The absolute minimum of $f(x)$ is $364.$

Let $A$ and $B$ be fixed distinct points on the $X$ axis, none of which coincides with the origin $O(0, 0),$ and let $C$ be a point on the $Y$ axis of an orthogonal Cartesian coordinate system. Let $g$ be a line through the origin $O(0, 0)$ and perpendicular to the line $AC.$ Find the locus of the point of intersection of the lines $g$ and $BC$ if $C$ varies along the $Y$ axis. Give an equation and a description of the locus.

The expressions $a + b + c, ab + ac + bc,$ and $abc$ are called the elementary symmetric expressions on the three letters $a, b, c;$ symmetric because if we interchange any two letters, say $a$ and $c,$ the expressions remain algebraically the same. The common degree of its terms is called the order of the expression. Let $S_k(n)$ denote the elementary expression on $k$ different letters of order $n;$ for example $S_4(3) = abc + abd + acd + bcd.$ There are four terms in $S_4(3).$ How many terms are there in $S_{9891}(1989)?$ (Assume that we have $9891$ different letters.)

Given two distinct numbers $b_1$ and $b_2$ , their product can be formed in two ways: $b_1 \times b_2$ and $b_2 \times b_1.$ Given three distinct numbers, $b_1, b_2, b_3,$ their product can be formed in twelve ways:

$b_1\times(b_2 \times b_3);$ $(b_1 \times b_2) \times b_3;$ $b_1 \times (b_3 \times b_2);$ $(b_1 \times b_3) \times b_2;$ $b_2 \times (b_1 \times b_3);$ $(b_2 \times b_1) \times b_3;$ $b_2 \times(b_3 \times b_1);$ $(b_2 \times b_3)\times b_1;$ $b_3 \times(b_1 \times b_2);$ $(b_3 \times b_1)\times b_2;$ $b_3 \times(b_2 \times b_1);$ $(b_3 \times b_2) \times b_1.$

In how many ways can the product of $n$ distinct letters be formed?

Let $(\log_2(x))^2 - 4 \cdot \log_2(x) - m^2 - 2m - 13 = 0$ be an equation in $x.$ Prove:(a) For any real value of $m$ the equation has two distinct solutions.(b) The product of the solutions of the equation does not depend on $m.$ (c) One of the solutions of the equation is less than 1, while the other solution is greater than 1.

Find the minimum value of the larger solution and the maximum value of the smaller solution.

Let S be the point of intersection of the two lines $l_1 : 7x - 5y + 8 = 0$ and $l_2 : 3x + 4y - 13 = 0.$ Let $P = (3, 7), Q = (11, 13),$ and let $A$ and $B$ be points on the line $PQ$ such that $P$ is between $A$ and $Q,$ and $B$ is between $P$ and $Q,$ and such that $$\frac{PA}{AQ} = \frac{PB}{BQ} = \frac{2}{3}.$$ Without finding the coordinates of $B$ find the equations of the lines $SA$ and $SB.$

Let $A,B$ denote two distinct fixed points in space. Let $X, P$ denote variable points (in space), while $K,N, n$ denote positive integers. Call $(X,K,N,P)$ admissible if $$(N - K) \cdot PA + K \cdot PB \geq N \cdot PX.$$ Call $(X,K,N)$ admissible if $(X,K,N,P)$ is admissible for all choices of $P.$ Call $(X,N)$ admissible if $(X,K,N)$ is admissible for some choice of $K$ in the interval $0 < K < N.$ Finally, call $X$ admissible if $(X,N)$ is admissible for some choice of $N, (N > 1).$ Determine:

(a) the set of admissible $X;$ (b) the set of $X$ for which $(X, 1989)$ is admissible but not $(X, n), n < 1989.$

Let $t(n)$ for $n = 3, 4, 5, \ldots,$ represent the number of distinct, incongruent, integer-sided triangles whose perimeter is $n;$ e.g., $t(3) = 1.$ Prove that

$$t(2n-1) - t(2n) = \left[ \frac{6}{n} \right] \text{ or } \left[ \frac{6}{n} + 1 \right].$$

Let $f(x) = \prod^n_{k=1} (x - a_k) - 2,$ where $n \geq 3$ and $a_1, a_2, \ldots,$ an are distinct integers. Suppose that $f(x) = g(x)h(x),$ where $g(x), h(x)$ are both nonconstant polynomials with integer coefficients. Prove that $n = 3.$

Let $f$ be a function from the real numbers to the real numbers such that $f(1) = 1, f(a+b) = f(a)+f(b)$ for all $a, b,$ and $f(x)f \left( \frac{1}{x} \right) = 1$ for all $x \neq 0.$ Prove that $f(x) = x$ for all real numbers $x.$

Let $\alpha$ be the positive root of the equation $x^2 - 1989x - 1 = 0.$ Prove that there exist infinitely many natural numbers $n$ that satisfy the equation:

$$\lfloor \alpha n + 1989 \alpha \lfloor \alpha n \rfloor \rfloor = 1989n + \left( 1989^2 + 1 \right) \lfloor \alpha n \rfloor.$$

Let $n = 2k - 1$ where $k \geq 6$ is an integer. Let $T$ be the set of all $n-$ tuples $(x_1, x_2, \ldots, x_n)$ where $x_i \in \{0,1\}$ $\forall i = \{1,2, \ldots, n\}$ For $x = (x_1, x_2, \ldots, x_n) \in T$ and $y = (y_1, y_2, \ldots, y_n) \in T$ let $d(x,y)$ denote the number of integers $j$ with $1 \leq j \leq n$ such that $x_i \neq x_j$ , in particular $d(x,x) = 0.$ Suppose that there exists a subset $S$ of $T$ with $2^k$ elements that has the following property: Given any element $x \in T,$ there is a unique element $y \in S$ with $d(x, y) \leq 3.$ Prove that $n = 23.$

Let $P_1(x), P_2(x), \ldots, P_n(x)$ be real polynomials, i.e. they have real coefficients. Show that there exist real polynomials $A_r(x),B_r(x) (r = 1, 2, 3)$ such that

$$\sum^n_{s=1} \left\{ P_s(x) \right \}^2 \equiv \left( A_1(x) \right)^2 + \left( B_1(x) \right)^2$$ $$\sum^n_{s=1} \left\{ P_s(x) \right \}^2 \equiv \left( A_2(x) \right)^2 + x \left( B_2(x) \right)^2$$ $$\sum^n_{s=1} \left\{ P_s(x) \right \}^2 \equiv \left( A_3(x) \right)^2 - x \left( B_3(x) \right)^2$$

Let $v_1, v_2, \ldots, v_{1989}$ be a set of coplanar vectors with $|v_r| \leq 1$ for $1 \leq r \leq 1989.$ Show that it is possible to find $\epsilon_r$ , $1 \leq r \leq 1989,$ each equal to $\pm 1,$ such that $$\left | \sum^{1989}_{r=1} \epsilon_r v_r \right | \leq \sqrt{3}.$$

A regular $n-$ gon $A_1A_2A_3 \cdots A_k \cdots A_n$ inscribed in a circle of radius $R$ is given. If $S$ is a point on the circle, calculate $$T = \sum^n_{k=1} SA^2_k.$$

A family of sets $A_1, A_2, \ldots ,A_n$ has the following properties:

(i) Each $A_i$ contains 30 elements. (ii) $A_i \cap A_j$ contains exactly one element for all $i, j, 1 \leq i < j \leq n.$

Determine the largest possible $n$ if the intersection of all these sets is empty.

Prove for $0 < k \leq 1$ and $a_i \in \mathbb{R}^+,$ $i = 1,2 \ldots, n$ the following inequality holds:

$$\left( \frac{a_1}{a_2 + \ldots + a_n} \right)^k + \ldots + \left( \frac{a_n}{a_1 + \ldots + a_{n-1}} \right)^k \geq \frac{n}{(n-1)^k}.$$

Let $l_i,$ $i = 1,2,3$ be three non-collinear straight lines in the plane, which build a triangle, and $f_i$ the axial reflections in $l_i$ . Prove that for each point $P$ in the plane there exists finite interconnections (compositions) of the reflections of $f_i$ which carries $P$ into the triangle built by the straight lines $l_i,$ i.e. maps that point to a point interior to the triangle.

Let $ABCD$ be a quadrilateral inscribed in a circle of radius $AB$ such that $BC = a, CD = b,$ $DA = \frac{3 \sqrt{3} - 1}{2} \cdot a$ For each point $M$ on the semicircle with radius $AB$ not containing $C$ and $D,$ denote by $h_1, h_2, h_3$ the distances from $M$ to the straight lines (sides) $BC, CD,$ and $DA.$ Find the maximum of $h_1 + h_2 + h_3.$

Let $k$ and $s$ be positive integers. For sets of real numbers $\{\alpha_1, \alpha_2, \ldots , \alpha_s\}$ and $\{\beta_1, \beta_2, \ldots, \beta_s\}$ that satisfy

$$\sum^s_{i=1} \alpha^j_i = \sum^s_{i=1} \beta^j_i \forall j = \{1,2 \ldots, k\}$$

we write $$\{\alpha_1, \alpha_2, \ldots , \alpha_s\} \overset{k}{=} \{\beta_1, \beta_2, \ldots , \beta_s\}.$$

Prove that if $$\{\alpha_1, \alpha_2, \ldots , \alpha_s\} \overset{k}{=} \{\beta_1, \beta_2, \ldots , \beta_s\}$$ and $s \leq k,$ then there exists a permutation $\pi$ of $\{1, 2, \ldots , s\}$ such that

$$\beta_i = \alpha_{\pi(i)} \forall i = 1,2, \ldots, s.$$

Given that $$\frac{\cos(x) + \cos(y) + \cos(z)}{\cos(x+y+z)} = \frac{\sin(x)+ \sin(y) + \sin(z)}{\sin(x + y + z)} = a,$$ show that $$\cos(y+z) + \cos(z+x) + \cos(x+y) = a.$$

To each pair $(x, y)$ of distinct elements of a finite set $X$ a number $f(x, y)$ equal to 0 or 1 is assigned in such a way that $f(x, y) \neq f(y, x)$ $\forall x,y$ and $x \neq y.$ Prove that exactly one of the following situations occurs:

(i) $X$ is the union of two disjoint nonempty subsets $U, V$ such that $f(u, v) = 1$ $\forall u \in U, v \in V.$

(ii) The elements of $X$ can be labeled $x_1, \ldots , x_n$ so that $$f(x_1, x_2) = f(x_2, x_3) = \cdots = f(x_{n-1}, x_n) = f(x_n, x_1) = 1.$$

Alternative formulation:

In a tournament of n participants, each pair plays one game (no ties). Prove that exactly one of the following situations occurs:

(i) The league can be partitioned into two nonempty groups such that each player in one of these groups has won against each player of the other. (ii) All participants can be ranked 1 through $n$ so that $i-$ th player wins the game against the $(i + 1)$ st and the $n-$ th player wins against the first.

We are given a finite collection of segments in the plane, of total length 1. Prove that there exists a line $l$ such that the sum of the lengths of the projections of the given segments to the line $l$ is less than $\frac{2}{\pi}.$

Solve in the set of real numbers the equation $$3x^3 - [x] = 3,$$ where $[x]$ denotes the integer part of $x.$

Poldavia is a strange kingdom. Its currency unit is the bourbaki and there exist only two types of coins: gold ones and silver ones. Each gold coin is worth $n$ bourbakis and each silver coin is worth $m$ bourbakis ( $n$ and $m$ are positive integers). Using gold and silver coins, it is possible to obtain sums such as 10000 bourbakis, 1875 bourbakis, 3072 bourbakis, and so on. But Poldavia's monetary system is not as strange as it seems:

(a) Prove that it is possible to buy anything that costs an integral number of bourbakis, as long as one can receive change. (b) Prove that any payment above $mn-2$ bourbakis can be made without the need to receive change.

Let $a, b, c, r,$ and $s$ be real numbers. Show that if $r$ is a root of $ax^2+bx+c = 0$ and s is a root of $-ax^2+bx+c = 0,$ then $$\frac{a}{2} x^2 + bx + c = 0$$ has a root between $r$ and $s.$

Let $P(x)$ be a polynomial with integer coefficients such that $$P(m_1) = P(m_2) = P(m_3) = P(m_4) = 7$$ for given distinct integers $m_1,m_2,m_3,$ and $m_4.$ Show that there is no integer m such that $P(m) = 14.$

Given two natural numbers $w$ and $n,$ the tower of $n$ $w's$ is the natural number $T_n(w)$ defined by

$$T_n(w) = w^{w^{\cdots^{w}}},$$

with $n$ $w's$ on the right side. More precisely, $T_1(w) = w$ and $T_{n+1}(w) = w^{T_n(w)}.$ For example, $T_3(2) = 2^{2^2} = 16,$ $T_4(2) = 2^{16} = 65536,$ and $T_2(3) = 3^3 = 27.$ Find the smallest tower of $3's$ that exceeds the tower of $1989$ $2's.$ In other words, find the smallest value of $n$ such that $T_n(3) > T_{1989}(2).$ Justify your answer.

A balance has a left pan, a right pan, and a pointer that moves along a graduated ruler. Like many other grocer balances, this one works as follows: An object of weight $L$ is placed in the left pan and another of weight $R$ in the right pan, the pointer stops at the number $R - L$ on the graduated ruler. There are $n, (n \geq 2)$ bags of coins, each containing $\frac{n(n-1)}{2} + 1$ coins. All coins look the same (shape, color, and so on). $n-1$ bags contain real coins, all with the same weight. The other bag (we don't know which one it is) contains false coins. All false coins have the same weight, and this weight is different from the weight of the real coins. A legal weighing consists of placing a certain number of coins in one of the pans, putting a certain number of coins in the other pan, and reading the number given by the pointer in the graduated ruler. With just two legal weighings it is possible to identify the bag containing false coins. Find a way to do this and explain it.

A real-valued function $f$ on $\mathbb{Q}$ satisfies the following conditions for arbitrary $\alpha, \beta \in \mathbb{Q}:$ (i) $f(0) = 0,$ (ii) $f(\alpha) > 0 \text{ if } \alpha \neq 0,$ (iii) $f(\alpha \cdot \beta) = f(\alpha)f(\beta),$ (iv) $f(\alpha + \beta) \leq f(\alpha) + f(\beta),$ (v) $f(m) \leq 1989$ $\forall m \in \mathbb{Z}.$ Prove that $$f(\alpha + \beta) = \max\{f(\alpha), f(\beta)\} \text{ if } f(\alpha) \neq f(\beta).$$

Let $A$ be a set of positive integers such that no positive integer greater than 1 divides all the elements of $A.$ Prove that any sufficiently large positive integer can be written as a sum of elements of $A.$ (Elements may occur several times in the sum.)

Let a regular $(2n +1)-$ gon be inscribed in a circle of radius $r.$ We consider all the triangles whose vertices are from those of the regular $(2n + 1)-$ gon.

(a) How many triangles among them contain the center of the circle in their interior?

(b) Find the sum of the areas of all those triangles that contain the center of the circle in their interior.

Prove that the sequence $(a_n)_{n \geq 0,}, a_n = [n \cdot \sqrt{2}],$ contains an infinite number of perfect squares.

Find the set of all $a \in \mathbb{R}$ for which there is no infinite sequene $(x_n)_{n \geq 0} \subset \mathbb{R}$ satisfying $x_0 = a,$ and for $n = 0,1, \ldots$ we have $$x_{n+1} = \frac{x_n + \alpha}{\beta x_n + 1}$$ where $\alpha \beta > 0.$

For $\phi: \mathbb{N} \mapsto \mathbb{Z}$ let us define $$M_{\phi} = \{f: \mathbb{N} \mapsto \mathbb{Z}, f(x) > f(\phi(x)), \forall x \in \mathbb{N} \}.$$ Prove that if $M_{\phi_1} = M_{\phi_2} \neq \emptyset,$ then $\phi_1 = \phi_2.$ Does this property remain true if $$M_{\phi} = \{f: \mathbb{N} \mapsto \mathbb{N}, f(x) > f(\phi(x)), \forall x \in \mathbb{N} \}?$$

Prove that $a < b$ implies that $a^3 - 3a \leq b^3 - 3b + 4.$ When does equality occur?

Let $n$ be a positive integer, $X = \{1, 2, \ldots , n\},$ and $k$ a positive integer such that $\frac{n}{2} \leq k \leq n.$ Determine, with proof, the number of all functions $f : X \mapsto X$ that satisfy the following conditions:

(i) $f^2 = f;$ (ii) the number of elements in the image of $f$ is $k;$ (iii) for each $y$ in the image of $f,$ the number of all points $x \in X$ such that $f(x)=y$ is at most $2.$

Let $f : \mathbb{N} \mapsto \mathbb{N}$ be such that

(i) $f$ is strictly increasing; (ii) $f(mn) = f(m)f(n) \forall m, n \in \mathbb{N};$ and (iii) if $m \neq n$ and $m^n = n^m,$ then $f(m) = n$ or $f(n) = m.$

Determine $f(30).$

An arithmetic function is a real-valued function whose domain is the set of positive integers. Define the convolution product of two arithmetic functions $f$ and $g$ to be the arithmetic function $f * g$ , where $$(f * g)(n) = \sum_{ij=n} f(i) \cdot g(j),$$ and $f^{*k} = f * f * \ldots * f$ ( $k$ times) We say that two arithmetic functions $f$ and $g$ are dependent if there exists a nontrivial polynomial of two variables $P(x, y) = \sum_{i,j} a_{ij} x^i y^j$ with real coefficients such that

$$P(f,g) = \sum_{i,j} a_{ij} f^{*i} * g^{*j} = 0,$$

and say that they are independent if they are not dependent. Let $p$ and $q$ be two distinct primes and set

$$f_1(n) = \begin{cases} 1 & \text{ if } n = p, 0 & \text{ otherwise}. \end{cases}$$

$$f_2(n) = \begin{cases} 1 & \text{ if } n = q, 0 & \text{ otherwise}. \end{cases}$$

Prove that $f_1$ and $f_2$ are independent.

Let $A$ be an $n \times n$ matrix whose elements are non-negative real numbers. Assume that $A$ is a non-singular matrix and all elements of $A^{-1}$ are non-negative real numbers. Prove that every row and every column of $A$ has exactly one non-zero element.

Let $ABC$ be an equilateral triangle and $\Gamma$ the semicircle drawn exteriorly to the triangle, having $BC$ as diameter. Show that if a line passing through $A$ trisects $BC,$ it also trisects the arc $\Gamma.$