ISL 2008

Find all functions $f:(0, \infty) \rightarrow(0, \infty)$ such that $$\frac{f(p)^{2}+f(q)^{2}}{f\left(r^{2}\right)+f\left(s^{2}\right)}=\frac{p^{2}+q^{2}}{r^{2}+s^{2}}$$ for all $p, q, r, s>0$ with $p q=r s$.

(a) Prove the inequality $$\frac{x^{2}}{(x-1)^{2}}+\frac{y^{2}}{(y-1)^{2}}+\frac{z^{2}}{(z-1)^{2}} \geq 1$$ for real numbers $x, y, z \neq 1$ satisfying the condition $x y z=1$. (b) Show that there are infinitely many triples of rational numbers $x, y, z$ for which this inequality turns into equality.

Let $S \subseteq \mathbb{R}$ be a set of real numbers. We say that a pair $(f, g)$ of functions from $S$ into $S$ is a Spanish Couple on $S$, if they satisfy the following conditions: (i) Both functions are strictly increasing, i.e. $f(x)<f(y)$ and $g(x)<g(y)$ for all $x, y \in S$ with $x<y$; (ii) The inequality $f(g(g(x)))<g(f(x))$ holds for all $x \in S$. Decide whether there exists a Spanish Couple (a) on the set $S=\mathbb{N}$ of positive integers; (b) on the set $S=\{a-1 / b: a, b \in \mathbb{N}\}$.

For an integer $m$, denote by $t(m)$ the unique number in $\{1,2,3\}$ such that $m+t(m)$ is a multiple of 3. A function $f: \mathbb{Z} \rightarrow \mathbb{Z}$ satisfies $f(-1)=0, f(0)=1, f(1)=-1$ and $$f\left(2^{n}+m\right)=f\left(2^{n}-t(m)\right)-f(m) \text { for all integers } m, n \geq 0 \text { with } 2^{n}>m \text {. }$$ Prove that $f(3 p) \geq 0$ holds for all integers $p \geq 0$.

Let $a, b, c, d$ be positive real numbers such that $$a b c d=1 \text { and } a+b+c+d>\frac{a}{b}+\frac{b}{c}+\frac{c}{d}+\frac{d}{a}$$ Prove that $$a+b+c+d<\frac{b}{a}+\frac{c}{b}+\frac{d}{c}+\frac{a}{d}$$

Let $f: \mathbb{R} \rightarrow \mathbb{N}$ be a function which satisfies $$f\left(x+\frac{1}{f(y)}\right)=f\left(y+\frac{1}{f(x)}\right) \text { for all } x, y \in \mathbb{R} .$$ Prove that there is a positive integer which is not a value of $f$.

Prove that for any four positive real numbers $a, b, c, d$ the inequality $$\frac{(a-b)(a-c)}{a+b+c}+\frac{(b-c)(b-d)}{b+c+d}+\frac{(c-d)(c-a)}{c+d+a}+\frac{(d-a)(d-b)}{d+a+b} \geq 0$$ holds. Determine all cases of equality.

In the plane we consider rectangles whose sides are parallel to the coordinate axes and have positive length. Such a rectangle will be called a box. Two boxes intersect if they have a common point in their interior or on their boundary. Find the largest $n$ for which there exist $n$ boxes $B_{1}, \ldots, B_{n}$ such that $B_{i}$ and $B_{j}$ intersect if and only if $i \not \equiv j \pm 1(\bmod n)$.

For every positive integer $n$ determine the number of permutations $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ of the set $\{1,2, \ldots, n\}$ with the following property: $$2\left(a_{1}+a_{2}+\cdots+a_{k}\right) \text { is divisible by } k \text { for } k=1,2, \ldots, n \text {. }$$

In the coordinate plane consider the set $S$ of all points with integer coordinates. For a positive integer $k$, two distinct points $A, B \in S$ will be called $k$-friends if there is a point $C \in S$ such that the area of the triangle $A B C$ is equal to $k$. A set $T \subset S$ will be called a $k$-clique if every two points in $T$ are $k$-friends. Find the least positive integer $k$ for which there exists a $k$-clique with more than 200 elements.

Let $n$ and $k$ be fixed positive integers of the same parity, $k \geq n$. We are given $2 n$ lamps numbered 1 through $2 n$; each of them can be on or off. At the beginning all lamps are off. We consider sequences of $k$ steps. At each step one of the lamps is switched (from off to on or from on to off). Let $N$ be the number of $k$-step sequences ending in the state: lamps $1, \ldots, n$ on, lamps $n+1, \ldots, 2 n$ off. Let $M$ be the number of $k$-step sequences leading to the same state and not touching lamps $n+1, \ldots, 2 n$ at all. Find the ratio $N / M$.

Let $S=\left\{x_{1}, x_{2}, \ldots, x_{k+\ell}\right\}$ be a $(k+\ell)$-element set of real numbers contained in the interval $[0,1] ; k$ and $\ell$ are positive integers. A $k$-element subset $A \subset S$ is called nice if $$\left|\frac{1}{k} \sum_{x_{i} \in A} x_{i}-\frac{1}{\ell} \sum_{x_{j} \in S \backslash A} x_{j}\right| \leq \frac{k+\ell}{2 k \ell} .$$ Prove that the number of nice subsets is at least $\frac{2}{k+\ell}\left(\begin{array}{c}k+\ell \\ k\end{array}\right)$.

For $n \geq 2$, let $S_{1}, S_{2}, \ldots, S_{2^{n}}$ be $2^{n}$ subsets of $A=\left\{1,2,3, \ldots, 2^{n+1}\right\}$ that satisfy the following property: There do not exist indices $a$ and $b$ with $a<b$ and elements $x, y, z \in A$ with $x<y<z$ such that $y, z \in S_{a}$ and $x, z \in S_{b}$. Prove that at least one of the sets $S_{1}, S_{2}, \ldots, S_{2^{n}}$ contains no more than $4 n$ elements.

In an acute-angled triangle $A B C$, point $H$ is the orthocentre and $A_{0}, B_{0}, C_{0}$ are the midpoints of the sides $B C, C A, A B$, respectively. Consider three circles passing through $H$ : $\omega_{a}$ around $A_{0}, \omega_{b}$ around $B_{0}$ and $\omega_{c}$ around $C_{0}$. The circle $\omega_{a}$ intersects the line $B C$ at $A_{1}$ and $A_{2} ; \omega_{b}$ intersects $C A$ at $B_{1}$ and $B_{2} ; \omega_{c}$ intersects $A B$ at $C_{1}$ and $C_{2}$. Show that the points $A_{1}, A_{2}, B_{1}, B_{2}, C_{1}, C_{2}$ lie on a circle.

Given trapezoid $A B C D$ with parallel sides $A B$ and $C D$, assume that there exist points $E$ on line $B C$ outside segment $B C$, and $F$ inside segment $A D$, such that $\angle D A E=\angle C B F$. Denote by $I$ the point of intersection of $C D$ and $E F$, and by $J$ the point of intersection of $A B$ and $E F$. Let $K$ be the midpoint of segment $E F$; assume it does not lie on line $A B$. Prove that $I$ belongs to the circumcircle of $A B K$ if and only if $K$ belongs to the circumcircle of $C D J$.

Let $A B C D$ be a convex quadrilateral and let $P$ and $Q$ be points in $A B C D$ such that $P Q D A$ and $Q P B C$ are cyclic quadrilaterals. Suppose that there exists a point $E$ on the line segment $P Q$ such that $\angle P A E=\angle Q D E$ and $\angle P B E=\angle Q C E$. Show that the quadrilateral $A B C D$ is cyclic.

In an acute triangle $A B C$ segments $B E$ and $C F$ are altitudes. Two circles passing through the points $A$ and $F$ are tangent to the line $B C$ at the points $P$ and $Q$ so that $B$ lies between $C$ and $Q$. Prove that the lines $P E$ and $Q F$ intersect on the circumcircle of triangle $A E F$.

Let $k$ and $n$ be integers with $0 \leq k \leq n-2$. Consider a set $L$ of $n$ lines in the plane such that no two of them are parallel and no three have a common point. Denote by $I$ the set of intersection points of lines in $L$. Let $O$ be a point in the plane not lying on any line of $L$. A point $X \in I$ is colored red if the open line segment $O X$ intersects at most $k$ lines in $L$. Prove that $I$ contains at least $\frac{1}{2}(k+1)(k+2)$ red points.

There is given a convex quadrilateral $A B C D$. Prove that there exists a point $P$ inside the quadrilateral such that $$\angle P A B+\angle P D C=\angle P B C+\angle P A D=\angle P C D+\angle P B A=\angle P D A+\angle P C B=90^{\circ}$$ if and only if the diagonals $A C$ and $B D$ are perpendicular.

Let $A B C D$ be a convex quadrilateral with $A B \neq B C$. Denote by $\omega_{1}$ and $\omega_{2}$ the incircles of triangles $A B C$ and $A D C$. Suppose that there exists a circle $\omega$ inscribed in angle $A B C$, tangent to the extensions of line segments $A D$ and $C D$. Prove that the common external tangents of $\omega_{1}$ and $\omega_{2}$ intersect on $\omega$.

Let $n$ be a positive integer and let $p$ be a prime number. Prove that if $a, b, c$ are integers (not necessarily positive) satisfying the equations $$a^{n}+p b=b^{n}+p c=c^{n}+p a,$$ then $a=b=c$.

Let $a_{1}, a_{2}, \ldots, a_{n}$ be distinct positive integers, $n \geq 3$. Prove that there exist distinct indices $i$ and $j$ such that $a_{i}+a_{j}$ does not divide any of the numbers $3 a_{1}, 3 a_{2}, \ldots, 3 a_{n}$.

Let $a_{0}, a_{1}, a_{2}, \ldots$ be a sequence of positive integers such that the greatest common divisor of any two consecutive terms is greater than the preceding term; in symbols, $\operatorname{gcd}\left(a_{i}, a_{i+1}\right)>a_{i-1}$. Prove that $a_{n} \geq 2^{n}$ for all $n \geq 0$.

Let $n$ be a positive integer. Show that the numbers $$\left(\begin{array}{c} 2^{n}-1 \\ 0 \end{array}\right), \left(\begin{array}{c} 2^{n}-1 \\ 1 \end{array}\right), \left(\begin{array}{c} 2^{n}-1 \\ 2 \end{array}\right), \ldots, \left(\begin{array}{c} 2^{n}-1 \\ 2^{n-1}-1 \end{array}\right)$$ are congruent modulo $2^{n}$ to $1,3,5, \ldots, 2^{n}-1$ in some order.

For every $n \in \mathbb{N}$ let $d(n)$ denote the number of (positive) divisors of $n$. Find all functions $f: \mathbb{N} \rightarrow \mathbb{N}$ with the following properties: (i) $d(f(x))=x$ for all $x \in \mathbb{N}$; (ii) $f(x y)$ divides $(x-1) y^{x y-1} f(x)$ for all $x, y \in \mathbb{N}$.

Prove that there exist infinitely many positive integers $n$ such that $n^{2}+1$ has a prime divisor greater than $2 n+\sqrt{2 n}$.