ISL 2007

Given a sequence $a_{1}, a_{2}, \ldots, a_{n}$ of real numbers. For each $i(1 \leq i \leq n)$ define $$d_{i}=\max \left\{a_{j}: 1 \leq j \leq i\right\}-\min \left\{a_{j}: i \leq j \leq n\right\}$$ and let $$d=\max \left\{d_{i}: 1 \leq i \leq n\right\}$$ (a) Prove that for arbitrary real numbers $x_{1} \leq x_{2} \leq \ldots \leq x_{n}$, $$\max \left\{\left|x_{i}-a_{i}\right|: 1 \leq i \leq n\right\} \geq \frac{d}{2}$$ (b) Show that there exists a sequence $x_{1} \leq x_{2} \leq \ldots \leq x_{n}$ of real numbers such that we have equality in (1). (New Zealand)

Consider those functions $f: \mathbb{N} \rightarrow \mathbb{N}$ which satisfy the condition $$f(m+n) \geq f(m)+f(f(n))-1$$ for all $m, n \in \mathbb{N}$. Find all possible values of $f(2007)$. $(\mathbb{N}$ denotes the set of all positive integers.) (Bulgaria)

Let $n$ be a positive integer, and let $x$ and $y$ be positive real numbers such that $x^{n}+y^{n}=1$. Prove that $$\left(\sum_{k=1}^{n} \frac{1+x^{2 k}}{1+x^{4 k}}\right)\left(\sum_{k=1}^{n} \frac{1+y^{2 k}}{1+y^{4 k}}\right)<\frac{1}{(1-x)(1-y)}$$ (Estonia)

Find all functions $f: \mathbb{R}^{+} \rightarrow \mathbb{R}^{+}$such that $$f(x+f(y))=f(x+y)+f(y)$$ for all $x, y \in \mathbb{R}^{+}$. (Symbol $\mathbb{R}^{+}$denotes the set of all positive real numbers.) (Thaliand)

Let $c>2$, and let $a(1), a(2), \ldots$ be a sequence of nonnegative real numbers such that $$a(m+n) \leq 2 a(m)+2 a(n) \text { for all } m, n \geq 1 \text {, }$$ and $$a\left(2^{k}\right) \leq \frac{1}{(k+1)^{c}} \text { for all } k \geq 0$$ Prove that the sequence $a(n)$ is bounded. (Croatia)

Let $a_{1}, a_{2}, \ldots, a_{100}$ be nonnegative real numbers such that $a_{1}^{2}+a_{2}^{2}+\ldots+a_{100}^{2}=1$. Prove that $$a_{1}^{2} a_{2}+a_{2}^{2} a_{3}+\ldots+a_{100}^{2} a_{1}<\frac{12}{25}$$ (Poland)

Let $n>1$ be an integer. In the space, consider the set $$S=\{(x, y, z) \mid x, y, z \in\{0,1, \ldots, n\}, x+y+z>0\}$$ Find the smallest number of planes that jointly contain all $(n+1)^{3}-1$ points of $S$ but none of them passes through the origin. (Netherlands)

Let $n>1$ be an integer. Find all sequences $a_{1}, a_{2}, \ldots, a_{n^{2}+n}$ satisfying the following conditions: (a) $a_{i} \in\{0,1\}$ for all $1 \leq i \leq n^{2}+n$; (b) $a_{i+1}+a_{i+2}+\ldots+a_{i+n}<a_{i+n+1}+a_{i+n+2}+\ldots+a_{i+2 n}$ for all $0 \leq i \leq n^{2}-n$. (Serbia)

A unit square is dissected into $n>1$ rectangles such that their sides are parallel to the sides of the square. Any line, parallel to a side of the square and intersecting its interior, also intersects the interior of some rectangle. Prove that in this dissection, there exists a rectangle having no point on the boundary of the square. (Japan)

Find all positive integers $n$, for which the numbers in the set $S=\{1,2, \ldots, n\}$ can be colored red and blue, with the following condition being satisfied: the set $S \times S \times S$ contains exactly 2007 ordered triples $(x, y, z)$ such that (i) $x, y, z$ are of the same color and (ii) $x+y+z$ is divisible by $n$. (Netherlands)

Let $A_{0}=\left(a_{1}, \ldots, a_{n}\right)$ be a finite sequence of real numbers. For each $k \geq 0$, from the sequence $A_{k}=\left(x_{1}, \ldots, x_{n}\right)$ we construct a new sequence $A_{k+1}$ in the following way. 1. We choose a partition $\{1, \ldots, n\}=I \cup J$, where $I$ and $J$ are two disjoint sets, such that the expression $$\left|\sum_{i \in I} x_{i}-\sum_{j \in J} x_{j}\right|$$ attains the smallest possible value. (We allow the sets $I$ or $J$ to be empty; in this case the corresponding sum is 0 .) If there are several such partitions, one is chosen arbitrarily. 2. We set $A_{k+1}=\left(y_{1}, \ldots, y_{n}\right)$, where $y_{i}=x_{i}+1$ if $i \in I$, and $y_{i}=x_{i}-1$ if $i \in J$. Prove that for some $k$, the sequence $A_{k}$ contains an element $x$ such that $|x| \geq n / 2$. (Iran)

In the Cartesian coordinate plane define the strip $S_{n}=\{(x, y) \mid n \leq x<n+1\}$ for every integer $n$. Assume that each strip $S_{n}$ is colored either red or blue, and let $a$ and $b$ be two distinct positive integers. Prove that there exists a rectangle with side lengths $a$ and $b$ such that its vertices have the same color. (Romania)

In a mathematical competition some competitors are friends; friendship is always mutual. Call a group of competitors a clique if each two of them are friends. The number of members in a clique is called its size. It is known that the largest size of cliques is even. Prove that the competitors can be arranged in two rooms such that the largest size of cliques in one room is the same as the largest size of cliques in the other room. (Russia)

Let $\alpha<\frac{3-\sqrt{5}}{2}$ be a positive real number. Prove that there exist positive integers $n$ and $p>\alpha \cdot 2^{n}$ for which one can select $2 p$ pairwise distinct subsets $S_{1}, \ldots, S_{p}, T_{1}, \ldots, T_{p}$ of the set $\{1,2, \ldots, n\}$ such that $S_{i} \cap T_{j} \neq \varnothing$ for all $1 \leq i, j \leq p$. (Austria)

Given a convex $n$-gon $P$ in the plane. For every three vertices of $P$, consider the triangle determined by them. Call such a triangle good if all its sides are of unit length. Prove that there are not more than $\frac{2}{3} n$ good triangles. (Ukraine)

In triangle $A B C$, the angle bisector at vertex $C$ intersects the circumcircle and the perpendicular bisectors of sides $B C$ and $C A$ at points $R, P$, and $Q$, respectively. The midpoints of $B C$ and $C A$ are $S$ and $T$, respectively. Prove that triangles $R Q T$ and $R P S$ have the same area. (Czech Republic)

Given an isosceles triangle $A B C$ with $A B=A C$. The midpoint of side $B C$ is denoted by $M$. Let $X$ be a variable point on the shorter arc $M A$ of the circumcircle of triangle $A B M$. Let $T$ be the point in the angle domain $B M A$, for which $\angle T M X=90^{\circ}$ and $T X=B X$. Prove that $\angle M T B-\angle C T M$ does not depend on $X$. (Canada)

The diagonals of a trapezoid $A B C D$ intersect at point $P$. Point $Q$ lies between the parallel lines $B C$ and $A D$ such that $\angle A Q D=\angle C Q B$, and line $C D$ separates points $P$ and $Q$. Prove that $\angle B Q P=\angle D A Q$. (Ukraine)

Consider five points $A, B, C, D, E$ such that $A B C D$ is a parallelogram and $B C E D$ is a cyclic quadrilateral. Let $\ell$ be a line passing through $A$, and let $\ell$ intersect segment $D C$ and line $B C$ at points $F$ and $G$, respectively. Suppose that $E F=E G=E C$. Prove that $\ell$ is the bisector of angle $D A B$. (Luxembourg)

Let $A B C$ be a fixed triangle, and let $A_{1}, B_{1}, C_{1}$ be the midpoints of sides $B C, C A, A B$, respectively. Let $P$ be a variable point on the circumcircle. Let lines $P A_{1}, P B_{1}, P C_{1}$ meet the circumcircle again at $A^{\prime}, B^{\prime}, C^{\prime}$ respectively. Assume that the points $A, B, C, A^{\prime}, B^{\prime}, C^{\prime}$ are distinct, and lines $A A^{\prime}, B B^{\prime}, C C^{\prime}$ form a triangle. Prove that the area of this triangle does not depend on $P$. (United Kingdom)

Determine the smallest positive real number $k$ with the following property. Let $A B C D$ be a convex quadrilateral, and let points $A_{1}, B_{1}, C_{1}$ and $D_{1}$ lie on sides $A B, B C$, $C D$ and $D A$, respectively. Consider the areas of triangles $A A_{1} D_{1}, B B_{1} A_{1}, C C_{1} B_{1}$, and $D D_{1} C_{1}$; let $S$ be the sum of the two smallest ones, and let $S_{1}$ be the area of quadrilateral $A_{1} B_{1} C_{1} D_{1}$. Then we always have $k S_{1} \geq S$. (U.S.A.)

Given an acute triangle $A B C$ with angles $\alpha, \beta$ and $\gamma$ at vertices $A, B$ and $C$, respectively, such that $\beta>\gamma$. Point $I$ is the incenter, and $R$ is the circumradius. Point $D$ is the foot of the altitude from vertex $A$. Point $K$ lies on line $A D$ such that $A K=2 R$, and $D$ separates $A$ and $K$. Finally, lines $D I$ and $K I$ meet sides $A C$ and $B C$ at $E$ and $F$, respectively. Prove that if $I E=I F$ then $\beta \leq 3 \gamma$. (Iran)

Point $P$ lies on side $A B$ of a convex quadrilateral $A B C D$. Let $\omega$ be the incircle of triangle $C P D$, and let $I$ be its incenter. Suppose that $\omega$ is tangent to the incircles of triangles $A P D$ and $B P C$ at points $K$ and $L$, respectively. Let lines $A C$ and $B D$ meet at $E$, and let lines $A K$ and $B L$ meet at $F$. Prove that points $E, I$, and $F$ are collinear. (Poland)

Find all pairs $(k, n)$ of positive integers for which $7^{k}-3^{n}$ divides $k^{4}+n^{2}$. (Austria)

Let $b, n>1$ be integers. Suppose that for each $k>1$ there exists an integer $a_{k}$ such that $b-a_{k}^{n}$ is divisible by $k$. Prove that $b=A^{n}$ for some integer $A$. (Canada)

Let $X$ be a set of 10000 integers, none of them is divisible by 47 . Prove that there exists a 2007-element subset $Y$ of $X$ such that $a-b+c-d+e$ is not divisible by 47 for any $a, b, c, d, e \in Y$. (Netherlands)

For every integer $k \geq 2$, prove that $2^{3 k}$ divides the number $$\left(\begin{array}{c} 2^{k+1} \\ 2^{k} \end{array}\right)-\left(\begin{array}{c} 2^{k} \\ 2^{k-1} \end{array}\right)$$ but $2^{3 k+1}$ does not. (Poland)

Find all surjective functions $f: \mathbb{N} \rightarrow \mathbb{N}$ such that for every $m, n \in \mathbb{N}$ and every prime $p$, the number $f(m+n)$ is divisible by $p$ if and only if $f(m)+f(n)$ is divisible by $p$. ( $\mathbb{N}$ is the set of all positive integers.) (Iran)

Let $k$ be a positive integer. Prove that the number $\left(4 k^{2}-1\right)^{2}$ has a positive divisor of the form $8 k n-1$ if and only if $k$ is even. (United Kingdom)

For a prime $p$ and a positive integer $n$, denote by $\nu_{p}(n)$ the exponent of $p$ in the prime factorization of $n$ !. Given a positive integer $d$ and a finite set $\left\{p_{1}, \ldots, p_{k}\right\}$ of primes. Show that there are infinitely many positive integers $n$ such that $d \mid \nu_{p_{i}}(n)$ for all $1 \leq i \leq k$. (India)