ISL 2015

Suppose that a sequence $a_{1}, a_{2}, \ldots$ of positive real numbers satisfies $$a_{k+1} \geqslant \frac{k a_{k}}{a_{k}^{2}+(k-1)}$$ for every positive integer $k$. Prove that $a_{1}+a_{2}+\cdots+a_{n} \geqslant n$ for every $n \geqslant 2$.

Determine all functions $f: \mathbb{Z} \rightarrow \mathbb{Z}$ with the property that $$f(x-f(y))=f(f(x))-f(y)-1$$ holds for all $x, y \in \mathbb{Z}$. (Croatia)

Let $n$ be a fixed positive integer. Find the maximum possible value of $$\sum_{1 \leqslant r<s \leqslant 2 n}(s-r-n) x_{r} x_{s},$$ where $-1 \leqslant x_{i} \leqslant 1$ for all $i=1,2, \ldots, 2 n$. (Austria)

Find all functions $f: \mathbb{R} \rightarrow \mathbb{R}$ satisfying the equation $$f(x+f(x+y))+f(x y)=x+f(x+y)+y f(x)$$ for all real numbers $x$ and $y$.

Let $2 \mathbb{Z}+1$ denote the set of odd integers. Find all functions $f: \mathbb{Z} \rightarrow 2 \mathbb{Z}+1$ satisfying $$f(x+f(x)+y)+f(x-f(x)-y)=f(x+y)+f(x-y)$$ for every $x, y \in \mathbb{Z}$.

Let $n$ be a fixed integer with $n \geqslant 2$. We say that two polynomials $P$ and $Q$ with real coefficients are block-similar if for each $i \in\{1,2, \ldots, n\}$ the sequences $$\begin{aligned} & P(2015 i), P(2015 i-1), \ldots, P(2015 i-2014) \text { and } \\ & Q(2015 i), Q(2015 i-1), \ldots, Q(2015 i-2014) \end{aligned}$$ are permutations of each other. (a) Prove that there exist distinct block-similar polynomials of degree $n+1$. (b) Prove that there do not exist distinct block-similar polynomials of degree $n$.

In Lineland there are $n \geqslant 1$ towns, arranged along a road running from left to right. Each town has a left bulldozer (put to the left of the town and facing left) and a right bulldozer (put to the right of the town and facing right). The sizes of the $2 n$ bulldozers are distinct. Every time when a right and a left bulldozer confront each other, the larger bulldozer pushes the smaller one off the road. On the other hand, the bulldozers are quite unprotected at their rears; so, if a bulldozer reaches the rear-end of another one, the first one pushes the second one off the road, regardless of their sizes. Let $A$ and $B$ be two towns, with $B$ being to the right of $A$. We say that town $A$ can sweep town $B$ away if the right bulldozer of $A$ can move over to $B$ pushing off all bulldozers it meets. Similarly, $B$ can sweep $A$ away if the left bulldozer of $B$ can move to $A$ pushing off all bulldozers of all towns on its way. Prove that there is exactly one town which cannot be swept away by any other one. (Estonia)

Let $\mathcal{V}$ be a finite set of points in the plane. We say that $\mathcal{V}$ is balanced if for any two distinct points $A, B \in \mathcal{V}$, there exists a point $C \in \mathcal{V}$ such that $A C=B C$. We say that $\mathcal{V}$ is center-free if for any distinct points $A, B, C \in \mathcal{V}$, there does not exist a point $P \in \mathcal{V}$ such that $P A=P B=P C$. (a) Show that for all $n \geqslant 3$, there exists a balanced set consisting of $n$ points. (b) For which $n \geqslant 3$ does there exist a balanced, center-free set consisting of $n$ points? (Netherlands)

For a finite set $A$ of positive integers, we call a partition of $A$ into two disjoint nonempty subsets $A_{1}$ and $A_{2}$ good if the least common multiple of the elements in $A_{1}$ is equal to the greatest common divisor of the elements in $A_{2}$. Determine the minimum value of $n$ such that there exists a set of $n$ positive integers with exactly 2015 good partitions. (Ukraine)

Let $n$ be a positive integer. Two players $A$ and $B$ play a game in which they take turns choosing positive integers $k \leqslant n$. The rules of the game are: (i) A player cannot choose a number that has been chosen by either player on any previous turn. (ii) A player cannot choose a number consecutive to any of those the player has already chosen on any previous turn. (iii) The game is a draw if all numbers have been chosen; otherwise the player who cannot choose a number anymore loses the game. The player $A$ takes the first turn. Determine the outcome of the game, assuming that both players use optimal strategies. (Finland)

Consider an infinite sequence $a_{1}, a_{2}, \ldots$ of positive integers with $a_{i} \leqslant 2015$ for all $i \geqslant 1$. Suppose that for any two distinct indices $i$ and $j$ we have $i+a_{i} \neq j+a_{j}$. Prove that there exist two positive integers $b$ and $N$ such that $$\left|\sum_{i=m+1}^{n}\left(a_{i}-b\right)\right| \leqslant 1007^{2}$$ whenever $n>m \geqslant N$.

Let $S$ be a nonempty set of positive integers. We say that a positive integer $n$ is clean if it has a unique representation as a sum of an odd number of distinct elements from $S$. Prove that there exist infinitely many positive integers that are not clean.

In a company of people some pairs are enemies. A group of people is called unsociable if the number of members in the group is odd and at least 3 , and it is possible to arrange all its members around a round table so that every two neighbors are enemies. Given that there are at most 2015 unsociable groups, prove that it is possible to partition the company into 11 parts so that no two enemies are in the same part.

Let $A B C$ be an acute triangle with orthocenter $H$. Let $G$ be the point such that the quadrilateral $A B G H$ is a parallelogram. Let $I$ be the point on the line $G H$ such that $A C$ bisects $H I$. Suppose that the line $A C$ intersects the circumcircle of the triangle $G C I$ at $C$ and $J$. Prove that $I J=A H$. (Australia)

Let $A B C$ be a triangle inscribed into a circle $\Omega$ with center $O$. A circle $\Gamma$ with center $A$ meets the side $B C$ at points $D$ and $E$ such that $D$ lies between $B$ and $E$. Moreover, let $F$ and $G$ be the common points of $\Gamma$ and $\Omega$. We assume that $F$ lies on the arc $A B$ of $\Omega$ not containing $C$, and $G$ lies on the arc $A C$ of $\Omega$ not containing $B$. The circumcircles of the triangles $B D F$ and $C E G$ meet the sides $A B$ and $A C$ again at $K$ and $L$, respectively. Suppose that the lines $F K$ and $G L$ are distinct and intersect at $X$. Prove that the points $A, X$, and $O$ are collinear. (Greece)

Let $A B C$ be a triangle with $\angle C=90^{\circ}$, and let $H$ be the foot of the altitude from $C$. A point $D$ is chosen inside the triangle $C B H$ so that $C H$ bisects $A D$. Let $P$ be the intersection point of the lines $B D$ and $C H$. Let $\omega$ be the semicircle with diameter $B D$ that meets the segment $C B$ at an interior point. A line through $P$ is tangent to $\omega$ at $Q$. Prove that the lines $C Q$ and $A D$ meet on $\omega$. (Georgia)

Let $A B C$ be an acute triangle, and let $M$ be the midpoint of $A C$. A circle $\omega$ passing through $B$ and $M$ meets the sides $A B$ and $B C$ again at $P$ and $Q$, respectively. Let $T$ be the point such that the quadrilateral $B P T Q$ is a parallelogram. Suppose that $T$ lies on the circumcircle of the triangle $A B C$. Determine all possible values of $B T / B M$. (Russia)

Let $A B C$ be a triangle with $C A \neq C B$. Let $D, F$, and $G$ be the midpoints of the sides $A B, A C$, and $B C$, respectively. A circle $\Gamma$ passing through $C$ and tangent to $A B$ at $D$ meets the segments $A F$ and $B G$ at $H$ and $I$, respectively. The points $H^{\prime}$ and $I^{\prime}$ are symmetric to $H$ and $I$ about $F$ and $G$, respectively. The line $H^{\prime} I^{\prime}$ meets $C D$ and $F G$ at $Q$ and $M$, respectively. The line $C M$ meets $\Gamma$ again at $P$. Prove that $C Q=Q P$. (El Salvador)

Let $A B C$ be an acute triangle with $A B>A C$, and let $\Gamma$ be its circumcircle. Let $H$, $M$, and $F$ be the orthocenter of the triangle, the midpoint of $B C$, and the foot of the altitude from $A$, respectively. Let $Q$ and $K$ be the two points on $\Gamma$ that satisfy $\angle A Q H=90^{\circ}$ and $\angle Q K H=90^{\circ}$. Prove that the circumcircles of the triangles $K Q H$ and $K F M$ are tangent to each other. (Ukraine)

Let $A B C D$ be a convex quadrilateral, and let $P, Q, R$, and $S$ be points on the sides $A B, B C, C D$, and $D A$, respectively. Let the line segments $P R$ and $Q S$ meet at $O$. Suppose that each of the quadrilaterals $A P O S, B Q O P, C R O Q$, and $D S O R$ has an incircle. Prove that the lines $A C, P Q$, and $R S$ are either concurrent or parallel to each other. (Bulgaria)

A triangulation of a convex polygon $\Pi$ is a partitioning of $\Pi$ into triangles by diagonals having no common points other than the vertices of the polygon. We say that a triangulation is a Thaiangulation if all triangles in it have the same area. Prove that any two different Thaiangulations of a convex polygon $\Pi$ differ by exactly two triangles. (In other words, prove that it is possible to replace one pair of triangles in the first Thaiangulation with a different pair of triangles so as to obtain the second Thaiangulation.) (Bulgaria)

Determine all positive integers $M$ for which the sequence $a_{0}, a_{1}, a_{2}, \ldots$, defined by $a_{0}=\frac{2 M+1}{2}$ and $a_{k+1}=a_{k}\left\lfloor a_{k}\right\rfloor$ for $k=0,1,2, \ldots$, contains at least one integer term. (Luxembourg)

Let $a$ and $b$ be positive integers such that $a!b$ ! is a multiple of $a!+b!$. Prove that $3 a \geqslant 2 b+2$. (United Kingdom)

Let $m$ and $n$ be positive integers such that $m>n$. Define $x_{k}=(m+k) /(n+k)$ for $k=$ $1,2, \ldots, n+1$. Prove that if all the numbers $x_{1}, x_{2}, \ldots, x_{n+1}$ are integers, then $x_{1} x_{2} \cdots x_{n+1}-1$ is divisible by an odd prime. (Austria)

Suppose that $a_{0}, a_{1}, \ldots$ and $b_{0}, b_{1}, \ldots$ are two sequences of positive integers satisfying $a_{0}, b_{0} \geqslant 2$ and $$a_{n+1}=\operatorname{gcd}\left(a_{n}, b_{n}\right)+1, b_{n+1}=\operatorname{lcm}\left(a_{n}, b_{n}\right)-1$$ for all $n \geqslant 0$. Prove that the sequence $\left(a_{n}\right)$ is eventually periodic; in other words, there exist integers $N \geqslant 0$ and $t>0$ such that $a_{n+t}=a_{n}$ for all $n \geqslant N$. (France)

Determine all triples $(a, b, c)$ of positive integers for which $a b-c, b c-a$, and $c a-b$ are powers of 2 . Explanation: A power of 2 is an integer of the form $2^{n}$, where $n$ denotes some nonnegative integer. (Serbia)

Let $\mathbb{Z}_{>0}$ denote the set of positive integers. Consider a function $f: \mathbb{Z}_{>0} \rightarrow \mathbb{Z}_{>0}$. For any $m, n \in \mathbb{Z}_{>0}$ we write $f^{n}(m)=\underbrace{f(f(\ldots f}_{n}(m) \ldots))$. Suppose that $f$ has the following two properties: (i) If $m, n \in \mathbb{Z}_{>0}$, then $\frac{f^{n}(m)-m}{n} \in \mathbb{Z}_{>0}$; (ii) The set $\mathbb{Z}_{>0} \backslash\left\{f(n) \mid n \in \mathbb{Z}_{>0}\right\}$ is finite. Prove that the sequence $f(1)-1, f(2)-2, f(3)-3, \ldots$ is periodic. (Singapore)

Let $\mathbb{Z}_{>0}$ denote the set of positive integers. For any positive integer $k$, a function $f: \mathbb{Z}_{>0} \rightarrow \mathbb{Z}_{>0}$ is called $k$-good if $\operatorname{gcd}(f(m)+n, f(n)+m) \leqslant k$ for all $m \neq n$. Find all $k$ such that there exists a $k$-good function. (Canada)

For every positive integer $n$ with prime factorization $n=\prod_{i=1}^{k} p_{i}^{\alpha_{i}}$, define $$\mho(n)=\sum_{i: p_{i}>10^{100}} \alpha_{i} .$$ That is, $\mho(n)$ is the number of prime factors of $n$ greater than $10^{100}$, counted with multiplicity. Find all strictly increasing functions $f: \mathbb{Z} \rightarrow \mathbb{Z}$ such that $$\mho(f(a)-f(b)) \leqslant \mho(a-b) \text { for all integers } a \text { and } b \text { with } a>b .$$