Eric Larsen Math Olympiad 2012 [Shortlists & Solutions]

Algebra

1. Let $x_1,x_2,x_3,y_1,y_2,y_3$ be nonzero real numbers satisfying $x_1+x_2+x_3=0$, $y_1+y_2+y_3=0$. Prove that ${\displaystyle \frac{x_1{x}_2+y_1{y}_2}{\sqrt{(x_1^2+y_1^2)(x_2^2+y_2^2)}}}+{\displaystyle \frac{x_2{x}_3+y_2{y}_3}{\sqrt{(x_2^2+y_2^2)(x_3^2+y_3^2)}}}+$ $+{\displaystyle \frac{x_3{x}_1+y_3{y}_1}{\sqrt{(x_3^2+y_3^2)(x_1^2+y_1^2)}}}\ge -{\displaystyle \frac{3}{2}}.$
   
2. Let $a,b,c$ be three positive real numbers such that $a\le b\le c$ and $a+b+c=1$. Prove that ${\displaystyle \frac{a+c}{\sqrt{a^2+c^2}}}+{\displaystyle \frac{b+c}{\sqrt{b^2+c^2}}}+$ $+{\displaystyle \frac{a+b}{\sqrt{a^2+b^2}}}\le {\displaystyle \frac{3\sqrt{6}(b+c{)}^2}{\sqrt{(a^2+b^2)(b^2+c^2)(c^2+a^2)}}}.$
3. Prove that any polynomial of the form $1+a_n{x}^n+a_{n+1}{x}^{n+1}+\cdots +a_k{x}^k$ ($k\ge n$) has at least $n-2$ non-real roots (counting multiplicity), where the $a_i$ ($n\le i\le k$) are real and $a_k\ne 0$.
4. Let $a_0,b_0$ be positive integers, and define $a_{i+1}=a_i+\lfloor \sqrt{b_i}\rfloor$ and $b_{i+1}=b_i+\lfloor \sqrt{a_i}\rfloor$ for all $i\ge 0$. Show that there exists a positive integer $n$ such that $a_n=b_n$.
5. Prove that if $m,n$ are relatively prime positive integers, $x^m-y^n$ is irreducible in the complex numbers. (A polynomial $P(x,y)$ is irreducible if there do not exist nonconstant polynomials $f(x,y)$ and $g(x,y)$ such that $P(x,y)=f(x,y)g(x,y)$ for all $x,y$.)
6. Let $a,b,c\ge 0$. Show that $$\begin{gathered} (a^2+2bc{)}^{2012}+(b^2+2ca{)}^{2012}+(c^2+2ab{)}^{2012} \\ \le (a^2+b^2+c^2{)}^{2012}+2(ab+bc+ca{)}^{2012} \end{gathered}$$
7. Let $f,g$ be polynomials with complex coefficients such that $gcd(\mathrm{deg}f,\mathrm{deg}g)=1$. Suppose that there exist polynomials $P(x,y)$ and $Q(x,y)$ with complex coefficients such that $f(x)+g(y)=P(x,y)Q(x,y)$. Show that one of $P$ and $Q$ must be constant.
8. Find all functions $f:\mathbb{Q}\to \mathbb{R}$ such that $$f(x)f(y)f(x+y)=f(xy)(f(x)+f(y))$$ for all $x,y\in \mathbb{Q}$.
9. Let $a,b,c$ be distinct positive real numbers, and let $k$ be a positive integer greater than $3$. Show that $$\left|\frac{a^{k+1}(b-c)+b^{k+1}(c-a)+c^{k+1}(a-b)}{a^k(b-c)+b^k(c-a)+c^k(a-b)}\right|\ge \frac{k+1}{3(k-1)}(a+b+c)$$ and $$\left|\frac{a^{k+2}(b-c)+b^{k+2}(c-a)+c^{k+2}(a-b)}{a^k(b-c)+b^k(c-a)+c^k(a-b)}\right|\ge \frac{(k+1)(k+2)}{3k(k-1)}(a^2+b^2+c^2).$$
10. Let $A_1{A}_2{A}_3{A}_4{A}_5{A}_6{A}_7{A}_8$ be a cyclic octagon. Let $B_i$ by the intersection of $A_i{A}_{i+1}$ and $A_{i+3}{A}_{i+4}$. (Take $A_9=A_1$, $A_{10}=A_2$, etc.) Prove that $B_1,B_2,\dots ,B_8$ lie on a conic.

Combinatorics

1. Let $n\ge 2$ be a positive integer. Given a sequence $\left(s_i\right)$ of $n$ distinct real numbers, define the "class" of the sequence to be the sequence $(a_1,a_2,\dots ,a_{n-1})$, where $a_i$ is $1$ if $s_{i+1}>s_i$ and $-1$ otherwise. Find the smallest integer $m$ such that there exists a sequence $\left(w_i\right)$ of length $m$ such that for every possible class of a sequence of length $n$, there is a subsequence of $\left(w_i\right)$ that has that class.
2. Determine whether it's possible to cover a $K_{2012}$ with
   a) 1000 $K_{1006}$'s;
   b) 1000 $K_{1006,1006}$'s.
3. Find all ordered pairs of positive integers $(m,n)$ for which there exists a set $C=\{c_1,\dots ,c_k\}$ ($k\ge 1$) of colors and an assignment of colors to each of the $mn$ unit squares of a $m\times n$ grid such that for every color $c_i\in C$ and unit square $S$ of color $c_i$, exactly two direct (non-diagonal) neighbors of $S$ have color $c_i$.
4. A tournament on $2k$ vertices contains no $7$-cycles. Show that its vertices can be partitioned into two sets, each with size $k$, such that the edges between vertices of the same set do not determine any $3$-cycles.
5. Form the infinite graph $A$ by taking the set of primes $p$ congruent to $1(\mathrm{mod}4)$, and connecting $p$ and $q$ if they are quadratic residues modulo each other. Do the same for a graph $B$ with the primes $1(\mathrm{mod}8)$. Show $A$ and $B$ are isomorphic to each other.
6. Consider a directed graph $G$ with $n$ vertices, where $1$-cycles and $2$-cycles are permitted. For any set $S$ of vertices, let $N^{+}(S)$ denote the out-neighborhood of $S$ (i.e. set of successors of $S$), and define $(N^{+}{)}^k(S)=N^{+}((N^{+}{)}^{k-1}(S))$ for $k\ge 2$. For fixed $n$, let $f(n)$ denote the maximum possible number of distinct sets of vertices in $\{(N^{+}{)}^k(X){\}}_{k=1}^{\mathrm{\infty }}$, where $X$ is some subset of $V(G)$. Show that there exists $n>2012$ such that $f(n)<{1.0001}^n$.
7. Consider a graph $G$ with $n$ vertices and at least $n^2/10$ edges. Suppose that each edge is colored in one of $c$ colors such that no two incident edges have the same color. Assume further that no cycles of size $10$ have the same set of colors. Prove that there is a constant $k$ such that $c$ is at least $k{n}^{\frac{8}{5}}$ for any $n$.
8. Consider the equilateral triangular lattice in the complex plane defined by the Eisenstein integers; let the ordered pair $(x,y)$ denote the complex number $x+y\omega$ for $\omega =e^{2\pi i/3}$. We define an $\omega$-chessboard polygon to be a (non self-intersecting) polygon whose sides are situated along lines of the form $x=a$ or $y=b$, where $a$ and $b$ are integers. These lines divide the interior into unit triangles, which are shaded alternately black and white so that adjacent triangles have different colors. To tile an $\omega$-chessboard polygon by lozenges is to exactly cover the polygon by non-overlapping rhombuses consisting of two bordering triangles. Finally, a tasteful tiling is one such that for every unit hexagon tiled by three lozenges, each lozenge has a black triangle on its left (defined by clockwise orientation) and a white triangle on its right (so the lozenges are BW, BW, BW in clockwise order).
   a) Prove that if an $\omega$-chessboard polygon can be tiled by lozenges, then it can be done so tastefully.
   b) Prove that such a tasteful tiling is unique.
9. For a set $A$ of integers, define $f(A)=\{x^2+xy+y^2:x,y\in A\}$. Is there a constant $c$ such that for all positive integers $n$, there exists a set $A$ of size $n$ such that $|f(A)|\le cn$?.

Geometry

1. In acute triangle $ABC$, let $D,E,F$ denote the feet of the altitudes from $A,B,C$, respectively, and let $\omega$ be the circumcircle of $\mathrm{△}AEF$. Let ${\omega }_1$ and ${\omega }_2$ be the circles through $D$ tangent to $\omega$ at $E$ and $F$, respectively. Show that ${\omega }_1$ and ${\omega }_2$ meet at a point $P$ on $BC$ other than $D$.
2. In triangle $ABC$, $P$ is a point on altitude $AD$. $Q,R$ are the feet of the perpendiculars from $P$ to $AB,AC$, and $QP,RP$ meet $BC$ at $S$ and $T$ respectively. the circumcircles of $BQS$ and $CRT$ meet $QR$ at $X,Y$.
   a) Prove $SX,TY,AD$ are concurrent at a point $Z$.
   b) Prove $Z$ is on $QR$ iff $Z=H$, where $H$ is the orthocenter of $ABC$.
3. $ABC$ is a triangle with incenter $I$. The foot of the perpendicular from $I$ to $BC$ is $D$, and the foot of the perpendicular from $I$ to $AD$ is $P$. Prove that $\mathrm{\angle }BPD=\mathrm{\angle }DPC$.
4. Circles $\mathrm{\Omega }$ and $\omega$ are internally tangent at point $C$. Chord $AB$ of $\mathrm{\Omega }$ is tangent to $\omega$ at $E$, where $E$ is the midpoint of $AB$. Another circle, ${\omega }_1$ is tangent to $\mathrm{\Omega },\omega ,$ and $AB$ at $D,Z,$ and $F$ respectively. Rays $CD$ and $AB$ meet at $P$. If $M$ is the midpoint of major arc $AB$, show that $\tan \mathrm{\angle }ZEP=\frac{PE}{CM}$.
5. Let $ABC$ be an acute triangle with $AB<AC$, and let $D$ and $E$ be points on side $BC$ such that $BD=CE$ and $D$ lies between $B$ and $E$. Suppose there exists a point $P$ inside $ABC$ such that $PD\parallel AE$ and $\mathrm{\angle }PAB=\mathrm{\angle }EAC$. Prove that $\mathrm{\angle }PBA=\mathrm{\angle }PCA$.
6. In $\mathrm{△}ABC$, $H$ is the orthocenter, and $AD,BE$ are arbitrary cevians. Let ${\omega }_1,{\omega }_2$ denote the circles with diameters $AD$ and $BE$, respectively. $HD,HE$ meet ${\omega }_1,{\omega }_2$ again at $F,G$. $DE$ meets ${\omega }_1,{\omega }_2$ again at $P_1,P_2$ respectively. $FG$ meets ${\omega }_1,{\omega }_2$ again $Q_1,Q_2$ respectively. $P_{1}H,Q_{1}H$ meet ${\omega }_1$ at $R_1,S_1$ respectively. $P_{2}H,Q_{2}H$ meet ${\omega }_2$ at $R_2,S_2$ respectively. Let $P_1{Q}_1\cap P_2{Q}_2=X$, and $R_1{S}_1\cap R_2{S}_2=Y$. Prove that $X,Y,H$ are collinear.
7. Let $\mathrm{△}ABC$ be an acute triangle with circumcenter $O$ such that $AB<AC$, let $Q$ be the intersection of the external bisector of $\mathrm{\angle }A$ with $BC$, and let $P$ be a point in the interior of $\mathrm{△}ABC$ such that $\mathrm{△}BPA$ is similar to $\mathrm{△}APC$. Show that $\mathrm{\angle }QPA+\mathrm{\angle }OQB={90}^{\circ }$.

Number Theory 

1. Find all positive integers $n$ such that $4^n+6^n+9^n$ is a square. 
2. For positive rational $x$, if $x$ is written in the form $p/q$ with $p,q$ positive relatively prime integers, define $f(x)=p+q$. For example, $f(1)=2$.
   a) Prove that if $f(x)=f(mx/n)$ for rational $x$ and positive integers $m,n$, then $f(x)$ divides $|m-n|$.
   b) Let $n$ be a positive integer. If all $x$ which satisfy $f(x)=f(2^{n}x)$ also satisfy $f(x)=2^n-1$, find all possible values of $n$. 
3.  Let $s(k)$ be the number of ways to express $k$ as the sum of distinct ${2012}^{th}$ powers, where order does not matter. Show that for every real number $c$ there exists an integer $n$ such that $s(n)>cn$. Do there exist positive integers $b,n>1$ such that when $n$ is expressed in base $b$, there are more than $n$ distinct permutations of its digits? For example, when $b=4$ and $n=18$, $18={102}_4$, but $102$ only has $6$ digit arrangements. (Leading zeros are allowed in the permutations.)
4. Let $n>2$ be a positive integer and let $p$ be a prime. Suppose that the nonzero integers are colored in $n$ colors. Let $a_1,a_2,\dots ,a_n$ be integers such that for all $1\le i\le n$, $p^i\nmid a_i$ and $p^{i-1}\mid a_i$. In terms of $n$, $p$, and $\{a_i{\}}_{i=1}^n$, determine if there must exist integers $x_1,x_2,\dots ,x_n$ of the same color such that $a_1{x}_1+a_2{x}_2+\cdots +a_n{x}_n=0$.
5. Prove that if $a$ and $b$ are positive integers and $ab>1$, then
   $$\lfloor \frac{(a-b{)}^2-1}{ab}\rfloor =\lfloor \frac{(a-b{)}^2-1}{ab-1}\rfloor .$$Here $\lfloor x\rfloor$ denotes the greatest integer not exceeding $x$.
6. A diabolical combination lock has $n$ dials (each with $c$ possible states), where $n,c>1$. The dials are initially set to states $d_1,d_2,\dots ,d_n$, where $0\le d_i\le c-1$ for each $1\le i\le n$. Unfortunately, the actual states of the dials (the $d_i$'s) are concealed, and the initial settings of the dials are also unknown. On a given turn, one may advance each dial by an integer amount $c_i$ ($0\le c_i\le c-1$), so that every dial is now in a state $d_i^{\prime }\equiv d_i+c_i(\mathrm{mod}c)$ with $0\le d_i^{\prime }\le c-1$. After each turn, the lock opens if and only if all of the dials are set to the zero state; otherwise, the lock selects a random integer $k$ and cyclically shifts the $d_i$'s by $k$ (so that for every $i$, $d_i$ is replaced by $d_{i-k}$, where indices are taken modulo $n$).
7. Show that the lock can always be opened, regardless of the choices of the initial configuration and the choices of $k$ (which may vary from turn to turn), if and only if $n$ and $c$ are powers of the same prime.
8. Fix two positive integers $a,k\ge 2$, and let $f\in \mathbb{Z}[x]$ be a nonconstant polynomial. Suppose that for all sufficiently large positive integers $n$, there exists a rational number $x$ satisfying $f(x)=f(a^n{)}^k$. Prove that there exists a polynomial $g\in \mathbb{Q}[x]$ such that $f(g(x))=f(x{)}^k$ for all real $x$.
9. Are there positive integers $m,n$ such that there exist at least $2012$ positive integers $x$ such that both $m-x^2$ and $n-x^2$ are perfect squares?

[DOWNLOAD SOLUTIONS]