Question bank IMO Shortlist 1977

(BUL 2) IMO6. Let $f:\mathbb N\to\mathbb N$ be a function that satisfies the inequality $f(n+1)>f(f(n))$ for all $n\in\mathbb N$. Prove that $f(n)=n$ for all natural numbers $n$.

(CZS 1) A lattice point in the plane is a point both of whose coordinates are integers. Each lattice point has four neighboring points: upper, lower, left, and right. Let $k$ be a circle with radius $r\ge2$, that does not pass through any lattice point. An interior boundary point is a lattice point lying inside the circle $k$ that has a neighboring point lying outside $k$. Similarly, an exterior boundary point is a lattice point lying outside the circle $k$ that has a neighboring point lying inside $k$. Prove that there are four more exterior boundary points than interior boundary points.

(FRG 1) IMO5. Let $a$ and $b$ be natural numbers and let $q$ and $r$ be the quotient and remainder respectively when $a^2+b^2$ is divided by $a+b$. Determine the numbers $a$ and $b$ if $q^2+r=1977$.

(FRG 4) Describe all closed bounded figures $\Phi$ in the plane any two points of which are connectable by a semicircle lying in $\Phi$.

(FRG 5) There are $2^n$ words of length $n$ over the alphabet $\{0,1\}$. Prove that the following algorithm generates the sequence $w_0,w_1,\ldots,w_{2^n-1}$ of all these words such that any two consecutive words differ in exactly one digit.
(1) $w_0=00\ldots0$ ($n$ zeros).
(2) Suppose $w_{m-1}=a_1a_2\ldots a_n$, $a_i\in\{0,1\}$. Let $e(m)$ be the exponent of $2$ in the representation of $n$ as a product of primes, and let $j=1+e(m)$. Replace the digit $a_j$ in the word $w_{m-1}$ by $1-a_j$. The obtained word is $w_m$.

(GDR 2) Let $n$ be a positive integer. How many integer solutions $(i,j,k,l)$, $1\le i,j,k,l\le n$, does the following system of inequalities have:
$$\begin{aligned}1&\le-j+k+l\le n\\1&\le i-k+l\le n\\1&\le i-j+l\le n\\1&\le i+j-k\le n\ ?\end{aligned}$$

(GBR 2) IMO4. Let $a,b,A,B$ be given constant real numbers and
$$f(x)=1-a\cos x-b\sin x-A\cos2x-B\sin2x.$$
Prove that if $f(x)\ge0$ for all real $x$, then
$$a^2+b^2\le2\qquad A^2+B^2\le1.$$

(GBR 4) Let $S$ be a convex quadrilateral $ABCD$ and $O$ a point inside it. The feet of the perpendiculars from $O$ to $AB,BC,CD,DA$ are $A_1,B_1,C_1,D_1$ respectively. The feet of the perpendiculars from $O$ to the sides of $S_i$, the quadrilateral $A_iB_iC_iD_i$, are $A_{i+1}B_{i+1}C_{i+1}D_{i+1}$, where $i=1,2,3$. Prove that $S_4$ is similar to $S$.

(HUN 1) For which positive integers $n$ do there exist two polynomials $f$ and $g$ with integer coefficients of $n$ variables $x_1,x_2,\ldots,x_n$ such that the following equality is satisfied:
$$\left(\sum_{i=1}^n x_i\right)f(x_1,x_2,\ldots,x_n)=g(x_1^2,x_2^2,\ldots,x_n^2)?$$

(NET 2) IMO3. Let $n$ be an integer greater than $2$. Define $V=\{1+kn\mid k=1,2,\ldots\}$. A number $p\in V$ is called indecomposable in $V$ if it is not possible to find numbers $q_1,q_2\in V$ such that $q_1q_2=p$. Prove that there exists a number $N\in V$ that can be factorized into indecomposable factors in $V$ in more than one way.

(NET 3) Let $n$ be an integer greater than $1$. Define
$$x_1=n,\quad y_1=1,\quad x_{i+1}=\left[\frac{x_i+y_i}{2}\right],\quad y_{i+1}=\left[\frac n{x_{i+1}}\right]\qquad i=1,2,\ldots,$$
where $[z]$ denotes the largest integer less than or equal to $z$. Prove that
$$\min\{x_1,x_2,\ldots,x_n\}=[\sqrt n].$$

(NET 4) IMO1. On the sides of a square $ABCD$ one constructs inwardly equilateral triangles $ABK,BCL,CDM,DAN$. Prove that the midpoints of the four segments $KL,LM,MN,NK$, together with the midpoints of the eight segments $AK,BK,BL,CL,CM,DM,DN,AN$, are the $12$ vertices of a regular dodecagon.

(POL 4) Let $B$ be a set of $k$ sequences each having $n$ terms equal to $1$ or $-1$. The product of two such sequences $(a_1,a_2,\ldots,a_n)$ and $(b_1,b_2,\ldots,b_n)$ is defined as $(a_1b_1,a_2b_2,\ldots,a_nb_n)$. Prove that there exists a sequence $(c_1,c_2,\ldots,c_n)$ such that the intersection of $B$ and the set containing all sequences from $B$ multiplied by $(c_1,c_2,\ldots,c_n)$ contains at most $k^2/2^n$ sequences.

(FIN 2′) Let $E$ be a finite set of points such that $E$ is not contained in a plane and no three points of $E$ are collinear. Show that at least one of the following alternatives holds:
(i) $E$ contains five points that are vertices of a convex pyramid having no other points in common with $E$;
(ii) some plane contains exactly three points from $E$.

(VIE 1) IMO2. The length of a finite sequence is defined as the number of terms of this sequence. Determine the maximal possible length of a finite sequence that satisfies the following condition: The sum of each seven successive terms is negative, and the sum of each eleven successive terms is positive.

(VIE 3) Let $E$ be a set of $n$ points in the plane $(n\ge3)$ whose coordinates are integers such that any three points from $E$ are vertices of a nondegenerate triangle whose centroid doesn't have both coordinates integers. Determine the maximal $n$.