# [Shortlists & Solutions] Eric Larsen Math Olympiad 2012

### 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 $\frac{x_1x_2+y_1y_2}{\sqrt{(x_1^2+y_1^2)(x_2^2+y_2^2)}}+\frac{x_2x_3+y_2y_3}{\sqrt{(x_2^2+y_2^2)(x_3^2+y_3^2)}}+\frac{x_3x_1+y_3y_1}{\sqrt{(x_3^2+y_3^2)(x_1^2+y_1^2)}} \ge -\frac32.$
2. Let $a,b,c$ be three positive real numbers such that $a \le b \le c$ and $a+b+c=1$. Prove that $\frac{a+c}{\sqrt{a^2+c^2}}+\frac{b+c}{\sqrt{b^2+c^2}}+\frac{a+b}{\sqrt{a^2+b^2}} \le \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_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?
 MOlympiad.NET là dự án thu thập và phát hành các đề thi tuyển sinh và học sinh giỏi toán. Quý bạn đọc muốn giúp chúng tôi chỉnh sửa đề thi này, xin hãy để lại bình luận facebook (có thể đính kèm hình ảnh) hoặc google (có thể sử dụng $\LaTeX$) bên dưới. BBT rất mong bạn đọc ủng hộ UPLOAD đề thi và đáp án mới hoặc liên hệbbt.molympiad@gmail.comChúng tôi nhận tất cả các định dạng của tài liệu: $\TeX$, PDF, WORD, IMG,...