IMO 1988 - Shortlisted problems

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

(BUL 3) Let $n$ be a positive integer. Find the number of odd coefficients of the polynomial $$u_n(x)=(x^2+x+1)^n.$$

(CAN 1) The triangle $ABC$ is inscribed in a circle. The interior bisectors of the angles $A$, $B$, and $C$ meet the circle again at $A'$, $B'$, and $C'$ respectively. Prove that the area of triangle $A'B'C'$ is greater than or equal to the area of triangle $ABC$.

(CZS 1) An $n\times n$ chessboard $(n\ge2)$ is numbered by the numbers $1,2,\ldots,n^2$ (every number occurs once). Prove that there exist two neighboring (which share a common edge) squares such that their numbers differ by at least $n$.

(CZS 2) IMO2 Let $n$ be an even positive integer. Let $A_1,A_2,\ldots,A_{n+1}$ be sets having $n$ elements each such that any two of them have exactly one element in common while every element of their union belongs to at least two of the given sets. For which $n$ can one assign to every element of the union one of the numbers $0$ and $1$ in such a manner that each of the sets has exactly $n/2$ zeros?

(CZS 3) In a given tetrahedron $ABCD$ let $K$ and $L$ be the centers of edges $AB$ and $CD$ respectively. Prove that every plane that contains the line $KL$ divides the tetrahedron into two parts of equal volume.

(FRA 2) Let $a$ be the greatest positive root of the equation $x^3-3x^2+1=0$. Show that $[a^{1788}]$ and $[a^{1988}]$ are both divisible by $17$. ($[x]$ denotes the integer part of $x$.)

(FRA 3) Let $u_1,u_2,\ldots,u_m$ be $m$ vectors in the plane, each of length less than or equal to $1$, which add up to zero. Show that one can rearrange $u_1,u_2,\ldots,u_m$ as a sequence $v_1,v_2,\ldots,v_m$ such that each partial sum $v_1,v_1+v_2,v_1+v_2+v_3,\ldots,v_1+v_2+\cdots+v_m$ has length less than or equal to $\sqrt5$.

(FRG 1) IMO6 Let $a$ and $b$ be two positive integers such that $ab+1$ divides $a^2+b^2$. Show that $\frac{a^2+b^2}{ab+1}$ is a perfect square.

(GDR 1) Let $N=\{1,2,\ldots,n\}$, $n\ge2$. A collection $F=\{A_1,\ldots,A_t\}$ of subsets $A_i\subseteq N$, $i=1,\ldots,t$, is said to be separating if for every pair $\{x,y\}\subseteq N$, there is a set $A_i\in F$ such that $A_i\cap\{x,y\}$ contains just one element. A collection $F$ is said to be covering if every element of $N$ is contained in at least one set $A_i\in F$. What is the smallest value $f(n)$ of $t$ such that there is a set $F=\{A_1,\ldots,A_t\}$ that is simultaneously separating and covering?

(GDR 3) The lock on a safe consists of three wheels, each of which may be set in eight different positions. Due to a defect in the safe mechanism the door will open if any two of the three wheels are in the correct position. What is the smallest number of combinations that must be tried if one is to guarantee being able to open the safe (assuming that the “right combination” is not known)?

(GRE 2) In a triangle $ABC$, choose any points $K\in BC$, $L\in AC$, $M\in AB$, $N\in LM$, $R\in MK$, and $F\in KL$. If $E_1,E_2,E_3,E_4,E_5,E_6$, and $E$ denote the areas of the triangles $AMR$, $CKR$, $BKF$, $ALF$, $BNM$, $CLN$, and $ABC$ respectively, show that $$E\ge8\sqrt[6]{E_1E_2E_3E_4E_5E_6}.$$ Remark. Points $K,L,M,N,R,F$ lie on segments $BC,AC,AB,LM,MK,KL$ respectively.

(GRE 3) IMO5 In a right-angled triangle $ABC$, let $AD$ be the altitude drawn to the hypotenuse and let the straight line joining the incenters of the triangles $ABD$, $ACD$ intersect the sides $AB$, $AC$ at the points $K$, $L$ respectively. If $E$ and $E_1$ denote the areas of the triangles $ABC$ and $AKL$ respectively, show that $\frac{E}{E_1}\ge2$.

(HUN 1) For what values of $n$ does there exist an $n\times n$ array of entries $-1$, $0$, or $1$ such that the $2n$ sums obtained by summing the elements of the rows and the columns are all different?

(ICE 1) Let $ABC$ be an acute-angled triangle. Three lines $L_A$, $L_B$, and $L_C$ are constructed through the vertices $A$, $B$, and $C$ respectively according to the following prescription: Let $H$ be the foot of the altitude drawn from the vertex $A$ to the side $BC$; let $S_A$ be the circle with diameter $AH$; let $S_A$ meet the sides $AB$ and $AC$ at $M$ and $N$ respectively, where $M$ and $N$ are distinct from $A$; then $L_A$ is the line through $A$ perpendicular to $MN$. The lines $L_B$ and $L_C$ are constructed similarly. Prove that $L_A$, $L_B$, and $L_C$ are concurrent.

(IRE 1) IMO4 Show that the solution set of the inequality $$\sum_{k=1}^{70}\frac{k}{x-k}\ge\frac54$$ is a union of disjoint intervals the sum of whose lengths is $1988$.

(ISR 2) In the convex pentagon $ABCDE$, the sides $BC$, $CD$, $DE$ have the same length. Moreover, each diagonal of the pentagon is parallel to a side ($AC$ is parallel to $DE$, $BD$ is parallel to $AE$, etc.). Prove that $ABCDE$ is a regular pentagon.

(LUX 1) IMO1 Consider two concentric circles of radii $R$ and $r$ $(R\gt r)$ with center $O$. Fix $P$ on the small circle and consider the variable chord $PA$ of the small circle. Points $B$ and $C$ lie on the large circle; $B,P,C$ are collinear and $BC$ is perpendicular to $AP$.

(a) For what value(s) of $\angle OPA$ is the sum $BC^2+CA^2+AB^2$ extremal?

(b) What are the possible positions of the midpoints $U$ of $BA$ and $V$ of $AC$ as $\angle OPA$ varies?

(MEX 1) Let $f(n)$ be a function defined on the set of all positive integers and having its values in the same set. Suppose that $f(f(m)+f(n))=m+n$ for all positive integers $n,m$. Find all possible values for $f(1988)$.

(MON 4) Find the least natural number $n$ such that if the set $\{1,2,\ldots,n\}$ is arbitrarily divided into two nonintersecting subsets, then one of the subsets contains three distinct numbers such that the product of two of them equals the third.