Question bank IMO Shortlist 1994

A1 (USA) Let $a_0=1994$ and $a_{n+1}=\frac{a_n^2}{a_n+1}$ for each nonnegative integer $n$. Prove that $1994-n$ is the greatest integer less than or equal to $a_n$, $0\le n\le998$.

A2 (FRA), IMO1. Let $m$ and $n$ be positive integers. The set $A=\{a_1,a_2,\ldots,a_m\}$ is a subset of $\{1,2,\ldots,n\}$. Whenever $a_i+a_j\le n$, $1\le i\le j\le m$, $a_i+a_j$ also belongs to $A$. Prove that
$$\frac{a_1+a_2+\cdots+a_m}{m}\ge\frac{n+1}{2}.$$

A3 (GBR), IMO5. Let $S$ be the set of real numbers greater than $-1$. Find all functions $f:S\to S$ such that
$$f(x+f(y)+xf(y))=y+f(x)+yf(x)$$
for all $x$ and $y$ in $S$, and $f(x)/x$ is strictly increasing for $-1\lt x\lt 0$ and for $0\lt x$.

A4 (MON) Let $\mathbb R$ denote the set of all real numbers and $\mathbb R^+$ the subset of all positive ones. Let $\alpha$ and $\beta$ be given elements in $\mathbb R$, not necessarily distinct. Find all functions $f:\mathbb R^+\to\mathbb R$ such that
$$f(x)f(y)=y^\alpha f\left(\frac x2\right)+x^\beta f\left(\frac y2\right)\qquad(x,y\in\mathbb R^+).$$

A5 (POL) Let $f(x)=\frac{x^2+1}{2x}$ for $x\ne0$. Define $f^{(0)}(x)=x$ and $f^{(n)}(x)=f(f^{(n-1)}(x))$ for all positive integers $n$ and $x\ne0$. Prove that for all nonnegative integers $n$ and $x\ne-1,0,$ or $1$,
$$\frac{f^{(n)}(x)}{f^{(n+1)}(x)}=1+\frac1{f\left(\left(\frac{x+1}{x-1}\right)^{2^n}\right)}.$$

C1 (UKR) On a $5\times5$ board, two players alternately mark numbers on empty cells. The first player always marks $1$'s, the second $0$'s. One number is marked per turn, until the board is filled. For each of the nine $3\times3$ squares the sum of the nine numbers on its cells is computed. Denote by $A$ the maximum of these sums. How large can the first player make $A$, regardless of the responses of the second player?

C2 (COL) In a certain city, age is reckoned in terms of real numbers rather than integers. Every two citizens $x$ and $x'$ either know each other or do not know each other. Moreover, if they do not, then there exists a chain of citizens $x=x_0,x_1,\ldots,x_n=x'$ for some integer $n\ge2$ such that $x_{i-1}$ and $x_i$ know each other. In a census, all male citizens declare their ages and there is at least one male citizen. Each female citizen provides only the information that her age is the average of the ages of all the citizens she knows. Prove that this is enough to determine uniquely the ages of all the female citizens.

C3 (MCD) Peter has three accounts in a bank, each with an integral number of dollars. He is only allowed to transfer money from one account to another so that the amount of money in the latter is doubled.
(a) Prove that Peter can always transfer all his money into two accounts.
(b) Can Peter always transfer all his money into one account?

C4 (EST) There are $n+1$ fixed positions in a row, labeled $0$ to $n$ in increasing order from right to left. Cards numbered $0$ to $n$ are shuffled and dealt, one in each position. The object of the game is to have card $i$ in the $i$th position for $0\le i\le n$. If this has not been achieved, the following move is executed. Determine the smallest $k$ such that the $k$th position is occupied by a card $l\gt k$. Remove this card, slide all cards from the $(k+1)$th to the $l$th position one place to the right, and replace the card $l$ in the $l$th position.
(a) Prove that the game lasts at most $2^n-1$ moves.
(b) Prove that there exists a unique initial configuration for which the game lasts exactly $2^n-1$ moves.

C5 (SWE) At a round table are $1994$ girls, playing a game with a deck of $n$ cards. Initially, one girl holds all the cards. In each turn, if at least one girl holds at least two cards, one of these girls must pass a card to each of her two neighbors. The game ends when and only when each girl is holding at most one card.
(a) Prove that if $n\ge1994$, then the game cannot end.
(b) Prove that if $n\lt 1994$, then the game must end.

C6 (FIN) On an infinite square grid, two players alternately mark symbols on empty cells. The first player always marks $X$'s, the second $O$'s. One symbol is marked per turn. The first player wins if there are $11$ consecutive $X$'s in a row, column, or diagonal. Prove that the second player can prevent the first from winning.

C7 (BRA) Prove that for any integer $n\ge2$, there exists a set of $2^{n-1}$ points in the plane such that no $3$ lie on a line and no $2n$ are the vertices of a convex $2n$-gon.

G1 (FRA) A semicircle $\Gamma$ is drawn on one side of a straight line $l$. $C$ and $D$ are points on $\Gamma$. The tangents to $\Gamma$ at $C$ and $D$ meet $l$ at $B$ and $A$ respectively, with the center of the semicircle between them. Let $E$ be the point of intersection of $AC$ and $BD$, and $F$ the point on $l$ such that $EF$ is perpendicular to $l$. Prove that $EF$ bisects $\angle CFD$.

G2 (UKR) $ABCD$ is a quadrilateral with $BC$ parallel to $AD$. $M$ is the midpoint of $CD$, $P$ that of $MA$ and $Q$ that of $MB$. The lines $DP$ and $CQ$ meet at $N$. Prove that $N$ is not outside triangle $ABM$.

Source footnote 8: This problem is false. However, it is true if “not outside $ABM$” is replaced by “not outside $ABCD$”.

G3 (RUS) A circle $\omega$ is tangent to two parallel lines $l_1$ and $l_2$. A second circle $\omega_1$ is tangent to $l_1$ at $A$ and to $\omega$ externally at $C$. A third circle $\omega_2$ is tangent to $l_2$ at $B$, to $\omega$ externally at $D$, and to $\omega_1$ externally at $E$. $AD$ intersects $BC$ at $Q$. Prove that $Q$ is the circumcenter of triangle $CDE$.

G4 (AUS-ARM), IMO2. $N$ is an arbitrary point on the bisector of $\angle BAC$. $P$ and $O$ are points on the lines $AB$ and $AN$, respectively, such that $\angle ANP=90^\circ=\angle APO$. $Q$ is an arbitrary point on $NP$, and an arbitrary line through $Q$ meets the lines $AB$ and $AC$ at $E$ and $F$ respectively. Prove that $\angle OQE=90^\circ$ if and only if $QE=QF$.

G5 (CYP) A line $l$ does not meet a circle $\omega$ with center $O$. $E$ is the point on $l$ such that $OE$ is perpendicular to $l$. $M$ is any point on $l$ other than $E$. The tangents from $M$ to $\omega$ touch it at $A$ and $B$. $C$ is the point on $MA$ such that $EC$ is perpendicular to $MA$. $D$ is the point on $MB$ such that $ED$ is perpendicular to $MB$. The line $CD$ cuts $OE$ at $F$. Prove that the location of $F$ is independent of that of $M$.

N1 (BUL) $M$ is a subset of $\{1,2,3,\ldots,15\}$ such that the product of any three distinct elements of $M$ is not a square. Determine the maximum number of elements in $M$.

N2 (AUS), IMO4. Determine all pairs $(m,n)$ of positive integers such that $\frac{n^3+1}{mn-1}$ is an integer.

N3 (FIN), IMO6. Find a set $A$ of positive integers such that for any infinite set $P$ of prime numbers, there exist positive integers $m\in A$ and $n\notin A$, both the product of the same number of distinct elements of $P$.