ELMO SL 2012

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.$$

Ray Li, Max Schindler.

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)}}.$$

Owen Goff.

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$.

David Yang.

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$ .

David Yang.

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$ .)

David Yang.

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}$ .

Calvin Deng.

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.

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}$ .

Sammy Luo and Alex Zhu.

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).$$

Calvin Deng.

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.

David Yang.

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.

David Yang.

Determine whether it's possible to cover a $K_{2012}$ with

a) 1000 $K_{1006}$ 's;

b) 1000 $K_{1006,1006}$ 's.

David Yang.

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$ .

David Yang.

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.

Calvin Deng.

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.

Linus Hamilton.

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$ .

Linus Hamilton.

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$ .

David Yang.

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.

Victor Wang.

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$ ?

David Yang.

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$ .

Ray Li.

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$ .

Ray Li.

$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$ .

Alex Zhu.

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}$ .

Ray Li.

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$ .

Calvin Deng.

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.

Ray Li.

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}$ .

Alex Zhu.

Find all positive integers $n$ such that $4^n+6^n+9^n$ is a square.

David Yang, Alex Zhu.

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$ .

Anderson Wang.

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$ .

Alex Zhu.

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.)

Lewis Chen.

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$ .

Ravi Jagadeesan.

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$ .

Calvin Deng.

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$ ).

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.

Bobby Shen.

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$ .

Victor Wang.

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?

David Yang.