Question bank IMO Shortlist 2011

For any set $A=\left\{a_{1}, a_{2}, a_{3}, a_{4}\right\}$ of four distinct positive integers with sum $s_{A}=a_{1}+a_{2}+a_{3}+a_{4}$, let $p_{A}$ denote the number of pairs $(i, j)$ with $1 \leq i\lt j \leq 4$ for which $a_{i}+a_{j}$ divides $s_{A}$. Among all sets of four distinct positive integers, determine those sets $A$ for which $p_{A}$ is maximal.

Determine all sequences $\left(x_{1}, x_{2}, \ldots, x_{2011}\right)$ of positive integers such that for every positive integer $n$ there is an integer $a$ with

$$
x_{1}^{n}+2 x_{2}^{n}+\cdots+2011 x_{2011}^{n}=a^{n+1}+1 .
$$

Determine all pairs $(f, g)$ of functions from the set of real numbers to itself that satisfy

$$
g(f(x+y))=f(x)+(2 x+y) g(y)
$$

for all real numbers $x$ and $y$.

Determine all pairs $(f, g)$ of functions from the set of positive integers to itself that satisfy

$$
f^{g(n)+1}(n)+g^{f(n)}(n)=f(n+1)-g(n+1)+1
$$

for every positive integer $n$. Here, $f^{k}(n)$ means $\underbrace{f(f(\ldots f}_{k}(n) \ldots))$.

Prove that for every positive integer $n$, the set $\{2,3,4, \ldots, 3 n+1\}$ can be partitioned into $n$ triples in such a way that the numbers from each triple are the lengths of the sides of some obtuse triangle.

Let $f$ be a function from the set of real numbers to itself that satisfies

$$
f(x+y) \leq y f(x)+f(f(x))
$$

for all real numbers $x$ and $y$. Prove that $f(x)=0$ for all $x \leq 0$.

Let $a, b$, and $c$ be positive real numbers satisfying $\min (a+b, b+c, c+a)\gt \sqrt{2}$ and $a^{2}+b^{2}+c^{2}=3$. Prove that

$$
\frac{a}{(b+c-a)^{2}}+\frac{b}{(c+a-b)^{2}}+\frac{c}{(a+b-c)^{2}} \geq \frac{3}{(a b c)^{2}}
$$

Let $n\gt 0$ be an integer. We are given a balance and $n$ weights of weight $2^{0}, 2^{1}, \ldots, 2^{n-1}$. In a sequence of $n$ moves we place all weights on the balance. In the first move we choose a weight and put it on the left pan. In each of the following moves we choose one of the remaining weights and we add it either to the left or to the right pan. Compute the number of ways in which we can perform these $n$ moves in such a way that the right pan is never heavier than the left pan.

Suppose that 1000 students are standing in a circle. Prove that there exists an integer $k$ with $100 \leq k \leq 300$ such that in this circle there exists a contiguous group of $2 k$ students, for which the first half contains the same number of girls as the second half.

Let $\mathcal{S}$ be a finite set of at least two points in the plane. Assume that no three points of $\mathcal{S}$ are collinear. By a windmill we mean a process as follows. Start with a line $\ell$ going through a point $P \in \mathcal{S}$. Rotate $\ell$ clockwise around the pivot $P$ until the line contains another point $Q$ of $\mathcal{S}$. The point $Q$ now takes over as the new pivot. This process continues indefinitely, with the pivot always being a point from $\mathcal{S}$.

Show that for a suitable $P \in \mathcal{S}$ and a suitable starting line $\ell$ containing $P$, the resulting windmill will visit each point of $\mathcal{S}$ as a pivot infinitely often.

Determine the greatest positive integer $k$ that satisfies the following property: The set of positive integers can be partitioned into $k$ subsets $A_{1}, A_{2}, \ldots, A_{k}$ such that for all integers $n \geq 15$ and all $i \in\{1,2, \ldots, k\}$ there exist two distinct elements of $A_{i}$ whose sum is $n$.

Let $m$ be a positive integer and consider a checkerboard consisting of $m$ by $m$ unit squares. At the midpoints of some of these unit squares there is an ant. At time 0 , each ant starts moving with speed 1 parallel to some edge of the checkerboard. When two ants moving in opposite directions meet, they both turn $90^{\circ}$ clockwise and continue moving with speed 1 . When more than two ants meet, or when two ants moving in perpendicular directions meet, the ants continue moving in the same direction as before they met. When an ant reaches one of the edges of the checkerboard, it falls off and will not re-appear.

Considering all possible starting positions, determine the latest possible moment at which the last ant falls off the checkerboard or prove that such a moment does not necessarily exist.

Let $n$ be a positive integer and let $W=\ldots x_{-1} x_{0} x_{1} x_{2} \ldots$ be an infinite periodic word consisting of the letters $a$ and $b$. Suppose that the minimal period $N$ of $W$ is greater than $2^{n}$.

A finite nonempty word $U$ is said to appear in $W$ if there exist indices $k \leq \ell$ such that $U=x_{k} x_{k+1} \ldots x_{\ell}$. A finite word $U$ is called ubiquitous if the four words $U a, U b, a U$, and $b U$ all appear in $W$. Prove that there are at least $n$ ubiquitous finite nonempty words.

On a square table of 2011 by 2011 cells we place a finite number of napkins that each cover a square of 52 by 52 cells. In each cell we write the number of napkins covering it, and we record the maximal number $k$ of cells that all contain the same nonzero number. Considering all possible napkin configurations, what is the largest value of $k$ ?

Let $A B C$ be an acute triangle. Let $\omega$ be a circle whose center $L$ lies on the side $B C$. Suppose that $\omega$ is tangent to $A B$ at $B^{\prime}$ and to $A C$ at $C^{\prime}$. Suppose also that the circumcenter $O$ of the triangle $A B C$ lies on the shorter arc $B^{\prime} C^{\prime}$ of $\omega$. Prove that the circumcircle of $A B C$ and $\omega$ meet at two points.

Let $A_{1} A_{2} A_{3} A_{4}$ be a non-cyclic quadrilateral. Let $O_{1}$ and $r_{1}$ be the circumcenter and the circumradius of the triangle $A_{2} A_{3} A_{4}$. Define $O_{2}, O_{3}, O_{4}$ and $r_{2}, r_{3}, r_{4}$ in a similar way. Prove that

$$
\frac{1}{O_{1} A_{1}^{2}-r_{1}^{2}}+\frac{1}{O_{2} A_{2}^{2}-r_{2}^{2}}+\frac{1}{O_{3} A_{3}^{2}-r_{3}^{2}}+\frac{1}{O_{4} A_{4}^{2}-r_{4}^{2}}=0
$$

Let $A B C D$ be a convex quadrilateral whose sides $A D$ and $B C$ are not parallel. Suppose that the circles with diameters $A B$ and $C D$ meet at points $E$ and $F$ inside the quadrilateral. Let $\omega_{E}$ be the circle through the feet of the perpendiculars from $E$ to the lines $A B, B C$, and $C D$. Let $\omega_{F}$ be the circle through the feet of the perpendiculars from $F$ to the lines $C D, D A$, and $A B$. Prove that the midpoint of the segment $E F$ lies on the line through the two intersection points of $\omega_{E}$ and $\omega_{F}$.

Let $A B C$ be an acute triangle with circumcircle $\Omega$. Let $B_{0}$ be the midpoint of $A C$ and let $C_{0}$ be the midpoint of $A B$. Let $D$ be the foot of the altitude from $A$, and let $G$ be the centroid of the triangle $A B C$. Let $\omega$ be a circle through $B_{0}$ and $C_{0}$ that is tangent to the circle $\Omega$ at a point $X \neq A$. Prove that the points $D, G$, and $X$ are collinear.

Let $A B C$ be a triangle with incenter $I$ and circumcircle $\omega$. Let $D$ and $E$ be the second intersection points of $\omega$ with the lines $A I$ and $B I$, respectively. The chord $D E$ meets $A C$ at a point $F$, and $B C$ at a point $G$. Let $P$ be the intersection point of the line through $F$ parallel to $A D$ and the line through $G$ parallel to $B E$. Suppose that the tangents to $\omega$ at $A$ and at $B$ meet at a point $K$. Prove that the three lines $A E, B D$, and $K P$ are either parallel or concurrent.

Let $A B C$ be a triangle with $A B=A C$, and let $D$ be the midpoint of $A C$. The angle bisector of $\angle B A C$ intersects the circle through $D, B$, and $C$ in a point $E$ inside the triangle $A B C$. The line $B D$ intersects the circle through $A, E$, and $B$ in two points $B$ and $F$. The lines $A F$ and $B E$ meet at a point $I$, and the lines $C I$ and $B D$ meet at a point $K$. Show that $I$ is the incenter of triangle $K A B$.