# [Shortlists] International Mathematical Olympiad 2008

### Algebra

1. Find all functions $f: (0, \infty) \mapsto (0, \infty)$ (so $f$ is a function from the positive real numbers) such that $\frac {\left( f(w) \right)^2 + \left( f(x) \right)^2}{f(y^2) + f(z^2) } = \frac {w^2 + x^2}{y^2 + z^2}$ for all positive real numbers $w,x,y,z,$ satisfying $wx = yz.$
2. a) Prove that $\frac {x^{2}}{\left(x - 1\right)^{2}} + \frac {y^{2}}{\left(y - 1\right)^{2}} + \frac {z^{2}}{\left(z - 1\right)^{2}} \geq 1$ for all real numbers $x$, $y$, $z$, each different from $1$, and satisfying $xyz=1$.
b) Prove that equality holds above for infinitely many triples of rational numbers $x$, $y$, $z$, each different from $1$, and satisfying $xyz=1$.
3. 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
• 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$;
• the inequality $f\left(g\left(g\left(x\right)\right)\right) < g\left(f\left(x\right)\right)$ 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 - \frac {1}{b}: a, b\in\mathbb{N}\}$
4. 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}\to\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)$ for all integers $m$, $n\ge 0$ with $2^n > m$. Prove that $f(3p)\ge 0$ holds for all integers $p\ge 0$.
5. Let $a$, $b$, $c$, $d$ be positive real numbers such that $abcd = 1$ and $a + b + c + d > \dfrac{a}{b} + \dfrac{b}{c} + \dfrac{c}{d} + \dfrac{d}{a}$. Prove that $a + b + c + d < \dfrac{b}{a} + \dfrac{c}{b} + \dfrac{d}{c} + \dfrac{a}{d}$
6. Let $f: \mathbb{R}\to\mathbb{N}$ be a function which satisfies $$f\left(x + \dfrac{1}{f(y)}\right) = f\left(y + \dfrac{1}{f(x)}\right)$$ for all $x$, $y\in\mathbb{R}$. Prove that there is a positive integer which is not a value of $f$.
7. 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}\ge 0$ holds. Determine all cases of equality.

### Combinatorics

1. 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\pmod n$.
2. Let $n \in \mathbb N$ and $A_n$ set of all permutations $(a_1, \ldots, a_n)$ of the set $\{1, 2, \ldots , n\}$ for which $k|2(a_1 + \cdots+ a_k), \text{ for all } 1 \leq k \leq n.$ Find the number of elements of the set $A_n$.
3. 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 $ABC$ is equal to $k$. A set $T\subset S$ will be called $k$-clique if every two points in $T$ are $k$-friends. Find the least positive integer $k$ for which there exits a $k$-clique with more than 200 elements.
4. Let $n$ and $k$ be positive integers with $k \geq n$ and $k - n$ an even number. Let $2n$ lamps labelled $1$, $2$, ..., $2n$ be given, each of which can be either on or off. Initially all the lamps are off. We consider sequences of steps: at each step one of the lamps is switched (from on to off or from off to on). Let $N$ be the number of such sequences consisting of $k$ steps and resulting in the state where lamps $1$ through $n$ are all on, and lamps $n + 1$ through $2n$ are all off. Let $M$ be number of such sequences consisting of $k$ steps, resulting in the state where lamps $1$ through $n$ are all on, and lamps $n + 1$ through $2n$ are all off, but where none of the lamps $n + 1$ through $2n$ is ever switched on. Determine $\frac {N}{M}$.
5. Let $S = \{x_1, x_2, \ldots, x_{k + l}\}$ be a $(k + l)$-element set of real numbers contained in the interval $[0, 1]$; $k$ and $l$ 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}{l}\sum_{x_j\in S\setminus A} x_j\right |\le \frac {k + l}{2kl}.$ Prove that the number of nice subsets is at least $\dfrac{2}{k + l}\dbinom{k + l}{k}$.
6. For $n\ge 2$, let $S_1$, $S_2$, $\ldots$, $S_{2^n}$ be $2^n$ subsets of $A = \{1, 2, 3, \ldots, 2^{n + 1}\}$ 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$ and $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 $4n$ elements.

### Geometry

1. Let $H$ be the orthocenter of an acute-angled triangle $ABC$. The circle $\Gamma_{A}$ centered at the midpoint of $BC$ and passing through $H$ intersects the sideline $BC$ at points $A_{1}$ and $A_{2}$. Similarly, define the points $B_{1}$, $B_{2}$, $C_{1}$ and $C_{2}$. Prove that the six points $A_{1}$, $A_{2}$, $B_{1}$, $B_{2}$, $C_{1}$ and $C_{2}$ are concyclic.
2. Given trapezoid $ABCD$ with parallel sides $AB$ and $CD$, assume that there exist points $E$ on line $BC$ outside segment $BC$, and $F$ inside segment $AD$ such that $\angle DAE = \angle CBF$. Denote by $I$ the point of intersection of $CD$ and $EF$, and by $J$ the point of intersection of $AB$ and $EF$. Let $K$ be the midpoint of segment $EF$, assume it does not lie on line $AB$. Prove that $I$ belongs to the circumcircle of $ABK$ if and only if $K$ belongs to the circumcircle of $CDJ$.
3. Let $ABCD$ be a convex quadrilateral and let $P$ and $Q$ be points in $ABCD$ such that $PQDA$ and $QPBC$ are cyclic quadrilaterals. Suppose that there exists a point $E$ on the line segment $PQ$ such that $\angle PAE = \angle QDE$ and $\angle PBE = \angle QCE$. Show that the quadrilateral $ABCD$ is cyclic.
4. In an acute triangle $ABC$ segments $BE$ and $CF$ are altitudes. Two circles passing through the point $A$ anf $F$ and tangent to the line $BC$ at the points $P$ and $Q$ so that $B$ lies between $C$ and $Q$. Prove that lines $PE$ and $QF$ intersect on the circumcircle of triangle $AEF$.
5. Let $k$ and $n$ be integers with $0\le k\le 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 intersections 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 $OX$ intersects at most $k$ lines in $L$. Prove that $I$ contains at least $\dfrac{1}{2}(k + 1)(k + 2)$ red points.
6. There is given a convex quadrilateral $ABCD$. Prove that there exists a point $P$ inside the quadrilateral such that $\angle PAB + \angle PDC$ $= \angle PBC + \angle PAD$ $= \angle PCD + \angle PBA$ $= \angle PDA + \angle PCB$ $= 90^{\circ}$ if and only if the diagonals $AC$ and $BD$ are perpendicular.
7. Let $ABCD$ be a convex quadrilateral with $BA\neq BC$. Denote the incircles of triangles $ABC$ and $ADC$ by $\omega_{1}$ and $\omega_{2}$ respectively. Suppose that there exists a circle $\omega$ tangent to ray $BA$ beyond $A$ and to the ray $BC$ beyond $C$, which is also tangent to the lines $AD$ and $CD$. Prove that the common external tangents to $\omega_{1}$ and $\omega_{2}$ intersect on $\omega$.

### Number Theory

1. 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 + pb = b^n + pc = c^n + pa$ then $a = b = c$.
2. Let $a_1$, $a_2$, $\ldots$, $a_n$ be distinct positive integers, $n\ge 3$. Prove that there exist distinct indices $i$ and $j$ such that $a_i + a_j$ does not divide any of the numbers $3a_1$, $3a_2$, $\ldots$, $3a_n$.
3. 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, $\gcd (a_i, a_{i + 1}) > a_{i - 1}$. Prove that $a_n\ge 2^n$ for all $n\ge 0$.
4. Let $n$ be a positive integer. Show that the numbers $\binom{2^n - 1}{0},\; \binom{2^n - 1}{1},\; \binom{2^n - 1}{2},\; \ldots,\; \binom{2^n - 1}{2^{n - 1} - 1}$ are congruent modulo $2^n$ to $1$, $3$, $5$, $\ldots$, $2^n - 1$ in some order.
5. For every $n\in\mathbb{N}$ let $d(n)$ denote the number of (positive) divisors of $n$. Find all functions $f: \mathbb{N}\to\mathbb{N}$ with the following properties
• $d\left(f(x)\right) = x$ for all $x\in\mathbb{N}$.
• $f(xy)$ divides $(x - 1)y^{xy - 1}f(x)$ for all $x$, $y\in\mathbb{N}$.
6. Prove that there are infinitely many positive integers $n$ such that $n^{2} + 1$ has a prime divisor greater than $2n + \sqrt {2n}$.
 MOlympiad.NET là dự án thu thập và phát hành các đề thi tuyển sinh và học sinh giỏi toán. Quý bạn đọc muốn giúp chúng tôi chỉnh sửa đề thi này, xin hãy để lại bình luận facebook (có thể đính kèm hình ảnh) hoặc google (có thể sử dụng $\LaTeX$) bên dưới. BBT rất mong bạn đọc ủng hộ UPLOAD đề thi và đáp án mới hoặc liên hệbbt.molympiad@gmail.comChúng tôi nhận tất cả các định dạng của tài liệu: $\TeX$, PDF, WORD, IMG,...