ISL 2012

Find all the functions $f: \mathbb{Z} \rightarrow \mathbb{Z}$ such that $$f(a)^{2}+f(b)^{2}+f(c)^{2}=2 f(a) f(b)+2 f(b) f(c)+2 f(c) f(a)$$ for all integers $a, b, c$ satisfying $a+b+c=0$.

Let $\mathbb{Z}$ and $\mathbb{Q}$ be the sets of integers and rationals respectively. a) Does there exist a partition of $\mathbb{Z}$ into three non-empty subsets $A, B, C$ such that the sets $A+B, B+C, C+A$ are disjoint? b) Does there exist a partition of $\mathbb{Q}$ into three non-empty subsets $A, B, C$ such that the sets $A+B, B+C, C+A$ are disjoint? Here $X+Y$ denotes the set $\{x+y \mid x \in X, y \in Y\}$, for $X, Y \subseteq \mathbb{Z}$ and $X, Y \subseteq \mathbb{Q}$.

Let $a_{2}, \ldots, a_{n}$ be $n-1$ positive real numbers, where $n \geq 3$, such that $a_{2} a_{3} \cdots a_{n}=1$. Prove that $$\left(1+a_{2}\right)^{2}\left(1+a_{3}\right)^{3} \cdots\left(1+a_{n}\right)^{n}>n^{n} .$$

Let $f$ and $g$ be two nonzero polynomials with integer coefficients and $\operatorname{deg} f>\operatorname{deg} g$. Suppose that for infinitely many primes $p$ the polynomial $p f+g$ has a rational root. Prove that $f$ has a rational root.

Find all functions $f: \mathbb{R} \rightarrow \mathbb{R}$ that satisfy the conditions $$f(1+x y)-f(x+y)=f(x) f(y) \text { for all } x, y \in \mathbb{R}$$ and $f(-1) \neq 0$.

Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a function, and let $f^{m}$ be $f$ applied $m$ times. Suppose that for every $n \in \mathbb{N}$ there exists a $k \in \mathbb{N}$ such that $f^{2 k}(n)=n+k$, and let $k_{n}$ be the smallest such $k$. Prove that the sequence $k_{1}, k_{2}, \ldots$ is unbounded.

We say that a function $f: \mathbb{R}^{k} \rightarrow \mathbb{R}$ is a metapolynomial if, for some positive integers $m$ and $n$, it can be represented in the form $$f\left(x_{1}, \ldots, x_{k}\right)=\max _{i=1, \ldots, m} \min _{j=1, \ldots, n} P_{i, j}\left(x_{1}, \ldots, x_{k}\right)$$ where $P_{i, j}$ are multivariate polynomials. Prove that the product of two metapolynomials is also a metapolynomial.

Several positive integers are written in a row. Iteratively, Alice chooses two adjacent numbers $x$ and $y$ such that $x>y$ and $x$ is to the left of $y$, and replaces the pair $(x, y)$ by either $(y+1, x)$ or $(x-1, x)$. Prove that she can perform only finitely many such iterations.

Let $n \geq 1$ be an integer. What is the maximum number of disjoint pairs of elements of the set $\{1,2, \ldots, n\}$ such that the sums of the different pairs are different integers not exceeding $n$ ?

In a $999 \times 999$ square table some cells are white and the remaining ones are red. Let $T$ be the number of triples $\left(C_{1}, C_{2}, C_{3}\right)$ of cells, the first two in the same row and the last two in the same column, with $C_{1}$ and $C_{3}$ white and $C_{2}$ red. Find the maximum value $T$ can attain.

Players $A$ and $B$ play a game with $N \geq 2012$ coins and 2012 boxes arranged around a circle. Initially $A$ distributes the coins among the boxes so that there is at least 1 coin in each box. Then the two of them make moves in the order $B, A, B, A, \ldots$ by the following rules: - On every move of his $B$ passes 1 coin from every box to an adjacent box. - On every move of hers $A$ chooses several coins that were not involved in $B$ 's previous move and are in different boxes. She passes every chosen coin to an adjacent box. Player $A$ 's goal is to ensure at least 1 coin in each box after every move of hers, regardless of how $B$ plays and how many moves are made. Find the least $N$ that enables her to succeed.

The columns and the rows of a $3 n \times 3 n$ square board are numbered $1,2, \ldots, 3 n$. Every square $(x, y)$ with $1 \leq x, y \leq 3 n$ is colored asparagus, byzantium or citrine according as the modulo 3 remainder of $x+y$ is 0,1 or 2 respectively. One token colored asparagus, byzantium or citrine is placed on each square, so that there are $3 n^{2}$ tokens of each color. Suppose that one can permute the tokens so that each token is moved to a distance of at most $d$ from its original position, each asparagus token replaces a byzantium token, each byzantium token replaces a citrine token, and each citrine token replaces an asparagus token. Prove that it is possible to permute the tokens so that each token is moved to a distance of at most $d+2$ from its original position, and each square contains a token with the same color as the square.

Let $k$ and $n$ be fixed positive integers. In the liar's guessing game, Amy chooses integers $x$ and $N$ with $1 \leq x \leq N$. She tells Ben what $N$ is, but not what $x$ is. Ben may then repeatedly ask Amy whether $x \in S$ for arbitrary sets $S$ of integers. Amy will always answer with yes or no, but she might lie. The only restriction is that she can lie at most $k$ times in a row. After he has asked as many questions as he wants, Ben must specify a set of at most $n$ positive integers. If $x$ is in this set he wins; otherwise, he loses. Prove that: a) If $n \geq 2^{k}$ then Ben can always win. b) For sufficiently large $k$ there exist $n \geq 1.99^{k}$ such that Ben cannot guarantee a win.

There are given $2^{500}$ points on a circle labeled $1,2, \ldots, 2^{500}$ in some order. Prove that one can choose 100 pairwise disjoint chords joining some of these points so that the 100 sums of the pairs of numbers at the endpoints of the chosen chords are equal.

In the triangle $A B C$ the point $J$ is the center of the excircle opposite to $A$. This excircle is tangent to the side $B C$ at $M$, and to the lines $A B$ and $A C$ at $K$ and $L$ respectively. The lines $L M$ and $B J$ meet at $F$, and the lines $K M$ and $C J$ meet at $G$. Let $S$ be the point of intersection of the lines $A F$ and $B C$, and let $T$ be the point of intersection of the lines $A G$ and $B C$. Prove that $M$ is the midpoint of $S T$.

Let $A B C D$ be a cyclic quadrilateral whose diagonals $A C$ and $B D$ meet at $E$. The extensions of the sides $A D$ and $B C$ beyond $A$ and $B$ meet at $F$. Let $G$ be the point such that $E C G D$ is a parallelogram, and let $H$ be the image of $E$ under reflection in $A D$. Prove that $D, H, F, G$ are concyclic.

In an acute triangle $A B C$ the points $D, E$ and $F$ are the feet of the altitudes through $A$, $B$ and $C$ respectively. The incenters of the triangles $A E F$ and $B D F$ are $I_{1}$ and $I_{2}$ respectively; the circumcenters of the triangles $A C I_{1}$ and $B C I_{2}$ are $O_{1}$ and $O_{2}$ respectively. Prove that $I_{1} I_{2}$ and $O_{1} O_{2}$ are parallel.

Let $A B C$ be a triangle with $A B \neq A C$ and circumcenter $O$. The bisector of $\angle B A C$ intersects $B C$ at $D$. Let $E$ be the reflection of $D$ with respect to the midpoint of $B C$. The lines through $D$ and $E$ perpendicular to $B C$ intersect the lines $A O$ and $A D$ at $X$ and $Y$ respectively. Prove that the quadrilateral $B X C Y$ is cyclic.

Let $A B C$ be a triangle with $\angle B C A=90^{\circ}$, and let $C_{0}$ be the foot of the altitude from $C$. Choose a point $X$ in the interior of the segment $C C_{0}$, and let $K, L$ be the points on the segments $A X, B X$ for which $B K=B C$ and $A L=A C$ respectively. Denote by $M$ the intersection of $A L$ and $B K$. Show that $M K=M L$.

Let $A B C$ be a triangle with circumcenter $O$ and incenter $I$. The points $D, E$ and $F$ on the sides $B C, C A$ and $A B$ respectively are such that $B D+B F=C A$ and $C D+C E=A B$. The circumcircles of the triangles $B F D$ and $C D E$ intersect at $P \neq D$. Prove that $O P=O I$.

Let $A B C D$ be a convex quadrilateral with non-parallel sides $B C$ and $A D$. Assume that there is a point $E$ on the side $B C$ such that the quadrilaterals $A B E D$ and $A E C D$ are circumscribed. Prove that there is a point $F$ on the side $A D$ such that the quadrilaterals $A B C F$ and $B C D F$ are circumscribed if and only if $A B$ is parallel to $C D$.

Let $A B C$ be a triangle with circumcircle $\omega$ and $\ell$ a line without common points with $\omega$. Denote by $P$ the foot of the perpendicular from the center of $\omega$ to $\ell$. The side-lines $B C, C A, A B$ intersect $\ell$ at the points $X, Y, Z$ different from $P$. Prove that the circumcircles of the triangles $A X P, B Y P$ and $C Z P$ have a common point different from $P$ or are mutually tangent at $P$.

Call admissible a set $A$ of integers that has the following property: $$\text { If } x, y \in A \text { (possibly } x=y \text { ) then } x^{2}+k x y+y^{2} \in A \text { for every integer } k \text {. }$$ Determine all pairs $m, n$ of nonzero integers such that the only admissible set containing both $m$ and $n$ is the set of all integers.

Find all triples $(x, y, z)$ of positive integers such that $x \leq y \leq z$ and $$x^{3}\left(y^{3}+z^{3}\right)=2012(x y z+2) \text {. }$$

Determine all integers $m \geq 2$ such that every $n$ with $\frac{m}{3} \leq n \leq \frac{m}{2}$ divides the binomial coefficient $\left(\begin{array}{c}n \\ m-2 n\end{array}\right)$.

An integer $a$ is called friendly if the equation $\left(m^{2}+n\right)\left(n^{2}+m\right)=a(m-n)^{3}$ has a solution over the positive integers. a) Prove that there are at least 500 friendly integers in the set $\{1,2, \ldots, 2012\}$. b) Decide whether $a=2$ is friendly.

For a nonnegative integer $n$ define $\operatorname{rad}(n)=1$ if $n=0$ or $n=1$, and $\operatorname{rad}(n)=p_{1} p_{2} \cdots p_{k}$ where $p_{1}<p_{2}<\cdots<p_{k}$ are all prime factors of $n$. Find all polynomials $f(x)$ with nonnegative integer coefficients such that $\operatorname{rad}(f(n))$ divides $\operatorname{rad}\left(f\left(n^{r a d(n)}\right)\right)$ for every nonnegative integer $n$.

Let $x$ and $y$ be positive integers. If $x^{2^{n}}-1$ is divisible by $2^{n} y+1$ for every positive integer $n$, prove that $x=1$.

Find all $n \in \mathbb{N}$ for which there exist nonnegative integers $a_{1}, a_{2}, \ldots, a_{n}$ such that $$\frac{1}{2^{a_{1}}}+\frac{1}{2^{a_{2}}}+\cdots+\frac{1}{2^{a_{n}}}=\frac{1}{3^{a_{1}}}+\frac{2}{3^{a_{2}}}+\cdots+\frac{n}{3^{a_{n}}}=1 .$$

Prove that for every prime $p>100$ and every integer $r$ there exist two integers $a$ and $b$ such that $p$ divides $a^{2}+b^{5}-r$.