[Shortlists & Solutions] Entirely Legitimate (Junior) Math Olympiad 2013

Algebra

1. 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$.)
2. Prove that for all positive reals $a,b,c$, \[\frac{1}{a+\frac{1}{b}+1}+\frac{1}{b+\frac{1}{c}+1}+\frac{1}{c+\frac{1}{a}+1}\ge \frac{3}{\sqrt[3]{abc}+\frac{1}{\sqrt[3]{abc}}+1}. \]
3. Find all $f:\mathbb{R}\to\mathbb{R}$ such that for all $x,y\in\mathbb{R}$, $f(x)+f(y) = f(x+y)$ and $f(x^{2013}) = f(x)^{2013}$.
4. Positive reals $a$, $b$, and $c$ obey $$\frac{a^2+b^2+c^2}{ab+bc+ca} = \frac{ab+bc+ca+1}{2}.$$ Prove that \[ \sqrt{a^2+b^2+c^2} \le 1 + \frac{\lvert a-b \rvert + \lvert b-c \rvert + \lvert c-a \rvert}{2}. \]
5. Let $a,b,c$ be positive reals satisfying $a+b+c = \sqrt[7]{a} + \sqrt[7]{b} + \sqrt[7]{c}$. Prove that $a^a b^b c^c \ge 1$.
6. Let $a, b, c$ be positive reals such that $a+b+c=3$. Prove that \[18\sum_{\text{cyc}}\frac{1}{(3-c)(4-c)}+2(ab+bc+ca)\ge 15. \]
7. Consider a function $f: \mathbb Z \to \mathbb Z$ such that for every integer $n \ge 0$, there are at most $0.001n^2$ pairs of integers $(x,y)$ for which $f(x+y) \neq f(x)+f(y)$ and $\max\{ \lvert x \rvert, \lvert y \rvert \} \le n$. Is it possible that for some integer $n \ge 0$, there are more than $n$ integers $a$ such that $f(a) \neq a \cdot f(1)$ and $\lvert a \rvert \le n$?
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, and let $$\sqrt[2013]{\frac{3}{a^{2013}+b^{2013}+c^{2013}}}=P.$$ Prove that \[\prod_{\text{cyc}}\left(\frac{(2P+\frac{1}{2a+b})(2P+\frac{1}{a+2b})}{(2P+\frac{1}{a+b+c})^2}\right)\ge \prod_{\text{cyc}}\left(\frac{(P+\frac{1}{4a+b+c})(P+\frac{1}{3b+3c})}{(P+\frac{1}{3a+2b+c})(P+\frac{1}{3a+b+2c})}\right).\]

Combinatorics

1. Let $n\ge2$ be a positive integer. The numbers $1,2,..., n^2$ are consecutively placed into squares of an $n\times n$, so the first row contains $1,2,...,n$ from left to right, the second row contains $n+1,n+2,...,2n$ from left to right, and so on. The magic square value of a grid is defined to be the number of rows, columns, and main diagonals whose elements have an average value of $\frac{n^2 + 1}{2}$. Show that the magic-square value of the grid stays constant under the following two operations: (1) a permutation of the rows; and (2) a permutation of the columns. (The operations can be used multiple times, and in any order.)
2. Let $n$ be a fixed positive integer. Initially, $n$ 1's are written on a blackboard. Every minute, David picks two numbers $x$ and $y$ written on the blackboard, erases them, and writes the number $(x+y)^4$ on the blackboard. Show that after $n-1$ minutes, the number written on the blackboard is at least $2^{\frac{4n^2-4}{3}}$.
3. Let $a_1,a_2,...,a_9$ be nine real numbers, not necessarily distinct, with average $m$. Let $A$ denote the number of triples $1 \le i < j < k \le 9$ for which $a_i + a_j + a_k \ge 3m$. What is the minimum possible value of $A$? 
4. Let $n$ be a positive integer. The numbers $\{1, 2, ..., n^2\}$ are placed in an $n \times n$ grid, each exactly once. The grid is said to be Muirhead-able if the sum of the entries in each column is the same, but for every $1 \le i,k \le n-1$, the sum of the first $k$ entries in column $i$ is at least the sum of the first $k$ entries in column $i+1$. For which $n$ can one construct a Muirhead-able array such that the entries in each column are decreasing? 
5. There is a $2012\times 2012$ grid with rows numbered $1,2,\dots 2012$ and columns numbered $1,2,\dots, 2012$, and we place some rectangular napkins on it such that the sides of the napkins all lie on grid lines. Each napkin has a positive integer thickness. (in micrometers!) 
   a) Show that there exist $2012^2$ unique integers $a_{i,j}$ where $i,j \in [1,2012]$ such that for all $x,y\in [1,2012]$, the sum \[ \sum _{i=1}^{x} \sum_{j=1}^{y} a_{i,j} \] is equal to the sum of the thicknesses of all the napkins that cover the grid square in row $x$ and column $y$. 
   b) Show that if we use at most $500,000$ napkins, at least half of the $a_{i,j}$ will be $0$. 
6.  A $4\times4$ grid has its 16 cells colored arbitrarily in three colors. A swap is an exchange between the colors of two cells. Prove or disprove that it always takes at most three swaps to produce a line of symmetry, regardless of the grid's initial coloring. 
7.  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? 
8. There are 20 people at a party. Each person holds some number of coins. Every minute, each person who has at least 19 coins simultaneously gives one coin to every other person at the party. (So, it is possible that $A$ gives $B$ a coin and $B$ gives $A$ a coin at the same time.) Suppose that this process continues indefinitely. That is, for any positive integer $n$, there exists a person who will give away coins during the $n$th minute. What is the smallest number of coins that could be at the party?
9. 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$.
10. Let $N\ge2$ be a fixed positive integer. There are $2N$ people, numbered $1,2,...,2N$, participating in a tennis tournament. For any two positive integers $i,j$ with $1\le i<j\le 2N$, player $i$ has a higher skill level than player $j$. Prior to the first round, the players are paired arbitrarily and each pair is assigned a unique court among $N$ courts, numbered $1,2,...,N$. During a round, each player plays against the other person assigned to his court (so that exactly one match takes place per court), and the player with higher skill wins the match (in other words, there are no upsets). Afterwards, for $i=2,3,...,N$, the winner of court $i$ moves to court $i-1$ and the loser of court $i$ stays on court $i$; however, the winner of court 1 stays on court 1 and the loser of court 1 moves to court $N$. Find all positive integers $M$ such that, regardless of the initial pairing, the players $2, 3, \ldots, N+1$ all change courts immediately after the $M$th round.

Geometry

1. Let $ABC$ be a triangle with incenter $I$. Let $U$, $V$ and $W$ be the intersections of the angle bisectors of angles $A$, $B$, and $C$ with the incircle, so that $V$ lies between $B$ and $I$, and similarly with $U$ and $W$. Let $X$, $Y$, and $Z$ be the points of tangency of the incircle of triangle $ABC$ with $BC$, $AC$, and $AB$, respectively. Let triangle $UVW$ be the David Yang triangle of $ABC$ and let $XYZ$ be the Scott Wu triangle of $ABC$. Prove that the David Yang and Scott Wu triangles of a triangle are congruent if and only if $ABC$ is equilateral.
2. Let $ABC$ be a scalene triangle with circumcircle $\Gamma$, and let $D$,$E$,$F$ be the points where its incircle meets $BC$, $AC$, $AB$ respectively. Let the circumcircles of $\triangle AEF$, $\triangle BFD$, and $\triangle CDE$ meet $\Gamma$ a second time at $X,Y,Z$ respectively. Prove that the perpendiculars from $A,B,C$ to $AX,BY,CZ$ respectively are concurrent.
3. In $\triangle ABC$, a point $D$ lies on line $BC$. The circumcircle of $ABD$ meets $AC$ at $F$ (other than $A$), and the circumcircle of $ADC$ meets $AB$ at $E$ (other than $A$). Prove that as $D$ varies, the circumcircle of $AEF$ always passes through a fixed point other than $A$, and that this point lies on the median from $A$ to $BC$.
4. Triangle $ABC$ is inscribed in circle $\omega$. A circle with chord $BC$ intersects segments $AB$ and $AC$ again at $S$ and $R$, respectively. Segments $BR$ and $CS$ meet at $L$, and rays $LR$ and $LS$ intersect $\omega$ at $D$ and $E$, respectively. The internal angle bisector of $\angle BDE$ meets line $ER$ at $K$. Prove that if $BE = BR$, then $\angle ELK = \tfrac{1}{2} \angle BCD$.
5. Let $\omega_1$ and $\omega_2$ be two orthogonal circles, and let the center of $\omega_1$ be $O$. Diameter $AB$ of $\omega_1$ is selected so that $B$ lies strictly inside $\omega_2$. The two circles tangent to $\omega_2$, passing through $O$ and $A$, touch $\omega_2$ at $F$ and $G$. Prove that $FGOB$ is cyclic.
6. Let $ABCDEF$ be a non-degenerate cyclic hexagon with no two opposite sides parallel, and define $X=AB\cap DE$, $Y=BC\cap EF$, and $Z=CD\cap FA$. Prove that
   \[\frac{XY}{XZ}=\frac{BE}{AD}\frac{\sin |\angle{B}-\angle{E}|}{\sin |\angle{A}-\angle{D}|}.\]
7. Let $ABC$ be a triangle inscribed in circle $\omega$, and let the medians from $B$ and $C$ intersect $\omega$ at $D$ and $E$ respectively. Let $O_1$ be the center of the circle through $D$ tangent to $AC$ at $C$, and let $O_2$ be the center of the circle through $E$ tangent to $AB$ at $B$. Prove that $O_1$, $O_2$, and the nine-point center of $ABC$ are collinear.
8. Let $ABC$ be a triangle, and let $D$, $A$, $B$, $E$ be points on line $AB$, in that order, such that $AC=AD$ and $BE=BC$. Let $\omega_1, \omega_2$ be the circumcircles of $\triangle ABC$ and $\triangle CDE$, respectively, which meet at a point $F \neq C$. If the tangent to $\omega_2$ at $F$ cuts $\omega_1$ again at $G$, and the foot of the altitude from $G$ to $FC$ is $H$, prove that $\angle AGH=\angle BGH$.
9. Let $ABCD$ be a cyclic quadrilateral inscribed in circle $\omega$ whose diagonals meet at $F$. Lines $AB$ and $CD$ meet at $E$. Segment $EF$ intersects $\omega$ at $X$. Lines $BX$ and $CD$ meet at $M$, and lines $CX$ and $AB$ meet at $N$. Prove that $MN$ and $BC$ concur with the tangent to $\omega$ at $X$.
10. 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$.
11. Let $\triangle ABC$ be a nondegenerate isosceles triangle with $AB=AC$, and let $D, E, F$ be the midpoints of $BC, CA, AB$ respectively. $BE$ intersects the circumcircle of $\triangle ABC$ again at $G$, and $H$ is the midpoint of minor arc $BC$. $CF\cap DG=I, BI\cap AC=J$. Prove that $\angle BJH=\angle ADG$ if and only if $\angle BID=\angle GBC$.
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$.
13. In $\triangle ABC$, $AB<AC$. $D$ and $P$ are the feet of the internal and external angle bisectors of $\angle BAC$, respectively. $M$ is the midpoint of segment $BC$, and $\omega$ is the circumcircle of $\triangle APD$. Suppose $Q$ is on the minor arc $AD$ of $\omega$ such that $MQ$ is tangent to $\omega$. $QB$ meets $\omega$ again at $R$, and the line through $R$ perpendicular to $BC$ meets $PQ$ at $S$. Prove $SD$ is tangent to the circumcircle of $\triangle QDM$.
14. Let $O$ be a point (in the plane) and $T$ be an infinite set of points such that $|P_1P_2| \le 2012$ for every two distinct points $P_1,P_2\in T$. Let $S(T)$ be the set of points $Q$ in the plane satisfying $|QP| \le 2013$ for at least one point $P\in T$. Now let $L$ be the set of lines containing exactly one point of $S(T)$. Call a line $\ell_0$ passing through $O$ bad if there does not exist a line $\ell\in L$ parallel to (or coinciding with) $\ell_0$.
    a) Prove that $L$ is nonempty.
    b) Prove that one can assign a line $\ell(i)$ to each positive integer $i$ so that for every bad line $\ell_0$ passing through $O$, there exists a positive integer $n$ with $\ell(n) = \ell_0$

Number Theory 

1. Find all ordered triples of non-negative integers $(a,b,c)$ such that $a^2+2b+c$, $b^2+2c+a$, and $c^2+2a+b$ are all perfect squares. 
2. For what polynomials $P(n)$ with integer coefficients can a positive integer be assigned to every lattice point in $\mathbb{R}^3$ so that for every integer $n \ge 1$, the sum of the $n^3$ integers assigned to any $n \times n \times n$ grid of lattice points is divisible by $P(n)$?
3.  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. 
4. 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$. 
5. Let $m_1,m_2,...,m_{2013} > 1$ be 2013 pairwise relatively prime positive integers and $A_1,A_2,...,A_{2013}$ be 2013 (possibly empty) sets with $A_i\subseteq \{1,2,...,m_i-1\}$ for $i=1,2,...,2013$. Prove that there is a positive integer $N$ such that
   \[ N \le \left( 2\left\lvert A_1 \right\rvert + 1 \right)\left( 2\left\lvert A_2 \right\rvert + 1 \right)\cdots\left( 2\left\lvert A_{2013} \right\rvert + 1 \right) \]
   and for each $i = 1, 2, ..., 2013$, there does not exist $a \in A_i$ such that $m_i$ divides $N-a$.
6. 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$.
7. 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)$.
8. We define the Fibonacci sequence $\{F_n\}_{n\ge0}$ by $F_0=0$, $F_1=1$, and for $n\ge2$, $F_n=F_{n-1}+F_{n-2}$; we define the Stirling number of the second kind $S(n,k)$ as the number of ways to partition a set of $n\ge1$ distinguishable elements into $k\ge1$ indistinguishable nonempty subsets.
9. For every positive integer $n$, let $t_n = \sum_{k=1}^{n} S(n,k) F_k$. Let $p\ge7$ be a prime. Prove that \[ t_{n+p^{2p}-1} \equiv t_n \pmod{p} \] for all $n\ge1$.

[DOWNLOAD SOLUTIONS ##download##]