Question bank IMO Shortlist 1993

(BRA 1) Show that there exists a finite set $A\subset\mathbb R^2$ such that for every $X\in A$ there are points $Y_1,Y_2,\ldots,Y_{1993}$ in $A$ such that the distance between $X$ and $Y_i$ is equal to $1$, for every $i$.

(CAN 2) Let triangle $ABC$ be such that its circumradius $R$ is equal to $1$. Let $r$ be the inradius of $ABC$ and let $p$ be the inradius of the orthic triangle $A'B'C'$ of triangle $ABC$.
Prove that $p\le1-\frac13(1+r)^2$.
Remark. The orthic triangle is the triangle whose vertices are the feet of the altitudes of $ABC$.

(SPA 1) Consider the triangle $ABC$, its circumcircle $k$ with center $O$ and radius $R$, and its incircle with center $I$ and radius $r$. Another circle $k_c$ is tangent to the sides $CA,CB$ at $D,E$, respectively, and it is internally tangent to $k$.

Show that the incenter $I$ is the midpoint of $DE$.

(SPA 2) In the triangle $ABC$, let $D,E$ be points on the side $BC$ such that $\angle BAD=\angle CAE$. If $M,N$ are, respectively, the points of tangency with $BC$ of the incircles of the triangles $ABD$ and $ACE$, show that
$$\frac1{MB}+\frac1{MD}=\frac1{NC}+\frac1{NE}.$$

(FIN 3; IMO 3) On an infinite chessboard, a solitaire game is played as follows: At the start, we have $n^2$ pieces occupying $n^2$ squares that form a square of side $n$. The only allowed move is a jump horizontally or vertically over an occupied square to an unoccupied one, and the piece that has been jumped over is removed. For what positive integers $n$ can the game end with only one piece remaining on the board?

(GER 1; IMO 5) Let $\mathbb N=\{1,2,3,\ldots\}$. Determine whether there exists a strictly increasing function $f:\mathbb N\to\mathbb N$ with the following properties:
$$f(1)=2;\tag{1}$$
$$f(f(n))=f(n)+n\qquad(n\in\mathbb N).\tag{2}$$

(GEO 3) Let $a,b,c$ be given integers $a\gt 0$, $ac-b^2=P=P_1\cdots P_m$ where $P_1,\ldots,P_m$ are (distinct) prime numbers. Let $M(n)$ denote the number of pairs of integers $(x,y)$ for which
$$ax^2+2bxy+cy^2=n.$$
Prove that $M(n)$ is finite and $M(n)=M(P^k\cdot n)$ for every integer $k\ge0$.

(IND 1) Define a sequence $\langle f(n)\rangle_{n=1}^\infty$ of positive integers by $f(1)=1$ and
$$f(n)=\begin{cases}f(n-1)-n,&f(n-1)\gt n;\\f(n-1)+n,&f(n-1)\le n,\end{cases}$$
for $n\ge2$. Let $S=\{n\in\mathbb N\mid f(n)=1993\}$.
(a) Prove that $S$ is an infinite set.
(b) Find the least positive integer in $S$.
(c) If all the elements of $S$ are written in ascending order as $n_1\lt n_2\lt n_3\lt \cdots$, show that
$$\lim_{i\to\infty}\frac{n_{i+1}}{n_i}=3.$$

(IND 4)
(a) Show that the set $\mathbb Q^+$ of all positive rational numbers can be partitioned into three disjoint subsets $A,B,C$ satisfying the following conditions:
$$BA=B,\qquad B^2=C,\qquad BC=A,$$
where $HK$ stands for the set $\{hk\mid h\in H,k\in K\}$ for any two subsets $H,K$ of $\mathbb Q^+$ and $H^2$ stands for $HH$.
(b) Show that all positive rational cubes are in $A$ for such a partition of $\mathbb Q^+$.
(c) Find such a partition $\mathbb Q^+=A\cup B\cup C$ with the property that for no positive integer $n\le34$ are both $n$ and $n+1$ in $A$; that is,
$$\min\{n\in\mathbb N\mid n\in A,n+1\in A\}\gt 34.$$

(IND 5) A natural number $n$ is said to have the property $P$ if whenever $n$ divides $a^n-1$ for some integer $a$, $n^2$ also necessarily divides $a^n-1$.
(a) Show that every prime number has property $P$.
(b) Show that there are infinitely many composite numbers $n$ that possess property $P$.

(IRE 1; IMO 1) Let $n\gt 1$ be an integer and let $f(x)=x^n+5x^{n-1}+3$. Prove that there do not exist polynomials $g(x),h(x)$, each having integer coefficients and degree at least one, such that $f(x)=g(x)h(x)$.

(IRE 2) Let $n,k$ be positive integers with $k\le n$ and let $S$ be a set containing $n$ distinct real numbers. Let $T$ be the set of all real numbers of the form $x_1+x_2+\cdots+x_k$, where $x_1,x_2,\ldots,x_k$ are distinct elements of $S$. Prove that $T$ contains at least $k(n-k)+1$ distinct elements.

(IRE 3) Let $S$ be the set of all pairs $(m,n)$ of relatively prime positive integers $m,n$ with $n$ even and $m\lt n$. For $s=(m,n)\in S$ write $n=2^kn_0$, where $k,n_0$ are positive integers with $n_0$ odd and define $f(s)=(n_0,m+n-n_0)$.
Prove that $f$ is a function from $S$ to $S$ and that for each $s=(m,n)\in S$, there exists a positive integer $t\le\frac{m+n+1}{4}$ such that $f^t(s)=s$, where
$$f^t(s)=(\underbrace{f\circ f\circ\cdots\circ f}_{t})(s).$$
The underbrace indicates $t$ compositions.
If $m+n$ is a prime number that does not divide $2^k-1$ for $k=1,2,\ldots,m+n-2$, prove that the smallest value of $t$ that satisfies the above conditions is $\left[\frac{m+n+1}{4}\right]$, where $[x]$ denotes the greatest integer less than or equal to $x$.

(ISR 1) The vertices $D,E,F$ of an equilateral triangle lie on the sides $BC,CA,AB$ respectively of a triangle $ABC$. If $a,b,c$ are the respective lengths of these sides, and $S$ the area of $ABC$, prove that
$$DE\ge\frac{2\sqrt2S}{\sqrt{a^2+b^2+c^2+4\sqrt3S}}.$$

(MCD 1; IMO 4) For three points $A,B,C$ in the plane we define $m(ABC)$ to be the smallest length of the three altitudes of the triangle $ABC$, where in the case of $A,B,C$ collinear, $m(ABC)=0$. Let $A,B,C$ be given points in the plane. Prove that for any point $X$ in the plane,
$$m(ABC)\le m(ABX)+m(AXC)+m(XBC).$$

(MCD 3) Let $n\in\mathbb N$, $n\ge2$, and $A_0=(a_{01},a_{02},\ldots,a_{0n})$ be any $n$-tuple of natural numbers such that $0\le a_{0i}\le i-1$, for $i=1,\ldots,n$. The $n$-tuples $A_1=(a_{11},a_{12},\ldots,a_{1n})$, $A_2=(a_{21},a_{22},\ldots,a_{2n}),\ldots$ are defined by
$$a_{i+1,j}=\operatorname{Card}\{a_{i,l}\mid1\le l\le j-1,\ a_{i,l}\ge a_{i,j}\},\qquad i\in\mathbb N,\ j=1,\ldots,n.$$
Prove that there exists $k\in\mathbb N$ such that $A_{k+2}=A_k$.

(NET 2; IMO 6) Let $n$ be an integer greater than $1$. In a circular arrangement of $n$ lamps $L_0,\ldots,L_{n-1}$, each one of that can be either ON or OFF, we start with the situation where all lamps are ON, and then carry out a sequence of steps, $\mathrm{Step}_0,\mathrm{Step}_1,\ldots$. If $L_{j-1}$ ($j$ is taken mod $n$) is ON, then $\mathrm{Step}_j$ changes the status of $L_j$ (it goes from ON to OFF or from OFF to ON) but does not change the status of any of the other lamps. If $L_{j-1}$ is OFF, then $\mathrm{Step}_j$ does not change anything at all. Show that:
(a) There is a positive integer $M(n)$ such that after $M(n)$ steps all lamps are ON again.
(b) If $n$ has the form $2^k$, then all lamps are ON after $n^2-1$ steps.
(c) If $n$ has the form $2^k+1$, then all lamps are ON after $n^2-n+1$ steps.

(POL 1) Let $S_n$ be the number of sequences $(a_1,a_2,\ldots,a_n)$, where $a_i\in\{0,1\}$, in which no six consecutive blocks are equal. Prove that $S_n\to\infty$ as $n\to\infty$.

(ROM 2) Let $a,b,n$ be positive integers, $b\gt 1$ and $b^n-1\mid a$. Show that the representation of the number $a$ in the base $b$ contains at least $n$ digits different from zero.

(ROM 3) Let $c_1,\ldots,c_n\in\mathbb R$ ($n\ge2$) such that $0\le\sum_{i=1}^n c_i\le n$. Show that we can find integers $k_1,\ldots,k_n$ such that $\sum_{i=1}^n k_i=0$ and
$$1-n\le c_i+nk_i\le n$$
for every $i=1,\ldots,n$.