MathLinks Contest 2008

1. Given is an acute triangle $ ABC$ and the points $ A_1,B_1,C_1$, that are the feet of its altitudes from $ A,B,C$ respectively. A circle passes through $ A_1$ and $ B_1$ and touches the smaller arc $ AB$ of the circumcircle of $ ABC$ in point $ C_2$. Points $ A_2$ and $ B_2$ are defined analogously. Prove that the lines $ A_1A_2$, $ B_1B_2$, $ C_1C_2$ have a common point, which lies on the Euler line of $ ABC$. 
2. Let $ a,b,c,d$ be four distinct positive integers in arithmetic progression. Prove that $ abcd$ is not a perfect square. 
3. We are given the finite sets $ X$, $ A_1$, $ A_2$, $ \dots$, $ A_{n - 1}$ and the functions $ f_i: \ X\rightarrow A_i$. A vector $ (x_1,x_2,\dots,x_n)\in X^n$ is called nice, if $ f_i(x_i) = f_i(x_{i + 1})$, for each $ i = 1,2,\dots,n - 1$. Prove that the number of nice vectors is at least \[ \frac {|X|^n}{\prod\limits_{i = 1}^{n - 1} |A_i|}.\]
4. Let $ k$ be an integer, $ k \geq 2$, and let $ p_{1},\ p_{2},\ \ldots,\ p_{k}$ be positive reals with $ p_{1} + p_{2} + \ldots + p_{k} = 1$. Suppose we have a collection $ \left(A_{1,1},\ A_{1,2},\ \ldots,\ A_{1,k}\right)$, $ \left(A_{2,1},\ A_{2,2},\ \ldots,\ A_{2,k}\right)$, $ \ldots$, $ \left(A_{m,1},\ A_{1,2},\ \ldots,\ A_{m,k}\right)$ of $ k$-tuples of finite sets satisfying the following two properties
   
   • for every $ i$ and every $ j \neq j^{\prime}$, $ A_{i,j}\cap A_{i,j^{\prime}} = \emptyset$, and 
   • for every $ i\neq i^{\prime}$ there exist $ j\neq j^{\prime}$ for which $ A_{i,j} \cap A_{i^{\prime},j^{\prime}}\neq\emptyset$.
   Prove that \[ \sum_{b = 1}^{m}{\prod_{a = 1}^{k}{p_{a}^{|A_{b,a}|}}} \leq 1.\]
5. For a prime $ p$ an a positive integer $ n$, denote by $ \nu_p(n)$ the exponent of $ p$ in the prime factorization of $ n!$. Given a positive integer $ d$ and a finite set $ \{p_1,p_2,\ldots, p_k\}$ of primes, show that there are infinitely many positive integers $ n$ such that $ \nu_{p_i}(n) \equiv 0 \pmod d$, for all $ 1\leq i \leq k$. 
6. Let $ ABC$ be a given triangle with the incenter $ I$, and denote by $ X$, $ Y$, $ Z$ the intersections of the lines $ AI$, $ BI$, $ CI$ with the sides $ BC$, $ CA$, and $ AB$, respectively. Consider $ \mathcal{K}_{a}$ the circle tangent simultanously to the sidelines $ AB$, $ AC$, and internally to the circumcircle $ \mathcal{C}(O)$ of $ ABC$, and let $ A^{\prime}$ be the tangency point of $ \mathcal{K}_{a}$ with $ \mathcal{C}$. Similarly, define $ B^{\prime}$, and $ C^{\prime}$. Prove that the circumcircles of triangles $ AXA^{\prime}$, $ BYB^{\prime}$, and $ CZC^{\prime}$ all pass through two distinct points. 
7. Let $ p$ be a prime and let $ d \in \left\{0,\ 1,\ \ldots,\ p\right\}$. Prove that \[ \sum_{k = 0}^{p - 1}{\binom{2k}{k + d}}\equiv r \pmod{p},\] where $ r \equiv p-d \pmod 3$, $ r\in\{-1,0,1\}$. 
8. Prove that for positive integers $ x,y,z$ the number $ x^2 + y^2 + z^2$ is not divisible by $ 3(xy + yz + zx)$. 
9. Find the greatest positive real number $ k$ such that the inequality below holds for any positive real numbers $ a,b,c$ \[ \frac ab + \frac bc + \frac ca - 3 \geq k \left( \frac a{b + c} + \frac b{c + a} + \frac c{a + b} - \frac 32 \right).\]
10. Let $ A,B,C,D,E$ be five distinct points, such that no three of them lie on the same line. Prove that \[ AB+BC+CA + DE < AD + AE + BD+BE + CD+CE .\]
11. Find the number of finite sequences $ \{a_1,a_2,\ldots,a_{2n+1}\}$, formed with nonnegative integers, for which $ a_1=a_{2n+1}=0$ and $ |a_k -a_{k+1}|=1$, for all $ k\in\{1,2,\ldots,2n\}$. 
12. Let $ a,b,c$ be positive real numbers such that $ ab+bc+ca=3$. Prove that \[ \frac 1{1+a^2(b+c)} + \frac 1{1+b^2(c+a)} + \frac 1 {1+c^2(a+b) } \leq \frac 3 {1+2abc} .\]
13. Find all real polynomials $ g(x)$ of degree at most $ n - 3$, $ n\geq 3$, knowing that all the roots of the polynomial $ f(x) = x^n + nx^{n - 1} + \frac {n(n - 1)}2 x^{n - 2} + g(x)$ are real. 
14. Let $ A^{\prime}$ be an arbitrary point on the side $ BC$ of a triangle $ ABC$. Denote by $ \mathcal{T}_{A}^{b}$, $ \mathcal{T}_{A}^{c}$ the circles simultanously tangent to $ AA^{\prime}$, $ A^{\prime}B$, $ \Gamma$ and $ AA^{\prime}$, $ A^{\prime}C$, $ \Gamma$, respectively, where $ \Gamma$ is the circumcircle of $ ABC$. Prove that $ \mathcal{T}_{A}^{b}$, $ \mathcal{T}_{A}^{c}$ are congruent if and only if $ AA^{\prime}$ passes through the Nagel point of triangle $ ABC$. (If $ M,N,P$ are the points of tangency of the excircles of the triangle $ ABC$ with the sides of the triangle $ BC$, $ CA$ and $ AB$ respectively, then the Nagel point of the triangle is the intersection point of the lines $ AM$, $ BN$ and $ CP$.) 
15. If $ a\geq b\geq c\geq d > 0$ such that $ abcd=1$, then prove that \[ \frac 1{1+a} + \frac 1{1+b} + \frac 1{1+c} \geq \frac {3}{1+\sqrt[3]{abc}}.\]
16. Let $ \{x_n\}_{n\geq 1}$ be a sequences, given by $ x_1 = 1$, $ x_2 = 2$ and \[ x_{n + 2} = \frac { x_{n + 1}^2 + 3 }{x_n}.\] Prove that $ x_{2008}$ is the sum of two perfect squares. 
17. Find all functions $ f,g: \mathbb Q \to \mathbb Q$ such that for all rational numbers $ x,y$ we have \[ f(f(x) + g(y) ) = g(f(x)) + y.\]
18. Let $ \Omega$ be the circumcircle of triangle $ ABC$. Let $ D$ be the point at which the incircle of $ ABC$ touches its side $ BC$. Let $ M$ be the point on $ \Omega$ such that the line $ AM$ is parallel to $ BC$. Also, let $ P$ be the point at which the circle tangent to the segments $ AB$ and $ AC$ and to the circle $ \Omega$ touches $ \Omega$. Prove that the points $ P$, $ D$, $ M$ are collinear. 
19. Find all pairs of positive integers $ a,b$ such that \begin{align*} b^2 + b+ 1 & \equiv 0 \pmod a \\ a^2+a+1 &\equiv 0 \pmod b . \end{align*}
20. Prove that the set of all the points with both coordinates begin rational numbers can be written as a reunion of two disjoint sets $ A$ and $ B$ such that any line that that is parallel with $ Ox$, and respectively $ Oy$ intersects $ A$, and respectively $ B$ in a finite number of points. 
21. Let $ n$ be a positive integer, and let $ M = \{1,2,\ldots, 2n\}$. Find the minimal positive integer $ m$, such that no matter how we choose the subsets $ A_i \subset M$, $ 1\leq i\leq m$, with the properties
• $ |A_i-A_j|\geq 1$, for all $ i\neq j$, (2) $ \bigcup_{i=1}^m A_i = M$,
• we can always find two subsets $ A_k$ and $ A_l$ such that $ A_k \cup A_l = M$ (here $ |X|$ represents the number of elements in the set $ X$.)