ISL 2009

Find the largest possible integer $k$, such that the following statement is true: Let 2009 arbitrary non-degenerated triangles be given. In every triangle the three sides are colored, such that one is blue, one is red and one is white. Now, for every color separately, let us sort the lengths of the sides. We obtain $$\begin{aligned} & b_{1} \leq b_{2} \\ & \leq \ldots \leq b_{2009} \text { the lengths of the blue sides, } \\ r_{1} & \leq r_{2} \leq \ldots \leq r_{2009} \text { the lengths of the red sides, } \\ \text { and } w_{1} & \leq w_{2} \leq \ldots \leq w_{2009} \text { the lengths of the white sides. } \end{aligned}$$ Then there exist $k$ indices $j$ such that we can form a non-degenerated triangle with side lengths $b_{j}, r_{j}, w_{j}$ 。

Let $a, b, c$ be positive real numbers such that $\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=a+b+c$. Prove that $$\frac{1}{(2 a+b+c)^{2}}+\frac{1}{(2 b+c+a)^{2}}+\frac{1}{(2 c+a+b)^{2}} \leq \frac{3}{16}$$

Determine all functions $f$ from the set of positive integers into the set of positive integers such that for all $x$ and $y$ there exists a non degenerated triangle with sides of lengths $$x, f(y) \text { and } f(y+f(x)-1)$$

Let $a, b, c$ be positive real numbers such that $a b+b c+c a \leq 3 a b c$. Prove that $$\sqrt{\frac{a^{2}+b^{2}}{a+b}}+\sqrt{\frac{b^{2}+c^{2}}{b+c}}+\sqrt{\frac{c^{2}+a^{2}}{c+a}}+3 \leq \sqrt{2}(\sqrt{a+b}+\sqrt{b+c}+\sqrt{c+a}) .$$

Let $f$ be any function that maps the set of real numbers into the set of real numbers. Prove that there exist real numbers $x$ and $y$ such that $$f(x-f(y))>y f(x)+x$$

Suppose that $s_{1}, s_{2}, s_{3}, \ldots$ is a strictly increasing sequence of positive integers such that the subsequences $$s_{s_{1}}, s_{s_{2}}, s_{s_{3}}, \ldots \text { and } s_{s_{1}+1}, s_{s_{2}+1}, s_{s_{3}+1}, \ldots$$ are both arithmetic progressions. Prove that $s_{1}, s_{2}, s_{3}, \ldots$ is itself an arithmetic progression.

Find all functions $f$ from the set of real numbers into the set of real numbers which satisfy for all real $x, y$ the identity $$f(x f(x+y))=f(y f(x))+x^{2}$$

Consider 2009 cards, each having one gold side and one black side, lying in parallel on a long table. Initially all cards show their gold sides. Two players, standing by the same long side of the table, play a game with alternating moves. Each move consists of choosing a block of 50 consecutive cards, the leftmost of which is showing gold, and turning them all over, so those which showed gold now show black and vice versa. The last player who can make a legal move wins. (a) Does the game necessarily end? (b) Does there exist a winning strategy for the starting player?

For any integer $n \geq 2$, let $N(n)$ be the maximal number of triples $\left(a_{i}, b_{i}, c_{i}\right), i=1, \ldots, N(n)$, consisting of nonnegative integers $a_{i}, b_{i}$ and $c_{i}$ such that the following two conditions are satisfied: (1) $a_{i}+b_{i}+c_{i}=n$ for all $i=1, \ldots, N(n)$, (2) If $i \neq j$, then $a_{i} \neq a_{j}, b_{i} \neq b_{j}$ and $c_{i} \neq c_{j}$. Determine $N(n)$ for all $n \geq 2$. Comment. The original problem was formulated for $m$-tuples instead for triples. The numbers $N(m, n)$ are then defined similarly to $N(n)$ in the case $m=3$. The numbers $N(3, n)$ and $N(n, n)$ should be determined. The case $m=3$ is the same as in the present problem. The upper bound for $N(n, n)$ can be proved by a simple generalization. The construction of a set of triples attaining the bound can be easily done by induction from $n$ to $n+2$.

Let $n$ be a positive integer. Given a sequence $\varepsilon_{1}, \ldots, \varepsilon_{n-1}$ with $\varepsilon_{i}=0$ or $\varepsilon_{i}=1$ for each $i=1, \ldots, n-1$, the sequences $a_{0}, \ldots, a_{n}$ and $b_{0}, \ldots, b_{n}$ are constructed by the following rules: $$\begin{gathered} a_{0}=b_{0}=1, a_{1}=b_{1}=7, \\ a_{i+1}=\left\{\begin{array}{ll} 2 a_{i-1}+3 a_{i}, & \text { if } \varepsilon_{i}=0, \\ 3 a_{i-1}+a_{i}, & \text { if } \varepsilon_{i}=1, \end{array} \text { for each } i=1, \ldots, n-1,\right. \\ b_{i+1}=\left\{\begin{array}{ll} 2 b_{i-1}+3 b_{i}, & \text { if } \varepsilon_{n-i}=0, \\ 3 b_{i-1}+b_{i}, & \text { if } \varepsilon_{n-i}=1, \end{array} \text { for each } i=1, \ldots, n-1 .\right. \end{gathered}$$ Prove that $a_{n}=b_{n}$.

For an integer $m \geq 1$, we consider partitions of a $2^{m} \times 2^{m}$ chessboard into rectangles consisting of cells of the chessboard, in which each of the $2^{m}$ cells along one diagonal forms a separate rectangle of side length 1 . Determine the smallest possible sum of rectangle perimeters in such a partition.

Five identical empty buckets of 2-liter capacity stand at the vertices of a regular pentagon. Cinderella and her wicked Stepmother go through a sequence of rounds: At the beginning of every round, the Stepmother takes one liter of water from the nearby river and distributes it arbitrarily over the five buckets. Then Cinderella chooses a pair of neighboring buckets, empties them into the river, and puts them back. Then the next round begins. The Stepmother's goal is to make one of these buckets overflow. Cinderella's goal is to prevent this. Can the wicked Stepmother enforce a bucket overflow?

On a $999 \times 999$ board a limp rook can move in the following way: From any square it can move to any of its adjacent squares, i.e. a square having a common side with it, and every move must be a turn, i.e. the directions of any two consecutive moves must be perpendicular. A nonintersecting route of the limp rook consists of a sequence of pairwise different squares that the limp rook can visit in that order by an admissible sequence of moves. Such a non-intersecting route is called cyclic, if the limp rook can, after reaching the last square of the route, move directly to the first square of the route and start over. How many squares does the longest possible cyclic, non-intersecting route of a limp rook visit?

A grasshopper jumps along the real axis. He starts at point 0 and makes 2009 jumps to the right with lengths $1,2, \ldots, 2009$ in an arbitrary order. Let $M$ be a set of 2008 positive integers less than 1005 - 2009. Prove that the grasshopper can arrange his jumps in such a way that he never lands on a point from $M$. Variant 2. Let $n$ be a nonnegative integer. A grasshopper jumps along the real axis. He starts at point 0 and makes $n+1$ jumps to the right with pairwise different positive integral lengths $a_{1}, a_{2}, \ldots, a_{n+1}$ in an arbitrary order. Let $M$ be a set of $n$ positive integers in the interval $(0, s)$, where $s=a_{1}+a_{2}+\cdots+a_{n+1}$. Prove that the grasshopper can arrange his jumps in such a way that he never lands on a point from $M$.

For any integer $n \geq 2$, we compute the integer $h(n)$ by applying the following procedure to its decimal representation. Let $r$ be the rightmost digit of $n$. (1) If $r=0$, then the decimal representation of $h(n)$ results from the decimal representation of $n$ by removing this rightmost digit 0 . (2) If $1 \leq r \leq 9$ we split the decimal representation of $n$ into a maximal right part $R$ that solely consists of digits not less than $r$ and into a left part $L$ that either is empty or ends with a digit strictly smaller than $r$. Then the decimal representation of $h(n)$ consists of the decimal representation of $L$, followed by two copies of the decimal representation of $R-1$. For instance, for the number $n=17,151,345,543$, we will have $L=17,151, R=345,543$ and $h(n)=17,151,345,542,345,542$. Prove that, starting with an arbitrary integer $n \geq 2$, iterated application of $h$ produces the integer 1 after finitely many steps.

Let $A B C$ be a triangle with $A B=A C$. The angle bisectors of $A$ and $B$ meet the sides $B C$ and $A C$ in $D$ and $E$, respectively. Let $K$ be the incenter of triangle $A D C$. Suppose that $\angle B E K=45^{\circ}$. Find all possible values of $\angle B A C$.

Let $A B C$ be a triangle with circumcenter $O$. The points $P$ and $Q$ are interior points of the sides $C A$ and $A B$, respectively. The circle $k$ passes through the midpoints of the segments $B P$, $C Q$, and $P Q$. Prove that if the line $P Q$ is tangent to circle $k$ then $O P=O Q$.

Let $A B C$ be a triangle. The incircle of $A B C$ touches the sides $A B$ and $A C$ at the points $Z$ and $Y$, respectively. Let $G$ be the point where the lines $B Y$ and $C Z$ meet, and let $R$ and $S$ be points such that the two quadrilaterals $B C Y R$ and $B C S Z$ are parallelograms. Prove that $G R=G S$.

Given a cyclic quadrilateral $A B C D$, let the diagonals $A C$ and $B D$ meet at $E$ and the lines $A D$ and $B C$ meet at $F$. The midpoints of $A B$ and $C D$ are $G$ and $H$, respectively. Show that $E F$ is tangent at $E$ to the circle through the points $E, G$, and $H$.

Let $P$ be a polygon that is convex and symmetric to some point $O$. Prove that for some parallelogram $R$ satisfying $P \subset R$ we have $$\frac{|R|}{|P|} \leq \sqrt{2}$$ where $|R|$ and $|P|$ denote the area of the sets $R$ and $P$, respectively.

Let the sides $A D$ and $B C$ of the quadrilateral $A B C D$ (such that $A B$ is not parallel to $C D$ ) intersect at point $P$. Points $O_{1}$ and $O_{2}$ are the circumcenters and points $H_{1}$ and $H_{2}$ are the orthocenters of triangles $A B P$ and $D C P$, respectively. Denote the midpoints of segments $O_{1} H_{1}$ and $O_{2} H_{2}$ by $E_{1}$ and $E_{2}$, respectively. Prove that the perpendicular from $E_{1}$ on $C D$, the perpendicular from $E_{2}$ on $A B$ and the line $H_{1} H_{2}$ are concurrent.

Let $A B C$ be a triangle with incenter $I$ and let $X, Y$ and $Z$ be the incenters of the triangles $B I C, C I A$ and $A I B$, respectively. Let the triangle $X Y Z$ be equilateral. Prove that $A B C$ is equilateral too.

Let $A B C D$ be a circumscribed quadrilateral. Let $g$ be a line through $A$ which meets the segment $B C$ in $M$ and the line $C D$ in $N$. Denote by $I_{1}, I_{2}$, and $I_{3}$ the incenters of $\triangle A B M$, $\triangle M N C$, and $\triangle N D A$, respectively. Show that the orthocenter of $\triangle I_{1} I_{2} I_{3}$ lies on $g$.

A social club has $n$ members. They have the membership numbers $1,2, \ldots, n$, respectively. From time to time members send presents to other members, including items they have already received as presents from other members. In order to avoid the embarrassing situation that a member might receive a present that he or she has sent to other members, the club adds the following rule to its statutes at one of its annual general meetings: "A member with membership number $a$ is permitted to send a present to a member with membership number $b$ if and only if $a(b-1)$ is a multiple of $n$." Prove that, if each member follows this rule, none will receive a present from another member that he or she has already sent to other members. Alternative formulation: Let $G$ be a directed graph with $n$ vertices $v_{1}, v_{2}, \ldots, v_{n}$, such that there is an edge going from $v_{a}$ to $v_{b}$ if and only if $a$ and $b$ are distinct and $a(b-1)$ is a multiple of $n$. Prove that this graph does not contain a directed cycle.

A positive integer $N$ is called balanced, if $N=1$ or if $N$ can be written as a product of an even number of not necessarily distinct primes. Given positive integers $a$ and $b$, consider the polynomial $P$ defined by $P(x)=(x+a)(x+b)$. (a) Prove that there exist distinct positive integers $a$ and $b$ such that all the numbers $P(1), P(2)$, $\ldots, P(50)$ are balanced. (b) Prove that if $P(n)$ is balanced for all positive integers $n$, then $a=b$.

Let $f$ be a non-constant function from the set of positive integers into the set of positive integers, such that $a-b$ divides $f(a)-f(b)$ for all distinct positive integers $a, b$. Prove that there exist infinitely many primes $p$ such that $p$ divides $f(c)$ for some positive integer $c$.

Find all positive integers $n$ such that there exists a sequence of positive integers $a_{1}, a_{2}, \ldots, a_{n}$ satisfying $$a_{k+1}=\frac{a_{k}^{2}+1}{a_{k-1}+1}-1$$ for every $k$ with $2 \leq k \leq n-1$.

Let $P(x)$ be a non-constant polynomial with integer coefficients. Prove that there is no function $T$ from the set of integers into the set of integers such that the number of integers $x$ with $T^{n}(x)=x$ is equal to $P(n)$ for every $n \geq 1$, where $T^{n}$ denotes the $n$-fold application of $T$.

Let $k$ be a positive integer. Show that if there exists a sequence $a_{0}, a_{1}, \ldots$ of integers satisfying the condition $$a_{n}=\frac{a_{n-1}+n^{k}}{n} \text { for all } n \geq 1$$ then $k-2$ is divisible by 3 .

Let $a$ and $b$ be distinct integers greater than 1 . Prove that there exists a positive integer $n$ such that $\left(a^{n}-1\right)\left(b^{n}-1\right)$ is not a perfect square.