ISL 2006

A sequence of real numbers $a_{0}, a_{1}, a_{2}, \ldots$ is defined by the formula $$a_{i+1}=\left\lfloor a_{i}\right\rfloor \cdot\left\langle a_{i}\right\rangle \text { for } i \geq 0 \text {; }$$ here $a_{0}$ is an arbitrary real number, $\left\lfloor a_{i}\right\rfloor$ denotes the greatest integer not exceeding $a_{i}$, and $\left\langle a_{i}\right\rangle=a_{i}-\left\lfloor a_{i}\right\rfloor$. Prove that $a_{i}=a_{i+2}$ for $i$ sufficiently large. (Estonia)

The sequence of real numbers $a_{0}, a_{1}, a_{2}, \ldots$ is defined recursively by $$a_{0}=-1, \sum_{k=0}^{n} \frac{a_{n-k}}{k+1}=0 \text { for } n \geq 1$$ Show that $a_{n}>0$ for $n \geq 1$. (Poland)

The sequence $c_{0}, c_{1}, \ldots, c_{n}, \ldots$ is defined by $c_{0}=1, c_{1}=0$ and $c_{n+2}=c_{n+1}+c_{n}$ for $n \geq 0$. Consider the set $S$ of ordered pairs $(x, y)$ for which there is a finite set $J$ of positive integers such that $x=\sum_{j \in J} c_{j}, y=\sum_{j \in J} c_{j-1}$. Prove that there exist real numbers $\alpha, \beta$ and $m, M$ with the following property: An ordered pair of nonnegative integers $(x, y)$ satisfies the inequality $$m<\alpha x+\beta y<M$$ if and only if $(x, y) \in S$. N. B. A sum over the elements of the empty set is assumed to be 0 . (Russia)

Prove the inequality $$\sum_{i<j} \frac{a_{i} a_{j}}{a_{i}+a_{j}} \leq \frac{n}{2\left(a_{1}+a_{2}+\cdots+a_{n}\right)} \sum_{i<j} a_{i} a_{j}$$ for positive real numbers $a_{1}, a_{2}, \ldots, a_{n}$. (Serbia)

Let $a, b, c$ be the sides of a triangle. Prove that $$\frac{\sqrt{b+c-a}}{\sqrt{b}+\sqrt{c}-\sqrt{a}}+\frac{\sqrt{c+a-b}}{\sqrt{c}+\sqrt{a}-\sqrt{b}}+\frac{\sqrt{a+b-c}}{\sqrt{a}+\sqrt{b}-\sqrt{c}} \leq 3 .$$ (Korea)

Determine the smallest number $M$ such that the inequality $$\left|a b\left(a^{2}-b^{2}\right)+b c\left(b^{2}-c^{2}\right)+c a\left(c^{2}-a^{2}\right)\right| \leq M\left(a^{2}+b^{2}+c^{2}\right)^{2}$$ holds for all real numbers $a, b, c$. (Ireland)

We have $n \geq 2$ lamps $L_{1}, \ldots, L_{n}$ in a row, each of them being either on or off. Every second we simultaneously modify the state of each lamp as follows: - if the lamp $L_{i}$ and its neighbours (only one neighbour for $i=1$ or $i=n$, two neighbours for other $i$ ) are in the same state, then $L_{i}$ is switched off; - otherwise, $L_{i}$ is switched on. Initially all the lamps are off except the leftmost one which is on. (a) Prove that there are infinitely many integers $n$ for which all the lamps will eventually be off. (b) Prove that there are infinitely many integers $n$ for which the lamps will never be all off. (France)

A diagonal of a regular 2006-gon is called odd if its endpoints divide the boundary into two parts, each composed of an odd number of sides. Sides are also regarded as odd diagonals. Suppose the 2006-gon has been dissected into triangles by 2003 nonintersecting diagonals. Find the maximum possible number of isosceles triangles with two odd sides. (Serbia)

Let $S$ be a finite set of points in the plane such that no three of them are on a line. For each convex polygon $P$ whose vertices are in $S$, let $a(P)$ be the number of vertices of $P$, and let $b(P)$ be the number of points of $S$ which are outside $P$. Prove that for every real number $x$ $$\sum_{P} x^{a(P)}(1-x)^{b(P)}=1$$ where the sum is taken over all convex polygons with vertices in $S$. NB. A line segment, a point and the empty set are considered as convex polygons of 2,1 and 0 vertices, respectively. (Colombia)

A cake has the form of an $n \times n$ square composed of $n^{2}$ unit squares. Strawberries lie on some of the unit squares so that each row or column contains exactly one strawberry; call this arrangement $\mathcal{A}$. Let $\mathcal{B}$ be another such arrangement. Suppose that every grid rectangle with one vertex at the top left corner of the cake contains no fewer strawberries of arrangement $\mathcal{B}$ than of arrangement $\mathcal{A}$. Prove that arrangement $\mathcal{B}$ can be obtained from $\mathcal{A}$ by performing a number of switches, defined as follows: A switch consists in selecting a grid rectangle with only two strawberries, situated at its top right corner and bottom left corner, and moving these two strawberries to the other two corners of that rectangle. (Taiwan)

An $(n, k)$-tournament is a contest with $n$ players held in $k$ rounds such that: (i) Each player plays in each round, and every two players meet at most once. (ii) If player $A$ meets player $B$ in round $i$, player $C$ meets player $D$ in round $i$, and player $A$ meets player $C$ in round $j$, then player $B$ meets player $D$ in round $j$. Determine all pairs $(n, k)$ for which there exists an $(n, k)$-tournament. (Argentina)

A holey triangle is an upward equilateral triangle of side length $n$ with $n$ upward unit triangular holes cut out. A diamond is a $60^{\circ}-120^{\circ}$ unit rhombus. Prove that a holey triangle $T$ can be tiled with diamonds if and only if the following condition holds: Every upward equilateral triangle of side length $k$ in $T$ contains at most $k$ holes, for $1 \leq k \leq n$. (Colombia)

Consider a convex polyhedron without parallel edges and without an edge parallel to any face other than the two faces adjacent to it. Call a pair of points of the polyhedron antipodal if there exist two parallel planes passing through these points and such that the polyhedron is contained between these planes. Let $A$ be the number of antipodal pairs of vertices, and let $B$ be the number of antipodal pairs of midpoints of edges. Determine the difference $A-B$ in terms of the numbers of vertices, edges and faces. (Japan)

Let $A B C$ be a triangle with incentre $I$. A point $P$ in the interior of the triangle satisfies $$\angle P B A+\angle P C A=\angle P B C+\angle P C B .$$ Show that $A P \geq A I$ and that equality holds if and only if $P$ coincides with $I$. (Korea)

Let $A B C D$ be a trapezoid with parallel sides $A B>C D$. Points $K$ and $L$ lie on the line segments $A B$ and $C D$, respectively, so that $A K / K B=D L / L C$. Suppose that there are points $P$ and $Q$ on the line segment $K L$ satisfying $$\angle A P B=\angle B C D \text { and } \angle C Q D=\angle A B C \text {. }$$ Prove that the points $P, Q, B$ and $C$ are concyclic. (Ukraine)

Let $A B C D E$ be a convex pentagon such that $$\angle B A C=\angle C A D=\angle D A E \text { and } \angle A B C=\angle A C D=\angle A D E \text {. }$$ The diagonals $B D$ and $C E$ meet at $P$. Prove that the line $A P$ bisects the side $C D$.

A point $D$ is chosen on the side $A C$ of a triangle $A B C$ with $\angle C<\angle A<90^{\circ}$ in such a way that $B D=B A$. The incircle of $A B C$ is tangent to $A B$ and $A C$ at points $K$ and $L$, respectively. Let $J$ be the incentre of triangle $B C D$. Prove that the line $K L$ intersects the line segment $A J$ at its midpoint. (Russia)

In triangle $A B C$, let $J$ be the centre of the excircle tangent to side $B C$ at $A_{1}$ and to the extensions of sides $A C$ and $A B$ at $B_{1}$ and $C_{1}$, respectively. Suppose that the lines $A_{1} B_{1}$ and $A B$ are perpendicular and intersect at $D$. Let $E$ be the foot of the perpendicular from $C_{1}$ to line $D J$. Determine the angles $\angle B E A_{1}$ and $\angle A E B_{1}$. (Greece)

Circles $\omega_{1}$ and $\omega_{2}$ with centres $O_{1}$ and $O_{2}$ are externally tangent at point $D$ and internally tangent to a circle $\omega$ at points $E$ and $F$, respectively. Line $t$ is the common tangent of $\omega_{1}$ and $\omega_{2}$ at $D$. Let $A B$ be the diameter of $\omega$ perpendicular to $t$, so that $A, E$ and $O_{1}$ are on the same side of $t$. Prove that lines $A O_{1}, B O_{2}, E F$ and $t$ are concurrent. (Brasil)

In a triangle $A B C$, let $M_{a}, M_{b}, M_{c}$ be respectively the midpoints of the sides $B C, C A$, $A B$ and $T_{a}, T_{b}, T_{c}$ be the midpoints of the $\operatorname{arcs} B C, C A, A B$ of the circumcircle of $A B C$, not containing the opposite vertices. For $i \in\{a, b, c\}$, let $\omega_{i}$ be the circle with $M_{i} T_{i}$ as diameter. Let $p_{i}$ be the common external tangent to $\omega_{j}, \omega_{k}(\{i, j, k\}=\{a, b, c\})$ such that $\omega_{i}$ lies on the opposite side of $p_{i}$ than $\omega_{j}, \omega_{k}$ do. Prove that the lines $p_{a}, p_{b}, p_{c}$ form a triangle similar to $A B C$ and find the ratio of similitude. (Slovakia)

Let $A B C D$ be a convex quadrilateral. A circle passing through the points $A$ and $D$ and a circle passing through the points $B$ and $C$ are externally tangent at a point $P$ inside the quadrilateral. Suppose that $$\angle P A B+\angle P D C \leq 90^{\circ} \text { and } \angle P B A+\angle P C D \leq 90^{\circ} \text {. }$$ Prove that $A B+C D \geq B C+A D$. (Poland)

Points $A_{1}, B_{1}, C_{1}$ are chosen on the sides $B C, C A, A B$ of a triangle $A B C$, respectively. The circumcircles of triangles $A B_{1} C_{1}, B C_{1} A_{1}, C A_{1} B_{1}$ intersect the circumcircle of triangle $A B C$ again at points $A_{2}, B_{2}, C_{2}$, respectively $\left(A_{2} \neq A, B_{2} \neq B, C_{2} \neq C\right)$. Points $A_{3}, B_{3}, C_{3}$ are symmetric to $A_{1}, B_{1}, C_{1}$ with respect to the midpoints of the sides $B C, C A, A B$ respectively. Prove that the triangles $A_{2} B_{2} C_{2}$ and $A_{3} B_{3} C_{3}$ are similar. (Russia)

To each side $a$ of a convex polygon we assign the maximum area of a triangle contained in the polygon and having $a$ as one of its sides. Show that the sum of the areas assigned to all sides of the polygon is not less than twice the area of the polygon. (Serbia)

Determine all pairs $(x, y)$ of integers satisfying the equation $$1+2^{x}+2^{2 x+1}=y^{2} .$$

For $x \in(0,1)$ let $y \in(0,1)$ be the number whose $n$th digit after the decimal point is the $\left(2^{n}\right)$ th digit after the decimal point of $x$. Show that if $x$ is rational then so is $y$. (Canada)

The sequence $f(1), f(2), f(3), \ldots$ is defined by $$f(n)=\frac{1}{n}\left(\left\lfloor\frac{n}{1}\right\rfloor+\left\lfloor\frac{n}{2}\right\rfloor+\cdots+\left\lfloor\frac{n}{n}\right\rfloor\right),$$ where $\lfloor x\rfloor$ denotes the integer part of $x$. (a) Prove that $f(n+1)>f(n)$ infinitely often. (b) Prove that $f(n+1)<f(n)$ infinitely often. (South Africa)

Let $P$ be a polynomial of degree $n>1$ with integer coefficients and let $k$ be any positive integer. Consider the polynomial $Q(x)=P(P(\ldots P(P(x)) \ldots))$, with $k$ pairs of parentheses. Prove that $Q$ has no more than $n$ integer fixed points, i.e. integers satisfying the equation $Q(x)=x$. (Romania)

Find all integer solutions of the equation $$\frac{x^{7}-1}{x-1}=y^{5}-1$$ (Russia)

Let $a>b>1$ be relatively prime positive integers. Define the weight of an integer $c$, denoted by $w(c)$, to be the minimal possible value of $|x|+|y|$ taken over all pairs of integers $x$ and $y$ such that $$a x+b y=c .$$ An integer $c$ is called a local champion if $w(c) \geq w(c \pm a)$ and $w(c) \geq w(c \pm b)$. Find all local champions and determine their number.

Prove that, for every positive integer $n$, there exists an integer $m$ such that $2^{m}+m$ is divisible by $n$. (Estonia)