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 $\dfrac{x_1x_2+y_1y_2}{\sqrt{(x_1^2+y_1^2)(x_2^2+y_2^2)}}+\dfrac{x_2x_3+y_2y_3}{\sqrt{(x_2^2+y_2^2)(x_3^2+y_3^2)}}+$ $+\dfrac{x_3x_1+y_3y_1}{\sqrt{(x_3^2+y_3^2)(x_1^2+y_1^2)}} \ge -\dfrac32.$
   
2. Let $a,b,c$ be three positive real numbers such that $ a \le b \le c$ and $a+b+c=1$. Prove that $\dfrac{a+c}{\sqrt{a^2+c^2}}+\dfrac{b+c}{\sqrt{b^2+c^2}}+$ $+\dfrac{a+b}{\sqrt{a^2+b^2}} \le \dfrac{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_nx^n + a_{n+1}x^{n+1} + \cdots + a_kx^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\ge0$. 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\ge0$. Show that $$(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}$$
7. Let $f,g$ be polynomials with complex coefficients such that $\gcd(\deg f,\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\lvert\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\rvert\ge \frac{k+1}{3(k-1)}(a+b+c)\] and \[\left\lvert\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\rvert\ge \frac{(k+1)(k+2)}{3k(k-1)}(a^2+b^2+c^2).\]
10. Let $A_1A_2A_3A_4A_5A_6A_7A_8$ be a cyclic octagon. Let $B_i$ by the intersection of $A_iA_{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, \ldots , B_8$ lie on a conic.

Combinatorics

1. Let $n\ge2$ 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 $\left(a_1,a_2,\ldots,a_{n-1}\right)$, 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,\ldots,c_k\}$ ($k\ge1$) 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\pmod{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\pmod{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\ge2$. For fixed $n$, let $f(n)$ denote the maximum possible number of distinct sets of vertices in $\{(N^{+})^k(X)\}_{k=1}^{\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 $kn^\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 $\triangle 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 $\angle BPD = \angle DPC$.
4. Circles $\Omega$ and $\omega$ are internally tangent at point $C$. Chord $AB$ of $\Omega$ is tangent to $\omega$ at $E$, where $E$ is the midpoint of $AB$. Another circle, $\omega_1$ is tangent to $\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 \angle ZEP = \tfrac{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 $\angle PAB=\angle EAC$. Prove that $\angle PBA=\angle PCA$.
6. In $\triangle 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_1H,Q_1H$ meet $\omega_1$ at $R_1,S_1$ respectively. $P_2H,Q_2H$ meet $\omega_2$ at $R_2,S_2$ respectively. Let $P_1Q_1\cap P_2Q_2 = X$, and $R_1S_1\cap R_2S_2=Y$. Prove that $X,Y,H$ are collinear.
7. Let $\triangle ABC$ be an acute triangle with circumcenter $O$ such that $AB<AC$, let $Q$ be the intersection of the external bisector of $\angle A$ with $BC$, and let $P$ be a point in the interior of $\triangle ABC$ such that $\triangle BPA$ is similar to $\triangle APC$. Show that $\angle QPA + \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^nx)$ 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,\ldots,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,\ldots,x_{n}$ of the same color such that $a_1x_1+a_2x_2+\cdots+a_{n}x_{n}=0$.
5. Prove that if $a$ and $b$ are positive integers and $ab>1$, then
   \[\left\lfloor\frac{(a-b)^2-1}{ab}\right\rfloor=\left\lfloor\frac{(a-b)^2-1}{ab-1}\right\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, \ldots, 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 '\equiv d_i+c_i \pmod{c}$ with $0\le d_i ' \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\ge2$, 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]