ELMO SL 2011

Let $n$ be a positive integer. There are $n$ soldiers stationed on the $n$ t h root of unity in the complex plane. Each round, you pick a point, and all the soldiers shoot in a straight line towards that point; if their shot hits another soldier, the hit soldier dies and no longer shoots during the next round. What is the minimum number of rounds, in terms of $n$, required to eliminate all the soldiers?

David Yang.

Find all functions $f : \mathbb{R}^+ \mapsto \mathbb{R}^+$, where $\mathbb{R}^+$ denotes the positive reals, such that whenever $a > b > c > d > 0$ are reel numbers with $ad = bc$, $$f(a + d) + f(b - c) = f(a - d) + f(b + c).$$

Let $N$ be a positive integer. Define a sequence $a_0,a_1,\ldots$ by $a_0=0$, $a_1=1$, and $a_{n+1}+a_{n-1}=a_n(2-1/N)$ for $n\ge1$. Prove that $a_n<\sqrt{N+1}$ for all $n$.

Evan O'Dorney.

In terms of $n\ge2$ , find the largest constant $c$ such that for all nonnegative $a_1,a_2,\ldots,a_n$ satisfying $a_1+a_2+\cdots+a_n=n$ , the following inequality holds: $$\frac1{n+ca_1^2}+\frac1{n+ca_2^2}+\cdots+\frac1{n+ca_n^2}\le \frac{n}{n+c}.$$

Calvin Deng.

Given positive reals $x,y,z$ such that $xy+yz+zx=1$ , show that $$\sum_{\text{cyc}}\sqrt{(xy+kx+ky)(xz+kx+kz)}\ge k^2,$$where $k=2+\sqrt{3}$ .

Victor Wang.

Let $Q(x)$ be a polynomial with integer coefficients. Prove that there exists a polynomial $P(x)$ with integer coefficients such that for every integer $n\ge\deg{Q}$ , $$\sum_{i=0}^{n}\frac{!i P(i)}{i!(n-i)!} = Q(n),$$where $!i$ denotes the number of derangements (permutations with no fixed points) of $1,2,\ldots,i$ .

Calvin Deng.

Determine whether there exists a sequence $\{a_n\}_{n=0}^{\infty}$ of real numbers such that the following holds:

• For all $n \ge 0$, $a_n \neq 0$.
• There exist real numbers $x$ and $y$ such that $a_{n+2} = xa_{n+1} + ya_n$ for all $n \ge 0$.
• For all positive real numbers $r$, there exists positive integers $i$ and $j$ such that $|a_i| < r < |a_j|$.

Let $n>1$ be an integer and $a,b,c$ be three complex numbers such that $a+b+c=0$ and $a^n+b^n+c^n=0$ . Prove that two of $a,b,c$ have the same magnitude.

Evan O'Dorney.

Let $S$ be a finite set, and let $F$ be a family of subsets of $S$ such that

a) If $A\subseteq S$ , then $A\in F$ if and only if $S\setminus A\notin F$ ;

b) If $A\subseteq B\subseteq S$ and $B\in F$ , then $A\in F$ .

Determine if there must exist a function $f:S\to\mathbb{R}$ such that for every $A\subseteq S$ , $A\in F$ if and only if $$\sum_{s\in A}f(s)<\sum_{s\in S\setminus A}f(s).$$

Evan O'Dorney.

A directed graph has each vertex with outdegree 2. Prove that it is possible to split the vertices into 3 sets so that for each vertex $v$ , $v$ is not simultaneously in the same set with both of the vertices that it points to.

David Yang.

Wanda the Worm likes to eat Pascal's triangle. One day, she starts at the top of the triangle and eats $\binom{0}{0}=1$ . Each move, she travels to an adjacent positive integer and eats it, but she can never return to a spot that she has previously eaten. If Wanda can never eat numbers $a,b,c$ such that $a+b=c$ , prove that it is possible for her to eat 100,000 numbers in the first 2011 rows given that she is not restricted to traveling only in the first 2011 rows.

(Here, the $n+1$ st row of Pascal's triangle consists of entries of the form $\binom{n}{k}$ for integers $0\le k\le n$ . Thus, the entry $\binom{n}{k}$ is considered adjacent to the entries $\binom{n-1}{k-1}$ , $\binom{n-1}{k}$ , $\binom{n}{k-1}$ , $\binom{n}{k+1}$ , $\binom{n+1}{k}$ , $\binom{n+1}{k+1}$ .)

Linus Hamilton.

Consider the infinite grid of lattice points in $\mathbb{Z}^3$ . Little D and Big Z play a game, where Little D first loses a shoe on an unmunched point in the grid. Then, Big Z munches a shoe-free plane perpendicular to one of the coordinate axes. They continue to alternate turns in this fashion, with Little D's goal to lose a shoe on each of $n$ consecutive lattice points on a line parallel to one of the coordinate axes. Determine all $n$ for which Little D can accomplish his goal.

David Yang.

Prove there exists a constant $c$ (independent of $n$ ) such that for any graph $G$ with $n>2$ vertices, we can split $G$ into a forest and at most $cf(n)$ disjoint cycles, where

a) $f(n)=n\ln{n}$ ;

b) $f(n)=n$ .

David Yang.

Do there exist positive integers $k$ and $n$ such that for any finite graph $G$ with diameter $k+1$ there exists a set $S$ of at most $n$ vertices such that for any $v\in V(G)\setminus S$ , there exists a vertex $u\in S$ of distance at most $k$ from $v$ ?

David Yang.

Let $T$ be a tree. Prove that there is a constant $c>0$ (independent of $n$ ) such that every graph with $n$ vertices that does not contain a subgraph isomorphic to $T$ has at most $cn$ edges.

David Yang.

Let $ABCD$ be a convex quadrilateral. Let $E,F,G,H$ be points on segments $AB$ , $BC$ , $CD$ , $DA$ , respectively, and let $P$ be the intersection of $EG$ and $FH$ . Given that quadrilaterals $HAEP$ , $EBFP$ , $FCGP$ , $GDHP$ all have inscribed circles, prove that $ABCD$ also has an inscribed circle.

Evan O'Dorney.

Let $\omega,\omega_1,\omega_2$ be three mutually tangent circles such that $\omega_1,\omega_2$ are externally tangent at $P$ , $\omega_1,\omega$ are internally tangent at $A$ , and $\omega,\omega_2$ are internally tangent at $B$ . Let $O,O_1,O_2$ be the centers of $\omega,\omega_1,\omega_2$ , respectively. Given that $X$ is the foot of the perpendicular from $P$ to $AB$ , prove that $\angle{O_1XP}=\angle{O_2XP}$ .

David Yang.

Let $ABC$ be a triangle. Draw circles $\omega_A$ , $\omega_B$ , and $\omega_C$ such that $\omega_A$ is tangent to $AB$ and $AC$ , and $\omega_B$ and $\omega_C$ are defined similarly. Let $P_A$ be the insimilicenter of $\omega_B$ and $\omega_C$ . Define $P_B$ and $P_C$ similarly. Prove that $AP_A$ , $BP_B$ , and $CP_C$ are concurrent.

Tom Lu.

Prove that for any convex pentagon $A_1A_2A_3A_4A_5$ , there exists a unique pair of points $\{P,Q\}$ (possibly with $P=Q$ ) such that $\measuredangle{PA_i A_{i-1}} = \measuredangle{A_{i+1}A_iQ}$ for $1\le i\le 5$ , where indices are taken $\pmod5$ and angles are directed $\pmod\pi$ .

Calvin Deng.

Prove that $n^3-n-3$ is not a perfect square for any integer $n$ .

Calvin Deng.

Let $p\ge5$ be a prime. Show that $$\sum_{k=0}^{(p-1)/2}\binom{p}{k}3^k\equiv 2^p - 1\pmod{p^2}.$$

Victor Wang.

Let $n>1$ be a fixed positive integer, and call an $n$ -tuple $(a_1,a_2,\ldots,a_n)$ of integers greater than $1$ good if and only if $a_i\Big|\left(\frac{a_1a_2\cdots a_n}{a_i}-1\right)$ for $i=1,2,\ldots,n$ . Prove that there are finitely many good $n$ -tuples.

Mitchell Lee.