[Solutions] Iranian National Mathematical Olympiad 2012-2013

Iran National Math Olympiad (Second Round) 2012

1. Consider a circle $C_1$ and a point $O$ on it. Circle $C_2$ with center $O$, intersects $C_1$ in two points $P$ and $Q$. $C_3$ is a circle which is externally tangent to $C_2$ at $R$ and internally tangent to $C_1$ at $S$ and suppose that $RS$ passes through $Q$. Suppose $X$ and $Y$ are second intersection points of $PR$ and $OR$ with $C_1$. Prove that $QX$ is parallel with $SY$.
2. Suppose $n$ is a natural number. In how many ways can we place numbers $1,2,....,n$ around a circle such that each number is a divisor of the sum of it's two adjacent numbers?
3. Prove that if $t$ is a natural number then there exists a natural number $n>1$ such that $(n,t)=1$ and none of the numbers $n+t,n^2+t,n^3+t,....$ are perfect powers.
   a) Do there exist $2$-element subsets $A_1,A_2,A_3,...$ of natural numbers such that each natural number appears in exactly one of these sets and also for each natural number $n$, sum of the elements of $A_n$ equals $1391+n$?
   b) Do there exist $2$-element subsets $A_1,A_2,A_3,...$ of natural numbers such that each natural number appears in exactly one of these sets and also for each natural number $n$, sum of the elements of $A_n$ equals $1391+n^2$?
4. Consider the second degree polynomial $x^2+ax+b$ with real coefficients. We know that the necessary and sufficient condition for this polynomial to have roots in real numbers is that its discriminant, $a^2-4b$ be greater than or equal to zero. Note that the discriminant is also a polynomial with variables $a$ and $b$. Prove that the same story is not true for polynomials of degree $4$: Prove that there does not exist a $4$ variable polynomial $P(a,b,c,d)$ such that: The fourth degree polynomial $x^4+ax^3+bx^2+cx+d$ can be written as the product of four $1$st degree polynomials if and only if $P(a,b,c,d)\ge 0$. (All the coefficients are real numbers.)
5. The incircle of triangle $ABC$, is tangent to sides $BC,CA$ and $AB$ in $D,E$ and $F$ respectively. The reflection of $F$ with respect to $B$ and the reflection of $E$ with respect to $C$ are $T$ and $S$ respectively. Prove that the incenter of triangle $AST$ is inside or on the incircle of triangle $ABC$.

National Math Olympiad (3rd Round) 2012

1. Let $G$ be a simple undirected graph with vertices $v_1,v_2,...,v_n$. We denote the number of acyclic orientations of $G$ with $f(G)$.
   a) Prove that $f(G)\le f(G-v_1)+f(G-v_2)+...+f(G-v_n)$.
   b) Let $e$ be an edge of the graph $G$. Denote by $G'$ the graph obtained by omiting $e$ and making it's two endpoints as one vertex. Prove that $f(G)=f(G-e)+f(G')$.
   c) Prove that for each $\alpha >1$, there exists a graph $G$ and an edge $e$ of it such that $\frac{f(G)}{f(G-e)}<\alpha$.
2. Suppose $S$ is a convex figure in plane with area $10$. Consider a chord of length $3$ in $S$ and let $A$ and $B$ be two points on this chord which divide it into three equal parts. For a variable point $X$ in $S-\{A,B\}$, let $A'$ and $B'$ be the intersection points of rays $AX$ and $BX$ with the boundary of $S$. Let $S'$ be those points $X$ for which $AA'>\frac{1}{3} BB'$. Prove that the area of $S'$ is at least $6$.
3. Prove that for each $n \in \mathbb N$ there exist natural numbers $a_1<a_2<...<a_n$ such that $\phi(a_1)>\phi(a_2)>...>\phi(a_n)$.
4. We have $n$ bags each having $100$ coins. All of the bags have $10$ gram coins except one of them which has $9$ gram coins. We have a balance which can show weights of things that have weight of at most $1$ kilogram. At least how many times shall we use the balance in order to find the different bag?
5. We call the three variable polynomial $P$ cyclic if $P(x,y,z)=P(y,z,x)$. Prove that cyclic three variable polynomials $P_1,P_2,P_3$ and $P_4$ exist such that for each cyclic three variable polynomial $P$, there exists a four variable polynomial $Q$ such that $$P(x,y,z)=Q(P_1(x,y,z),P_2(x,y,z),P_3(x,y,z),P_4(x,y,z)).$$
6. a) Prove that $a>0$ exists such that for each natural number $n$, there exists a convex $n$-gon $P$ in plane with lattice points as vertices such that the area of $P$ is less than $an^3$.
   b) Prove that there exists $b>0$ such that for each natural number $n$ and each $n$-gon $P$ in plane with lattice points as vertices, the area of $P$ is not less than $bn^2$.
   c) Prove that there exist $\alpha,c>0$ such that for each natural number $n$ and each $n$-gon $P$ in plane with lattice points as vertices, the area of $P$ is not less than $cn^{2+\alpha}$.
7. The city of Bridge Village has some highways. Highways are closed curves that have intersections with each other or themselves in $4$-way crossroads. Mr.Bridge Lover, mayor of the city, wants to build a bridge on each crossroad in order to decrease the number of accidents. He wants to build the bridges in such a way that in each highway, cars pass above a bridge and under a bridge alternately. By knowing the number of highways determine that this action is possible or not.
   a) Does there exist an infinite subset $S$ of the natural numbers, such that $S\neq \mathbb{N}$, and such that for each natural number $n\not \in S$, exactly $n$ members of $S$ are coprime with $n$?
   b) Does there exist an infinite subset $S$ of the natural numbers, such that for each natural number $n\in S$, exactly $n$ members of $S$ are coprime with $n$?

Iran Team Selection Test 2013

1. In acute-angled triangle $ABC$, let $H$ be the foot of perpendicular from $A$ to $BC$ and also suppose that $J$ and $I$ are excenters oposite to the side $AH$ in triangles $ABH$ and $ACH$. If $P$ is the point that incircle touches $BC$, prove that $I,J,P,H$ are concyclic.
2. Find the maximum number of subsets from $\left \{ 1,...,n \right \}$ such that for any two of them like $A,B$ if $A\subset B$ then $\left | B-A \right |\geq 3$. (Here $\left | X \right |$ is the number of elements of the set $X$.)
3. For nonnegative integers $m$ and $n$, define the sequence $a(m,n)$ of real numbers as follows. Set $a(0,0)=2$ and for every natural number $n$, set $a(0,n)=1$ and $a(n,0)=2$. Then for $m,n\geq1$, define \[ a(m,n)=a(m-1,n)+a(m,n-1). \] Prove that for every natural number $k$, all the roots of the polynomial $P_{k}(x)=\sum_{i=0}^{k}a(i,2k+1-2i)x^{i}$ are real.
4. $m$ and $n$ are two nonnegative integers. In the Philosopher's Chess, The chessboard is an infinite grid of identical regular hexagons and a new piece named the Donkey moves on it as follows: Starting from one of the hexagons, the Donkey moves $m$ cells in one of the $6$ directions, then it turns $60$ degrees clockwise and after that moves $n$ cells in this new direction until it reaches it's final cell.
   At most how many cells are in the Philosopher's chessboard such that one cannot go from anyone of them to the other with a finite number of movements of the Donkey?
5. Do there exist natural numbers $a, b$ and $c$ such that $a^2+b^2+c^2$ is divisible by $2013(ab+bc+ca)$?
6. Points $A, B, C$ and $D$ lie on line $l$ in this order. Two circular arcs $C_1$ and $C_2$, which both lie on one side of line $l$, pass through points $A$ and $B$ and two circular arcs $C_3$ and $C_4$ pass through points $C$ and $D$ such that $C_1$ is tangent to $C_3$ and $C_2$ is tangent to $C_4$. Prove that the common external tangent of $C_2$ and $C_3$ and the common external tangent of $C_1$ and $C_4$ meet each other on line $l$.
7. Nonnegative real numbers $p_{1},\ldots,p_{n}$ and $q_{1},\ldots,q_{n}$ are such that $p_{1}+\cdots+p_{n}=q_{1}+\cdots+q_{n}$
   Among all the matrices with nonnegative entries having $p_i$ as sum of the $i$-th row's entries and $q_j$ as sum of the $j$-th column's entries, find the maximum sum of the entries on the main diagonal.
8. Find all Arithmetic progressions $a_{1},a_{2},...$ of natural numbers for which there exists natural number $N>1$ such that for every $k\in \mathbb{N}$: $a_{1}a_{2}...a_{k}\mid a_{N+1}a_{N+2}...a_{N+k}$
9. Find all functions $f,g:\mathbb{R}^{+} \rightarrow \mathbb{R}^{+}$ such that $f$ is increasing and also: $$f(f(x)+2g(x)+3f(y))=g(x)+2f(x)+3g(y)$$ $$g(f(x)+y+g(y))=2x-g(x)+f(y)+y$$
10. On each edge of a graph is written a real number,such that for every even tour of this graph,sum the edges with signs alternatively positive and negative is zero.prove that one can assign to each of the vertices of the graph a real number such that sum of the numbers on two adjacent vertices is the number on the edge between them.(tour is a closed path from the edges of the graph that may have repeated edges or vertices)
11. Let $a,b,c$ be sides of a triangle such that $a\geq b \geq c$. prove that:
    $$\sqrt{a(a+b-\sqrt{ab})}+\sqrt{b(a+c-\sqrt{ac})}+\sqrt{c(b+c-\sqrt{bc})}\geq a+b+c$$
12. Let $ABCD$ be a cyclic quadrilateral that inscribed in the circle $\omega$.Let $I_{1},I_{2}$ and $r_{1},r_{2}$ be incenters and radii of incircles of triangles $ACD$ and $ABC$,respectively.assume that $r_{1}=r_{2}$. let $\omega'$ be a circle that touches $AB,AD$ and touches $\omega$ at $T$. tangents from $A,T$ to $\omega$ meet at the point $K$.prove that $I_{1},I_{2},K$ lie on a line.
13. $P$ is an arbitrary point inside acute triangle $ABC$. Let $A_1,B_1,C_1$ be the reflections of point $P$ with respect to sides $BC,CA,AB$. Prove that the centroid of triangle $A_1B_1C_1$ lies inside triangle $ABC$.
14. We are given $n$ rectangles in the plane. Prove that between $4n$ right angles formed by these rectangles there are at least $[4\sqrt n]$ distinct right angles.
    a) Does there exist a sequence $a_1<a_2<\dots$ of positive integers, such that there is a positive integer $N$ that $\forall m>N$, $a_m$ has exactly $d(m)-1$ divisors among $a_i$s?
    b) Does there exist a sequence $a_1<a_2<\dots$ of positive integers, such that there is a positive integer $N$ that $\forall m>N$, $a_m$ has exactly $d(m)+1$ divisors among $a_i$s?
15. The function $f:\mathbb Z \to \mathbb Z$ has the property that for all integers $m$ and $n$ \[f(m)+f(n)+f(f(m^2+n^2))=1.\] We know that integers $a$ and $b$ exist such that $f(a)-f(b)=3$. Prove that integers $c$ and $d$ can be found such that $f(c)-f(d)=1$.
16. In triangle $ABC$, $AD$ and $AH$ are the angle bisector and the altitude of vertex $A$, respectively. The perpendicular bisector of $AD$, intersects the semicircles with diameters $AB$ and $AC$ which are drawn outside triangle $ABC$ in $X$ and $Y$, respectively. Prove that the quadrilateral $XYDH$ is concyclic.
17. A special kind of parallelogram tile is made up by attaching the legs of two right isosceles triangles of side length $1$. We want to put a number of these tiles on the floor of an $n\times n$ room such that the distance from each vertex of each tile to the sides of the room is an integer and also no two tiles overlap. Prove that at least an area $n$ of the room will not be covered by the tiles.

DOWNLOAD SOLUTIONS