2014 ELMO Shortlist

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. \]Proposed by Ryan Alweiss

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). \]Proposed by AJ Dennis

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). \]Proposed by Allen Liu

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$.) Proposed by Evan Chen

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$. Proposed by Ryan Alweiss

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}. \]Proposed by Sammy Luo

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. Proposed by Yang Liu

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}. \]Proposed by David Stoner

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. \]Proposed by Robin Park

Combinatorics

1

You have some cyan, magenta, and yellow beads on a non-reorientable circle, and you can perform only the following operations: 1. Move a cyan bead right (clockwise) past a yellow bead, and turn the yellow bead magenta. 2. Move a magenta bead left of a cyan bead, and insert a yellow bead left of where the magenta bead ends up. 3. Do either of the above, switching the roles of the words ``magenta'' and ``left'' with those of ``yellow'' and ``right'', respectively. 4. 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. 5. 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''. Proposed by Sammy Luo

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? Proposed by David Yang

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$.) Proposed by Sammy Luo

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 . \] Proposed by Sammy Luo

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. \]Proposed by Sammy Luo

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$. Proposed by Bobby Shen

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. Proposed by Sammy Luo

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. Proposed by Yang Liu

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\}$. Proposed by Robin Park

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$, and $J = DF \cap AB$. Prove that $GI$, $HJ$, and the $B$-symmedian are concurrent. Proposed by Robin Park

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.) Proposed by Sammy Luo

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$. Proposed by Yang Liu

7

Let $ABC$ be a triangle inscribed in circle $\omega$ with center $O$, let $\omega_A$ be its $A$-mixtilinear incircle, $\omega_B$ be its $B$-mixtilinear incircle, $\omega_C$ be its $C$-mixtilinear incircle, and $X$ be the radical center of $\omega_A$, $\omega_B$, $\omega_C$. Let $A'$, $B'$, $C'$ be the points at which $\omega_A$, $\omega_B$, $\omega_C$ are tangent to $\omega$. Prove that $AA'$, $BB'$, $CC'$ and $OX$ are concurrent. Proposed by Robin Park

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'$. Proposed by Sammy Luo

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$. Proposed by Sammy Luo

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. Proposed by Sammy Luo

11

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$. Proposed by Yang Liu

12

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$. Proposed by David Stoner

13

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$. Proposed by David Stoner

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$? Proposed by Jesse Zhang

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$. Proposed by Ryan Alweiss

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$. Proposed by Michael Kural

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$. Proposed by Evan Chen

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. Proposed by Matthew Babbitt

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$. Proposed by Yang Liu

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$. Proposed by Evan Chen

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$. Proposed by Yang Liu

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)}. \]Proposed by Shashwat Kishore

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$. Proposed by Yang Liu

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)$. Proposed by Victor Wang