ISL 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<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)>\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>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.

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 $\operatorname{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$.

Let $A B C D E F$ be a convex hexagon all of whose sides are tangent to a circle $\omega$ with center $O$. Suppose that the circumcircle of triangle $A C E$ is concentric with $\omega$. Let $J$ be the foot of the perpendicular from $B$ to $C D$. Suppose that the perpendicular from $B$ to $D F$ intersects the line $E O$ at a point $K$. Let $L$ be the foot of the perpendicular from $K$ to $D E$. Prove that $D J=D L$.

Let $A B C$ be an acute triangle with circumcircle $\omega$. Let $t$ be a tangent line to $\omega$. Let $t_{a}, t_{b}$, and $t_{c}$ be the lines obtained by reflecting $t$ in the lines $B C, C A$, and $A B$, respectively. Show that the circumcircle of the triangle determined by the lines $t_{a}, t_{b}$, and $t_{c}$ is tangent to the circle $\omega$. To avoid a large case distinction, we will use the notion of oriented angles. Namely, for two lines $\ell$ and $m$, we denote by $\angle(\ell, m)$ the angle by which one may rotate $\ell$ anticlockwise to obtain a line parallel to $m$. Thus, all oriented angles are considered modulo $180^{\circ}$.

For any integer $d>0$, let $f(d)$ be the smallest positive integer that has exactly $d$ positive divisors (so for example we have $f(1)=1, f(5)=16$, and $f(6)=12$ ). Prove that for every integer $k \geq 0$ the number $f\left(2^{k}\right)$ divides $f\left(2^{k+1}\right)$.

Consider a polynomial $P(x)=\left(x+d_{1}\right)\left(x+d_{2}\right) \cdot \ldots \cdot\left(x+d_{9}\right)$, where $d_{1}, d_{2}, \ldots, d_{9}$ are nine distinct integers. Prove that there exists an integer $N$ such that for all integers $x \geq N$ the number $P(x)$ is divisible by a prime number greater than 20 .

Let $n \geq 1$ be an odd integer. Determine all functions $f$ from the set of integers to itself such that for all integers $x$ and $y$ the difference $f(x)-f(y)$ divides $x^{n}-y^{n}$.

For each positive integer $k$, let $t(k)$ be the largest odd divisor of $k$. Determine all positive integers $a$ for which there exists a positive integer $n$ such that all the differences $$t(n+a)-t(n), t(n+a+1)-t(n+1), \ldots, t(n+2 a-1)-t(n+a-1)$$ are divisible by 4 .

Let $f$ be a function from the set of integers to the set of positive integers. Suppose that for any two integers $m$ and $n$, the difference $f(m)-f(n)$ is divisible by $f(m-n)$. Prove that for all integers $m, n$ with $f(m) \leq f(n)$ the number $f(n)$ is divisible by $f(m)$.

Let $P(x)$ and $Q(x)$ be two polynomials with integer coefficients such that no nonconstant polynomial with rational coefficients divides both $P(x)$ and $Q(x)$. Suppose that for every positive integer $n$ the integers $P(n)$ and $Q(n)$ are positive, and $2^{Q(n)}-1$ divides $3^{P(n)}-1$. Prove that $Q(x)$ is a constant polynomial.

Let $p$ be an odd prime number. For every integer $a$, define the number $$S_{a}=\frac{a}{1}+\frac{a^{2}}{2}+\cdots+\frac{a^{p-1}}{p-1}$$ Let $m$ and $n$ be integers such that $$S_{3}+S_{4}-3 S_{2}=\frac{m}{n}$$ Prove that $p$ divides $m$.

Let $k$ be a positive integer and set $n=2^{k}+1$. Prove that $n$ is a prime number if and only if the following holds: there is a permutation $a_{1}, \ldots, a_{n-1}$ of the numbers $1,2, \ldots, n-1$ and a sequence of integers $g_{1}, g_{2}, \ldots, g_{n-1}$ such that $n$ divides $g_{i}^{a_{i}}-a_{i+1}$ for every $i \in\{1,2, \ldots, n-1\}$, where we set $a_{n}=a_{1}$.