Question bank IMO Shortlist 2001

Let $T$ denote the set of all ordered triples $(p, q, r)$ of nonnegative integers. Find all functions $f: T \to \mathbb{R}$ such that

$$f(p,q,r)=\begin{cases}0,&pqr=0,\\1+\frac16\bigl(f(p+1,q-1,r)+f(p-1,q+1,r)+f(p-1,q,r+1)+f(p+1,q,r-1)+f(p,q+1,r-1)+f(p,q-1,r+1)\bigr),&pqr\ne0.\end{cases}$$

Let $a_0, a_1, a_2, \ldots$ be an arbitrary infinite sequence of positive numbers. Show that the inequality $1 + a_n \gt a_{n-1}\sqrt[n]{2}$ holds for infinitely many positive integers $n$.

Let $x_{1}, x_{2}, \ldots, x_{n}$ be arbitrary real numbers. Prove the inequality

$$ \frac{x_{1}}{1+x_{1}^{2}}+\frac{x_{2}}{1+x_{1}^{2}+x_{2}^{2}}+\cdots+\frac{x_{n}}{1+x_{1}^{2}+\cdots+x_{n}^{2}} \lt \sqrt{n}. $$

Find all functions $ f: \mathbb{R} \to \mathbb{R} $, satisfying

$$ f(xy)(f(x)-f(y))=(x-y)f(x)f(y) $$

for all $x, y$.

Find all positive integers $ a_{1}, a_{2}, \ldots, a_{n} $ such that

$$ \frac{99}{100}=\frac{a_{0}}{a_{1}}+\frac{a_{1}}{a_{2}}+\cdots+\frac{a_{n-1}}{a_{n}}, $$

where $ a_{0}=1 $ and $ (a_{k+1}-1)a_{k-1}\geq a_{k}^{2}(a_{k}-1) $ for $ k=1,2,\ldots,n-1 $.

Prove that for all positive real numbers $a, b, c$,

$$ \frac{a}{\sqrt{a^{2}+8bc}}+\frac{b}{\sqrt{b^{2}+8ca}}+\frac{c}{\sqrt{c^{2}+8ab}}\geq1. $$

Let $ A = (a_1, a_2, \ldots, a_{2001}) $ be a sequence of positive integers. Let m be the number of 3-element subsequences $ (a_i, a_j, a_k) $ with $ 1 \leq i \lt j \lt k \leq 2001 $, such that $ a_j = a_i + 1 $ and $ a_k = a_j + 1 $. Considering all such sequences A, find the greatest value of m.

Let $n$ be an odd integer greater than 1 and let $c_1, c_2, \ldots, c_n$ be integers. For each permutation $a = (a_1, a_2, \ldots, a_n)$ of $\{1, 2, \ldots, n\}$, define $S(a) = \sum_{i=1}^{n} c_i a_i$. Prove that there exist permutations $a \neq b$ of $\{1, 2, \ldots, n\}$ such that $n!$ is a divisor of $S(a) - S(b)$.

Define a k-clique to be a set of k people such that every pair of them are acquainted with each other. At a certain party, every pair of 3-cliques has at least one person in common, and there are no 5-cliques. Prove that there are two or fewer people at the party whose departure leaves no 3-clique remaining.

A set of three nonnegative integers $\{x, y, z\}$ with $x \lt y \lt z$ is called historic if $\{z - y, y - x\} = \{1776, 2001\}$. Show that the set of all nonnegative integers can be written as the union of pairwise disjoint historic sets.

Find all finite sequences $(x_0, x_1, \ldots, x_n)$ such that for every $j, 0 \leq j \leq n$, $x_j$ equals the number of times $j$ appears in the sequence.

For a positive integer n define a sequence of zeros and ones to be balanced if it contains n zeros and n ones. Two balanced sequences a and b are neighbors if you can move one of the 2n symbols of a to another position to form b. For instance, when n = 4, the balanced sequences 01101001 and 00110101 are neighbors because the third (or fourth) zero in the first sequence can be moved to the first or second position to form the second sequence. Prove that there is a set S of at most $ \frac{1}{n+1}\binom{2n}{n} $ balanced sequences such that every balanced sequence is equal to or is a neighbor of at least one sequence in S.

A pile of n pebbles is placed in a vertical column. This configuration is modified according to the following rules. A pebble can be moved if it is at the top of a column which contains at least two more pebbles than the column immediately to its right. (If there are no pebbles to the right, think of this as a column with 0 pebbles.) At each stage, choose a pebble from among those that can be moved (if there are any) and place it at the top of the column to its right. If no pebbles can be moved, the configuration is called a final configuration. For each n, show that, no matter what choices are made at each stage, the final configuration obtained is unique. Describe that configuration in terms of n.

Alternative Version. A pile of 2001 pebbles is placed in a vertical column. This configuration is modified according to the following rules. A pebble can be moved if it is at the top of a column which contains at least two more pebbles than the column immediately to its right. (If there are no pebbles to the right, think of this as a column with 0 pebbles.) At each stage, choose a pebble from among those that can be moved (if there are any) and place it at the top of the column to its right. If no pebbles can be moved, the configuration is called a final configuration. Show that, no matter what choices are made at each stage, the final configuration obtained is unique. Describe that configuration as follows: Determine the number, $c$, of nonempty columns, and for each $i = 1, 2, \ldots, c$, determine the number of pebbles $p_i$ in column $i$, where column 1 is the leftmost column, column 2 the next to the right, and so on.

Twenty-one girls and twenty-one boys took part in a mathematical competition. It turned out that

(a) each contestant solved at most six problems, and

(b) for each pair of a girl and a boy, there was at least one problem that was solved by both the girl and the boy.

Show that there is a problem that was solved by at least three girls and at least three boys.

Let $A_{1}$ be the center of the square inscribed in acute triangle $ABC$ with two vertices of the square on side $BC$. Thus one of the two remaining vertices of the square is on side $AB$ and the other is on $AC$. Points $B_{1}, C_{1}$ are defined in a similar way for inscribed squares with two vertices on sides $AC$ and $AB$, respectively. Prove that lines $AA_{1}, BB_{1}, CC_{1}$ are concurrent.

In acute triangle $ABC$ with circumcenter $O$ and altitude $AP, \angle C \geq \angle B + 30^\circ$. Prove that $\angle A + \angle COP \lt 90^\circ$.

Let $ABC$ be a triangle with centroid $G$. Determine, with proof, the position of the point $P$ in the plane of $ABC$ such that $AP\cdot AG+BP\cdot BG+CP\cdot CG$ is a minimum, and express this minimum value in terms of the side lengths of $ABC$.

Let M be a point in the interior of triangle ABC. Let $ A' $ lie on BC with $ MA' $ perpendicular to BC. Define $ B' $ on CA and $ C' $ on AB similarly. Define

$$ p(M)=\frac{MA^{\prime}\cdot MB^{\prime}\cdot MC^{\prime}}{MA\cdot MB\cdot MC}. $$

Determine, with proof, the location of $M$ such that $p(M)$ is maximal. Let $\mu(ABC)$ denote this maximum value. For which triangles $ABC$ is the value of $\mu(ABC)$ maximal?

Let $ABC$ be an acute triangle. Let $DAC, EAB$, and $FBC$ be isosceles triangles exterior to $ABC$, with $DA = DC, EA = EB$, and $FB = FC$, such that

$$ \angle ADC=2\angle BAC,\quad\angle BEA=2\angle ABC,\quad\angle CFB=2\angle ACB. $$

Let $D'$ be the intersection of lines $DB$ and $EF$, let $E'$ be the intersection of $EC$ and $DF$, and let $F'$ be the intersection of $FA$ and $DE$. Find, with proof, the value of the sum

$$ \frac{DB}{DD^{\prime}}+\frac{EC}{EE^{\prime}}+\frac{FA}{FF^{\prime}}. $$

Let $ABC$ be a triangle and $P$ an exterior point in the plane of the triangle. Suppose $AP, BP, CP$ meet the sides $BC, CA, AB$ (or extensions thereof) in $D, E, F$, respectively. Suppose further that the areas of triangles $PBD, PCE, PAF$ are all equal. Prove that each of these areas is equal to the area of triangle $ABC$ itself.