[Solutions] Iranian National Mathematical Olympiad 2010-2011

National Math Olympiad (Second Round) 2010

1. Let $a,b$ be two positive integers and $a>b$. We know that $\gcd(a-b,ab+1)=1$ and $\gcd(a+b,ab-1)=1$. Prove that $(a-b)^2+(ab+1)^2$ is not a perfect square. 
2. There are $n$ points in the page such that no three of them are collinear.Prove that number of triangles that vertices of them are chosen from these $n$ points and area of them is 1,is not greater than $\frac23(n^2-n)$. 
3. Circles $W_1$, $W_2$ meet at $D$and $P$. $A$ and $B$ are on $W_1$, $W_2$ respectively, such that $AB$ is tangent to $W_1$ and $W_2$. Suppose $D$ is closer than $P$ to the line $AB$. $AD$ meet circle $W_2$ for second time at $C$. Let $M$ be the midpoint of $BC$. Prove that $$\angle{DPM}=\angle{BDC}.$$
4. Let $P(x)=ax^3+bx^2+cx+d$ be a polynomial with real coefficients such that \[\min\{d,b+d\}> \max\{|{c}|,|{a+c}|\}\] Prove that $P(x)$ do not have a real root in $[-1,1]$. 
5. In triangle $ABC$ we havev $\angle A=\frac{\pi}{3}$. Construct $E$ and $F$ on continue of $AB$ and $AC$ respectively such that $BE=CF=BC$. Suppose that $EF$ meets circumcircle of $\triangle ACE$ in $K$ ($K\not \equiv E$). Prove that $K$ is on the bisector of $\angle A$. 
6. A school has $n$ students and some super classes are provided for them. Each student can participate in any number of classes that he/she wants. Every class has at least two students participating in it. We know that if two different classes have at least two common students, then the number of the students in the first of these two classes is different from the number of the students in the second one. Prove that the number of classes is not greater that $\left(n-1\right)^2$. 

National Math Olympiad (Third Round) 2010

1. Suppose that polynomial $p(x)=x^{2010}\pm x^{2009}\pm...\pm x\pm 1$ does not have a real root. what is the maximum number of coefficients to be $-1$? 
2. $a,b,c$ are positive real numbers. prove the following inequality $$\frac{1}{a^2}+\frac{1}{b^2}+\frac{1}{c^2}+\frac{1}{(a+b+c)^2}\ge \frac{7}{25}\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}+\frac{1}{a+b+c}\right)^2$$
3. Prove that for each natural number $n$ there exist a polynomial with degree $2n+1$ with coefficients in $\mathbb{Q}[x]$ such that it has exactly $2$ complex zeros and it's irreducible in $\mathbb{Q}[x]$. 
4. For each polynomial $p(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0$ we define it's derivative as this and we show it by $p'(x)$ \[p'(x)=na_nx^{n-1}+(n-1)a_{n-1}x^{n-2}+...+2a_2x+a_1\] a) For each two polynomials $p(x)$ and $q(x)$ prove that \[(p(x)q(x))'=p'(x)q(x)+p(x)q'(x)\] b) Suppose that $p(x)$ is a polynomial with degree $n$ and $x_1,x_2,...,x_n$ are it's zeros. prove that:(3 points) \[\frac{p'(x)}{p(x)}=\sum_{i=1}^{n}\frac{1}{x-x_i}\] c) $p(x)$ is a monic polynomial with degree $n$ and $z_1,z_2,...,z_n$ are it's zeros such that \[|z_1|=1, \quad \forall i\in\{2,..,n\}:|z_i|\le1\] Prove that $p'(x)$ has at least one zero in the disc with length one with the center $z_1$ in complex plane. (disc with length one with the center $z_1$ in complex plane: $D=\{z \in \mathbb C: |z-z_1|\le1\}$)
5. Let $x,y,z$ be positive real numbers such that $xy+yz+zx=1$. Prove that $$3-\sqrt{3}+\frac{x^2}{y}+\frac{y^2}{z}+\frac{z^2}{x}\ge(x+y+z)^2$$
6. Suppose that $a=3^{100}$ and $b=5454$. how many $z$s in $[1,3^{99})$ exist such that for every $c$ that $\gcd(c,3)=1$, two equations $x^z\equiv c$ and $x^b\equiv c$ (mod $a$) have the same number of answers? 
7. $R$ is a ring such that $xy=yx$ for every $x,y\in R$ and if $ab=0$ then $a=0$ or $b=0$. if for every Ideal $I\subset R$ there exist $x_1,x_2,..,x_n$ in $R$ ($n$ is not constant) such that $I=(x_1,x_2,...,x_n)$, prove that every element in $R$ that is not $0$ and it's not a unit, is the product of finite irreducible elements. 
8. If $p$ is a prime number, what is the product of elements like $g$ such that $1\le g\le p^2$ and $g$ is a primitive root modulo $p$ but it's not a primitive root modulo $p^2$, modulo $p^2$? 
9. Suppose that $\sigma_k:\mathbb N \longrightarrow \mathbb R$ is a function such that $\sigma_k(n)=\sum_{d|n}d^k$. $\rho_k:\mathbb N \longrightarrow \mathbb R$ is a function such that $\rho_k\ast \sigma_k=\delta$. find a formula for $\rho_k$.
10. Prove that if $p$ is a prime number such that $p=12k+\{2,3,5,7,8,11\}$ ($k \in \mathbb N \cup \{0\}$), there exist a field with $p^2$ elements. 
11. $g$ and $n$ are natural numbers such that $gcd(g^2-g,n)=1$ and $A=\{g^i|i \in \mathbb N\}$ and $B=\{x\equiv (n)|x\in A\}$(by $x\equiv (n)$ we mean a number from the set $\{0,1,...,n-1\}$ which is congruent with $x$ modulo $n$). if for $0\le i\le g-1$ $a_i=|[\frac{ni}{g},\frac{n(i+1)}{g})\cap B|$. Prove that $g-1|\sum_{i=0}^{g-1}ia_i$. (the symbol $|$ $|$ means the number of elements of the set) 
12. In a triangle $ABC$, $O$ is the circumcenter and $I$ is the incenter. $X$ is the reflection of $I$ to $O$. $A_1$ is foot of the perpendicular from $X$ to $BC$. $B_1$ and $C_1$ are defined similarly. prove that $AA_1$, $BB_1$ and $CC_1$ are concurrent. 
13. In a quadrilateral $ABCD$, $E$ and $F$ are on $BC$ and $AD$ respectively such that the area of triangles $AED$ and $BCF$ is $\dfrac{4}{7}$ of the area of $ABCD$. $R$ is the intersection point of digonals of $ABCD$. $\dfrac{AR}{RC}=\dfrac{3}{5}$ and $\dfrac{BR}{RD}=\frac{5}{6}$.
    a) in what ratio does $EF$ cut the digonals?
    b) find $\dfrac{AF}{FD}$. 
14. In a quadrilateral $ABCD$ digonals are perpendicular to each other. let $S$ be the intersection of digonals. $K$, $L$, $M$ and $N$ are reflections of $S$ to $AB$, $BC$, $CD$ and $DA$. $BN$ cuts the circumcircle of $SKN$ in $E$ and $BM$ cuts the circumcircle of $SLM$ in $F$. Prove that $EFLK$ is concyclic. 
15. In a triangle $ABC$, $I$ is the incenter. $BI$ and $CI$ cut the circumcircle of $ABC$ at $E$ and $F$ respectively. $M$ is the midpoint of $EF$. $C$ is a circle with diameter $EF$. $IM$ cuts $C$ at two points $L$ and $K$ and the arc $BC$ of circumcircle of $ABC$ (not containing $A$) at $D$. Prove that $$\frac{DL}{IL}=\frac{DK}{IK}$$
16. In a triangle $ABC$, $I$ is the incenter. $D$ is the reflection of $A$ to $I$. the incircle is tangent to $BC$ at point $E$. $DE$ cuts $IG$ at $P$ ($G$ is centroid). $M$ is the midpoint of $BC$. Prove that
    a) $AP||DM$.
    b) $AP=2DM$. 
17. In a triangle $ABC$, $\angle C=45$. $AD$ is the altitude of the triangle. $X$ is on $AD$ such that $\angle XBC=90-\angle B$ ($X$ is in the triangle). $AD$ and $CX$ cut the circumcircle of $ABC$ in $M$ and $N$ respectively. if tangent to circumcircle of $ABC$ at $M$ cuts $AN$ at $P$, prove that $P$,$B$ and $O$ are collinear. 
18. Suppose that $\mathcal F\subseteq X^{(k)}$ and $|X|=n$. we know that for every three distinct elements of $\mathcal F$ like $A$, $B$, $C$, at most one of $A\cap B$, $B\cap C$ and $C\cap A$ is $\phi$. for $k\le \frac{n}{2}$. Prove that
    a) $|\mathcal F|\le \max(1,4-\frac{n}{k})\times \dbinom{n-1}{k-1}$.
    b) find all cases of equality in a) for $k\le \frac{n}{3}$. 
19. Suppose that $\mathcal F\subseteq \bigcup_{j=k+1}^{n}X^{(j)}$ and $|X|=n$. we know that $\mathcal F$ is a sperner family and it's also $H_k$. Prove that $$\sum_{B\in \mathcal F}\frac{1}{\dbinom{n-1}{|B|-1}}\le 1$$
20. Suppose that $\mathcal F\subseteq p(X)$ and $|X|=n$. we know that for every $A_i,A_j\in \mathcal F$ that $A_i\supseteq A_j$ we have $3\le |A_i|-|A_j|$. Prove that $$|\mathcal F|\le \lfloor\frac{2^n}{3}+\frac{1}{2}\dbinom{n}{\lfloor\frac{n}{2}\rfloor}\rfloor$$
21. Suppose that $\mathcal F\subseteq X^{(K)}$ and $|X|=n$. we know that for every three distinct elements of $\mathcal F$ like $A,B$ and $C$ we have $A\cap B \not\subset C$.
    a) Prove that \[|\mathcal F|\le \dbinom{k}{\lfloor\frac{k}{2}\rfloor}+1\] b) if elements of $\mathcal F$ do not necessarily have $k$ elements, with the above conditions show that \[|\mathcal F|\le \dbinom{n}{\lceil\frac{n-2}{3}\rceil}+2\]
22. Suppose that $\mathcal F\subseteq p(X)$ and $|X|=n$. prove that if $|\mathcal F|>\sum_{i=0}^{k-1}\dbinom{n}{i}$ then there exist $Y\subseteq X$ with $|Y|=k$ such that $p(Y)=\mathcal F\cap Y$ that $\mathcal F\cap Y=\{F\cap Y:F\in \mathcal F\}$
23. Suppose that $X$ is a set with $n$ elements and $\mathcal F\subseteq X^{(k)}$ and $X_1,X_2,...,X_s$ is a partition of $X$. We know that for every $A,B\in \mathcal F$ and every $1\le j\le s$, $E=B\cap (\bigcup_{i=1}^{j}X_i)\neq A\cap (\bigcup_{i=1}^{j} X_i)=F$ shows that none of $E,F$ contains the other one. Prove that \[|\mathcal F|\le \max_{\sum\limits_{i=1}^{S}w_i=k}\prod_{j=1}^{s}\binom{|X_j|}{w_j}\]
24. $P(x,y)$ is a two variable polynomial with real coefficients. degree of a monomial means sum of the powers of $x$ and $y$ in it. we denote by $Q(x,y)$ sum of monomials with the most degree in $P(x,y)$. (for example if $P(x,y)=3x^4y-2x^2y^3+5xy^2+x-5$ then $Q(x,y)=3x^4y-2x^2y^3$.) Suppose that there are real numbers $x_1$,$y_1$,$x_2$ and $y_2$ such that 
25. $Q(x_1,y_1)>0$, $Q(x_2,y_2)<0$. Prove that the set $\{(x,y)|P(x,y)=0\}$ is not bounded. (We call a set $S$ of plane bounded if there exist positive number $M$ such that the distance of elements of $S$ from the origin is less than $M$.) 
26. $a$,$b$ and $c$ are natural numbers. we have a $(2a+1)\times (2b+1)\times (2c+1)$ cube. this cube is on an infinite plane with unit squares. you call roll the cube to every side you want. faces of the cube are divided to unit squares and the square in the middle of each face is coloured (it means that if this square goes on a square of the plane, then that square will be coloured.) Prove that if any two of lengths of sides of the cube are relatively prime, then we can colour every square in plane. 
27. Set $A$ containing $n$ points in plane is given. a $copy$ of $A$ is a set of points that is made by using transformation, rotation, homogeneity or their combination on elements of $A$. we want to put $n$ $copies$ of $A$ in plane, such that every two copies have exactly one point in common and every three of them have no common elements.
    a) prove that if no $4$ points of $A$ make a parallelogram, you can do this only using transformation. ($A$ doesn't have a parallelogram with angle $0$ and a parallelogram that it's two non-adjacent vertices are one!)
    b) prove that you can always do this by using a combination of all these things. 
28. Suppose that $S$ is a figure in the plane such that it's border doesn't contain any lattice points. suppose that $x,y$ are two lattice points with the distance $1$ (we call a point lattice point if it's coordinates are integers). suppose that we can cover the plane with copies of $S$ such that $x,y$ always go on lattice points ( you can rotate or reverse copies of $S$). prove that the area of $S$ is equal to lattice points inside it. 
29. $n$ is a natural number and $x_1,x_2,...$ is a sequence of numbers $1$ and $-1$ with these properties: it is periodic and its least period number is $2^n-1$. (it means that for every natural number $j$ we have $x_{j+2^n-1}=x_j$ and $2^n-1$ is the least number with this property.) There exist distinct integers $0\le t_1<t_2<...<t_k<n$ such that for every natural number $j$ we have \[x_{j+n}=x_{j+t_1}\times x_{j+t_2}\times ... \times x_{j+t_k}\] Prove that for every natural number $s$ that $s<2^n-1$ we have \[\sum_{i=1}^{2^n-1}x_ix_{i+s}=-1\]
30. We call a $12$-gon in plane good whenever: first, it should be regular, second, it's inner plane must be filled!!, third, it's center must be the origin of the coordinates, forth, it's vertices must have points $(0,1)$,$(1,0)$,$(-1,0)$ and $(0,-1)$. find the faces of the massivest polyhedral that it's image on every three plane $xy$,$yz$ and $zx$ is a good $12$-gon. (it's obvios that centers of these three $12$-gons are the origin of coordinates for three dimensions.) 
31. $S$ is a set with $n$ elements and $P(S)$ is the set of all subsets of $S$ and $f : P(S) \rightarrow \mathbb N$ is a function with these properties: for every subset $A$ of $S$ we have $f(A)=f(S-A)$. for every two subsets of $S$ like $A$ and $B$ we have $\max(f(A),f(B))\ge f(A\cup B)$. Prove that number of natural numbers like $x$ such that there exists $A\subseteq S$ and $f(A)=x$ is less than $n$. Prove that there are infinitely many natural numbers of the form $n^2+1$ such that they don't have any divisor of the form $k^2+1$ except $1$ and themselves. 
32. Prove that the group of orientation-preserving symmetries of the cube is isomorphic to $S_4$ (the group of permutations of $\{1,2,3,4\}$).
33. Prove the third sylow theorem: suppose that $G$ is a group and $|G|=p^em$ which $p$ is a prime number and $(p,m)=1$. Suppose that $a$ is the number of $p$-sylow subgroups of $G$ ($H<G$ that $|H|=p^e$). Prove that $a|m$ and $p|a-1$. (Hint: you can use this: every two $p$-sylow subgroups are conjugate. 
34. Suppose that $G<S_n$ is a subgroup of permutations of $\{1,...,n\}$ with this property that for every $e\neq g\in G$ there exist exactly one $k\in \{1,...,n\}$ such that $g.k=k$. prove that there exist one $k\in \{1,...,n\}$ such that for every $g\in G$ we have $g.k=k$. 
35. a) Prove that every discrete subgroup of $(\mathbb R^2,+)$ is in one of these forms i-$\{0\}$. ii-$\{mv|m\in \mathbb Z\}$ for a vector $v$ in $\mathbb R^2$. iii-$\{mv+nw|m,n\in \mathbb Z\}$ for the linearly independent vectors $v$ and $w$ in $\mathbb R^2$.(lattice $L$) b) prove that every finite group of symmetries that fixes the origin and the lattice $L$ is in one of these forms: $\mathcal C_i$ or $\mathcal D_i$ that $i=1,2,3,4,6$ ($\mathcal C_i$ is the cyclic group of order $i$ and $\mathcal D_i$ is the dyhedral group of order $i$).
36. Suppose that $p$ is a prime number. find that smallest $n$ such that there exists a non-abelian group $G$ with $|G|=p^n$. SL is an acronym for Special Lesson. this year our special lesson was Groups and Symmetries.

Iran Team Selection Test 2011 

1. In acute triangle $ABC$ angle $B$ is greater than$C$. Let $M$ is midpoint of $BC$. $D$ and $E$ are the feet of the altitude from $C$ and $B$ respectively. $K$ and $L$ are midpoint of $ME$ and $MD$ respectively. If $KL$ intersect the line through $A$ parallel to $BC$ in $T$, prove that $TA=TM$. 
2. Find all natural numbers $n$ greater than $2$ such that there exist $n$ natural numbers $a_{1},a_{2},\ldots,a_{n}$ such that they are not all equal, and the sequence $a_{1}a_{2},a_{2}a_{3},\ldots,a_{n}a_{1}$ forms an arithmetic progression with nonzero common difference. 
3. There are $n$ points on a circle ($n>1$). Define an "interval" as an arc of a circle such that it's start and finish are from those points. Consider a family of intervals $F$ such that for every element of $F$ like $A$ there is almost one other element of $F$ like $B$ such that $A \subseteq B$ (in this case we call $A$ is sub-interval of $B$). We call an interval maximal if it is not a sub-interval of any other interval. If $m$ is the number of maximal elements of $F$ and $a$ is number of non-maximal elements of $F,$ prove that $n\geq m+\frac a2.$ 
4. Define a finite set $A$ to be 'good' if it satisfies the following conditions
   
   • For every three disjoint element of $A,$ like $a,b,c$ we have $\gcd(a,b,c)=1;$
   • For every two distinct $b,c\in A,$ there exists an $a\in A,$ distinct from $b,c$ such that $bc$ is divisible by $a.$ 
   Find all good sets. 
5. Find all surjective functions $f: \mathbb R \to \mathbb R$ such that for every $x,y\in \mathbb R,$ we have \[f(x+f(x)+2f(y))=f(2x)+f(2y).\]
6. The circle $\omega$ with center $O$ has given. From an arbitrary point $T$ outside of $\omega$ draw tangents $TB$ and $TC$ to it. $K$ and $H$ are on $TB$ and $TC$ respectively.
   a) $B'$ and $C'$ are the second intersection point of $OB$ and $OC$ with $\omega$ respectively. $K'$ and $H'$ are on angle bisectors of $\angle BCO$ and $\angle CBO$ respectively such that $KK' \bot BC$ and $HH'\bot BC$. Prove that $K,H',B'$ are collinear if and only if $H,K',C'$ are collinear.
   b) Consider there exist two circle in $TBC$ such that they are tangent two each other at $J$ and both of them are tangent to $\omega$.and one of them is tangent to $TB$ at $K$ and other one is tangent to $TC$ at $H$. Prove that two quadrilateral $BKJI$ and $CHJI$ are cyclic ($I$ is incenter of triangle $OBC$). 
7. Find the locus of points $P$ in an equilateral triangle $ABC$ for which the square root of the distance of $P$ to one of the sides is equal to the sum of the square root of the distance of $P$ to the two other sides. 
8. Let $p$ be a prime and $k$ a positive integer such that $k \le p$. We know that $f(x)$ is a polynomial in $\mathbb Z[x]$ such that for all $x \in \mathbb{Z}$ we have $p^k | f(x)$.
   a) Prove that there exist polynomials $A_0(x),\ldots,A_k(x)$ all in $\mathbb Z[x]$ such that \[ f(x)=\sum_{i=0}^{k} (x^p-x)^ip^{k-i}A_i(x),\] b) Find a counter example for each prime $p$ and each $k > p$. 
9. We have $n$ points in the plane such that they are not all collinear. We call a line $\ell$ a 'good' line if we can divide those $n$ points in two sets $A,B$ such that the sum of the distances of all points in $A$ to $\ell$ is equal to the sum of the distances of all points in $B$ to $\ell$. Prove that there exist infinitely many points in the plane such that for each of them we have at least $n+1$ good lines passing through them.
10. Find the least value of $k$ such that for all $a,b,c,d \in \mathbb{R}$ the inequality \[ \sqrt{(a^2+1)(b^2+1)(c^2+1)} \\ +\sqrt{(b^2+1)(c^2+1)(d^2+1)} \\ +\sqrt{(c^2+1)(d^2+1)(a^2+1)} \\ +\sqrt{(d^2+1)(a^2+1)(b^2+1)} \\ \ge 2( ab+bc+cd+da+ac+bd)-k \] holds. 
11. Let $ABC$ be a triangle and $A',B',C'$ be the midpoints of $BC,CA,AB$ respectively. Let $P$ and $P'$ be points in plane such that $PA=P'A'$, $PB=P'B'$, $PC=P'C'$. Prove that all $PP'$ pass through a fixed point. 
12. Suppose that $f : \mathbb{N} \rightarrow \mathbb{N}$ is a function for which the expression $af(a)+bf(b)+2ab$ for all $a,b \in \mathbb{N}$ is always a perfect square. Prove that $f(a)=a$ for all $a \in \mathbb{N}$.

DOWNLOAD SOLUTIONS