Let $\, a_1, a_2, a_3, \ldots \,$ be a sequence of positive real numbers satisfying $\, \sum_{j = 1}^n a_j \geq \sqrt {n} \,$ for all $\, n \geq 1$. Prove that, for all $\, n \geq 1, \,$

Solution: Note that if we try to minimize $(a_j)^2$, we would try to make the $a_j$ as equal as possible. However, by the condition given in the problem, this isn't possible, the $a_j$'s have to be an increasing sequence. Thinking of minimizing sequences, we realize that the optimal equation is $a_n = \sqrt{n} - \sqrt{n-1} = 1/(\sqrt{n} + \sqrt{n-1})$. Note that this is strictly greater than $1/(2\sqrt{n})$. So it is greater than the sum of $(1/\sqrt{4n})^2$ over all n from 1 to $\infty$. So the sum we are looking to minimize is strictly greater than the sum of $1/4n$ over all $n$ from 1 to $\infty$, which is what we wanted to do.


Let $\, |U|, \, \sigma(U) \,$ and $\, \pi(U) \,$ denote the number of elements, the sum, and the product, respectively, of a finite set $\, U \,$ of positive integers.  (If $\, U \,$ is the empty set, $\, |U| = 0, \, \sigma(U) = 0, \, \pi(U) = 1$.) Let $\, S \,$ be a finite set of positive integers. As usual, let $\, \binom{n}{k} \,$ denote $\, n! \over k! \, (n-k)!$. Prove that  for all integers $\, m \geq \sigma(S)$.

Solution:
Let, for $|S|\geq k \geq 1$, $A_k$ be a collection of sets such that $\left|\bigcap_{k \in U}A_k\right| = \binom{m- \sigma(U)}{|S|}$. We'll try to find such a collection to prove $\left|\bigcup_{k \in U}A_k\right| = \binom{m}{|S|}-\pi(S)$, since we can use PIE to show that $\left|\bigcup_{k \in U}A_k\right| = \sum_{\emptyset \neq U \subseteq S} (-1)^{|U|+1}\left|\bigcap_{k \in U}A_k\right|$.
Let $Z$ be the set of binary sequences with size $m$, which we'll divide into blocks, in particular, with $S=\{x_1, x_2, ..., x_n\}$, the first block has size $x_1$, the next has size $x_2$ and so on, until we reach $\sigma(S)$, the last few we shall consider as an extra block with size $m-\sigma(S)=R$.
Now we perceive that the $\sigma(U)$ function has the property, that, for $U \subseteq S$, $\sigma(S)-\sigma(U)= \sigma(S\setminus U)$, so, $m- \sigma(U)= \sigma(S\setminus U)+R$.
Let $A_k$ be the number of binary sequences with exactly $|S|$ times $1$, but no appearances of $1$ in the $k$-th block. It is easy to see that $\bigcap_{k \in U}A_k$ is all of the binary sequences with exactly $|S|$ times $1$, but no appearances of $1$ in any of the $k$-th blocks, for $k \in U$. So, we can simply eliminate those blocks, with is equivalent to eliminating $U$ from $S$ , so we are left with $\sigma(S\setminus U)+R$ places to put the $1$'s $|S|$ times. This is $\binom{\sigma(S\setminus U)+R}{|S|}$, and we saw that is is equal to $\binom{m- \sigma(U)}{|S|}$. So, we've found a collection that fits the description.
The number of ways to pick $1$'s $|S|$ times from $m$ places is $\binom{m}{|S|}$. But we don't want for the $1$'s to fill every block, since this is not in the union. We have $\pi(S)$ ways to put the $1$'s $|S|$ times, where each $1$ is in exacty one block ($x_1$ places $\times$ $x_2$ places and so on). So, we find that $| \bigcup_{k \in U}A_k | = \binom{m}{|S|}-\pi(S)$. Which implies, by the Principle of Inclusion Exclusion,
$\binom{m}{|S|}-\pi(S) = \sum_{\emptyset \neq U \subseteq S} (-1)^{|U|+1}\binom{m- \sigma(U)}{|S|} \iff \pi(S) = \sum_{U \subseteq S} (-1)^{|U|}\binom{m- \sigma(U)}{|S|}$


Let $\, p \,$ be an odd prime.  The sequence $(a_n)_{n \geq 0}$ is defined as follows: $\, a_0 = 0,$ $a_1 = 1, \, \ldots, \, a_{p-2} = p-2 \,$ and, for all $\, n \geq p-1, \,$ $\, a_n \,$ is the least positive integer that does not form an arithmetic sequence of length $\, p \,$ with any of the preceding terms. Prove that, for all $\, n, \,$ $\, a_n \,$ is the number obtained by writing $\, n \,$ in base $\, p-1 \,$ and reading the result in base $\, p$.

Solution:
I have to make the assumption that $a_{n+1}>a_{n}$ (without this assumption, I can have the sequence
${1,\cdots,p-2,1,1,\cdots,1,2,1,\cdots}$)
All of the following work are in base $p$ otherwise stated

Lemma 1: for an arithmetic sequence of length $\, p \,$ to exist, there must be a number in the sequence with $(p-1)$ as a digit.
A arithmetic sequence of length $\, p \,$ can be represented as
$a,a+d,a+2d,\cdots,a+(p-1)d$
Since no number repeats, $d\neq0$. Thus, d must have a rightmost non-zero digits, and every term in the sequence $0,d,2d,\cdots,(p-1)d$ have the same number of tailing zeros, let's say there are $x$ tailing zeros.
and let $\dfrac{{0,d,2d,\cdots,(p-1)d}}{p^x}=S$
$S\equiv{1,2,...,(p-1)}(mod)p$ since p is an odd prime and the operation divide by $p^x$ has remove all factors of p in S
Thus, there must be a number with $(p-1)$ as a digit if a length-p sequence exist.

Now, I'm going to prove the statement by strong induction.
I'm going to assume that for all $\, k \,$  less than $\, n \,$
$\, a_k \,$ is the number obtained by writing $\, k \,$ in base $\, p-1 \,$ and reading the result in base $\, p$.
(which is true for $n=p-2$ already)
Or in another word, the terms precede $a_n$ contains all number less than $n$ written in base $\, p-1 \,$ and reading the result in base $\, p$.

Lemma 2: Any term containing the digit $p-1$ will form an arithmetic sequence of length-p with preceding terms
let $p-1$ be the $x^{th}$ digit from the right (There may be more than 1 $(p-1)$)
$a=$ the number with all $(p-1)$ replaced by 0 (e.g: $p=7$, the number$=1361264$, then $a=1301204$)
$d=\sum p^{x-1}$ (for all $x$'s)
$a,a+d,a+2d,\cdots,a+(p-2)d$ all precede $a_n$, thus, $a+(p-1)d$ can't be in the sequence $(a_n)_{n \geq 0}$
Therefore, any term containing the digit $p-1$ can't be a term in the sequence ${(a_n)}_{n\ge0}$

Since the digit $p-1$ won't appear (lemma 2) and as long as it doesn't appear, the arithmetic sequence of length $\, p \,$ won't be formed (lemma 1), and $a_n$ must be as small as possible,
Therefore, for all $\, n, \,$ $\, a_n \,$ is the number obtained by writing $\, n \,$ in base $\, p-1 \,$ and reading the result in base $\, p$.


A calculator is broken so that the only keys that still work are the $\, \sin, \; \cos,$ $\tan, \; \sin^{-1}, \; \cos^{-1}, \,$ and $\, \tan^{-1} \,$ buttons.  The display initially shows 0. Given any positive rational number $\, q, \,$ show that pressing some finite sequence of buttons will yield $\, q$.   Assume that the calculator does real number calculations with infinite precision.  All functions are in terms of radians.

Solution:
We will prove the following, stronger statement :  If $m$ and $n$ are relatively prime nonnegative integers such that $n>0$, then the some finite sequence of buttons will yield $\sqrt{m/n}$.
To prove this statement, we induct strongly on $m+n$.  For our base case, $m+n=1$, we have $n=1$ and $m=0$, and $\sqrt{m/n} = 0$, which is initially shown on the screen.  For the inductive step, we consider separately the cases $m=0$, $0<m\le n$, and $n<m$.
If $m=0$, then $n=1$, and we have the base case.
If $0< m \le n$, then by inductive hypothesis, $\sqrt{(n-m)/m}$ can be obtained in finitely many steps; then so can
If $n<m$, then by the previous case, $\sqrt{n/m}$ can be obtained in finitely many steps.  Since $\cos \tan^{-1} \sqrt{n/m} = \sin \tan^{-1} \sqrt{m/n}$, it follows that

can be obtained in finitely many steps.  Thus the induction is complete.  $\blacksquare$


Given a nonisosceles, nonright triangle $ABC,$ let $O$ denote the center of its circumscribed circle, and let $A_1, \, B_1,$ and $C_1$ be the midpoints of sides $BC, \, CA,$ and $AB,$ respectively.  Point $A_2$ is located on the ray $OA_1$ so that $\triangle OAA_1$ is similar to $\triangle OA_2A$.  Points $B_2$ and $C_2$ on rays $OB_1$ and $OC_1,$ respectively, are defined similarly.  Prove that lines $AA_2, \, BB_2,$ and $CC_2$ are concurrent, i.e. these three lines intersect at a point.

Solution:
LEMMA 1:  In $\triangle ABC$ with circumcenter $O$, $\angle OAC = 90 - \angle B$.
PROOF of Lemma 1: The arc $AC$ equals $2\angle B$ which equals $\angle AOC$.  Since $\triangle AOC$ is isosceles we have that $\angle OAC = \angle OCA = 90 - \angle B$.
QED
Define $H \in BC$ s.t. $AH \perp BC$.  Since $OA_1 \perp BC$, $AH \parallel OA_1$.  Let $\angle AA_2O = \angle A_1AO = x$ and $\angle AA_1O = \angle A_2AO = y$.  Since we have $AH \parallel OA_1$, we have that $\angle HAA_2 = x$.  Also, we have that $\angle A_2AA_1 = y-x$.  Furthermore, $\angle BAH = 90 - \angle B = \angle OAC$, by lemma 1.  Therefore, $\angle A_1AC = 90 - \angle B + x = \angle BAA_2$.  Since $A_1$ is the midpoint of $BC$, $AA_1$ is the median.  However $\angle A_1AC =  \angle BAA_2$ tells us that $AA_2$ is just $AA_1$ reflected across the internal angle bisector of $A$.  By definition, $AA_2$ is the $A$-symmedian.  Likewise, $BB_2$ is the $B$-symmedian and $CC_2$ is the $C$-symmedian.  Since the symmedians concur at the symmedian point, we are done.
QED


Suppose $q_1,q_2,...$ is an infinite sequence of integers satisfying the following two conditions:
(a) $m - n$ divides $q_m - q_n$ for $m>n \geq 0$
(b) There is a polynomial $P$ such that $|q_n|<P(n)$ for all $n$.
Prove that there is a polynomial $Q$ such that $q_n = Q(n)$ for each $n$.

Solution:
Step 1: Suppose $P$ has degree $d$. Let $Q$ be the polynomial of degree at most $d$ with $Q(x)=q_x$ for $0\leq x\leq d$. Since the $q_x$ are all integers, $Q$ has rational coefficients, and there exists $k$ so that $kQ$ has integer coefficients. Then $m-n|kQ(m)-kQ(n)$ for all $m,n\in \mathbb N_0$.
Step 2: We show that $Q$ is the desired polynomial.
Let $x>n$ be given. Now

Since $kQ(x)$ satisfies these relations as well, and $kq_m=kQ(m)$,

and hence

Now

so by induction $\text{lcm}(x,x-1,\ldots, x-d)\geq \frac{x(x-1)\cdots (x-d)}{d!(d-1)!\cdots 1!}$. Since $P(x), Q(x)$ have degree $d$, for large enough $x$ (say $x>L$) we have $\left|Q(x)\pm\frac{x(x-1)\cdots (x-d)}{kd!(d-1)!\cdots 1!}\right|>P(x)$. By (1) $kq_x$ must differ by a multiple of $\text{lcm}(x,x-1,\ldots, x-d)$ from $kQ(x)$; hence $q_x$ must differ by a multiple of $\frac{x(x-1)\cdots (x-d)}{kd!(d-1)!\cdots 1!}$ from $Q(x)$, and for $x>L$ we must have $q_x=Q(x)$.
Now for any $y$ we have $kQ(y)\equiv kQ(x)\equiv kq_x \equiv kq_y\pmod{x-y}$ for any $x>L$. Since $x-y$ can be arbitrarily large, we must have $Q(y)=q_y$, as needed.


Suppose that in a certain society, each pair of persons can be classified as either amicable or hostile. We shall say that each member of an amicable pair is a friend of the other, and each member of a hostile pair is a  foe of the other.  Suppose that the society has $\, n \,$ persons and $\, q \,$ amicable pairs, and that for every set of three persons, at least one pair is hostile.  Prove that there is at least one member of the society whose foes include $\, q(1 - 4q/n^2) \,$ or fewer amicable pairs.

Solution:
Consider the graph with two people joined if they are friends.
For each person $X$, let $A(X)$ be the set of its friends and $B(X)$ the set of its foes. Note that any edge goes either: from $X$ to $A(X)$ (type 1), from $A(X)$ to $B(X)$ (type 2) or from a point of $B(X)$ to another (type 3), but there's no edge joining two points of $A(X)$ (since they would form a triangle with $X$). Let the number of type 1, type 2, type 3 edges of $X$ be $x_1, x_2, x_3$ respectively, so that $x_1$ is the degree of $X$ and we want to show that for some $X$, we have $x_3 \leq q(1-4q/n^2)$.
Since each edge is of one of those types, we have $x_1+x_2+x_3=q$. Thus

That is, what we want is equivalent to proving that for some vertex $X$, the set of edges touching either $X$ or a vertex joined to $X$ is at least $4q^2/n^2$. Obviously now we'll sum $x_1+x_2$ over all vertices $X$. In the resulting sum, an edge joining $X, Y$ is counted once for each edge that $X, Y$ have, that is, it is counted $D(X)+D(Y)$ times, where $D(X)=x_1$ is the degree of $X$. Thus each vertex $X$ contributes to the overall sum with $D(X)$ for each edge it has, and since it has $D(X)$ edges, it contributes with $D(X)^2$. Thus the considered sum is equal to

(That's Cauchy.) Since we are summing over $n$ vertices, one of the summands is at least $4q^2/n^2$ by pigeonhole, which is what we wanted to prove.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Prove that the average of the numbers $n\sin n^{\circ}\; (n = 2,4,6,\ldots,180)$ is $\cot 1^\circ$.

First, as $180\sin{180^\circ}=0,$ we omit that term. Now, we multiply by $\sin 1^\circ$ to get, after using product to sum, $(\cos 1^\circ-\cos 3^\circ)+2(\cos 3^\circ-\cos 5^\circ)+\cdots +89(\cos 177^\circ-\cos 179^\circ)$.
This simplifies to $\cos 1^\circ+\cos 3^\circ +\cos 5^\circ+\cos 7^\circ+...+\cos 177^\circ-89\cos 179^\circ$. Since $\cos x=-\cos(180-x),$ this simplifies to $90\cos 1^\circ$. We multiplied by $\sin 1^\circ$ in the beginning, so we must divide by it now, and thus the sum is just $90\cot 1^\circ$, so the average is $\cot 1^\circ$, as desired.
$\Box$

Notice that for every $n\sin n^\circ$ there exists a corresponding pair term $(180^\circ - n)\sin{180^\circ - n} = (180^\circ - n)\sin n^\circ$, for $n$ not $90^\circ$. Pairing gives the sum of all $n\sin n^\circ$ terms to be $90(\sin 2^\circ + \sin 4^\circ + ... + \sin 178^\circ)$, and thus the average is  We need to show that $S = \cot 1^\circ$. Multiplying (*) by $2\sin 1^\circ$ and using sum-to-product and telescoping gives $2\sin 1^\circ S = \cos 1^\circ - \cos 179^\circ = 2\cos 1^\circ$. Thus, $S = \frac{\cos 1^\circ}{\sin 1^\circ} = \cot 1^\circ$, as desired.
$\Box$

We know that the average of a list of numbers is the sum of all the terms, divided by the number of terms. So we will set up an average. This average will average to $\cot 1^\circ$. So we can set it equal to $\frac{\cos 1^\circ}{\sin 1^\circ}$. Doing so, gives us
We should try to simplify the numerator as it looks pretty messy.
Now we know that $\sin x = \sin (180-x)$, so maybe we can use this to clear things up a bit. Applying this to $(1)$ gives us
Now, we know that $\sin 2^\circ = \sin 178^\circ$, and $\sin 4^\circ = \sin 176^\circ$ and so on. We also know that $\sin 0^\circ = 0$, so we can omit the last term. Also, we know that $\sin 90 = 1$. Thus $90 \sin 90 = 90$. So we will use all these when we further simplify. Another thing that we can simplify is to notice that when we reach the term $92\sin 88^\circ$, we can rewrite it as $92\sin 92^\circ$. Thus we can rewrite everything in the form $x\sin y^\circ$ as $x \sin x^\circ$, starting with the term $92\sin 88^\circ$, then $94\sin 86^\circ$, and so on.
Thus we can further simplify our equation. Doing so, gives us
Then, to make things easier, we can rewrite all the numbers with degrees less than $90^\circ$ and combine like terms. Doing so gives us
Now we can factor out $180$ to get
Then we can simplify it by getting rid of the denominator to get to
Now we notice that we can multiply both sides by $\sin 1^\circ$. Doing so gives us
Now, simplifying $\sin 2^\circ+ \sin 4^\circ + \sin 6^\circ + \sin 8^\circ + \sin 10^\circ ... + \sin 88^\circ$ doesn't look too promising. So maybe if we expand again, we can maybe somehow use our product to sum formulas.
Doing so, gives us
Now we can use our product of sines to sum formula and see if we can find a pattern.
We will start with expanding $(\sin 1^\circ)(2 \sin 2^\circ)$. Because the format of our formula for the product of sines is $\sin \alpha + \sin \beta$, we can factor out the $2$ and find the product, then multiply by $2$. So, we are at $2(\sin 1^\circ)(\sin 2^\circ)$. Our formula for the product of sines is $\sin \alpha + \sin \beta = \frac{1}{2}[\cos(\alpha - \beta) - \cos(\alpha + \beta)]$. Plugging in our values into the formula and simplifying gives us $2\left(\frac{1}{2}(\cos 1^\circ - \cos 3^\circ)\right)$. We know that $2\left(\frac{1}{2}\right)$ will just cancel out to $1$. So we are left with $\cos 1^\circ - \cos 3^\circ$. $(9)$
Next we expand $(\sin 1^\circ)(2\sin 4^\circ)$. We use the same steps or strategy as we did above and get $\cos 3^\circ - \cos 5^\circ$. $(10)$
We may be noticing a pattern. Just to make sure it is true, we will expand $(\sin 1^\circ)(2\sin 6^\circ)$. When we expand this using the same strategy above, we get $\cos 5^\circ - \cos 7^\circ$. $(11)$ So our pattern is that $(\sin 1^\circ)(2\sin \mu^\circ) = \cos (\mu-1)^\circ - \cos (\mu+1)^\circ. (12)$
Now we notice that when we add $(9)$ and $(10)$, $-\cos 3^\circ$ and $+\cos 3^\circ$ cancel themselves out to just $\cos 1^\circ - \cos 5^\circ$. Then, when we add $(11)$ to it, $+ \cos 5^\circ$ and $- \cos 5^\circ$ also cancel themselves out.
Now, we need to figure out when we should stop canceling out. We can use formula $(12)$ and replace $88$ with $\mu$ since $88$ is the last one in $(8)$. Applying this formula and simplifying gives us $\cos 87^\circ - \cos 89$, so the last term would be $- \cos 89$.
Thus we know that everything we cancel themselves out except the first and the last term. So, we are left with
Now we notice that we have $\cos 1^\circ$ on both sides. Thus we can subtract $\cos 1^\circ$ from both sides to get $- \cos 89^\circ + \sin 1^\circ = 0$. Now we can add $\cos 89^\circ$ to both sides and get $\sin 1^\circ = \cos 89^\circ$. Now we also know that $\sin (\omega)^\circ = \cos(90-\omega)$. Thus we know that $\sin 1^\circ = \cos 89^\circ$. Hence, our proof is complete. $\square$


For any nonempty set $S$ of real numbers, let $\sigma(S)$ denote the sum of the elements of $S$. Given a set $A$ of $n$ positive integers, consider the collection of all distinct sums $\sigma(S)$ as $S$ ranges over the nonempty subsets of $A$. Prove that this collection of sums can be partitioned into $n$ classes so that in each class, the ratio of the largest sum to the smallest sum does not exceed 2.

Let set $A$ consist of the integers $a_1\le a_2\le a_3\le\dots\le a_n$. For $k\ge 2$, call $a_k$ greedy if $\sum_{i=1}^{k-1}a_i < a_k$. Also call $a_1$ greedy. Now put all elements of $A$ into groups of consecutive terms in such a way that each group $G$ begins with a greedy term, call it $a_p$, and ends on the term $a_{q-1}$ just before the next greedy term after $a_p$. (If $a_p$ is the last greedy term, let $q-1=n$.) We introduce some more terminology. A sum $\sigma(S)$ is said to "belong to" a group $G$ if $\max(S)\in G$. Denote by $\mathcal{S}(G)$ the set of all sums belonging to $G$.
We now show that we can divide $\mathcal{S}(G)$ into $|G|$ (the cardinality of $G$) classes in such a way that the maximum and minimum sum belonging to each class differ by no more than a factor of 2. Using the previous notation, we first prove that $\frac{\max{\mathcal{S}(G)}}{\min{\mathcal{S}(G)}}< 2^{|G|}=2^{q-p}$. Note that  and  Taking note of that fact that $a_{p+1},a_{p+2},\dots,a_{q-1}$ are not greedy numbers, we write:

where the inequalities after the ellipses result from the fact that $a_p$ is a greedy number (which implies by definition that $\sum_{i=1}^{p-1}a_i<a_p$). This proves the desired inequality. Now we can prove the result in bold above. Divide $\mathcal{S}(G)$ into $|G|=q-p$ classes by taking those terms in $[a_p,2a_p)$ and placing them in the first class, taking those terms in $[2a_p,2^2a_p)$ and placing them in another, and so on, until we reach $[2^{q-p-1}a_p,2^{q-p}a_p)$. The inequality we proved above shows that all of the sums in $\mathcal{S}(G)$ will fall in one of these classes, as the intervals into which the classes fall form a continuous range bounded by $\min\mathcal{S}(G)=a_p$ on the bottom and $2^{q-p}a_p>\max\mathcal{S}(G)$ on the top. This proves the result in bold.
However, that clearly implies the desired conclusion, as every sum belongs to a group, and every sum belonging to a group is a member of a class. Moreover, there will be precisely $n$ classes, because every term $a_i$ belongs to a group and for each group $G$, there are as many classes for $\mathcal{S}(G)$ as there are terms in $G$.

We proceed to solve this problem by induction. Our base case is when $A$ has 1 integer - there is 1 class: itself.
Let $A$ now have $n$ elements, and assume it works for this case. We add $k$, another element, to the set. WLOG, let $k$ be the maximum element. Note that $\sigma(A)$ has to be the maximum element of a class.
We always get a new class that works: $\sigma(A+\{k\})$ being the maximum element. This way all elements including $k$ will be in that class if $k>\sigma(A)$. When $k<\sigma(A)$ it also works since $k$ must be the maximum element from our WLOG condition above, so our induction step is done.


Let $ABC$ be a triangle. Prove that there is a line $l$ (in the plane of triangle $ABC$) such that the intersection of the interior of triangle $ABC$ and the interior of its reflection $A'B'C'$ in $l$ has area more than $\frac{2}{3}$ the area of triangle $ABC$.

Solution:
Let the triangle be $ABC$. Assume $A$ is the largest angle. Let $AD$ be the altitude. Assume $AB \le AC$, so that $BD \le BC/2$. If $BD > \frac{BC}{3}$, then reflect in $AD$. If $B'$ is the reflection of $B$, then $B'D = BD$ and the intersection of the two triangles is just $ABB'$. But $BB' = 2BD > \frac{2}{3} BC$, so $ABB'$ has more than $\frac{2}{3}$ the area of $ABC$.
If $BD < BC/3$, then reflect in the angle bisector of $C$. The reflection of $A'$ is a point on the segment $BD$ and not $D$. (It lies on the line $BC$ because we are reflecting in the angle bisector. $A'C > DC$ because $\angle{CAD} < \angle{CDA} = 90^{\circ}$. Finally, $A'C \le BC$ because we assumed $\angle B$ does not exceed $\angle A$). The intersection is at least $AA'C$. But  $\frac{[AA'C]}{[ABC]} = \frac{CA'}{CB} > CD/CB \ge 2/3$.


An $n$-term sequence $(x_1, x_2, \ldots, x_n)$ in which each term is either 0 or 1 is called a binary sequence of length $n$. Let $a_n$ be the number of binary sequences of length n containing no three consecutive terms equal to 0, 1, 0 in that order. Let $b_n$ be the number of binary sequences of length $n$ that contain no four consecutive terms equal to 0, 0, 1, 1 or 1, 1, 0, 0 in that order. Prove that $b_{n+1} = 2a_n$ for all positive integers $n$.
(proposed by Kiran Kedlaya)

Solution:
Given any binary sequence $B=(b_1,b_2,b_3,\dots,b_k)$, define $f(B)=(|b_2-b_1|,|b_3-b_2|,\dots,|b_k-b_{k-1}|)$. The operator $f$ basically takes pairs of consecutive terms and returns 0 if the terms are the same and 1 otherwise. Note that for every sequence $S$ of length $n$ there exist exactly two binary sequences $B$ of length $n+1$ such that $f(B)=S$.
If $f(B)$ does not contain the string 0, 1, 0, $B$ cannot contain either of the strings 0, 0, 1, 1 or 1, 1, 0, 0. Conversely, if $B$ does not contain the sequences 0, 0, 1, 1 or 1, 1, 0, 0, $f(B)$ cannot contain 0, 1, 0. There are $a_n$ such $f(B)$ and $b_{n+1}$ such $B$. Since each $S$ corresponds with two $B$, there are twice as many such $B$ as such $S$; thus, $b_{n+1}=2a_n$.


Let $ABC$ be a triangle, and $M$ an interior point such that $\angle MAB=10^\circ$, $\angle MBA=20^\circ$ , $\angle MAC= 40^\circ$ and $\angle MCA=30^\circ$. Prove that the triangle is isosceles.

Clearly, $\angle AMB = 150^\circ$ and $\angle AMC = 110^\circ$. Now by the Law of Sines on triangles $ABM$ and $ACM$, we have  and  Combining these equations gives us  Without loss of generality, let $AB = \sin 150^\circ \sin 30^\circ = \frac{1}{4}$ and $AC = \sin 20^\circ \sin 110^\circ$. Then by the Law of Cosines, we have

Thus, $AB = BC$, our desired conclusion.

By the law of sines, $\frac{BM}{sin(10^\circ)}=\frac{AM}{sin(20^\circ)}$ and $\frac{CM}{sin(40^\circ)}=\frac{AM}{sin(30^\circ)}$, so $\frac{BM}{CM}=\frac{sin(10^\circ)sin(30^\circ)}{sin(20^\circ)sin(40^\circ)}$.
Let $\angle MBC=x$. Then, $\angle MCB=80^\circ-x$. By the law of sines, $\frac{BM}{CM}=\frac{sin(80^\circ-x)}{sin(x)}$.
Combining, we have $\frac{sin(80^\circ-x)}{sin(x)}=\frac{sin(10^\circ)sin(30^\circ)}{sin(20^\circ)sin(40^\circ)}$. From here, we can use the given trigonometric identities at each step:
The only acute angle satisfying this equality is $x=60^\circ$. Therefore, $\angle ACB=80^\circ-x+30^\circ=50^\circ$ and $\angle BAC=10^\circ+40^\circ=50^\circ$. Thus, $\triangle ABC$ is isosceles.

If $\angle{MBC} = x$ then by Angle Sum in a Triangle we have $\angle{MCB} = 80^\circ - x$. By Trig Ceva we have

Because $\dfrac{\sin x}{\sin (80^\circ - x)}$ is monotonic increasing over $(0, \dfrac{\pi}{2})$, there is only one solution $0 \le x \le \dfrac{\pi}{2}$ to the equation. We claim it is $x = 60^\circ$, which will make $ABC$ isosceles with $\angle{A} = \angle{C}$.
Notice that

as desired.


Determine (with proof) whether there is a subset $X$ of the integers with the following property: for any integer $n$ there is exactly one solution of $a + 2b = n$ with $a,b \in X$.

Solution:
Start with an incomplete subset $S = (S_1, S_2, S_3, ... S_m)$, such that for any integer n, there is exactly zero or one solutions to $a + 2b = n$ with $a,b \in S$. Let $N$ be the smallest integer such that for any $S_i$, $|S_i| < N$. Note that $|S_i+2S_j| < 3N$ for any $S_i$ and $S_j$
Suppose $M$ is the smallest non-negative integer without a solution in $S$ yet. Clearly, $0 \le M \le 3N$. Generate $S_{m+1}$ and $S_{m+2}$ such that $S_{m+1} = -10N - M$, and $S_{m+2} = 5N + M$. Thus, we now have the solution $S_{m+1}+2S_{m+2} = M$.
Note: The values 10 and 5 can be replaced by any sufficiently large values such that the first is twice the second.
Now, we must prove that the addition of these two terms to $S$ does not result in an integer n that has two solutions. Of course, $S_{m+1} + 2S_{m+2} = M$ which previously had no solutions. Furthermore, $S_{m+1} + 2S_{m+2} = -15N - M$.
Since all of these sums (other than $M$) are either greater than $3N$ or less than $-3N$, they are all sums that previously had no solutions. Furthermore, none of these sums are duplicated, as sums of different forms are contained in disjoint ranges of integers.
Thus, we have proved that we can generate a subset $S$ such that all non-negative integers n have a unique solution $a + 2b = n$.
For negative integers M that have no solutions in $S$ a similar proof holds, but instead generating the terms $S_{m+1} = 10N - M$ and $S_{m+2} = -5N + M$.
For any integer M that currently has no solution in S, we can always add two terms $S_{m+1}$ and $S_{m+2}$ such that $S_{m+1} + 2S_{m+2} = M$ that do not result in duplicated sums.
Thus, there does exist a subset $X$ of the integers such that for any integer $n$ there is exactly one solution to $a + 2b = n$ with $a, b \in X$.


Let $p_1,p_2,p_3,...$ be the prime numbers listed in increasing order, and let $x_0$ be a real number between $0$ and $1$. For positive integer $k$, define
$x_{k}=\begin{cases}0&\text{ if }x_{k-1}=0\\ \left\{\frac{p_{k}}{x_{k-1}}\right\}&\text{ if }x_{k-1}\ne0\end{cases}$
where $\{x\}$ denotes the fractional part of $x$. (The fractional part of $x$ is given by $x-\lfloor{x}\rfloor$ where $\lfloor{x}\rfloor$ is the greatest integer less than or equal to $x$.) Find, with proof, all $x_0$ satisfying $0<x_0<1$ for which the sequence $x_0,x_1,x_2,...$ eventually becomes $0$.

Solution:
All rational numbers between 0 and 1 inclusive will eventually yield some $x_k = 0$. To begin, note that by definition, all rational numbers can be written as a quotient of coprime integers. Let $x_0 = \frac{m}{n}$, where $m,n$ are coprime positive integers. Since $0<x_0<1$, $0<m<n$. Now  From this, we can see that applying the iterative process will decrease the value of the denominator, since $m<n$. Moreover, the numerator is always smaller than the denominator, thanks to the fractional part operator. So we have a strictly decreasing denominator that bounds the numerator. Thus, the numerator will eventually become 0.
On the other hand, if $x_0$ is irrational, then a simple induction will show that $x_k$ will always be irrational. Indeed, the base case has been established, and, if $x_k$ is irrational, then $\dfrac{p_{k+1}}{x_k}$ must be too, and likewise for its fractional portion, which differs from it by an integer. Hence $x_{k+1}$ is irrational, completing the proof.


$\triangle ABC$ is a triangle. Take points $D, E, F$ on the perpendicular bisectors of $BC, CA, AB$ respectively. Show that the lines through $A, B, C$ perpendicular to $EF, FD, DE$ respectively are concurrent.

Let the perpendicular from A meet FE at A'. Define B' and C' similiarly. By Carnot's Theorem, The three lines are concurrent if
But this is clearly true, since D lies on the perpendicular bisector of BC, BD = DC.
QED

We split this into two cases:
Case 1: $D,E,F$ are non-collinear
Observe that since $D,E,F$ lie on perpendicular bisectors, then we get that $DC=DB$, $EC=EA$, and $FA=FB$. This motivates us to construct a circle $\omega_1$ centered at $D$ with radius $DC$, and similarly construct $\omega_2$ and $\omega_3$ respectively for $E$ and $F$.
Now, clearly $\omega_1$ and $\omega_2$ intersect at $C$ and some other point. Now, we know that $DE$ is the line containing the two centers. So, the line perpendicular to $DE$ and passing through $C$ must be the radical axis of $\omega_1$ and $\omega_2$, which is exactly the line that the problem describes! We do this similarly for the others pairs of circles.
Now by the radical lemma, the pairwise radical axes of $\omega_1,\omega_2,\omega_3$ are concurrent, as desired, and they intersect at the radical center.
Case 2: $D,E,F$ are collinear
Now, we are drawing perpendicular lines from $A$, $B$, and $C$ onto the single line $DEF$. Clearly, these lines are parallel and concur at the point of infinity.


Prove that for any integer $n$, there exists a unique polynomial $Q(x)$ with coefficients in $\{0,1,...,9\}$ such that $Q(-2)=Q(-5)=n$.

Solution:
The problem implies that $Q(x) = (x+2)(x+5) \cdot H_y(x) + n$. We define $H_y(x) = a_0 + a_1x + ... + a_nx^n$. Then, after expanding, the coefficient of $x^k$ is $10a_k + 7a_{k-1} + a_{k-2}$ where $2 \le k \le n$. The constant term is $10a_0 + n$. Since this has to be within the set ${0,1,...,9}$, $a_0$ must be unique according to $n$. The linear term is determined by $10a_1 + 7a_0$, which also must be within the set ${0,1,...,9}$. Since $a_0$ is determined uniquely by $n$, in order to keep the linear coefficient in the set ${0,1,...,9}$, $a_1$ is also determined uniquely. With $a_0$ and $a_1$ determined uniquely, we move on to the general coefficient.
Note that $10a_k + 7a_{k-1} + a_{k-2}$ is in the set ${0,1,...,9}$. We define $J_h(x)$ to be a function determining the remainder when $x$ is divided by $10$. Thus, for all $x$, $0 \le J_h(x) \le 9$. Note also that $J_h(10a_k + 7a_{k-1} + a_{k-2}) = 10a_k + 7a_{k-1} + a_{k-2}$, since $10a_k + 7a_{k-1} + a_{k-2}$ is in the range of $J_h(x)$. Therefore, $J_h(7a_{k-1} + a_{k-2}) = 10a_k + 7a_{k-1} + a_{k-2}$, which results in $a_k = \lfloor \frac{7a_{k-1} + a_{k-2}}{10} \rfloor$ for all $2 \le k \le n$. Thus, $a_k$ is determined uniquely, since all coefficients $a_i$ where $0 \le i < k$ are uniquely determined, which in turn determines a unique polynomial $Q(x)$.


To clip a convex $n$-gon means to choose a pair of consecutive sides $AB, BC$ and to replace them by three segments $AM, MN,$ and $NC,$ where $M$ is the midpoint of $AB$ and $N$ is the midpoint of $BC$. In other words, one cuts off the triangle $MBN$ to obtain a convex $(n+1)$-gon. A regular hexagon $P_6$ of area $1$ is clipped to obtain a heptagon $P_7$. Then $P_7$ is clipped (in one of the seven possible ways) to obtain an octagon $P_8$, and so on. Prove that no matter how the clippings are done, the area of $P_n$ is greater than $\frac{1}{3}$, for all $n\ge6$.

Solution:
$\textbf{Claim:}$  It is impossible to choose two non-adjacent sides and clip a whole part of it off.
$\textbf{Proof:}$  If you clip adjacent sides, you can cut off at most up to the blue lines; Clipping more is impossible due to the degrees getting larger and larger and more and more circular.
Thus, after infinitely many clips, the hexagon bounded by the blue lines is left, so after finitely many clips, the area left is more than that hexagon.
The side length of that hexagon is $\frac{\sqrt{3}}{3}$ of the large one, because of 30-30-120 triangles. Thus, the area is $\frac13$ of the larger one, so we are done.


Prove that, for all positive real numbers $a, b, c,$
$\frac{1}{a^3+b^3+abc}+\frac{1}{b^3+c^3+abc}+\frac{1}{a^3+c^3+abc} \le \frac{1}{abc}$.

Because the inequality is homogenous (i.e. $(a, b, c)$ can be replaced with $(ka, kb, kc)$ without changing the inequality other than by a factor of $k^n$ for some $n$), without loss of generality, let $abc = 1$.
Lemma:

Proof: Rearranging gives $(a^3 + b^3) c + c \ge a + b + c$, which is a simple consequence of $a^3 + b^3 = (a + b)(a^2 - ab + b^2)$ and
Thus, by $abc = 1$:

Rearranging the AM-HM inequality, we get $\frac{1}{x}+\frac{1}{y}+\frac{1}{z} \le \frac{9}{x+y+z}$. Letting $x=a^{3}+b^{3}+abc$, $y=b^{3}+c^{3}+abc$, and $z=c^{3}+a^{3}+abc$, we get  By AM-GM on $a^{3}$, $b^{3}$, and $c^{3}$, we have  So, $\frac{1}{a^{3}+b^{3}+abc}+\frac{1}{b^{3}+c^{3}+abc}+\frac{1}{c^{3}+a^{3}+abc} \le \frac{1}{abc}$.
-Tigerzhang
$\textbf{WARNING:}$
This solution doesn’t work because $(x+y+z)\left(\frac{1}{x}+\frac{1}{y}+\frac{1}{z}\right)\geq 9$, so $\frac{1}{x}+\frac{1}{y}+\frac{1}{z}\geq \frac{9}{x+y+z}$

If we multiply each side by $abc$, we get that we must just prove that  If we divide our LHS equation, we get that   Make the astute observation that by Titu's Lemma,   Therefore:  If we expand it out, we get that  Since our original equation is less than this, we get that
-KEVIN_LIU


Suppose the sequence of nonnegative integers $a_1,a_2,...,a_{1997}$ satisfies
$a_i+a_j \le a_{i+j} \le a_i+a_j+1$
for all $i, j \ge 1$ with $i+j \le 1997$. Show that there exists a real number $x$ such that $a_n=\lfloor{nx}\rfloor$ (the greatest integer $\le nx$) for all $1 \le n \le 1997$.

Solution:
Given nonnegative integers $a_1,a_2,\dots, a_{1997}$ satisfying the given inequalities, let $I_n$ be the set of all $x$ such that $a_n=\lfloor nx\rfloor$. Therefore,

We can rewrite this as

So we know that each $I_n$ is an interval. We start by proving that if $n$ and $k$ are positive integers, then $I_n\cap I_{k}\ne \emptyset$. To prove this, we need the following lemma.
Lemma 1: If $n$ and $k$ are positive integers, then
Proof: We prove this by induction. If $k=1$, then we wish to show that $na_1< a_n+1$. By the given lower bound, we know that

Therefore, $na_1\le a_n<a_n+1$, so the hypothesis is true for $k=1$. If $n=1$, then we wish to prove that $a_k < k(a_1+1)$. By the given upper bound, we know that

Therefore, $a_k<ka_1+k=k(a_1+1)$, so the hypothesis is true for $n=1$.
Now suppose that (2) holds for all $k,n<j$. If $k=n=j$, then (2) is equivalent to $0<j$, which is obviously true. If $n=j>k$, then by the division algorithm, we can write $n=qk+r$ for nonnegative integers $q$ and $r$ with $0\le r<k$. Thus by applying the lower bound repeatedly (with one of the indices equal to $1$), we find

But then as $k,r<j$, we can apply the inductive hypothesis with $n=r$ and $k=k$ to find $k(a_r+1)> ra_k$. Substituting this into (3), we find

This proves the hypothesis for $n=j>k$.
Suppose that $k=j>n$. Then by the division algorithm, we can write $k=qn+r$ for nonnegative integers $q$ and $r$ with $0\le r<n$. Then by applying the upper bound repeatedly (with one of the indices equal to $1$), we find

But as $n,r<j$, we can apply the inductive hypothesis with $n=n$ and $k=r$, finding that $na_r< r(a_n+1)$. Subsituting this into (4), we find

This proves the hypothesis for $k=j>n$.
Therefore, if the hypothesis is true for all $k,n<j$, then it must be true for all $k,n\le j$. Hence by induction, it must be true for all positive integers $k$ and $n$. $\hfill\ensuremath{\square}$
Now suppose for the sake of contradiction that $I_n$ and $I_k$ are disjoint intervals. Without loss of generality, we may assume that $I_n$ precedes $I_k$ on the number line. Hence the upper bound of $I_n$ is less than or equal to the minimum value of $I_k$, or rather

This simplifies to $na_k\ge k(a_n+1)$. But this contradicts the statement of Lemma 1. Therefore, $I_k\cap I_n\ne \emptyset$.
Now we claim that $I_1\cap I_2\cap \cdots \cap I_{1997}\ne \emptyset$. We prove this by induction. By the above, we know that $I_1\cap I_2\ne \emptyset$. Now suppose that $I_1\cap I_2\cap\cdots\cap I_k\ne \emptyset$. The intersection of two overlapping intervals of the form $[a,b)$ and $[c,d)$ is an interval of the form $[e,f)$, where $e=\max\{a,c\}$ and $f=\min\{b,d\}$. Therefore, by induction, we know that if the intersection of $k$ overlapping intervals is nonempty, then it must also be an interval, say

If $I_{k+1}$ does not intersect $[x_k,y_k)$, then as an interval, it must appear either completely before $x_k$ or completely after $y_k$.  If $I_{k+1}$ appears completely before $x_k$, then it has a nonempty intersection with each of $I_1, I_2, \dots, I_k$. But we also know that $x_k$ is a lower bound of one of the intervals, hence $I_{k+1}$ cannot intersect that interval, a contradiction. A similar contradiction arises if $I_{k+1}$ appears completely after $y_k$. Therefore,

Thus by induction, $I_1\cap I_2\cap\cdots\cap I_{1997}\ne \emptyset$. So let $x\in I_1\cap I_2\cap\cdots\cap I_{1997}$. Then by the definition of $I_n$, we know that $a_n=\lfloor nx\rfloor$ for all $1\le n\le 1997$, and we are done.


Suppose that the set $\{1,2,\cdots, 1998\}$ has been partitioned into disjoint pairs $\{a_i,b_i\}$ ($1\leq i\leq 999$) so that for all $i$, $|a_i-b_i|$ equals $1$ or $6$. Prove that the sum  ends in the digit $9$.

Solution:
Notice that $|a_i - b_i| \equiv 1 \pmod 5$, so $S=|a_1-b_1|+|a_2-b_2|+\cdots +|a_{999}-b_{999}| \equiv 1+1+\cdots + 1 \equiv 999 \equiv 4 \bmod{5}$.
Also, for integers $M, N$ we have $|M-N| \equiv M-N \equiv M+N \bmod{2}$.
Thus, we also have $S \equiv a_1+b_1+a_2+b_2+\cdots +a_{999}+b_{999} \equiv 1+2+ \cdots +1998 \equiv 999*1999 \equiv 1 \bmod{2}$ also, so by the Chinese Remainder Theorem $S \equiv 9\bmod{10}$. Thus, $S$ ends in the digit 9, as desired.


Let ${\cal C}_1$ and ${\cal C}_2$ be  concentric circles, with ${\cal C}_2$ in the interior of  ${\cal C}_1$. From a point $A$ on ${\cal C}_1$ one draws the tangent $AB$ to ${\cal C}_2$ ($B\in {\cal C}_2$). Let $C$ be the second point of intersection of $AB$ and ${\cal C}_1$, and let $D$ be the midpoint of $AB$. A line passing through $A$ intersects ${\cal C}_2$ at $E$ and $F$ in such a way that the perpendicular  bisectors of $DE$ and $CF$ intersect at a point $M$ on $AB$. Find, with proof,  the ratio $AM/MC$.

Solution:
First, $AD=\frac{AB}{2}=\frac{AC}{4}$. Because $E$,$F$ and $B$ all lie on a circle, $AE \cdot AF=AB \cdot AB=\frac{AB}{2} \cdot 2AB=AD \cdot AC$. Therefore, $\triangle ACF \sim \triangle AED$, so $\angle ACF = \angle AED$. Thus, quadrilateral $CFED$ is cyclic, and $M$ must be the center of the circumcircle of $CFED$, which implies that $MC=\frac{CD}{2}$. Putting it all together,
$\frac{AM}{MC}=\frac{AC-MC}{MC}=\frac{AC-\frac{CD}{2}}{\frac{CD}{2}}=\frac{AC-\frac{AC-AD}{2}}{\frac{AC-AD}{2}}=\frac{AC-\frac{3AC}{8}}{\frac{3AC}{8}}=\frac{\frac{5AC}{8}}{\frac{3AC}{8}}=\frac{5}{3}$
Borrowed from https://mks.mff.cuni.cz/kalva/usa/usoln/usol982.html

We will use signed lengths. WLOG let $AC = 4$, $AM = x$, and $AE = y > 0$. Then $AB = 2$ and $AD = 1$. Therefore, $DM = x - 1$ and $MC = 4 - x$. By Power of a Point, $AE \cdot AF = AB^2 = 4$, so $AF = \frac{4}{AE} = \frac{4}{y}$, and $EF = \frac{4}{y} - y = \frac{4 - y^2}{y}$. Since $M$ is on the perpendicular bisectors of $DE$ and $CF$, we have $|DM| = |EM| = |x - 1|$ and $|CM| = |FM| = |4 - x|$.
By Stewart's Theorem on $\triangle MFA$ and cevian $DM$,
So either $8x - 20 = 0$ or $y^2 - 1 = 0$. If $y^2 - 1 = 0$, then $AE = y = 1 = AD$ and $AF = AC = 4$, so the perpendicular bisectors of $CF$ and $DE$ are the same line, and they do not intersect at a point. Therefore, $AM = x = \frac{5}{2}$ and $MC = \frac{3}{2}$, so $\frac{AM}{MC} = \boxed{\frac{5}{3}}$.


Let $a_0,\cdots a_n$ be real numbers in the interval $\left(0,\frac {\pi}{2}\right)$ such that

Prove that $\tan{\left(a_0\right)}\tan{\left(a_1\right)}\cdots \tan{\left(a_n\right)}\ge n^{n + 1}$.

Solution:
Let $y_i = \tan{(a_i - \frac {\pi}{4})}$, where $0\le i\le n$. Then we have
By AM-GM,

Note that by the addition formula for tangents, .
So $\prod_{i = 0}^n{\frac {1 + y_i}{1 - y_i}} = \tan{(a_0)}\tan{(a_1)}\cdots \tan{(a_n)}\ge n^{n + 1}$, as desired. $\blacksquare$


A computer screen shows a $98 \times 98$ chessboard, colored in the usual way. One can select with a mouse any rectangle with sides on the lines of the chessboard and click the mouse button: as a result,  the colors in the selected rectangle switch (black becomes white, white becomes black). Find, with proof, the minimum number of mouse clicks needed to make the chessboard all one color.

Solution:
Answer: $98$.
There are $4\cdot97$ adjacent pairs of squares in the border and each pair has one black and one white square. Each move can fix at most $4$ pairs, so we need at least $97$ moves. However, we start with two corners one color and two another, so at least one rectangle must include a corner square. But such a rectangle can only fix two pairs, so at least $98$ moves are needed.
It is easy to see that 98 moves suffice: take 49 $1\times98$ rectangles (alternate rows), and 49 $98\times1$ rectangles (alternate columns).
credit: https://mks.mff.cuni.cz/kalva/usa/usoln/usol984.html
editor: Brian Joseph
second editor: integralarefun


Prove that for each $n\geq 2$, there is a set $S$ of $n$ integers such that $(a-b)^2$ divides $ab$ for every distinct $a,b\in S$.

Solution:
Proof by induction.  For n=2, the proof is trivial, since $S = (1,2)$ satisfies the condition.  Assume now that there is such a set S of n elements, $a_1, a_2,...a_n$ which satisfy the condition.  The key is to note that if $m=a_1a_2...a_n$, then if we define $b_i=a_i + km$ for all $i\le n$, where k is a positive integer, then $a_i \mid b_i$ and $b_i - b_j = a_i - a_j$, and so $(b_i - b_j)^2 = (a_i - a_j)^2 \mid a_ia_j \mid b_ib_j$.
Let $b_{n+1}=m +km$.   Consider the set $T = (b_1,b_2,...,b_n,b_{n+1})$. To finish the proof, we simply need to choose a k such that $(b_{n+1}-b_i)^2 \mid b_{n+1}b_i$ for all $i\le n$.  Since $(b_{n+1}-b_i)^2 = (m-a_i)^2$, simply choose k so that $k+1 = (m-a_1)^2(m-a_2)^2...(m-a_n)^2$.


Let $n \geq 5$ be an integer. Find the largest integer $k$ (as a function of $n$) such that there exists a convex $n$-gon $A_{1}A_{2}\dots A_{n}$ for which exactly $k$ of the quadrilaterals $A_{i}A_{i+1}A_{i+2}A_{i+3}$ have an inscribed circle. (Here $A_{n+j} = A_{j}$.)

Solution:
Lemma: If quadrilaterals $A_iA_{i+1}A_{i+2}A_{i+3}$ and $A_{i+2}A_{i+3}A_{i+4}A_{i+5}$ in an equiangular $n$-gon are tangential, and $A_iA_{i+3}$ is the longest side quadrilateral $A_iA_{i+1}A_{i+2}A_{i+3}$ for all $i$, then quadrilateral $A_{i+1}A_{i+2}A_{i+3}A_{i+4}$ is not tangential.
Proof:

If quadrilaterals $A_iA_{i+1}A_{i+2}A_{i+3}$ and $A_{i+2}A_{i+3}A_{i+4}A_{i+5}$ are tangential, then $A_iA_{i+3}$ must have side length of $j+y-u$, and $A_{i+2}A_{i+5}$ must have side length of $h + y - n$ (One can see this from what is known as walk-around). Suppose quadrilateral $A_{i+1}A_{i+2}A_{i+3}A_{i+4}$ is tangential. Then, again, we see that $A_{i+1}A_{i+4}$ must have side length $u + n - y$. We assumed by lemma that $A_iA_{i+3} > A_{i}A_{i+1}$ for all $i$, so we have $A_iA_{i+3} > j$, $A_{i+1}A_{i+4} > y$, and $A_{i+2}A_{i+5} > h$. If we add up the side lengths $A_iA_{i+3} + A_{i+1}A_{i+4} + A_{i+2}A_{i+5}$, we get:
However, by the lemma, we assumed that $A_iA_{i+3} > j$, $A_{i+1}A_{i+4} > y$, and $A_{i+2}A_{i+5} > h$. Adding these up, we get:
which is a contradiction. Thus, quadrilateral $A_{i+1}A_{i+2}A_{i+3}A_{i+4}$ is not tangential, proving the lemma.

By lemma, the maximum number of quadrilaterals in a $n$-gon occurs when the tangential quadrilaterals alternate, giving us $k = \lfloor \frac{n}{2} \rfloor$.
Note that one can find the ratio of side of an equiangular $n$-gon in order for alternating quadrilaterals to be tangential.

Since exterior angles of a equiangular $n$-gon have degree measure $\frac{2pi}{n}$, one can write the equation:

Thus, we can find the ratio of sides of an equiangular $n$-gon which fits the maximum to be $1 : 1- \cos \frac{2\pi}{n}$. Note that if $n$ is even, we can easily alternate them, but if $n$ is odd, we must have two adjacent sides be the same length, and that length must be the larger side in the ratio  of adjacent sides. The proof is left as an exercise for the reader.


Some checkers placed on an $n\times n$ checkerboard satisfy the following conditions:
(a) every square that does not contain a checker shares a side with one that does;
(b) given any pair of squares that contain checkers, there is a sequence of squares containing checkers, starting and ending with the given squares, such that every two consecutive squares of the sequence share a side.
Prove that at least $(n^{2}-2)/3$ checkers have been placed on the board.

For the proof let's look at the checkers board as a graph $G$, where the checkers are the vertices and the edges are every pair of checkers sharing a side.
Define $R$ as the circuit rank of $G$(the minimum number of edges to remove from a graph to remove all its cycles).
Define $x$ as the number of checkers placed on the board.
1. From (a) for every square containing a checker there can be up to 4 distinct squares without checkers; thus, $4\times x + x = 5\times x \ge n^2$ (this is the most naive upper bound).
2. From (b) this graph has to be connected. which means that no square which contains a checker can share 4 sides with squares that doesn't contain a checker (because it has to share at least one side with a square that  contains a checker).
3. Now it is possible to improve the upper bound. Since every edge in G represents a square with a checker that shares a side with a square with another checker, the new upper bound is $5\times x - \text{[sum of degrees in G]} \ge n^2.$
4. Thus, $5x - (2x - 2 + 2R) \ge n^2$ (see lemma below).
5. Thus,  $3x + 2 - 2R \ge n^2.$
6. Thus,  $x \ge \frac{n^2 - 2 + 2R}3,$ where $R\ge0$ and is equal to 0 if $G$ is a tree.
$\textit{Clarification/Lemma:}$ The sum of degrees of a connected graph $G = (V,E)$ is $2V -2 + 2R = 2E,$ where $R$ is the circuit rank of $G$.
$\textit{Proof.}$ $2 \times V -2$ is the sum of ranks of the spanning tree created by decircuiting the graph $G$. Since the circuit rank of $G$ is $R$, $2R$ is the sum of ranks removed from $G$. Thus,  $2V -2 + 2R = 2 E.$ $\blacksquare$

Call a square of the checkerboard “good” if it either has a checker on it or
shares a side with a square with a checker on it.
Say there are $k$ checkers on the board, sitting on squares $s_1, \ldots, s_k$. We can assume WLOG that $s_1, \ldots, s_k$ is ordered in such a way that if $1 \leq i \leq k$, then $s_i$ shares a side with at least one of $s_1, \ldots, s_{i - 1}$. (If such an ordering were impossible, then there would be an $s_i$ which isn’t connected to $s_1$ by a sequence of squares with checkers on them, violating condition (b).)
Now imagine removing all the checkers and then putting them back onto the squares $s_1, \ldots, s_k$ in that order, counting the number of good squares after each
step. When we put a checker on $s_1$, we increase the number of good squares
by at most 5: the square $s_1$ becomes good, and each square it
shares a side with (at most 4) becomes good. When we put a checker onto $s_i$,
where $i > 1$, we increase the number of good squares by at most $3$, since $s_i$ is
already good, and at least $1$ of its at most $4$ neighbors already has a checker on it.
So the total number of good squares when we’ve put back every checker is at most $5 + 3(k - 1) = 3k + 2$. In order to satisfy condition (a), we have to make each of the $n^2$ squares good. In other words, we need $3k + 2 \geq n^2$, or


Let $ABCD$ be a cyclic quadrilateral. Prove that

Solution:
Let arc $AB$ of the circumscribed circle (which we assume WLOG has radius 0.5) have value $2x$, $BC$ have $2y$, $CD$ have $2z$, and $DA$ have $2w$.
Then our inequality reduces to, for $x+y+z+w = 180^\circ$:
This is equivalent to by sum-to-product and use of $\cos x = \sin (90^\circ - x)$:

Clearly $90^\circ \ge \frac{x+z}{2} > \frac{x-z}{2} \ge 0^\circ$. As sine is increasing over $[0, \pi/2]$, $|\sin \frac{x+z}{2}| > |\sin \frac{x-z}{2}|$.
Similarly, $|\sin \frac{y+w}{2}| > |\sin \frac{y-w}{2}|$. The result now follows after multiplying the first inequality by $|\sin \frac{x-z}{2}|$, the second by $|\sin \frac{y-w}{2}|$, and adding. (Equality holds if and only if $x=z$ and $y=w$, ie. $ABCD$ is a parallelogram.)
--Suli 11:23, 5 October 2014 (EDT)


Let $p > 2$ be a prime and let $a,b,c,d$ be integers not divisible by $p$, such that

for any integer $r$ not divisible by $p$. Prove that at least two of the numbers $a+b$, $a+c$, $a+d$, $b+c$, $b+d$, $c+d$ are divisible by $p$.
(Note: $\{x\} = x - \lfloor x \rfloor$ denotes the fractional part of $x$.)

Solution:
We see that $\biggl\{\frac{ra+rb+rc+rd}{p}\biggr\}=0$ means that $p|r(a+b+c+d)$. Now, since $p$ does not divide $r$ and $p$ is prime, their GCD is 1 so $p\mathrel{|}a+b+c+d$.
Since $\biggl\{\frac{ra}{p}\biggr\}+\biggl\{\frac{rb}{p}\biggr\}+\biggl\{\frac{rc}{p}\biggr\}+\biggl\{\frac{rd}{p}\biggr\}=2$, then we see that they have to represent mods $\bmod\medspace p$, and thus, our possible values of $p$ are all such that $k^4 \equiv 1\pmod{p}$  for all $k$ that are relatively prime to $p$. This happens when $p=3$ or $5$.
When $p=3$ then $r$ is not divisible by 3, thus two are $1$, and the other two are $2$. Thus, four pairwise sums sum to 3.
When $p=5$ then $r$ is not divisible by 5 so $a, b, c, d$ are $1, 2, 3,$ and $4$, so two pairwise sums sum to 5.
All three possible cases work so we are done.
(This solution makes absolutely no sense. Why is $k^4\equiv 1$? And how do we know that only $3$ and $5$ work!?)


Let $a_{1}, a_{2}, \dots, a_{n}$ ($n > 3$) be real numbers such that

Prove that $\max(a_{1}, a_{2}, \dots, a_{n}) \geq 2$.

First, suppose all the $a_i$ are positive.  Then

Suppose, on the other hand, that without loss of generality,

with $1\le k <n$.  If $a_1 >2$ we are done, so suppose that $a_1 \le2$.  Then
$\sum_{i=1}^k a_i \le 2k$, so

Since $-a_i$ is a positive real for all $k+1 \le i \le n$, it follows that

Then

Since $k<n$, $4(n-k) > 4$.  It follows that $\max(a_1, \dotsc, a_n) \ge \sqrt{4} = 2$, as desired.  $\blacksquare$

Assume the contrary and suppose each $a_i$ is less than 2.
Without loss of generality let $a_1 \le a_2 \le a_3 \le ... \le a_n < 2$, and let $k$ be the largest integer such that $a_k \le 0$ and $0 \le a_{k+1}$ if it exists, or 0 if all the $a_i$ are non-negative. If $k = 0$, then (as $n \ge 4$) $\sum_{i=1}^n a_i^2 < \sum_{i=1}^n 4 = 4n \le n^2$, a contradiction. Hence, assume $n \ge k \ge 1$. Then

Because $a_i \le 0$ for $i \le k$, both sides of the inequality are non-positive, so squaring flips the sign. But we also know that $a_i a_j \ge 0$ for $i, j \le k$, so

which results in

a contradiction to our given condition. The proof is complete.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


The Y2K Game is played on a $1 \times 2000$ grid as follows. Two players in turn write either an S or an O in an empty square. The first player who produces three consecutive boxes that spell SOS wins. If all boxes are filled without producing SOS then the game is a draw. Prove that the second player has a winning strategy.

Solution:
Label the squares $1$ through $2000$. The first player writes a letter in any square $k$. The second player now selects any empty square $l$ such that $\text{min}\,(|l-1|,|l-2000|,|l-k|) > 3$, and fills in a S. The first player may again play anywhere, say $m$. If the second player can now complete SOS, he does so; otherwise, if $l > m$ he fills an S in $l + 3$ and if $l < m$ he fills an S in $l-3$.
We thus have two Ss separated by two empty squares. Note that if any player plays any letter between the two Ss, the other player can always complete a SOS.
Now the second player repeats the following algorithm:
Eventually, assuming the second player has not won yet (and since the first player does not have a winning opportunity yet), this algorithm must stop. It follows that all of the empty squares are now in pairs. Since there are an even number of empty squares, it is the first player's turn. If the first player plays on one of any pair of empty squares that does not have Ss on both its sides, then the second player plays any letter in the other square of the pair. Then, we will only have pairs of empty squares with Ss on both sides remaining (since from the first moves we have constructed at least one, and no one has played between them otherwise the game will have ended), and the first player will have to play between them, so that the second player will win.


Let $ABCD$ be an isosceles trapezoid with $AB \parallel CD$. The inscribed circle $\omega$ of triangle $BCD$ meets $CD$ at $E$. Let $F$ be a point on the (internal) angle bisector of $\angle DAC$ such that $EF \perp CD$. Let the circumscribed circle of triangle $ACF$ meet line $CD$ at $C$ and $G$. Prove that the triangle $AFG$ is isosceles.

Solution:
Quadrilateral $ABCD$ is cyclic since it is an isosceles trapezoid. $AD=BC$. Triangle $ADC$ and triangle $BCD$ are reflections of each other with respect to diameter which is perpendicular to $AB$. Let the incircle of triangle $ADC$ touch $DC$ at $K$. The reflection implies that $DK=CE$, which then implies that the excircle of triangle $ADC$ is tangent to $DC$ at $E$. Since $EF$ is perpendicular to $DC$ which is tangent to the excircle, this implies that $EF$ passes through center of excircle of triangle $ADC$.
We know that the center of the excircle lies on the angular bisector of $DAC$ and the perpendicular line from $DC$ to $E$. This implies that $F$ is the center of the excircle.
Now $\angle GFA=\angle GCA=\angle DCA$.
$\angle ACF=90+\frac{\angle DCA}{2}$.
This means that $\angle AGF=90-\frac{\angle ACD}{2}$. (due to cyclic quadilateral $ACFG$ as given).
Now $\angle FAG - (\angle AFG + \angle FGA)=90-\frac{\angle ACD}{2}=\angle AGF$.
Therefore $\angle FAG=\angle AGF$.
QED.


Call a real-valued function $f$ very convex if

holds for all real numbers $x$ and $y$. Prove that no very convex function exists.

Let $y \ge x$, and substitute $a = x, 2b = y-x$. Then a function is very convex if $\frac{f(a) + f(a+2b)}{2} \ge f(a + b) + 2b$, or rearranging,

Let $g(a) = \frac{f(a+b) - f(a)}{b}$, which is the slope of the secant between $(a,f(a))(a+b,f(a+b))$. Let $b$ be arbitrarily small; then it follows that $g(a+b) - g(a) > 4$, $g(a+2b) - g(a+b) > 4,\, \cdots, g(a+kb) - g(a+ [k-1]b) > 4$. Summing these inequalities yields $g(a+kb)-g(a) > 4k$. As $k \rightarrow \infty$ (but $b << \frac{1}{k}$, so $bk < \epsilon$ is still arbitrarily small), we have $\lim_{k \rightarrow \infty} g(a+kb) - g(a) = g(a + \epsilon) - g(a) > \lim_{k \rightarrow \infty} 4k = \infty$. This implies that in the vicinity of any $a$, the function becomes vertical, which contradicts the definition of a function. Hence no very convex function exists.

Suppose, for the sake of contradiction, that there exists a very convex function $f.$ Notice that $f(x)$ is convex if and only if $f(x) + C$ is convex, where $C$ is a constant. Thus, we may set $f(0) = 0$ for convenience.
Suppose that $f(1) = A$ and $f(-1) = B.$ By the very convex condition,

A straightforward induction shows that:

for all nonnegative integers $n.$
Using a similar line of reasoning as above,

Therefore, for every nonnegative integer $n,$

Now, we choose $n$ large enough such that $n > \frac{A+B}{4} - 1.$ This is always possible because $A$ and $B$ are fixed for any particular function $f.$ It follows that:

However, by the very convex condition,

This is a contradiction. It follows that no very convex function exists.


Let $S$ be the set of all triangles $ABC$ for which

where $r$ is the inradius and $P, Q, R$ are the points of tangency of the incircle with sides $AB, BC, CA,$ respectively. Prove that all triangles in $S$ are isosceles  and similar to one another.

Solution:
We let $x = AP = s - a, y = BQ = s-b, z = CR = s-c$, and without loss of generality let $x \le y \le z$. Then $x + y + z = 3s - (a+b+c) = s$, so $r = \frac {A}{s} = \frac{\sqrt{(x+y+z)xyz}}{x+y+z} = \sqrt{\frac{xyz}{x+y+z}}$. Thus,

Squaring and simplifying yields (after much grueling work)

We claim that the inequality

holds true, with equality iff $4x = y = z$.
Note that $(*)$ is homogeneous in $x,y,z$, so without loss of generality, scale so that $x=1$. Then

which is a quadratic in $y$. As $4z^2 - 16z + 25 = 4(z-4)^2 + 9 \ge 0$, it suffices to show that the quadratic cannot have more than one root, or the discriminant $\Delta \le 0$. Then,

as desired. Equality comes when $z = 4$; since $(*)$ is symmetric in $y$ and $z$, it follows that $y = 4$ is also necessary for equality. Reversing our scaling, it follows that $x:y:z = 1:4:4$.
Then $s = x+y+z = 9x$, and $s-a = x, s-b = 4x, s-c = 4x$ yields $a:b:c = 8:5:5$. Thus, we have proved that all possible ABC are isosceles (as b = c), and that they are similar to a 5-5-8 triangle.
$\blacksquare$

Let $A$, $B$, $C$ be the three angles of the triangle, then $r/AP = \tan{(A/2)}$, $r/BQ=\tan{(B/2)}$, and $r/CR=\tan{(C/2)}$. Without loss of generality, assume $A \leq B \leq C$, then $CR=min{(AP,BQ,CR)}$. Denote $x=\tan{(A/2)}$, $x=\tan{(B/2)}$, $z=\tan{(C/2)}$, then we have,

Meanwhile,

Substitute $z$ in $(1)$, we get

Treating (2) as a quadratic equation for $x$, the discriminant is:

For $x$, $y$ to be both real numbers, $\Delta$ must not be negative, so $\Delta = 0$, which yields $y=1/3$. Solving for x, we get $x=\frac{-(8y-6)}{2*5}=1/3$. Using the formula $\tan(A)=\frac{2\tan(A/2)}{1-\tan^2(A/2)}$, we have $\tan(A)=\tan(B)=3/4$. Therefore $A=B=\arctan{(3/4)}$. This proves that all possible triangle $ABC$ are isosceles with the same set of angles, i.e., they are similar to each other.
It's inconsequential to the proof, but it can be easily found that, since $tan(A) = 3/4$, the altitude to the base of the isosceles triangle divides the triangle into two 3-4-5 right triangles with $4$ on the base; therefore, the entire triangle is 5-5-8. $\square$.
Solution by $Mathdummy$.


A game of solitaire is played with $R$ red cards, $W$ white cards, and $B$ blue cards. A player plays all the cards one at a time. With each play he accumulates a penalty. If he plays a blue card, then he is charged a penalty which is the number of white cards still in his hand. If he plays a white card, then he is charged a penalty which is twice the number of red cards still in his hand. If he plays a red card, then he is charged a penalty which is three times the number of blue cards still in his hand. Find, as a function of $R, W,$ and $B,$ the minimal total penalty a player can amass and all the ways in which this minimum can be achieved.

Solution:
We claim (inductively) that the minimum is just going to be $\min(BW,2WR,3RB)$. We'll start our induction with the case where one of the three quantities is zero, in which case we verify that we can indeed get away without any penalty by, for example, discarding blue if we are out of white.
Now, for the inductive step, let $f(B,W,R)$ be the minimum we seek. Note that

By our inductive hypothesis, $f(B-1,W,R) = \min((B-1)W,2WR,3R(B-1))$. In order for this to cause our inductive step not to hold, we would require that $W+\min((B-1)W,2WR,3R(B-1)) < \min(BW,2WR,3RB)$. It is evident that the first two entries in the $min$ expression cannot cause this to happen, so that we need only consider $W+3R(B-1) < \min(BW,2WR,3RB)$. So $W+3R(B-1) < BW$, whence $3R < W$. But $W+3R(B-1) < 3RB$, so that $W < 3R$, a contradiction.
For the other two cases, we can get similar contradictions, so that our inductive step must hold, and so $f(B,W,R)$ is indeed $\min(BW,2WR,3RB)$.
We now need only establish how many ways to do this. If one of these quantities is smaller, our induction and the fact that it is eventually zero guarantees that it will continue to be the smallest quantity as cards are discarded. (For example, if it is currently optimal to discard a blue card, it will continue to be so until we run out of blue cards.) Therefore, assuming that there is currently only one best choice of card to discard, this will continue to be so in the future, whence if $BW \neq 2WR \neq 3RB$, there is only $1$ optimal strategy.
Suppose, now, that $BW = 2WR$. It is thus optimal to discard either a $B$ or $W$ card. If we ever discard a blue card, then we will cause $BW < 2WR$, whence there is only one possible strategy from then on. However, if we discard a white card, then we will still have $BW = 2WR$, meaning that we continue to have the choice of discarding a white or blue card. Since we can discard a white card at most $W$ times, there are $W+1$ choices for how many $W$ cards to discard ($0$ to $W$), meaning that there are $W+1$ optimal strategies.
By similar logic, we get $R+1$ optimal strategies if $2WR = 3RB$, and $B+1$ optimal strategies if $3RB = BW$.
The final case, then, is if $BW = 2WR = 3RB$. In this case, if we first discard a white card, we are left with the $BW = 2WR$ case, and similarly for a blue and red card. The total number of optimal strategies in this case is then the sum of the optimal strategies in those cases, or, in other words, $B+W+R$.
To summarize:
The minimum penalty is $\min(BW,2WR,3RB)$.
If $BW \neq 2WR \neq 3RB$, there is $1$ optimal strategy.
If $BW = 2WR < 3RB$, there are $W+1$ strategies.
If $2WR = 3RB < BW$, there are $R+1$ strategies.
If $3RB = BW < 2WR$, there are $B+1$ strategies.
If $BW = 2WR = 3RB$, there are $R+B+W$ strategies.
By J Steinhardt, from AoPS Community


Find the smallest positive integer $n$ such that if $n$ squares of a $1000 \times 1000$ chessboard are colored, then there will exist three colored squares whose centers form a right triangle with sides parallel to the edges of the board.

Solution:
We claim that $n = 1999$ is the smallest such number. For $n \le 1998$, we can simply color any of the $1998$ squares forming the top row and the left column, but excluding the top left corner square.
We now show that no configuration with no colored right triangles exists for $n = 1999$. We call a row or column filled if all $1000$ of its squares are colored. Then any of the remaining $999$ colored squares must share a column or row, respectively, with one of the colored squares in a filled row or column. These two squares, and any other square in the filled row or column, form a colored right triangle, giving us a contradiction. Hence, no filled row or column may exist.
Let $m$ be the number of columns with $1$ colored square. Then there are $1999-m$ colored squares in the remaining columns, and in each of these $< 1999-m$ columns that have a colored square must have at least two colored squares in them. These two colored squares will form a triangle with any other colored square in either of the rows containing the colored squares. Hence, each of the $1999-m$ colored squares must be placed in different rows, but as there are only $1000$ rows, the inequality $1999 - m \le 1000 \Longrightarrow m \ge 999$ holds. If $m = 1000$, then each column only has $1$ colored square, leaving no place for the remaining $999$, contradiction. If $m = 999$, then each of the $1000$ rows has $1$ black square, leaving no place for the other $999$, contradiction. Hence $n = \boxed{1999}$ is the minimal value.


Let $A_1A_2A_3$ be a triangle and let $\omega_1$ be a circle in its plane passing through $A_1$ and $A_2.$ Suppose there exist circles $\omega_2, \omega_3, \dots, \omega_7$ such that for $k = 2, 3, \dots, 7,$ $\omega_k$ is externally tangent to $\omega_{k - 1}$ and passes through $A_k$ and $A_{k + 1},$  where $A_{n + 3} = A_{n}$ for all $n \ge 1$. Prove that $\omega_7 = \omega_1.$

Let the circumcenter of $\triangle ABC$ be $O$, and let the center of $\omega_k$ be $O_k$. $\omega_k$ and $\omega_{k-1}$ are externally tangent at the point $A_k$, so $O_k, A_k, O_{k-1}$ are collinear.
$O$ is the intersection of the perpendicular bisectors of $\overline{A_1A_2}, \overline{A_2A_3}, \overline{A_3A_1}$, and each of the centers $O_k$ lie on the perpendicular bisector of the side of the triangle that determines $\omega_k$. It follows from $OA_k = OA_{k+1}, O_kA_k = O_kA_{k+1}, OO_k = OO_k \Longrightarrow \triangle OA_kO_k \cong \triangle OA_{k+1}O_k$ that $\angle OA_kO_k = \angle OA_{k+1}O_k$.
Since $O, A_k$, and the perpendicular bisector of $\overline{A_kA_{k+1}}$ are fixed, the angle $OA_kO_k$ determines the position of $O_k$ (since $O_k$ lies on the perpendicular bisector). Let $\theta_k = m\angle OA_kO_k$; then, $\theta_i = \theta_j$ and $i \equiv j \pmod{3}$ together imply that $O_i \equiv O_j$.
Now $\theta_1 = \angle OA_1O_1 = \angle OA_2O_1 = 180 - \angle OA_2O_2 = 180 - \theta_2$ (due to collinearility). Hence, we have the recursion $\theta_k = 180 - \theta_{k-1}$, and so $\theta_k = \theta_{k-2}$. Thus, $\theta_{1} = \theta_{7}$.
$\theta_{1} = \theta_{7}$ implies that $O_1 \equiv O_7$, and circles $\omega_1$ and $\omega_7$ are the same circle since they have the same center and go through the same two points.

Using the collinearity of certain points and the fact that $A_k A_{k+1} O_k$ is isosceles, we quickly deduce that

From ASA Congruence we deduce that $A_1 A_2 O_1$ and $A_7 A_8 O_7$ are congruent triangles, and so $O_1 A_1 = O_7 A_7$, that is $\omega_1 = \omega_7$.


Let $a_1, b_1, a_2, b_2, \dots , a_n, b_n$ be nonnegative real numbers. Prove that

Solution:
Credit for this solution goes to Ravi Boppana.
Lemma 1: If $r_1, r_2, \ldots , r_n$ are non-negative reals and $x_1, x_2, \ldots x_n$ are reals, then

Proof: Without loss of generality assume that the sequence $\{r_i\}$ is increasing. For convenience, define $r_0=0$. The LHS of our inequality becomes

This expression is equivalent to the sum

Each term in the summation is non-negative, so the sum itself is non-negative. $\blacksquare$
We now define $r_i=\frac{\max(a_i,b_i)}{\min(a_i,b_i)}-1$. If $\min(a_i,b_i)=0$, then let $r_i$ be any non-negative number. Define $x_i=\text{sgn}(a_i-b_i)\min(a_i,b_i)$.
Lemma 2: $\min(a_{i}b_{j}, a_{j}b_{i})-\min(a_{i}a_{j}, b_{i}b_{j}) =\min(r_{i}, r_{j}) x_{i}x_{j}$
Proof: Switching the signs of $a_i$ and $b_i$ preserves inequality, so we may assume that $a_i>b_i$. Similarly, we can assume that $a_j>b_j$. If $b_ib_j=0$, then both sides are zero, so we may assume that $b_i$ and $b_j$ are positive. We then have from the definitions of $r_i$ and $x_i$ that

This means that

This concludes the proof of Lemma 2. $\blacksquare$
We can then apply Lemma 2 and Lemma 1 in order to get that

This implies the desired inequality.


Each of eight boxes contains six balls. Each ball has been colored with one of $n$ colors, such that no two balls in the same box are the same color, and no two colors occur together in more than one box. Determine, with justification, the smallest integer $n$ for which this is possible.

We claim that $n=23$ is the minimum. Consider the following construction (replacing colors with numbers) which fulfills this:

Suppose a configuration exists with $n \le 22$.
Suppose a ball appears $5$ or more times. Then the remaining balls of the $5$ boxes must be distinct, so that there are at least $n \ge 5 \cdot 5 + 1 = 26$ balls, contradiction. If a ball appears $4$ or more times, the remaining balls of the $4$ boxes must be distinct, leading to $5 \cdot 4 + 1 = 21$ balls. The fifth box can contain at most four balls from the previous boxes, and then the remaining two balls must be distinct, leading to $n \ge 2 + 21 = 23$, contradiction.
However, by the Pigeonhole Principle, at least one ball must appear $3$ times. Without loss of generality suppose that $1$ appears three times, and let the boxes that contain these have balls with colors $\{1,2,3,4,5,6\},\{1,7,8,9,10,11\},\{1,12,13,14,15,16\}$. Each of the remaining five boxes can have at most $3$ balls from each of these boxes. Thus, each of the remaining five boxes must have $3$ additional balls $> 16$. Thus, it is necessary that we use $\le 22 - 16 = 6$ balls to fill a $3 \times 5$ grid by the same rules.
Again, no balls may appear $\ge 4$ times, but by Pigeonhole, one ball must appear $3$ times. Without loss of generality, let this ball have color $17$; then the three boxes containing $17$ must have at least $2 \cdot 3 + 1 = 7$ balls, contradiction.
Therefore, $n = 23$ is the minimum.

Similar to the above solution, no color can appear 4 times or more.
We can use PIE. Let $S_1,S_2,\cdots ,S_8$ be the colors in each of the $8$ boxes. Then $n=|\cup_{i=1}^8S_i|$. By PIE we know thatNote however that no color can appear 4 times or more, so all the items after $\sum_{1\leq i<j<k\leq 8}|S_i\cap S_j\cap S_k|$ must be equal to 0, soNow note that for each $i$, $|S_i|=6,$ so $\sum_{i=1}^8 |S_i|=48.$ Also no pair of colors appears twice, so for any $i,j, |S_i\cap S_j|\leq 1,$ and so $\sum_{1\leq i<j\leq 8}|S_i\cap S_j|\leq \binom82=28.$ Thus, $n\geq 48-28+\sum_{1\leq i<j<k\leq 8}|S_i\cap S_j\cap S_k|.$ Given that there are $n$ colors, to minimize the number of colors in 3 boxes means each color is in either 2 or 3 boxes, and since there are 48 total spots, this means there are $48-2n$ colors in 3 boxes and $3n-48$ colors in 2. Thus $n\geq 20+48-2n,$ so $3n\geq 68$, and $n\geq23$ and we are done.

Let $m_{i,j}$ be the number of balls which are the same color as the $j^{\text{th}}$ ball in box $i$ (including that ball). For a fixed box $i$, $1\leq i\leq 8$, consider the sums

For each fixed $i$, since no pair of colors is repeated, each of the remaining seven boxes can contribute at most one ball to $S_i$. Thus, $S_i\leq 13$. It follows by the convexity of $f(x) = 1/x$ that $s_i$ is minimized when one of the $m_{i,j}$ is equal to 3 and the other five equal to 2. Hence $s_i\geq 17/6$. Note that

Hence there must be 23 colors. The construction for $n = 23$ is above.


Let $ABC$ be a triangle and let $\omega$ be its incircle. Denote by $D_1$ and $E_1$ the points where $\omega$ is tangent to sides $BC$ and $AC$, respectively. Denote by $D_2$ and $E_2$ the points on sides $BC$ and $AC$, respectively, such that $CD_2 = BD_1$ and $CE_2 = AE_1$, and denote by $P$ the point of intersection of segments $AD_2$ and $BE_2$. Circle $\omega$ intersects segment $AD_2$ at two points, the closer of which to the vertex $A$ is denoted by $Q$. Prove that $AQ = D_2P$.

It is well known that the excircle opposite $A$ is tangent to $\overline{BC}$ at the point $D_2$. (Proof: let the points of tangency of the excircle with the lines $BC, AB, AC$ be $D_3, F,G$ respectively. Then $AB+BD_3=AB + BF=AF = AG = AC + CG=AC + CD_3$. It follows that $2CD_3 = AB + BC - AC$, and $CD_3 = s-b = BD_1 = CD_2$, so $D_3 \equiv D_2$.)
Now consider the homothety that carries the incircle of $\triangle ABC$ to its excircle. The homothety also carries $Q$ to $D_2$ (since $A,Q,D_2$ are collinear), and carries the tangency points $E_1$ to $G$. It follows that $\frac{AQ}{QD_2} = \frac{AE_1}{E_1G} = \frac{s-a}{E_1C + CD_2} = \frac{s-a}{CD_1 + BD_1} = \frac{s-a}{a}$.
By Menelaus' Theorem on $\triangle ACD_2$ with segment $\overline{BE_2}$, it follows that $\frac{CE_2}{E_2A} \cdot \frac{AP}{PD_2} \cdot \frac{BD_2}{BC} = 1 \Longrightarrow \frac{AP}{PD_2} = \frac{(c - (s-a)) \cdot a}{(a-(s-c)) \cdot AE_1} = \frac{a}{s-a}$. It easily follows that $AQ = D_2P$. $\blacksquare$

The key observation is the following lemma.
Lemma: Segment $D_1Q$ is a diameter of circle $\omega$.
Proof: Let $I$ be the center of circle $\omega$, i.e., $I$ is the incenter of triangle $ABC$. Extend segment $D_1I$ through $I$ to intersect circle $\omega$ again at $Q'$, and extend segment $AQ'$ through $Q'$ to intersect segment $BC$ at $D'$. We show that $D_2 = D'$, which in turn implies that $Q = Q'$, that is, $D_1Q$ is a diameter of $\omega$.
Let $l$ be the line tangent to circle $\omega$ at $Q'$, and let $l$ intersect the segments $AB$ and $AC$ at $B_1$ and $C_1$, respectively. Then $\omega$ is an excircle of triangle $AB_1C_1$. Let $\mathbf{H}_1$ denote the dilation with its center at $A$ and ratio $AD'/AQ'$. Since $l\perp D_1Q'$ and $BC\perp D_1Q'$, $l\parallel BC$. Hence $AB/AB_1 = AC/AC_1 = AD'/AQ'$. Thus $\mathbf{H}_1(Q') = D'$, $\mathbf{H}_1(B_1) = B$, and $\mathbf{H}_1(C_1) = C$. It also follows that an excircle $\Omega$ of triangle $ABC$ is tangent to the side $BC$ at $D'$.
It is well known that  We compute $BD'$. Let $X$ and $Y$ denote the points of tangency of circle $\Omega$ with rays $AB$ and $AC$, respectively. Then by equal tangents, $AX = AY$, $BD' = BX$, and $D'C = YC$. Hence  It follows that  Combining these two equations yields $BD' = CD_1$. Thus  that is, $D' = D_2$, as desired. $\blacksquare$
Now we prove our main result. Let $M_1$ and $M_2$ be the respective midpoints of segments $BC$ and $CA$. Then $M_1$ is also the midpoint of segment $D_1D_2$, from which it follows that $IM_1$ is the midline of triangle $D_1QD_2$. Hence  and $AD_2\parallel M_1I$. Similarly, we can prove that $BE_2\parallel M_2I$.
2001usamo2-2.png
Let $G$ be the centroid of triangle $ABC$. Thus segments $AM_1$ and $BM_2$ intersect at $G$. Define transformation $\mathbf{H}_2$ as the dilation with its center at $G$ and ratio $-1/2$. Then $\mathbf{H}_2(A) = M_1$ and $\mathbf{H}_2(B) = M_2$. Under the dilation, parallel lines go to parallel lines and the intersection of two lines goes to the intersection of their images. Since $AD_2\parallel M_1I$ and $BE_2\parallel M_2I$, $\mathbf{H}_2$ maps lines $AD_2$ and $BE_2$ to lines $M_1I$ and $M_2I$, respectively. It also follows that $\mathbf{H}_2(I) = P$ and  or  This yields  as desired.
Note: We used directed lengths in our calculations to avoid possible complications caused by the different shapes of triangle $ABC$.

Here is a rather nice solution using barycentric coordinates:
Let $A$ be $(1,0,0)$, $B$ be $(0,1,0)$, and $C$ be $(0,0,1)$. Let the side lengths of the triangle be $a,b,c$ and the semi-perimeter $s$.
Now,  Thus,
Therefore, $D_2=(0:s-b:s-c)$ and $E_2=(s-a:0:s-c).$ Clearly then, the non-normalized coordinates of $P=(s-a:s-b:s-c).$
Normalizing, we have that
Now, we find the point $Q'$ inside the triangle on the line $AD_2$ such that $AQ'=D_2P$. It is then sufficient to show that this point lies on the incircle.
$P$ is the fraction $\frac{s-a}{s}$ of the way "up" the line segment from $D_2$ to $A$. Thus, we are looking for the point that is $\frac{s-a}{s}$ of the way "down" the line segment from $A$ to $D_2$, or, the fraction $1-\frac{s-a}{s}$ of the way "up".
Thus, $Q'$ has normalized $x$-coordinate $1-\frac{s-a}{s}=\frac{a}{s}$.
As the line $AD_2$ has equation $(s-c)y=(s-b)z$, it can easily be found that
Recalling that the equation of the incircle is  We must show that this equation is true for $Q'$'s values of $x,y,z$.
Plugging in our values, this means showing that

Dividing by $a(s-a)$, this is just
Plugging in the value of $s:$

The first bracket is just

and the second bracket is
Dividing everything by $2a$ gives
 which is $0$, as desired.
As $Q'$ lies on the incircle and $AD_2$, $Q'=Q$, and our proof is complete.

We again use Barycentric coordinates. As before, let $A$ be $(1,0,0)$, $B$ be $(0,1,0)$, and $C$ be $(0,0,1)$. Also

Now, consider a point $Q'$ for which $AQ'=PD_{2}$. Then working component-vise, we get $Q'+P=A+D_{2}$ from which we can easily get the coordinates of $Q'$ as;

It suffices to show that $Q'=Q$.
Let $I=\left(\frac{a}{2s},\frac{b}{2s},\frac{c}{2s}\right)$  be the incenter of triangle $ABC$. We claim that $I$ is the midpoint of $Q'D_{1}$. Indeed,

Hence the claim has been proved.
Since $I$ is the center of $\omega$ and the midpoint of  $Q'D_{1}$, thus $Q'$ is the point diametrically opposite to $D_{1}$, and hence it lies on $\omega$ and closer to $A$ off the 2 points. Thus $Q=Q'$ as desired.


Let $a, b, c \geq 0$ and satisfy
Show that

First we prove the lower bound.
Note that we cannot have $a, b, c$ all greater than 1.
Therefore, suppose $a \le 1$.
Then

Note that, by the Pigeonhole Principle, at least two of $a,b,c$ are either both greater than or less than $1$. Without loss of generality, let them be $b$ and $c$. Therefore, $(b-1)(c-1)\ge 0$. From the given equation, we can express $a$ in terms of $b$ and $c$ as

Thus,
From the Cauchy-Schwarz Inequality,
This completes the proof.

The proof for the lower bound is the same as in the first solution.
Now we prove the upper bound. Let us note that at least two of the three numbers $a$, $b$, and $c$ are both greater than or equal to 1 or less than or equal to 1. Without loss of generality, we assume that the numbers with this property are $b$ and $c$. Then we have

The given equality $a^2 + b^2 + c^2 + abc = 4$ and the inequality $b^2 + c^2\geq 2bc$ imply that

or

Dividing both sides of the last inequality by $2 + a$ yields

Thus,

as desired.
The last equality holds if and only if $b = c$ and $a(1 - b)(1 - c) = 0$. Hence equality for the upper bound holds if and only if $(a,b,c)$ is one of the triples $(1,1,1)$, $(0,\sqrt{2},\sqrt{2})$, $(\sqrt{2},0,\sqrt{2})$, and $(\sqrt{2},\sqrt{2},0)$. Equality for the lower bound holds if and only if $(a,b,c)$ is one of the triples $(2,0,0)$, $(0,2,0)$ and $(0,0,2)$.

The proof for the lower bound is the same as in the first solution.
Now we prove the upper bound. It is clear that $a,b,c\leq 2$. If $abc = 0$, then the result is trivial. Suppose that $a,b,c > 0$. Solving for $a$ yields

This asks for the trigonometric substitution $b = 2\sin u$ and $c = 2\sin v$, where $0^\circ < u,v < 90^\circ$. Then

and if we set $u = B/2$ and $v = C/2$, then $a = 2\sin (A/2)$, $b = 2\sin (B/2)$, and $c = \sin (C/2)$, where $A$, $B$, and $C$ are the angles of a triangle. We have

where the inequality step follows from AM-GM. Likewise,

Therefore

as desired.


Let $P$ be a point in the plane of triangle $ABC$ such that the segments $PA$, $PB$, and $PC$ are the sides of an obtuse triangle. Assume that in this triangle the obtuse angle opposes the side congruent to $PA$. Prove that $\angle BAC$ is acute.

We know that $PB^2+PC^2 < PA^2$ and we wish to prove that $AB^2 + AC^2 > BC^2$.
It would be sufficient to prove that

Set $A(0,0)$, $B(1,0)$, $C(x,y)$, $P(p,q)$.
Then, we wish to show

which is true by the trivial inequality.

Let $A$ be the origin. For a point $Q$, denote by $q$ the vector $\overrightarrow{AQ}$, and denote by $|q|$ the length of $q$. The given conditions may be written as

or

Adding $2b\cdot c$ on both sides of the last inequality gives

Since the left-hand side of the last inequality is nonnegative, the right-hand side is positive. Hence

that is, $\angle BAC$ is acute.

For the sake of contradiction, let's assume to the contrary that $\angle BAC$. Let $AB = c$, $BC = a$, and $CA = b$. Then $a^2\geq b^2 + c^2$. We claim that the quadrilateral $ABPC$ is convex. Now applying the generalized Ptolemy's Theorem to the convex quadrilateral $ABPC$ yields

where the second inequality is by Cauchy-Schwarz. This implies $PA^2\leq PB^2 + PC^2$, in contradiction with the facts that $PA$, $PB$, and $PC$ are the sides of an obtuse triangle and $PA > \max\{PB, PC\}$.
We present two arguments to prove our claim.
First argument: Without loss of generality, we may assume that $A$, $B$, and $C$ are in counterclockwise order. Let lines $l_1$ and $l_2$ be the perpendicular bisectors of segments $AB$ and $AC$, respectively. Then $l_1$ and $l_2$ meet at $O$, the circumcenter of triangle $ABC$. Lines $l_1$ and $l_2$ cut the plane into four regions and $A$ is in the interior of one of these regions. Since $PA > PB$ and $PA > PC$, $P$ must be in the interior of the region that opposes $A$. Since $\angle BAC$ is not acute, ray $AC$ does not meet $l_1$ and ray $AB$ does not meet $l_2$. Hence $B$ and $C$ must lie in the interiors of the regions adjacent to $A$. Let $\mathcal{R}_X$ denote the region containing $X$. Then $\mathcal{R}_A$, $\mathcal{R}_B$, $\mathcal{R}_P$, and $\mathcal{R}_C$ are the four regions in counterclockwise order. Since $\angle BAC\geq 90^\circ$, either $O$ is on side $BC$ or $O$ and $A$ are on opposite sides of line $BC$. In either case $P$ and $A$ are on opposite sides of line $BC$. Also, since ray $AB$ does not meet $l_2$ and ray $AC$ does not meet $l_1$, it follows that $\mathcal{R}_P$ is entirely in the interior of $\angle BAC$. Hence $B$ and $C$ are on opposite sides of $AP$. Therefore $ABPC$ is convex.
Second argument: Since $PA > PB$ and $PA > PC$, $A$ cannot be inside or on the sides of triangle $PBC$. Since $PA > PB$, we have $\angle ABP > \angle BAP$ and hence $\angle BAC\geq 90^\circ > \angle BAP$. Hence $C$ cannot be inside or on the sides of triangle $BAP$. Symmetrically, $B$ cannot be inside or on the sides of triangle $CAP$. Finally, since $\angle ABP > \angle BAP$ and $\angle ACP > \angle CAP$, we have

Therefore $P$ cannot be inside or on the sides of triangle $ABC$. Since this covers all four cases, $ABPC$ is convex.

Let $P$ be the origin in vector space, and let $a, b, c$ denote the position vectors of $A, B, C$ respectively. Then the obtuse triangle condition, $PA^2 > PB^2 + PC^2$, becomes $a^2 > b^2 + c^2$ using the fact that the square of a vector (the dot product of itself and itself) is the square of its magnitude. Now, notice that to prove $\angle{BAC}$ is acute, it suffices to show that $(a - b)(a - c) > 0$, or $a^2 - ab - ac + bc > 0$. But this follows from the observation that

which leads to

and therefore our desired conclusion.

Let $M, N$ be midpoints of $AP$ and $BC$, respectively. For the points $A, B, P, C$; let's apply Euler's quadrilateral formula,

Given that $AP^2 > BP^2 + PC^2$. Thus,

and we get $\angle BAC$ is acute.
(Lokman GÖKÇE)

Without loss of generality, assume that in a Cartesian coordinate system, $A$ is at the point $(0, 0)$ and $C$ is at the point $(1,0)$. Let $B$ be at the point $(b_x,b_y)$ and $P$ be at the point $(p_x,p_y)$. Without loss of generality, also assume that $b_y>0$.
Now, assume for contradiction that $\angle BAC$ is not acute. Since $PA$, $PB$, and $PC$ are the sides of an obtuse triangle, with $PA$ the longest side, it follows that $PA^2>PB^2+PC^2$, implying that $p_x^2+p_y^2>(p_x-b_x)^2+(p_y-b_y)^2+(p_x-1)^2+p_y^2$. This inequality simplifies to $b_x^2-2p_x b_x+b_y^2-2p_y b_y+p_x^2-2p_x+1+p_y^2<0$. Note that since $p_x^2-2p_x+1$ and $b_y^2-2p_y b_y+p_y^2$ are both perfect squares, all terms of this inequality except for $-2p_x b_x$ are already guaranteed to be nonnegative.
If $p_x<0$, then $P$ would be closer to $A$ than to $C$, but since $PA^2=PB^2+PC^2$, this is not possible. Therefore, $p_x \geq 0$. Since $\angle BAC$ not being acute implies that $b_x \leq 0$, it follows that $-2p_x b_x \geq 0$. But now since all terms of $b_x^2-2p_x b_x+b_y^2-2p_y b_y+p_x^2-2p_x+1+p_y^2<0$ are guaranteed to be nonnegative, this entire expression cannot be negative, leading to a contradiction. Therefore, $\angle BAC$ is acute.


Let $S$ be a set of integers (not necessarily positive) such that
(a) there exist $a,b \in S$ with $\gcd(a,b) = \gcd(a - 2,b - 2) = 1$;
(b) if $x$ and $y$ are elements of $S$ (possibly equal), then $x^2 - y$ also belongs to $S$.
Prove that $S$ is the set of all integers.

Solution:
In the solution below we use the expression $S$ is stable under $x\mapsto f(x)$ to mean that if $x$ belongs to $S$ then $f(x)$ also belongs to $S$. If $c,d\in S$, then by (B), $S$ is stable under $x\mapsto c^2 - x$ and $x\mapsto d^2 - x$, hence stable under $x\mapsto c^2 - (d^2 - x) = x + (c^2 - d^2)$. Similarly $S$ is stable under $x\mapsto x + (d^2 - c^2)$. Hence $S$ is stable under $x\mapsto x + n$ and $x\mapsto x - n$ whenever $n$ is an integer linear combination of numbers of the form $c^2 - d^2$ with $c,d\in S$. In particular, this holds for $n = m$, where $m = \gcd\{c^2 - d^2 : c,d\in S\}$.
Since $S\neq \emptyset$ by (A), it suffices to prove that $m = 1$. For the sake of contradiction, assume that $m\neq 1$. Let $p$ be a prime dividing $m$. Then $c^2 - d^2\equiv 0\pmod{p}$ for all $c,d\in S$. In other words, for each $c,d\in S$, either $d\equiv c\pmod{p}$ or $d\equiv -c\pmod{p}$. Given $c\in S$, $c^2 - c\in S$ by (B), so $c^2 - c\equiv c\pmod{p}$ or $c^2 - c\equiv -c\pmod{p}$. Hence

By (A), there exist some $a$ and $b$ in $S$ such that $\gcd(a,b) = 1$, that is, at least one of $a$ or $b$ cannot be divisible by $p$. Denote such an element of $S$ by $\alpha$: thus, $\alpha\not\equiv 0\pmod{p}$. Similarly, by (A), $\gcd(a - 2, b - 2) = 1$, so $p$ cannot divide both $a - 2$ and $b - 2$. Thus, there is an element of $S$, call it $\beta$, such that $\beta\not\equiv 2\pmod{p}$. By $(*)$, $\alpha\equiv 2\pmod{p}$ and $\beta\equiv 0\pmod{p}$. By (B), $\beta^2 - \alpha\in S$. Taking $c = \beta^2 - \alpha$ in $(*)$ yields either $-2\equiv 0\pmod{p}$ or $-2\equiv 2\pmod{p}$, so $p = 2$. Now $(*)$ says that all elements of $S$ are even, contradicting (A). Hence our assumption is false and $S$ is the set of all integers.


Each point in the plane is assigned a real number such that, for any triangle, the number at the center of its inscribed circle is equal to the arithmetic mean of the three numbers at its vertices. Prove that all points in the plane are assigned the same number.

Solution:
We label each upper case point with the corresponding lower case letter as its assigned number. The key step is the following lemma.
Lemma: If $ABCD$ is an isosceles trapezoid, then $a + c = b + d$.
Proof: Assume without loss of generality that $BC\parallel AD$, and that rays $AB$ and $DC$ meet at $P$. Let $I$ be the incenter of triangle $PAC$, and let line $l$ bisect $\angle APD$. Then $I$ is on $l$, so reflecting everything across line $l$ shows that $I$ is also the incenter of triangle $PDB$. Therefore,

Hence $a + c = b + d$, as desired.$\blacksquare$
For any two distinct points $A_1$ and $A_2$ in the plane, we construct a regular pentagon $A_1A_2A_3A_4A_5$. Applying the lemma to isosceles trapezoids $A_1A_3A_4A_5$ and $A_2A_3A_4A_5$ yields

Hence $a_1 = a_2$. Since $A_1$ and $A_2$ were arbitrary, all points in the plane are assigned the same number.


Let $S$ be a set with 2002 elements, and let $N$ be an integer with $0 \le N \le 2^{2002}$.  Prove that it is possible to color every subset of $S$ either blue or red so that the following conditions hold:
(a) the union of any two red subsets is red;
(b) the union of any two blue subsets is blue;
(c) there are exactly $N$ red subsets.

Let a set colored in such a manner be properly colored.  We prove that any set with $n$ elements can be properly colored for any $0 \le N \le 2^n$.  We proceed by induction.
The base case, $n = 0$, is trivial.
Suppose that our claim holds for $n = k$.  Let $s \in S$, $|S| = k + 1$, and let $S'$ denote the set of all elements of $S$ other than $s$.
If $N \le 2^k$, then we may color all subsets of $S$ which contain $s$ blue, and we may properly color $S'$.  This is a proper coloring because the union of any two red sets must be a subset of $S'$, which is properly colored, and any the union of any two blue sets either must be in $S'$, which is properly colored, or must contain $s$ and therefore be blue.
If $N > 2^k$, then we color all subsets containing $s$ red, and we color $N - 2^k$ elements of $S'$ red in such a way that $S'$ is colored properly.  Then $S$ is properly colored, using similar reasoning as before.  Thus the induction is complete.

If $N = 0$, color every subset blue.  If $N = 2^{2002}$, color every subset red.  Otherwise, let $S$ be $\{ 0, 1, \ldots , 2001 \}$.  Write $N$ in binary, i.e., let
where each of the $a_i$ is an element of $S$.  We color each of the $a_i$ red and all the other elements of $S$ blue.  We color the empty set blue, and we color any other set the color of its largest element.  This satisfies the problem's first two conditions, as the largest element of the union of two red (or blue) sets will have a red (or blue) number as its largest element.  In addition, for each integer $n \in S$, there are $2^{n}$ subsets of $S$ with $n$ as a maximal element, so $\sum_{i=1}^{k} 2^{a_i} = N$ subsets of $S$ are colored red, as desired.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Let $ABC$ be a triangle such that
where $s$ and $r$ denote its semiperimeter and inradius, respectively.  Prove that triangle $ABC$ is similar to a triangle $T$ whose side lengths are all positive integers with no common divisor and determine those integers.

Solution:
Let $a,b,c$ denote $BC, CA, AB$, respectively.  Since the line from a triangle's incenter to one of its vertices bisects the angle at the triangle's vertex, the condition of the problem is equivalent to the
or
But by the Cauchy-Schwarz Inequality, we know
with equality only when $\frac{(s-a)^2}{36}, \frac{(s-b)^2}{9}, \frac{(s-c)^2}{4}$ are directly proportional to 36, 9, 4, respectively.  Therefore (clearing denominators and taking square roots) our problem requires that $(s-a), (s-b), (s-c)$ be directly proportional to 36, 9, 4, and since $a = (s-b) + (s-c)$ etc., this is equivalent to the condition that $a,b,c$ be in proportion with 13, 40, 45, Q.E.D.
Sidenote: A 13, 40, 45 obtuse triangle has an integer area of 252 and an inradius of $\frac{36}{7}$.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Prove that any monic polynomial (a polynomial with leading coefficient 1) of degree $n$ with real coefficients is the average of two monic polynomials of degree $n$ with $n$ real roots.

Lemma.  For any set of ordered pairs of reals $\{ (x_i , y_i ) \}_{i=1}^{n}$ with $x_i \neq x_j$ for all $i \neq j$, there exists a unique monic real polynomial  $P(x)$ of degree $n$ such that $P(x_i) = y_i$ for all integers $i \in [1,n]$.
Proof 1.  By the Lagrange Interpolation Formula, there exists a unique real polynomial $Q(x)$ of degree less than $n$ such that $Q(x_i) = y_i - x_i^n$.  Then it is necessary and sufficient that $P(x) = x^n + Q(x)$.
Proof 2.  Again by the Lagrange Interpolation Formula, there exists a unique real polynomial $Q(x)$ of degree less than $n$ such that $Q(x_i) = y_i$.  Then it is necessary and sufficient that $P(x) = Q(x) + \prod_{i=1}^{n}(x-x_i)$.
Let $F(x)$ be the monic polynomial of degree $n$ given in the problem.  Let $x_1, \ldots, x_n$ be a sequence of strictly increasing reals, and choose $y_1, \ldots, y_n$ such that for odd $i$, $y_i > \max (0, 2F(x_i))$, but for even $i$, $y_i < \min (0, 2F(x_i))$.  Let $P(x)$ be the unique monic polynomial such that $P(x_i) = y_i$.  We shall prove that $P(x)$ and $Q(x) = 2F(x) - P(x)$ satisfy the problem's conditions.
Note that for $i < n$, $P(x_i)$ and $P(x_{i+1})$ have different signs, so $P(x)$ has a real root between $x_i$ and $x_{i+1}$.  It follows that $P(x)$ has at least $n-1$ real roots.  But a polynomial with real coefficients must have an even number of non-real roots, so $P(x)$ must have $n$ real roots.  Similarly, $Q(x)$ must have $n$ real roots.  Q.E.D.

Let $F(x)$ be our polynomial.  If $n = 1$, then we may let $F = x + a$, which is the average of the polynomials $x$ and $x + 2a$, each of which has a real root.  Otherwise, let
and let
and
We will prove that for sufficiently large $k$, $P(x)$ and $Q(x)$ satisfy the problem's conditions.
We note that for the values $1, 3, \ldots, 2n-1$ of $x$, $G(x)$ alternates in sign, and always has magnitude at least 1 (since it is the product of several factors of magnitude at least one.  On the other hand, there exists some $c$ such that for all $x \in [1, 2n-1]$, $|x^n| < c$ and $|F(n) - x^n | < c$.  Let $k$ be greater than $c$.  Then both $P(x)$ and $Q(x)$ alternate in sign for $x = 1, 3, \ldots, 2n-1$.  It follows that each has at least $n-1$ real roots.  But since a polynomial with real coefficients can only have an even number of complex roots, this means that both $P$ and $Q$ must have $n$ roots.  Q.E.D.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Let $\mathbb{R}$ be the set of real numbers.  Determine all functions $f : \mathbb{R} \rightarrow \mathbb{R}$ such that
for all pairs of real numbers $x$ and $y$.

We first prove that $f$ is  odd.
Note that $f(0) = f(x^2 - x^2) = xf(x) - xf(x) = 0$, and for nonzero $y$, $xf(x) + yf(-y) = f(x^2 - y^2) = xf(x) - yf(y)$, or $yf(-y) = -yf(y)$, which implies $f(-y) = -f(y)$.  Therefore $f$ is odd.  Henceforth, we shall assume that all variables are non-negative.
If we let $y = 0$, then we obtain $f(x^2) = xf(x)$.  Therefore the problem's condition becomes
But for any $a,b$, we may set $x = \sqrt{a}$, $y = \sqrt{b}$ to obtain
(It is well known that the only continuous solutions to this functional equation are of the form $f(x) = kx$, but there do exist other solutions to this which are not solutions to the equation of this problem.)
We may let $a = 2t$, $b = t$ to obtain $2f(t) = f(2t)$.
Letting $x = t+1$ and $y = t$ in the original condition yields
But we know $f(2t + 1) = f(2t) + f(1) = 2f(t) + f(1)$, so we have $2f(t) + f(1) = f(t) + tf(1) + f(1)$, or
Hence all solutions to our equation are of the form $f(x) = kx$.  It is easy to see that real value of $k$ will suffice.

As in the first solution, we obtain the result that $f$ satisfies the condition
We note that
Since $f(2t) = 2f(t)$, this is equal to
It follows that $f$ must be of the form $f(x) = kx$.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Let $a, b$ be integers greater than 2.  Prove that there exists a positive integer $k$ and a finite sequence $n_1, n_2, \ldots, n_k$ of positive integers such that $n_1 = a$, $n_k = b$, and $n_in_{i+1}$ is divisible by $n_i + n_{i+1}$ for each $i$ ($1 \le i \le k$).

We may say that two integers $a$ and $b$ are connected (and write $a \leftrightarrow b$) if there exists such a sequence of integers as described in the problem.  For reference, we note that $\leftrightarrow$ is an equivalence relation: it is reflexive ($a \leftrightarrow a$), symmetric ($a \leftrightarrow b$ implies $b \leftrightarrow a$), and transitive ($a \leftrightarrow b \leftrightarrow c$ implies $a \leftrightarrow c$ ).

Note that for any divisor $d$ of some $n$, $n(d-1) + n = nd \mid n^2(d-1)$, so $n \leftrightarrow n(d-1)$.  It follows that in fact $n \leftrightarrow n(d-1)^k$, for any nonnegative integer $k$, and
for any positive integer $c < d$.
For all integers $a > b > 2$, there exists some integer $\lambda$ such that $(b-1)^{\lambda} > a$.  Let
We have
But we also have
Hence $a \leftrightarrow X \leftrightarrow b$, so $a \leftrightarrow b$, as desired.

We note that for any integer $n \ge 3$, $n \leftrightarrow 2n$, for
It follows that for $n \ge 4$,
Thus all integers greater than 2 are connected.

We note that $n_i + n_{i+1} \mid n_in_{i+1}$ if and only if
Therefore for any divisor $d > n_i$ of $n_i^2$, $d - n_i \leftrightarrow n_i$.
Now, for $a \ge 2$,
Also,
This means that all positive multiples of 4 are connected.
Furthermore, for $a \ge 2$,
which implies that every even number greater than 2 is connected to a multiple of 4.
Finally, for $a \ge 3$,
Since $a(a-1)$ is even, this means that all integers greater than or equal to 2 are connected to some even number.
Together, these imply that all integers greater than 2 are connected.

We note that if $d > 2$ is a divisor of $n$, then $n \leftrightarrow n(d-1)$.
We say a positive integer $k$ is safe if for all integers $n \ge 3$, $n \leftrightarrow kn$.  Note that the product of two safe numbers is also a safe number.  Define $f(n)$ ($n>2$) to be the smallest divisor of $n$ that is greater than 2.  We will prove that 2 is safe, by strong induction on $f(n)$.  For the case $f(n) = 3$, we have $n \leftrightarrow (3-1)n = 2n$.  If $f(n) > 3$, we note that $f[n(f(n) - 1)] < f(n)$, since $f(n) - 1$ must be less than all the divisors of $n$.  Thus the inductive hypothesis gives us $[f(n) - 1]n \leftrightarrow 2[f(n) - 1]n$.  Furthermore, we have $n \leftrightarrow [f(n)-1]n$ and $2n \leftrightarrow 2[f(n)-1]n$, both from our initial note.  Thus $n \leftrightarrow 2n$.
We will now prove that every prime $p$ is safe, by strong induction.  We have already proven the base case $p = 2$.  Now, for odd $p$, $p+1$ is the product of odd primes less than $p$, so $p+1$ is safe.  Then we have
Thus the induction is complete, and all primes are safe.
We have now shown that all integers greater than 1 are safe.  Specifically, $a$ and $b$ are safe, and $a \leftrightarrow ab \leftrightarrow b$.

Similarly to the first solution, we observe that for any integer $k < a$ and any positive integers $e_1, \ldots, e_k$,
We also note that if $a \leftrightarrow b$, then for any positive integer $k$, $ka \leftrightarrow kb$, for $(a+b) \mid (ab)$ implies $k(a+b) \mid k^2(ab)$.
It is sufficient to prove that for any $a > 3$, $a \leftrightarrow (a-1)$.  If $a$ is composite, then there exist $m \ge n > 0$ such that $(a-1-m)(a-1-n) = a$, and
If, on the other hand, $a$ is prime, then we use strong induction.  For the base case, $a = 5$, we note $4 \leftrightarrow 3 \leftrightarrow 3(3-1) = 6 \leftrightarrow 5$.  Now, assuming that $a>5$ and that this holds for all primes less than $a$ (we know it holds for all composites), it is sufficient to show that $(a+1) \leftrightarrow (a-1)$, since $(a+1)$ is composite and therefore $(a+1) \leftrightarrow a$.  But since $(a+1)$ and $(a-1)$ are both even, it suffices to show that $\frac{a+1}{2} \leftrightarrow \frac{a-1}{2} = \frac{a+1}{2} - 1$.  But this is true, since $\frac{a+1}{2}$ either composite, or a prime less than $a$, and it is greater than 3, since $a > 5$.  Thus the induction is complete.