[Solutions] Iranian National Mathematical Olympiad 2011-2012

Iran National Math Olympiad (Second Round) 2011

1. We have a line and $1390$ points around it such that the distance of each point to the line is less than $1$ centimeters and the distance between any two points is more than $2$ centimeters. prove that there are two points such that their distance is at least $10$ meters ($1000$ centimeters).
2. In triangle $ABC$, we have $\angle ABC=60$. The line through $B$ perpendicular to side $AB$ intersects angle bisector of $\angle BAC$ in $D$ and the line through $C$ perpendicular $BC$ intersects angle bisector of $\angle ABC$ in $E$. prove that $\angle BED\le 30$.
3. Find all increasing sequences $a_1,a_2,a_3,...$ of natural numbers such that for each $i,j\in \mathbb N$, number of the divisors of $i+j$ and $a_i+a_j$ is equal. (an increasing sequence is a sequence that if $i\le j$, then $a_i\le a_j$.)
4. Find the smallest natural number $n$ such that there exists $n$ real numbers in the interval $(-1,1)$ such that their sum equals zero and the sum of their squares equals $20$.
5. Rainbow is the name of a bird. this bird has $n$ colors and it's colors in two consecutive days are not equal. there doesn't exist $4$ days in this bird's life like $i,j,k,l$ such that $i<j<k<l$ and the bird has the same color in days $i$ and $k$ and the same color in days $j$ and $l$ different from the colors it has in days $i$ and $k$. what is the maximum number of days rainbow can live in terms of $n$?
6. The line $l$ intersects the extension of $AB$ in $D$ ($D$ is nearer to $B$ than $A$) and the extension of $AC$ in $E$ ($E$ is nearer to $C$ than $A$) of triangle $ABC$. Suppose that reflection of line $l$ to perpendicular bisector of side $BC$ intersects the mentioned extensions in $D'$ and $E'$ respectively. Prove that if $BD+CE=DE$, then $BD'+CE'=D'E'$.

National Math Olympiad (3rd Round) 2011

1. A regular dodecahedron is a convex polyhedra that its faces are regular pentagons. The regular dodecahedron has twenty vertices and there are three edges connected to each vertex. Suppose that we have marked ten vertices of the regular dodecahedron.
   a) prove that we can rotate the dodecahedron in such a way that at most four marked vertices go to a place that there was a marked vertex before.
   b) prove that the number four in previous part can't be replaced with three.
2. a) Prove that for every natural numbers $n$ and $k$, we have monic polynomials of degree $n$, with integer coefficients like $A=\{P_1(x),.....,P_k(x)\}$ such that no two of them have a common factor and for every subset of $A$, the sum of elements of $A$ has all its roots real.
   b) Are there infinitely many monic polynomial of degree $n$ with integer coefficients like $P_1(x),P_2(x),....$ such that no two of them have a common factor and the sum of a finite number of them has all it's roots real?
3. We have connected four metal pieces to each other such that they have formed a tetragon in space and also the angle between two connected metal pieces can vary. In the case that the tetragon can't be put in the plane, we've marked a point on each of the pieces such that they are all on a plane. Prove that as the tetragon varies, that four points remain on a plane.
4. The escalator of the station champion butcher has this property that if $m$ persons are on it, then it's speed is $m^{-\alpha}$ where $\alpha$ is a fixed positive real number. Suppose that $n$ persons want to go up by the escalator and the width of the stairs is such that all the persons can stand on a stair. If the length of the escalator is $l$, what's the least time that is needed for these persons to go up? Why?
5. Suppose that $\alpha$ is a real number and $a_1<a_2<.....$ is a strictly increasing sequence of natural numbers such that for each natural number $n$ we have $a_n\le n^{\alpha}$. We call the prime number $q$ golden if there exists a natural number $m$ such that $q|a_m$. Suppose that $q_1<q_2<q_3<.....$ are all the golden prime numbers of the sequence $\{a_n\}$.
   a) Prove that if $\alpha=1.5$, then $q_n\le 1390^n$. Can you find a better bound for $q_n$?
   b) Prove that if $\alpha=2.4$, then $q_n\le 1390^{2n}$. Can you find a better bound for $q_n$?
6. We call two circles in the space fighting if they are intersected or they are clipsed.
   Find a good necessary and sufficient condition for four distinct points $A,B,A',B'$ such that each circle passing through $A,B$ and each circle passing through $A',B'$ are fighting circles.
7. Suppose that $f:P(\mathbb N)\to \mathbb N$ and $A$ is a subset of $\mathbb N$. We call $f$ $A$-predicting if the set $\{x\in \mathbb N|x\notin A, f(A\cup x)\neq x \}$ is finite. Prove that there exists a function that for every subset $A$ of natural numbers, it's $A$-predicting.
8. We call the sequence $d_1,....,d_n$ of natural numbers, not necessarily distinct, covering if there exists arithmetic progressions like $c_1+kd_1$,....,$c_n+kd_n$ such that every natural number has come in at least one of them. We call this sequence short if we can not delete any of the $d_1,....,d_n$ such that the resulting sequence be still covering.
   a) Suppose that $d_1,....,d_n$ is a short covering sequence and suppose that we've covered all the natural numbers with arithmetic progressions $a_1+kd_1,.....,a_n+kd_n$, and suppose that $p$ is a prime number that $p$ divides $d_1,....,d_k$ but it does not divide $d_{k+1},....,d_n$. Prove that the remainders of $a_1,....,a_k$ modulo $p$ contains all the numbers $0,1,.....,p-1$.
   b) Write anything you can about covering sequences and short covering sequences in the case that each of $d_1,....,d_n$ has only one prime divisor.

Iran Team Selection Test 2012

1. Find all positive integers $n \geq 2$ such that for all integers $i,j$ that $ 0 \leq i,j\leq n$ , $i+j$ and $ {n\choose i}+ {n \choose j}$ have same parity.
2. Consider $\omega$ is circumcircle of an acute triangle $ABC$. $D$ is midpoint of arc $BAC$ and $I$ is incenter of triangle $ABC$. Let $DI$ intersect $BC$ in $E$ and $\omega$ for second time in $F$. Let $P$ be a point on line $AF$ such that $PE$ is parallel to $AI$. Prove that $PE$ is bisector of angle $BPC$.
3. Let $n$ be a positive integer. Let $S$ be a subset of points on the plane with these conditions:
   i) There does not exist $n$ lines in the plane such that every element of $S$ be on at least one of them.
   ii) For all $X \in S$ there exists $n$ lines in the plane such that every element of $S - {X} $ be on at least one of them.
   Find maximum of $\mid S\mid$.
4. Consider $m+1$ horizontal and $n+1$ vertical lines ($m,n\ge 4$) in the plane forming an $m\times n$ table. Cosider a closed path on the segments of this table such that it does not intersect itself and also it passes through all $(m-1)(n-1)$ interior vertices (each vertex is an intersection point of two lines) and it doesn't pass through any of outer vertices. Suppose $A$ is the number of vertices such that the path passes through them straight forward, $B$ number of the table squares that only their two opposite sides are used in the path, and $C$ number of the table squares that none of their sides is used in the path. Prove that \[A=B-C+m+n-1.\]
5. The function $f:\mathbb R^{\ge 0} \longrightarrow \mathbb R^{\ge 0}$ satisfies the following properties for all $a,b\in \mathbb R^{\ge 0}$:
   a) $f(a)=0 \Leftrightarrow a=0$
   b) $f(ab)=f(a)f(b)$
   c) $f(a+b)\le 2 \max \{f(a),f(b)\}$.
   Prove that for all $a,b\in \mathbb R^{\ge 0}$ we have $f(a+b)\le f(a)+f(b)$.
6. The pentagon $ABCDE$ is inscirbed in a circle $w$. Suppose that $w_a,w_b,w_c,w_d,w_e$ are reflections of $w$ with respect to sides $AB,BC,CD,DE,EA$ respectively. Let $A'$ be the second intersection point of $w_a,w_e$ and define $B',C',D',E'$ similarly. Prove that \[2\le \frac{S_{A'B'C'D'E'}}{S_{ABCDE}}\le 3,\] where $S_X$ denotes the surface of figure $X$.
7. Is it possible to put $\binom{n}{2}$ consecutive natural numbers on the edges of a complete graph with $n$ vertices in a way that for every path (or cycle) of length $3$ where the numbers $a,b$ and $c$ are written on its edges (edge $b$ is between edges $c$ and $a$), $b$ is divisible by the greatest common divisor of the numbers $a$ and $c$?
8. Let $g(x)$ be a polynomial of degree at least $2$ with all of its coefficients positive. Find all functions $f:\mathbb R^+ \longrightarrow \mathbb R^+$ such that \[f(f(x)+g(x)+2y)=f(x)+g(x)+2f(y) \quad \forall x,y\in \mathbb R^+.\]
9. Suppose $ABCD$ is a parallelogram. Consider circles $w_1$ and $w_2$ such that $w_1$ is tangent to segments $AB$ and $AD$ and $w_2$ is tangent to segments $BC$ and $CD$. Suppose that there exists a circle which is tangent to lines $AD$ and $DC$ and externally tangent to $w_1$ and $w_2$. Prove that there exists a circle which is tangent to lines $AB$ and $BC$ and also externally tangent to circles $w_1$ and $w_2$.
10. For positive reals $a,b$ and $c$ with $ab+bc+ca=1$, show that \[\sqrt{3}({\sqrt{a}+\sqrt{b}+\sqrt{c})\le \frac{a\sqrt{a}}{bc}+\frac{b\sqrt{b}}{ca}+\frac{c\sqrt{c}}{ab}.}\]
11. Points $A$ and $B$ are on a circle $\omega$ with center $O$ such that $\tfrac{\pi}{3}< \angle AOB <\tfrac{2\pi}{3}$. Let $C$ be the circumcenter of the triangle $AOB$. Let $l$ be a line passing through $C$ such that the angle between $l$ and the segment $OC$ is $\tfrac{\pi}{3}$. $l$ cuts tangents in $A$ and $B$ to $\omega$ in $M$ and $N$ respectively. Suppose circumcircles of triangles $CAM$ and $CBN$, cut $\omega$ again in $Q$ and $R$ respectively and theirselves in $P$ (other than $C$). Prove that $OP\perp QR$.
12. We call a subset $B$ of natural numbers loyal if there exists natural numbers $i\le j$ such that $B=\{i,i+1,...,j\}$. Let $Q$ be the set of all loyal sets. Now for every subset $A=\{a_1<a_2<...<a_k\}$ of $\{1,2,...,n\}$ we set $$f(A)=\max_{1\le i \le k-1}{a_{i+1}-a_i}, \quad g(A)=\max_{B\subseteq A, B\in Q} |B|$$ and we define $$F(n)=\sum_{A\subseteq \{1,2,...,n\}} f(A), \quad G(n)=\sum_{A\subseteq \{1,2,...,n\}} g(A).$$ Prove that there exists $m\in \mathbb N$ such that for each natural number $n>m$, we have $F(n)>G(n)$.
    (By $|A|$ we mean the number of elements of $A$ and if $|A|\le 1$, we define $f(A)$ to be zero).
13. Consider a regular $2^k$-gon with center $O$ and label its sides clockwise by $l_1,l_2,...,l_{2^k}$. Reflect $O$ with respect to $l_1$, then reflect the resulting point with respect to $l_2$ and do this process until the last side. Prove that the distance between the final point and $O$ is less than the perimeter of the $2^k$-gon.
14. Do there exist $2000$ real numbers (not necessarily distinct) such that all of them are not zero and if we put any group containing $1000$ of them as the roots of a monic polynomial of degree $1000$, the coefficients of the resulting polynomial (except the coefficient of $x^{1000}$) be a permutation of the $1000$ remaining numbers?
15. Find all integer numbers $x$ and $y$ such that: \[(y^3+xy-1)(x^2+x-y)=(x^3-xy+1)(y^2+x-y).\]
16. Suppose $p$ is an odd prime number. We call the polynomial $f(x)=\sum_{j=0}^n a_jx^j$ with integer coefficients $i$-remainder if $ \sum_{p-1|j,j>0}a_{j}\equiv i\pmod{p}$. Prove that the set $\{f(0),f(1),...,f(p-1)\}$ is a complete residue system modulo $p$ if and only if polynomials $f(x), (f(x))^2,...,(f(x))^{p-2}$ are $0$-remainder and the polynomial $(f(x))^{p-1}$ is $1$-remainder.
17. Let $n$ be a natural number. Suppose $A$ and $B$ are two sets, each containing $n$ points in the plane, such that no three points of a set are collinear. Let $T(A)$ be the number of broken lines, each containing $n-1$ segments, and such that it doesn't intersect itself and its vertices are points of $A$. Define $T(B)$ similarly. If the points of $B$ are vertices of a convex $n$-gon (are in convex position), but the points of $A$ are not, prove that $T(B)<T(A)$.
18. Let $O$ be the circumcenter of the acute triangle $ABC$. Suppose points $A',B'$ and $C'$ are on sides $BC,CA$ and $AB$ such that circumcircles of triangles $AB'C',BC'A'$ and $CA'B'$ pass through $O$. Let $\ell_a$ be the radical axis of the circle with center $B'$ and radius $B'C$ and circle with center $C'$ and radius $C'B$. Define $\ell_b$ and $\ell_c$ similarly. Prove that lines $\ell_a,\ell_b$ and $\ell_c$ form a triangle such that it's orthocenter coincides with orthocenter of triangle $ABC$.

DOWNLOAD SOLUTIONS