ISL 2014

Let $z_{0}<z_{1}<z_{2}<\cdots$ be an infinite sequence of positive integers. Prove that there exists a unique integer $n \geqslant 1$ such that $$z_{n}<\frac{z_{0}+z_{1}+\cdots+z_{n}}{n} \leqslant z_{n+1}$$ (Austria)

Define the function $f:(0,1) \rightarrow(0,1)$ by $$f(x)= \begin{cases}x+\frac{1}{2} & \text { if } x<\frac{1}{2} \\ x^{2} & \text { if } x \geqslant \frac{1}{2}\end{cases}$$ Let $a$ and $b$ be two real numbers such that $0<a<b<1$. We define the sequences $a_{n}$ and $b_{n}$ by $a_{0}=a, b_{0}=b$, and $a_{n}=f\left(a_{n-1}\right), b_{n}=f\left(b_{n-1}\right)$ for $n>0$. Show that there exists a positive integer $n$ such that $$\left(a_{n}-a_{n-1}\right)\left(b_{n}-b_{n-1}\right)<0 .$$ (Denmark)

For a sequence $x_{1}, x_{2}, \ldots, x_{n}$ of real numbers, we define its price as $$\max _{1 \leqslant i \leqslant n}\left|x_{1}+\cdots+x_{i}\right|$$ Given $n$ real numbers, Dave and George want to arrange them into a sequence with a low price. Diligent Dave checks all possible ways and finds the minimum possible price $D$. Greedy George, on the other hand, chooses $x_{1}$ such that $\left|x_{1}\right|$ is as small as possible; among the remaining numbers, he chooses $x_{2}$ such that $\left|x_{1}+x_{2}\right|$ is as small as possible, and so on. Thus, in the $i^{\text {th }}$ step he chooses $x_{i}$ among the remaining numbers so as to minimise the value of $\left|x_{1}+x_{2}+\cdots+x_{i}\right|$. In each step, if several numbers provide the same value, George chooses one at random. Finally he gets a sequence with price $G$. Find the least possible constant $c$ such that for every positive integer $n$, for every collection of $n$ real numbers, and for every possible sequence that George might obtain, the resulting values satisfy the inequality $G \leqslant c D$. (Georgia)

Determine all functions $f: \mathbb{Z} \rightarrow \mathbb{Z}$ satisfying $$f(f(m)+n)+f(m)=f(n)+f(3 m)+2014$$ for all integers $m$ and $n$.

Consider all polynomials $P(x)$ with real coefficients that have the following property: for any two real numbers $x$ and $y$ one has $$\left|y^{2}-P(x)\right| \leqslant 2|x| \text { if and only if } \left|x^{2}-P(y)\right| \leqslant 2|y|$$ Determine all possible values of $P(0)$.

Find all functions $f: \mathbb{Z} \rightarrow \mathbb{Z}$ such that $$n^{2}+4 f(n)=f(f(n))^{2}$$ for all $n \in \mathbb{Z}$. (United Kingdom)

Let $n$ points be given inside a rectangle $R$ such that no two of them lie on a line parallel to one of the sides of $R$. The rectangle $R$ is to be dissected into smaller rectangles with sides parallel to the sides of $R$ in such a way that none of these rectangles contains any of the given points in its interior. Prove that we have to dissect $R$ into at least $n+1$ smaller rectangles. (Serbia)

We have $2^{m}$ sheets of paper, with the number 1 written on each of them. We perform the following operation. In every step we choose two distinct sheets; if the numbers on the two sheets are $a$ and $b$, then we erase these numbers and write the number $a+b$ on both sheets. Prove that after $m 2^{m-1}$ steps, the sum of the numbers on all the sheets is at least $4^{m}$. (Iran)

Let $n \geqslant 2$ be an integer. Consider an $n \times n$ chessboard divided into $n^{2}$ unit squares. We call a configuration of $n$ rooks on this board happy if every row and every column contains exactly one rook. Find the greatest positive integer $k$ such that for every happy configuration of rooks, we can find a $k \times k$ square without a rook on any of its $k^{2}$ unit squares. (Croatia)

Construct a tetromino by attaching two $2 \times 1$ dominoes along their longer sides such that the midpoint of the longer side of one domino is a corner of the other domino. This construction yields two kinds of tetrominoes with opposite orientations. Let us call them Sand Z-tetrominoes, respectively. Assume that a lattice polygon $P$ can be tiled with S-tetrominoes. Prove than no matter how we tile $P$ using only S - and Z -tetrominoes, we always use an even number of Z -tetrominoes. (Hungary)

Consider $n \geqslant 3$ lines in the plane such that no two lines are parallel and no three have a common point. These lines divide the plane into polygonal regions; let $\mathcal{F}$ be the set of regions having finite area. Prove that it is possible to colour $\lceil\sqrt{n / 2}\rceil$ of the lines blue in such a way that no region in $\mathcal{F}$ has a completely blue boundary.

We are given an infinite deck of cards, each with a real number on it. For every real number $x$, there is exactly one card in the deck that has $x$ written on it. Now two players draw disjoint sets $A$ and $B$ of 100 cards each from this deck. We would like to define a rule that declares one of them a winner. This rule should satisfy the following conditions: 1. The winner only depends on the relative order of the 200 cards: if the cards are laid down in increasing order face down and we are told which card belongs to which player, but not what numbers are written on them, we can still decide the winner. 2. If we write the elements of both sets in increasing order as $A=\left\{a_{1}, a_{2}, \ldots, a_{100}\right\}$ and $B=\left\{b_{1}, b_{2}, \ldots, b_{100}\right\}$, and $a_{i}>b_{i}$ for all $i$, then $A$ beats $B$. 3. If three players draw three disjoint sets $A, B, C$ from the deck, $A$ beats $B$ and $B$ beats $C$, then $A$ also beats $C$. How many ways are there to define such a rule? Here, we consider two rules as different if there exist two sets $A$ and $B$ such that $A$ beats $B$ according to one rule, but $B$ beats $A$ according to the other. (Russia)

Let $M$ be a set of $n \geqslant 4$ points in the plane, no three of which are collinear. Initially these points are connected with $n$ segments so that each point in $M$ is the endpoint of exactly two segments. Then, at each step, one may choose two segments $A B$ and $C D$ sharing a common interior point and replace them by the segments $A C$ and $B D$ if none of them is present at this moment. Prove that it is impossible to perform $n^{3} / 4$ or more such moves. (Russia)

A card deck consists of 1024 cards. On each card, a set of distinct decimal digits is written in such a way that no two of these sets coincide (thus, one of the cards is empty). Two players alternately take cards from the deck, one card per turn. After the deck is empty, each player checks if he can throw out one of his cards so that each of the ten digits occurs on an even number of his remaining cards. If one player can do this but the other one cannot, the one who can is the winner; otherwise a draw is declared. Determine all possible first moves of the first player after which he has a winning strategy. (Russia)

There are $n$ circles drawn on a piece of paper in such a way that any two circles intersect in two points, and no three circles pass through the same point. Turbo the snail slides along the circles in the following fashion. Initially he moves on one of the circles in clockwise direction. Turbo always keeps sliding along the current circle until he reaches an intersection with another circle. Then he continues his journey on this new circle and also changes the direction of moving, i.e. from clockwise to anticlockwise or vice versa. Suppose that Turbo's path entirely covers all circles. Prove that $n$ must be odd.

The points $P$ and $Q$ are chosen on the side $B C$ of an acute-angled triangle $A B C$ so that $\angle P A B=\angle A C B$ and $\angle Q A C=\angle C B A$. The points $M$ and $N$ are taken on the rays $A P$ and $A Q$, respectively, so that $A P=P M$ and $A Q=Q N$. Prove that the lines $B M$ and $C N$ intersect on the circumcircle of the triangle $A B C$. (Georgia)

Let $A B C$ be a triangle. The points $K, L$, and $M$ lie on the segments $B C, C A$, and $A B$, respectively, such that the lines $A K, B L$, and $C M$ intersect in a common point. Prove that it is possible to choose two of the triangles $A L M, B M K$, and $C K L$ whose inradii sum up to at least the inradius of the triangle $A B C$. (Estonia)

Let $\Omega$ and $O$ be the circumcircle and the circumcentre of an acute-angled triangle $A B C$ with $A B>B C$. The angle bisector of $\angle A B C$ intersects $\Omega$ at $M \neq B$. Let $\Gamma$ be the circle with diameter $B M$. The angle bisectors of $\angle A O B$ and $\angle B O C$ intersect $\Gamma$ at points $P$ and $Q$, respectively. The point $R$ is chosen on the line $P Q$ so that $B R=M R$. Prove that $B R \| A C$. (Russia)

Consider a fixed circle $\Gamma$ with three fixed points $A, B$, and $C$ on it. Also, let us fix a real number $\lambda \in(0,1)$. For a variable point $P \notin\{A, B, C\}$ on $\Gamma$, let $M$ be the point on the segment $C P$ such that $C M=\lambda \cdot C P$. Let $Q$ be the second point of intersection of the circumcircles of the triangles $A M P$ and $B M C$. Prove that as $P$ varies, the point $Q$ lies on a fixed circle. (United Kingdom)

Let $A B C D$ be a convex quadrilateral with $\angle B=\angle D=90^{\circ}$. Point $H$ is the foot of the perpendicular from $A$ to $B D$. The points $S$ and $T$ are chosen on the sides $A B$ and $A D$, respectively, in such a way that $H$ lies inside triangle $S C T$ and $$\angle S H C-\angle B S C=90^{\circ}, \angle T H C-\angle D T C=90^{\circ} .$$ Prove that the circumcircle of triangle $S H T$ is tangent to the line $B D$. (Iran)

Let $A B C$ be a fixed acute-angled triangle. Consider some points $E$ and $F$ lying on the sides $A C$ and $A B$, respectively, and let $M$ be the midpoint of $E F$. Let the perpendicular bisector of $E F$ intersect the line $B C$ at $K$, and let the perpendicular bisector of $M K$ intersect the lines $A C$ and $A B$ at $S$ and $T$, respectively. We call the pair $(E, F)$ interesting, if the quadrilateral $K S A T$ is cyclic. Suppose that the pairs $\left(E_{1}, F_{1}\right)$ and $\left(E_{2}, F_{2}\right)$ are interesting. Prove that $$\frac{E_{1} E_{2}}{A B}=\frac{F_{1} F_{2}}{A C}$$ (Iran)

Let $A B C$ be a triangle with circumcircle $\Omega$ and incentre $I$. Let the line passing through $I$ and perpendicular to $C I$ intersect the segment $B C$ and the $\operatorname{arc} B C($ not containing $A)$ of $\Omega$ at points $U$ and $V$, respectively. Let the line passing through $U$ and parallel to $A I$ intersect $A V$ at $X$, and let the line passing through $V$ and parallel to $A I$ intersect $A B$ at $Y$. Let $W$ and $Z$ be the midpoints of $A X$ and $B C$, respectively. Prove that if the points $I, X$, and $Y$ are collinear, then the points $I, W$, and $Z$ are also collinear.

Let $n \geqslant 2$ be an integer, and let $A_{n}$ be the set $$A_{n}=\left\{2^{n}-2^{k} \mid k \in \mathbb{Z}, 0 \leqslant k<n\right\} .$$ Determine the largest positive integer that cannot be written as the sum of one or more (not necessarily distinct) elements of $A_{n}$. (Serbia)

Determine all pairs $(x, y)$ of positive integers such that $$\sqrt[3]{7 x^{2}-13 x y+7 y^{2}}=|x-y|+1$$

A coin is called a Cape Town coin if its value is $1 / n$ for some positive integer $n$. Given a collection of Cape Town coins of total value at most $99+\frac{1}{2}$, prove that it is possible to split this collection into at most 100 groups each of total value at most 1. (Luxembourg)

Let $n>1$ be a given integer. Prove that infinitely many terms of the sequence $\left(a_{k}\right)_{k \geqslant 1}$, defined by $$a_{k}=\left\lfloor\frac{n^{k}}{k}\right\rfloor$$ are odd. (For a real number $x,\lfloor x\rfloor$ denotes the largest integer not exceeding $x$.) (Hong Kong)

Find all triples $(p, x, y)$ consisting of a prime number $p$ and two positive integers $x$ and $y$ such that $x^{p-1}+y$ and $x+y^{p-1}$ are both powers of $p$. (Belgium)

Let $a_{1}<a_{2}<\cdots<a_{n}$ be pairwise coprime positive integers with $a_{1}$ being prime and $a_{1} \geqslant n+2$. On the segment $I=\left[0, a_{1} a_{2} \cdots a_{n}\right]$ of the real line, mark all integers that are divisible by at least one of the numbers $a_{1}, \ldots, a_{n}$. These points split $I$ into a number of smaller segments. Prove that the sum of the squares of the lengths of these segments is divisible by $a_{1}$. (Serbia)

Let $c \geqslant 1$ be an integer. Define a sequence of positive integers by $a_{1}=c$ and $$a_{n+1}=a_{n}^{3}-4 c \cdot a_{n}^{2}+5 c^{2} \cdot a_{n}+c$$ for all $n \geqslant 1$. Prove that for each integer $n \geqslant 2$ there exists a prime number $p$ dividing $a_{n}$ but none of the numbers $a_{1}, \ldots, a_{n-1}$. (Austria)

For every real number $x$, let $\|x\|$ denote the distance between $x$ and the nearest integer. Prove that for every pair $(a, b)$ of positive integers there exist an odd prime $p$ and a positive integer $k$ satisfying $$\left\|\frac{a}{p^{k}}\right\|+\left\|\frac{b}{p^{k}}\right\|+\left\|\frac{a+b}{p^{k}}\right\|=1 .$$ (Hungary)