# [Shortlists & Solutions] Ex-experimental Math Olympiad 2011

### Algebra

1. Let $n$ be a positive integer. There are $n$ soldiers stationed on the $n$th 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?
2. Find all functions $f:\mathbb{R}^+\to\mathbb{R}^+$ such that whenever $a>b>c>d>0$ and $ad=bc$, $f(a+d)+f(b-c)=f(a-d)+f(b+c).$
3. 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$.
4. 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}.$
5. 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}$.
6. 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$.
7. Determine whether there exist two reals $x,y$ and a sequence $\{a_n\}_{n=0}^{\infty}$ of nonzero reals such that $a_{n+2}=xa_{n+1}+ya_n$ for all $n\ge0$ and for every positive real number $r$, there exist positive integers $i,j$ such that $|a_i|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.

### Combinatorics

1. 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).$
2. 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.
3. Wanda the Worm likes to eat Pascal's triangle. One day, she starts at the top of the triangle and eats $\textstyle\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 $\textstyle\binom{n}{k}$ for integers $0\le k\le n$. Thus, the entry $\textstyle\binom{n}{k}$ is considered adjacent to the entries $\textstyle\binom{n-1}{k-1}$, $\textstyle\binom{n-1}{k}$, $\textstyle\binom{n}{k-1}$, $\textstyle\binom{n}{k+1}$, $\textstyle\binom{n+1}{k}$, $\textstyle\binom{n+1}{k+1}$.)
4. 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.
5. 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$.
6. 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$?
7. 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.

### Geometry

1. 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.
2. 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}$.
3. 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.
4. 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},\quad \forall 1\le i\le 5$$ where indices are taken $\pmod5$ and angles are directed $\pmod\pi$.

### Number Theory

1. Prove that $n^3-n-3$ is not a perfect square for any integer $n$.
2. 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}.$
3. 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.
4. Let $p>13$ be a prime of the form $2q+1$, where $q$ is prime. Find the number of ordered pairs of integers $(m,n)$ such that $0\le m<n<p-1$ and $3^m+(-12)^m\equiv 3^n+(-12)^n\pmod{p}.$
 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,...