ISL 2010

Determine all functions $f: \mathbb{R} \rightarrow \mathbb{R}$ such that the equality $$f([x] y)=f(x)[f(y)] .$$ holds for all $x, y \in \mathbb{R}$. Here, by $[x]$ we denote the greatest integer not exceeding $x$. (France)

Let the real numbers $a, b, c, d$ satisfy the relations $a+b+c+d=6$ and $a^{2}+b^{2}+c^{2}+d^{2}=12$. Prove that $$36 \leq 4\left(a^{3}+b^{3}+c^{3}+d^{3}\right)-\left(a^{4}+b^{4}+c^{4}+d^{4}\right) \leq 48$$ (Ukraine)

Let $x_{1}, \ldots, x_{100}$ be nonnegative real numbers such that $x_{i}+x_{i+1}+x_{i+2} \leq 1$ for all $i=1, \ldots, 100$ (we put $x_{101}=x_{1}, x_{102}=x_{2}$ ). Find the maximal possible value of the sum $$S=\sum_{i=1}^{100} x_{i} x_{i+2}$$ (Russia)

A sequence $x_{1}, x_{2}, \ldots$ is defined by $x_{1}=1$ and $x_{2 k}=-x_{k}, x_{2 k-1}=(-1)^{k+1} x_{k}$ for all $k \geq 1$. Prove that $x_{1}+x_{2}+\cdots+x_{n} \geq 0$ for all $n \geq 1$. (Austria)

Denote by $\mathbb{Q}^{+}$the set of all positive rational numbers. Determine all functions $f: \mathbb{Q}^{+} \rightarrow \mathbb{Q}^{+}$ which satisfy the following equation for all $x, y \in \mathbb{Q}^{+}$: $$f\left(f(x)^{2} y\right)=x^{3} f(x y)$$ (Switzerland)

Suppose that $f$ and $g$ are two functions defined on the set of positive integers and taking positive integer values. Suppose also that the equations $f(g(n))=f(n)+1$ and $g(f(n))=$ $g(n)+1$ hold for all positive integers. Prove that $f(n)=g(n)$ for all positive integer $n$. (Germany)

Let $a_{1}, \ldots, a_{r}$ be positive real numbers. For $n>r$, we inductively define $$a_{n}=\max _{1 \leq k \leq n-1}\left(a_{k}+a_{n-k}\right)$$ Prove that there exist positive integers $\ell \leq r$ and $N$ such that $a_{n}=a_{n-\ell}+a_{\ell}$ for all $n \geq N$. (Iran)

Given six positive numbers $a, b, c, d, e, f$ such that $a<b<c<d<e<f$. Let $a+c+e=S$ and $b+d+f=T$. Prove that $$2 S T>\sqrt{3(S+T)(S(b d+b f+d f)+T(a c+a e+c e))}$$ (South Korea)

In a concert, 20 singers will perform. For each singer, there is a (possibly empty) set of other singers such that he wishes to perform later than all the singers from that set. Can it happen that there are exactly 2010 orders of the singers such that all their wishes are satisfied? (Austria)

On some planet, there are $2^{N}$ countries $(N \geq 4)$. Each country has a flag $N$ units wide and one unit high composed of $N$ fields of size $1 \times 1$, each field being either yellow or blue. No two countries have the same flag. We say that a set of $N$ flags is diverse if these flags can be arranged into an $N \times N$ square so that all $N$ fields on its main diagonal will have the same color. Determine the smallest positive integer $M$ such that among any $M$ distinct flags, there exist $N$ flags forming a diverse set. (Croatia)

2500 chess kings have to be placed on a $100 \times 100$ chessboard so that (i) no king can capture any other one (i.e. no two kings are placed in two squares sharing a common vertex); (ii) each row and each column contains exactly 25 kings. Find the number of such arrangements. (Two arrangements differing by rotation or symmetry are supposed to be different.) (Russia)

Six stacks $S_{1}, \ldots, S_{6}$ of coins are standing in a row. In the beginning every stack contains a single coin. There are two types of allowed moves: Move 1: If stack $S_{k}$ with $1 \leq k \leq 5$ contains at least one coin, you may remove one coin from $S_{k}$ and add two coins to $S_{k+1}$. Move 2: If stack $S_{k}$ with $1 \leq k \leq 4$ contains at least one coin, then you may remove one coin from $S_{k}$ and exchange stacks $S_{k+1}$ and $S_{k+2}$. Decide whether it is possible to achieve by a sequence of such moves that the first five stacks are empty, whereas the sixth stack $S_{6}$ contains exactly $2010^{2010^{2010}}$ coins. Same as Problem C4, but the constant $2010^{2010^{2010}}$ is replaced by $2010^{2010}$. (Netherlands)

$n \geq 4$ players participated in a tennis tournament. Any two players have played exactly one game, and there was no tie game. We call a company of four players bad if one player was defeated by the other three players, and each of these three players won a game and lost another game among themselves. Suppose that there is no bad company in this tournament. Let $w_{i}$ and $\ell_{i}$ be respectively the number of wins and losses of the $i$ th player. Prove that $$\sum_{i=1}^{n}\left(w_{i}-\ell_{i}\right)^{3} \geq 0$$ (South Korea)

Given a positive integer $k$ and other two integers $b>w>1$. There are two strings of pearls, a string of $b$ black pearls and a string of $w$ white pearls. The length of a string is the number of pearls on it. One cuts these strings in some steps by the following rules. In each step: (i) The strings are ordered by their lengths in a non-increasing order. If there are some strings of equal lengths, then the white ones precede the black ones. Then $k$ first ones (if they consist of more than one pearl) are chosen; if there are less than $k$ strings longer than 1 , then one chooses all of them. (ii) Next, one cuts each chosen string into two parts differing in length by at most one. (For instance, if there are strings of $5,4,4,2$ black pearls, strings of $8,4,3$ white pearls and $k=4$, then the strings of 8 white, 5 black, 4 white and 4 black pearls are cut into the parts $(4,4),(3,2),(2,2)$ and $(2,2)$, respectively.) The process stops immediately after the step when a first isolated white pearl appears. Prove that at this stage, there will still exist a string of at least two black pearls. (Canada)

Let $P_{1}, \ldots, P_{s}$ be arithmetic progressions of integers, the following conditions being satisfied: (i) each integer belongs to at least one of them; (ii) each progression contains a number which does not belong to other progressions. Denote by $n$ the least common multiple of steps of these progressions; let $n=p_{1}^{\alpha_{1}} \ldots p_{k}^{\alpha_{k}}$ be its prime factorization. Prove that $$s \geq 1+\sum_{i=1}^{k} \alpha_{i}\left(p_{i}-1\right)$$ (Germany)

Let $A B C$ be an acute triangle with $D, E, F$ the feet of the altitudes lying on $B C, C A, A B$ respectively. One of the intersection points of the line $E F$ and the circumcircle is $P$. The lines $B P$ and $D F$ meet at point $Q$. Prove that $A P=A Q$. (United Kingdom)

Point $P$ lies inside triangle $A B C$. Lines $A P, B P, C P$ meet the circumcircle of $A B C$ again at points $K, L, M$, respectively. The tangent to the circumcircle at $C$ meets line $A B$ at $S$. Prove that $S C=S P$ if and only if $M K=M L$.

Let $A_{1} A_{2} \ldots A_{n}$ be a convex polygon. Point $P$ inside this polygon is chosen so that its projections $P_{1}, \ldots, P_{n}$ onto lines $A_{1} A_{2}, \ldots, A_{n} A_{1}$ respectively lie on the sides of the polygon. Prove that for arbitrary points $X_{1}, \ldots, X_{n}$ on sides $A_{1} A_{2}, \ldots, A_{n} A_{1}$ respectively, $$\max \left\{\frac{X_{1} X_{2}}{P_{1} P_{2}}, \ldots, \frac{X_{n} X_{1}}{P_{n} P_{1}}\right\} \geq 1$$ (Armenia)

Let $I$ be the incenter of a triangle $A B C$ and $\Gamma$ be its circumcircle. Let the line $A I$ intersect $\Gamma$ at a point $D \neq A$. Let $F$ and $E$ be points on side $B C$ and $\operatorname{arc} B D C$ respectively such that $\angle B A F=\angle C A E<\frac{1}{2} \angle B A C$. Finally, let $G$ be the midpoint of the segment $I F$. Prove that the lines $D G$ and $E I$ intersect on $\Gamma$. (Hong Kong)

Let $A B C D E$ be a convex pentagon such that $B C \| A E, A B=B C+A E$, and $\angle A B C=$ $\angle C D E$. Let $M$ be the midpoint of $C E$, and let $O$ be the circumcenter of triangle $B C D$. Given that $\angle D M O=90^{\circ}$, prove that $2 \angle B D A=\angle C D E$. (Ukraine)

The vertices $X, Y, Z$ of an equilateral triangle $X Y Z$ lie respectively on the sides $B C$, $C A, A B$ of an acute-angled triangle $A B C$. Prove that the incenter of triangle $A B C$ lies inside triangle $X Y Z$.

Three circular arcs $\gamma_{1}, \gamma_{2}$, and $\gamma_{3}$ connect the points $A$ and $C$. These arcs lie in the same half-plane defined by line $A C$ in such a way that arc $\gamma_{2}$ lies between the arcs $\gamma_{1}$ and $\gamma_{3}$. Point $B$ lies on the segment $A C$. Let $h_{1}, h_{2}$, and $h_{3}$ be three rays starting at $B$, lying in the same half-plane, $h_{2}$ being between $h_{1}$ and $h_{3}$. For $i, j=1,2,3$, denote by $V_{i j}$ the point of intersection of $h_{i}$ and $\gamma_{j}$ (see the Figure below). Denote by $\widehat{V_{i j} V_{k j}} \widehat{V_{k \ell} V_{i \ell}}$ the curved quadrilateral, whose sides are the segments $V_{i j} V_{i \ell}, V_{k j} V_{k \ell}$ and $\operatorname{arcs} V_{i j} V_{k j}$ and $V_{i \ell} V_{k \ell}$. We say that this quadrilateral is circumscribed if there exists a circle touching these two segments and two arcs. Prove that if the curved quadrilaterals $\sqrt{V_{11} V_{21}} \sqrt{22} V_{12}, \sqrt{V_{12} V_{22}} \sqrt{23} V_{13}, \sqrt{V_{21} V_{31}} \sqrt{V_{32} V_{22}}$ are circumscribed, then the curved quadrilateral $\sqrt{V_{22} V_{32}} \sqrt{33} V_{23}$ is circumscribed, too. Fig. 1 (Hungary)

Find the least positive integer $n$ for which there exists a set $\left\{s_{1}, s_{2}, \ldots, s_{n}\right\}$ consisting of $n$ distinct positive integers such that $$\left(1-\frac{1}{s_{1}}\right)\left(1-\frac{1}{s_{2}}\right) \ldots\left(1-\frac{1}{s_{n}}\right)=\frac{51}{2010}$$ $\mathbf{N} 1^{\prime}$. Same as Problem N1, but the constant $\frac{51}{2010}$ is replaced by $\frac{42}{2010}$. (Canada) Answer for Problem N1. $n=39$. Solution for Problem N1. Suppose that for some $n$ there exist the desired numbers; we may assume that $s_{1}<s_{2}<\cdots<s_{n}$. Surely $s_{1}>1$ since otherwise $1-\frac{1}{s_{1}}=0$. So we have $2 \leq s_{1} \leq s_{2}-1 \leq \cdots \leq s_{n}-(n-1)$, hence $s_{i} \geq i+1$ for each $i=1, \ldots, n$. Therefore $$\begin{aligned} \frac{51}{2010} & =\left(1-\frac{1}{s_{1}}\right)\left(1-\frac{1}{s_{2}}\right) \ldots\left(1-\frac{1}{s_{n}}\right) \\ & \geq\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right) \ldots\left(1-\frac{1}{n+1}\right)=\frac{1}{2} \cdot \frac{2}{3} \cdots \frac{n}{n+1}=\frac{1}{n+1} \end{aligned}$$ which implies $$n+1 \geq \frac{2010}{51}=\frac{670}{17}>39$$ so $n \geq 39$. Now we are left to show that $n=39$ fits. Consider the set $\{2,3, \ldots, 33,35,36, \ldots, 40,67\}$ which contains exactly 39 numbers. We have $$\frac{1}{2} \cdot \frac{2}{3} \cdots \frac{32}{33} \cdot \frac{34}{35} \cdots \frac{39}{40} \cdot \frac{66}{67}=\frac{1}{33} \cdot \frac{34}{40} \cdot \frac{66}{67}=\frac{17}{670}=\frac{51}{2010}$$ hence for $n=39$ there exists a desired example. Comment. One can show that the example (1) is unique. Answer for Problem N1' ${ }^{\prime} n=48$. Solution for Problem N1'. Suppose that for some $n$ there exist the desired numbers. In the same way we obtain that $s_{i} \geq i+1$. Moreover, since the denominator of the fraction $\frac{42}{2010}=\frac{7}{335}$ is divisible by 67 , some of $s_{i}$ 's should be divisible by 67 , so $s_{n} \geq s_{i} \geq 67$. This means that $$\frac{42}{2010} \geq \frac{1}{2} \cdot \frac{2}{3} \cdots \frac{n-1}{n} \cdot\left(1-\frac{1}{67}\right)=\frac{66}{67 n}$$ which implies $$n \geq \frac{2010 \cdot 66}{42 \cdot 67}=\frac{330}{7}>47$$ so $n \geq 48$. Now we are left to show that $n=48$ fits. Consider the set $\{2,3, \ldots, 33,36,37, \ldots, 50,67\}$ which contains exactly 48 numbers. We have $$\frac{1}{2} \cdot \frac{2}{3} \cdots \frac{32}{33} \cdot \frac{35}{36} \cdots \frac{49}{50} \cdot \frac{66}{67}=\frac{1}{33} \cdot \frac{35}{50} \cdot \frac{66}{67}=\frac{7}{335}=\frac{42}{2010}$$ hence for $n=48$ there exists a desired example. Comment 1. In this version of the problem, the estimate needs one more step, hence it is a bit harder. On the other hand, the example in this version is not unique. Another example is $$\frac{1}{2} \cdot \frac{2}{3} \cdots \frac{46}{47} \cdot \frac{66}{67} \cdot \frac{329}{330}=\frac{1}{67} \cdot \frac{66}{330} \cdot \frac{329}{47}=\frac{7}{67 \cdot 5}=\frac{42}{2010} .$$ Comment 2. N1' was the Proposer's formulation of the problem. We propose N1 according to the number of current IMO.

Find all pairs $(m, n)$ of nonnegative integers for which $$m^{2}+2 \cdot 3^{n}=m\left(2^{n+1}-1\right)$$ (Australia)

Find the smallest number $n$ such that there exist polynomials $f_{1}, f_{2}, \ldots, f_{n}$ with rational coefficients satisfying $$x^{2}+7=f_{1}(x)^{2}+f_{2}(x)^{2}+\cdots+f_{n}(x)^{2} .$$ (Poland)

Let $a, b$ be integers, and let $P(x)=a x^{3}+b x$. For any positive integer $n$ we say that the pair $(a, b)$ is $n$-good if $n \mid P(m)-P(k)$ implies $n \mid m-k$ for all integers $m, k$. We say that $(a, b)$ is very good if $(a, b)$ is $n$-good for infinitely many positive integers $n$. (a) Find a pair $(a, b)$ which is 51 -good, but not very good. (b) Show that all 2010-good pairs are very good. (Turkey)

Let $\mathbb{N}$ be the set of all positive integers. Find all functions $f: \mathbb{N} \rightarrow \mathbb{N}$ such that the number $(f(m)+n)(m+f(n))$ is a square for all $m, n \in \mathbb{N}$.

The rows and columns of a $2^{n} \times 2^{n}$ table are numbered from 0 to $2^{n}-1$. The cells of the table have been colored with the following property being satisfied: for each $0 \leq i, j \leq 2^{n}-1$, the $j$ th cell in the $i$ th row and the $Prove that the maximal possible number of colors is$2^{n}$.