[Shortlists & Solutions] Exceedingly Luck-Based Math Olympiad 2014

Algebra

1. In a non-obtuse triangle $ABC$, prove that \[ \frac{\sin A \sin B}{\sin C} + \frac{\sin B \sin C}{\sin A} + \frac{\sin C \sin A}{ \sin B} \ge \frac 52. \]
2. Given positive reals $a,b,c,p,q$ satisfying $abc=1$ and $p \geq q$, prove that \[ p \left(a^2+b^2+c^2\right) + q\left( \frac{1}{a} + \frac{1}{b} + \frac{1}{c}\right) \geq (p+q) (a+b+c). \]
3. Let $a,b,c,d,e,f$ be positive real numbers. Given that $$def+de+ef+fd=4.$$ Show that \[ ((a+b)de+(b+c)ef+(c+a)fd)^2 \geq\ 12(abde+bcef+cafd). \]
4. Find all triples $(f,g,h)$ of injective functions from the set of real numbers to itself satisfying $$\begin{align*} f(x+f(y)) &= g(x) + h(y) \\ g(x+g(y)) &= h(x) + f(y) \\ h(x+h(y)) &= f(x) + g(y) \end{align*}$$ for all real numbers $x$ and $y$. (We say a function $F$ is injective if $F(a)\neq F(b)$ for any distinct real numbers $a$ and $b$.)
5. Let $\mathbb R^\ast$ denote the set of nonzero reals. Find all functions $f: \mathbb R^\ast \to \mathbb R^\ast$ satisfying \[ f(x^2+y)+1=f(x^2+1)+\frac{f(xy)}{f(x)} \] for all $x,y \in \mathbb R^\ast$ with $x^2+y\neq 0$.
6. Let $a,b,c$ be positive reals such that $a+b+c=ab+bc+ca$. Prove that \[ (a+b)^{ab-bc}(b+c)^{bc-ca}(c+a)^{ca-ab} \ge a^{ca}b^{ab}c^{bc}. \]
7. Find all positive integers $n$ with $n \ge 2$ such that the polynomial \[ P(a_1, a_2, ..., a_n) = a_1^n+a_2^n + ... + a_n^n - n a_1 a_2 ... a_n \] in the $n$ variables $a_1$, $a_2$, $\dots$, $a_n$ is irreducible over the real numbers, i.e. it cannot be factored as the product of two nonconstant polynomials with real coefficients.
8. Let $a, b, c$ be positive reals with $$a^{2014}+b^{2014}+c^{2014}+abc=4.$$ Prove that \[ \frac{a^{2013}+b^{2013}-c}{c^{2013}} + \frac{b^{2013}+c^{2013}-a}{a^{2013}} + \frac{c^{2013}+a^{2013}-b}{b^{2013}} \ge a^{2012}+b^{2012}+c^{2012}. \]
9. Let $a$, $b$, $c$ be positive reals. Prove that \[ \sqrt{\frac{a^2(bc+a^2)}{b^2+c^2}}+\sqrt{\frac{b^2(ca+b^2)}{c^2+a^2}}+\sqrt{\frac{c^2(ab+c^2)}{a^2+b^2}}\ge a+b+c. \]

Combinatorics

1. You have some cyan, magenta, and yellow beads on a non-reorientable circle, and you can perform only the following operations: i) Move a cyan bead right (clockwise) past a yellow bead, and turn the yellow bead magenta. ii) Move a magenta bead left of a cyan bead, and insert a yellow bead left of where the magenta bead ends up. iii) Do either of the above, switching the roles of the words ''magenta'' and ''left'' with those of ''yellow'' and ''right'', respectively. iv) Pick any two disjoint consecutive pairs of beads, each either yellow-magenta or magenta-yellow, appearing somewhere in the circle, and swap the orders of each pair. v) Remove four consecutive beads of one color. Starting with the circle: ''yellow, yellow, magenta, magenta, cyan, cyan, cyan'', determine whether or not you can reach.
   a) ''yellow, magenta, yellow, magenta, cyan, cyan, cyan'',
   b) ''cyan, yellow, cyan, magenta, cyan'',
   c) ''magenta, magenta, cyan, cyan, cyan'',
   d) ''yellow, cyan, cyan, cyan''.
2. A $2^{2014} + 1$ by $2^{2014} + 1$ grid has some black squares filled. The filled black squares form one or more snakes on the plane, each of whose heads splits at some points but never comes back together. In other words, for every positive integer $n$ greater than $2$, there do not exist pairwise distinct black squares $s_1$, $s_2$, \dots, $s_n$ such that $s_i$ and $s_{i+1}$ share an edge for $i=1,2, \dots, n$ (here $s_{n+1}=s_1$). What is the maximum possible number of filled black squares?
3. We say a finite set $S$ of points in the plane is very if for every point $X$ in $S$, there exists an inversion with center $X$ mapping every point in $S$ other than $X$ to another point in $S$ (possibly the same point).
   a) Fix an integer $n$. Prove that if $n \ge 2$, then any line segment $\overline{AB}$ contains a unique very set $S$ of size $n$ such that $A, B \in S$.
   b) Find the largest possible size of a very set not contained in any line.
   (Here, an inversion with center $O$ and radius $r$ sends every point $P$ other than $O$ to the point $P'$ along ray $OP$ such that $OP\cdot OP' = r^2$.)
4. Let $r$ and $b$ be positive integers. The game of Monis, a variant of Tetris, consists of a single column of red and blue blocks. If two blocks of the same color ever touch each other, they both vanish immediately. A red block falls onto the top of the column exactly once every $r$ years, while a blue block falls exactly once every $b$ years.
   a) Suppose that $r$ and $b$ are odd, and moreover the cycles are offset in such a way that no two blocks ever fall at exactly the same time. Consider a period of $rb$ years in which the column is initially empty. Determine, in terms of $r$ and $b$, the number of blocks in the column at the end.
   b) Now suppose $r$ and $b$ are relatively prime and $r+b$ is odd. At time $t=0$, the column is initially empty. Suppose a red block falls at times $t = r, 2r, \dots, (b-1)r$ years, while a blue block falls at times $t = b, 2b, \dots, (r-1)b$ years. Prove that at time $t=rb$, the number of blocks in the column is $\left\lvert 1+2(r-1)(b+r)-8S \right\rvert$, where \[ S = \left\lfloor \frac{2r}{r+b} \right\rfloor + \left\lfloor \frac{4r}{r+b} \right\rfloor + ... + \left\lfloor \frac{(r+b-1)r}{r+b} \right\rfloor . \]
5. Let $n$ be a positive integer. For any $k$, denote by $a_k$ the number of permutations of $\{1,2,\dots,n\}$ with exactly $k$ disjoint cycles. (For example, if $n=3$ then $a_2=3$ since $(1)(23)$, $(2)(31)$, $(3)(12)$ are the only such permutations.) Evaluate \[ a_n n^n + a_{n-1} n^{n-1} + \dots + a_1 n. \]
6. Let $f_0$ be the function from $\mathbb{Z}^2$ to $\{0,1\}$ such that $f_0(0,0)=1$ and $f_0(x,y)=0$ otherwise. For each positive integer $m$, let $f_m(x,y)$ be the remainder when \[ f_{m-1}(x,y) + \sum_{j=-1}^{1} \sum_{k=-1}^{1} f_{m-1}(x+j,y+k) \] is divided by $2$. Finally, for each nonnegative integer $n$, let $a_n$ denote the number of pairs $(x,y)$ such that $f_n(x,y) = 1$. Find a closed form for $a_n$.

Geometry

1. Let $ABC$ be a triangle with symmedian point $K$. Select a point $A_1$ on line $BC$ such that the lines $AB$, $AC$, $A_1K$ and $BC$ are the sides of a cyclic quadrilateral. Define $B_1$ and $C_1$ similarly. Prove that $A_1$, $B_1$, and $C_1$ are collinear.
2. $ABCD$ is a cyclic quadrilateral inscribed in the circle $\omega$. Let $AB \cap CD = E$, $AD \cap BC = F$. Let $\omega_1, \omega_2$ be the circumcircles of $AEF, CEF$, respectively. Let $\omega \cap \omega_1 = G$, $\omega \cap \omega_2 = H$. Show that $AC, BD, GH$ are concurrent.
3. Let $A_1A_2A_3 \cdots A_{2013}$ be a cyclic $2013$-gon. Prove that for every point $P$ not the circumcenter of the $2013$-gon, there exists a point $Q\neq P$ such that $\frac{A_iP}{A_iQ}$ is constant for $i \in \{1, 2, 3, \cdots, 2013\}$.
4. Let $ABCD$ be a quadrilateral inscribed in circle $\omega$. Define $E = AA \cap CD$, $F = AA \cap BC$, $G = BE \cap \omega$, $H = BE \cap AD$, $I = DF \cap \omega$, $J = DF \cap AB$. Prove that $GI$, $HJ$, and the $B$-symmedian are concurrent.
5. Let $P$ be a point in the interior of an acute triangle $ABC$, and let $Q$ be its isogonal conjugate. Denote by $\omega_P$ and $\omega_Q$ the circumcircles of triangles $BPC$ and $BQC$, respectively. Suppose the circle with diameter $\overline{AP}$ intersects $\omega_P$ again at $M$, and line $AM$ intersects $\omega_P$ again at $X$. Similarly, suppose the circle with diameter $\overline{AQ}$ intersects $\omega_Q$ again at $N$, and line $AN$ intersects $\omega_Q$ again at $Y$. Prove that lines $MN$ and $XY$ are parallel. (Here, the points $P$ and $Q$ are isogonal conjugates with respect to $\triangle ABC$ if the internal angle bisectors of $\angle BAC$, $\angle CBA$, and $\angle ACB$ also bisect the angles $\angle PAQ$, $\angle PBQ$, and $\angle PCQ$, respectively. For example, the orthocenter is the isogonal conjugate of the circumcenter.)
6. Let $ABCD$ be a cyclic quadrilateral with center $O$. Suppose the circumcircles of triangles $AOB$ and $COD$ meet again at $G$, while the circumcircles of triangles $AOD$ and $BOC$ meet again at $H$. Let $\omega_1$ denote the circle passing through $G$ as well as the feet of the perpendiculars from $G$ to $AB$ and $CD$. Define $\omega_2$ analogously as the circle passing through $H$ and the feet of the perpendiculars from $H$ to $BC$ and $DA$. Show that the midpoint of $GH$ lies on the radical axis of $\omega_1$ and $\omega_2$.
7. Let $ABC$ be a triangle with circumcenter $O$. Let $P$ be a point inside $ABC$, so let the points $D, E, F$ be on $BC, AC, AB$ respectively so that the Miquel point of $DEF$ with respect to $ABC$ is $P$. Let the reflections of $D, E, F$ over the midpoints of the sides that they lie on be $R, S, T$. Let the Miquel point of $RST$ with respect to the triangle $ABC$ be $Q$. Show that $OP = OQ$.
8. In triangle $ABC$ with incenter $I$ and circumcenter $O$, let $A',B',C'$ be the points of tangency of its circumcircle with its $A,B,C$-mixtilinear circles, respectively. Let $\omega_A$ be the circle through $A'$ that is tangent to $AI$ at $I$, and define $\omega_B, \omega_C$ similarly. Prove that $\omega_A,\omega_B,\omega_C$ have a common point $X$ other than $I$, and that $\angle AXO = \angle OXA'$.
9. Let $P$ be a point inside a triangle $ABC$ such that $\angle PAC= \angle PCB$. Let the projections of $P$ onto $BC$, $CA$, and $AB$ be $X,Y,Z$ respectively. Let $O$ be the circumcenter of $\triangle XYZ$, $H$ be the foot of the altitude from $B$ to $AC$, $N$ be the midpoint of $AC$, and $T$ be the point such that $TYPO$ is a parallelogram. Show that $\triangle THN$ is similar to $\triangle PBC$.
10. We are given triangles $ABC$ and $DEF$ such that $D\in BC, E\in CA, F\in AB$, $AD\perp EF, BE\perp FD, CF\perp DE$. Let the circumcenter of $DEF$ be $O$, and let the circumcircle of $DEF$ intersect $BC,CA,AB$ again at $R,S,T$ respectively. Prove that the perpendiculars to $BC,CA,AB$ through $D,E,F$ respectively intersect at a point $X$, and the lines $AR,BS,CT$ intersect at a point $Y$, such that $O,X,Y$ are collinear.
11. Let $AB=AC$ in $\triangle ABC$, and let $D$ be a point on segment $AB$. The tangent at $D$ to the circumcircle $\omega$ of $BCD$ hits $AC$ at $E$. The other tangent from $E$ to $\omega$ touches it at $F$, and $G=BF \cap CD$, $H=AG \cap BC$. Prove that $BH=2HC$.
12. Let $ABC$ be a nondegenerate acute triangle with circumcircle $\omega$ and let its incircle $\gamma$ touch $AB, AC, BC$ at $X, Y, Z$ respectively. Let $XY$ hit arcs $AB, AC$ of $\omega$ at $M, N$ respectively, and let $P \neq X, Q \neq Y$ be the points on $\gamma$ such that $MP=MX, NQ=NY$. If $I$ is the center of $\gamma$, prove that $P, I, Q$ are collinear if and only if $\angle BAC=90^\circ$.

Number Theory

1. Does there exist a strictly increasing infinite sequence of perfect squares $a_1, a_2, a_3, ...$ such that for all $k\in \mathbb{Z}^+$ we have that $13^k | a_k+1$?
2. Define the Fibanocci sequence recursively by $F_1=1$, $F_2=1$ and $F_{i+2} = F_i + F_{i+1}$ for all $i$. Prove that for all integers $b,c>1$, there exists an integer $n$ such that the sum of the digits of $F_n$ when written in base $b$ is greater than $c$.
3. Let $t$ and $n$ be fixed integers each at least $2$. Find the largest positive integer $m$ for which there exists a polynomial $P$, of degree $n$ and with rational coefficients, such that the following property holds: exactly one of \[ \frac{P(k)}{t^k} \text{ and } \frac{P(k)}{t^{k+1}} \] is an integer for each $k = 0,1, ..., m$.
4. Let $\mathbb N$ denote the set of positive integers, and for a function $f$, let $f^k(n)$ denote the function $f$ applied $k$ times. Call a function $f : \mathbb N \to \mathbb N$ saturated if \[ f^{f^{f(n)}(n)}(n) = n \] for every positive integer $n$. Find all positive integers $m$ for which the following holds: every saturated function $f$ satisfies $f^{2014}(m) = m$.
5. Define a beautiful number to be an integer of the form $a^n$, where $a\in\{3,4,5,6\}$ and $n$ is a positive integer. Prove that each integer greater than $2$ can be expressed as the sum of pairwise distinct beautiful numbers.
6. Show that the numerator of \[ \frac{2^{p-1}}{p+1} - \left(\sum_{k = 0}^{p-1}\frac{\binom{p-1}{k}}{(1-kp)^2}\right) \] is a multiple of $p^3$ for any odd prime $p$.
7. Find all triples $(a,b,c)$ of positive integers such that if $n$ is not divisible by any prime less than $2014$, then $n+c$ divides $a^n+b^n+n$.
8. Let $\mathbb N$ denote the set of positive integers. Find all functions $f: \mathbb{N} \to \mathbb{N}$ such that: i) The greatest common divisor of the sequence $f(1), f(2), \dots$ is $1$. ii) For all sufficiently large integers $n$, we have $f(n) \neq 1$ and \[ f(a)^n \mid f(a+b)^{a^{n-1}} - f(b)^{a^{n-1}} \] for all positive integers $a$ and $b$.
9. Let $d$ be a positive integer and let $\varepsilon$ be any positive real. Prove that for all sufficiently large primes $p$ with $\gcd(p-1,d) \neq 1$, there exists an positive integer less than $p^r$ which is not a $d$th power modulo $p$, where $r$ is defined by \[ \log r = \varepsilon - \frac{1}{\gcd(d,p-1)}. \]
10. Find all positive integer bases $b \ge 9$ so that the number \[ \frac{{\overbrace{11 \cdots 1}^{n-1 \ 1's}0\overbrace{77 \cdots 7}^{n-1\ 7's}8\overbrace{11 \cdots 1}^{n \ 1's}}_b}{3} \] is a perfect cube in base 10 for all sufficiently large positive integers $n$.
11. Let $p$ be a prime satisfying $p^2\mid 2^{p-1}-1$, and let $n$ be a positive integer. Define \[ f(x) = \frac{(x-1)^{p^n}-(x^{p^n}-1)}{p(x-1)}. \] Find the largest positive integer $N$ such that there exist polynomials $g(x)$, $h(x)$ with integer coefficients and an integer $r$ satisfying $$f(x) = (x-r)^N g(x) + p \cdot h(x).$$

[DOWNLOAD SOLUTIONS ##download##]