RSI 2006

For anyone interested, I got accepted and will be attending!

Zero Has No Friends. Topic: Combinatorics/Inequalities/Sets. Level: Olympiad.

Problem: (360 Problems For Mathematical Contests - 6.1.9) Find the maximum number of nonzero terms of the sum

$ \displaystyle \sum_{i,j=1}^n |f(i)-f(j)| $

where $ f:\{1,2,\ldots,n\} \rightarrow \{a,b,c\} $ is one of the $ 3^n $ possible functions.

Solution: Let $ x $ be the number of elements $ p \in \{1,2,\ldots,n\} $ such that $ f(p) = a $. Similarly define $ y $ and $ z $ to be the corresponding values for $ f(p) = b $ and $ f(p) = c $, respectively. Since there are $ n $ total values in the domain, we know $ x+y+z = n $.

We will try counting the opposite of what we want and minimizing it; the number of pairs such that $ |f(i)-f(j)| = 0 $. The number of ways we can pick two elements that map to $ a $ is $ x^2 $ ($ x $ choices for both the first and second). Similarly, the number that map to $ b $ and $ c $ are $ y^2 $ and $ z^2 $, respectively.

Now it remains to minimize $ x^2+y^2+z^2 $ for $ x+y+z = n $. By Cauchy or AM-GM, we know $ x^2+y^2+z^2 \ge \frac{1}{3}(x+y+z)^2 = \frac{n^2}{3} $. But remember that $ x,y,z $ have to be positive integers, so we have two separate cases: (1) if $ n $ is a multiple of $ 3 $, then the minimum is $ \frac{n^2}{3} $, (2) otherwise, it is $ \frac{n^2+2}{3} $.

So we then subtract the minimum number of zero terms from the total number of terms $ n^2 $ to get $ \frac{2n^2}{3} $ if $ n $ is a multiple of $ 3 $ and $ \frac{2(n^2-1)}{3} $ otherwise. This can also be stated as $ \left\lfloor \frac{2n^2}{3} \right\rfloor $. QED.

--------------------

Comment: It can be a good idea to look at the complement of what you actually are counting because it may be a lot simpler to count. This is a common technique in probability problems as well.

--------------------

Practice Problem: (360 Problems For Mathematical Contests - 6.1.6) Let $ a_1, a_2, \ldots, a_n $ be positive real numbers and let $ k \ge 0 $. Prove that

$ \displaystyle k+\sqrt[n]{\prod_{i=1}^n a_i} \le \sqrt[n]{\prod_{i=1}^n (k+a_i)} \le k +\frac{1}{n} \sum_{i=1}^n a_i $.

Set To Set. Topic: Sets. Level: Olympiad.

Problem: (360 Problems For Mathematical Contests - 6.1.4) Let $ A $ be a set with $ n $ elements and let $ X $ be a subset of $ A $ with $ k \ge 1 $ elements. Find the number of functions $ f: A \rightarrow A $ such that $ f(X) = X $.

Problem: First consider the elements of $ X $. Since $ f(X) $ has to return the same set of elements, no two elements $ a,b \in X $ can have $ f(a) = f(b) $ (or we wouldn't be able to get the entire set back). So if we pick any element $ a $ we have $ k $ choices for $ f(a) $. Then when we pick $ b $ we only have $ k-1 $ choices for $ f(b) $. Continuing this, we find that there are $ k! $ ways to assign each element in $ X $.

Now for the other $ n-k $ elements of $ A $, we can arbitrarily assign where they map to. Since each has $ n $ elements to map to, there is an additional factor of $ n^{n-k} $ to the number of functions.

This gives us a total of $ k! \cdot n^{n-k} $ possible functions $ f $. QED.

--------------------

Comment: Basic sets and functions are a good thing to know in order to build on. They don't require much mathematical background to work through, and are mostly logical (with some combinatorics).

--------------------

Practice Problem: (360 Problems For Mathematical Contests - 6.1.1) Let $ A $ be a set with $ n $ elements and let $ B $ be a subset of $ A $ with $ m \ge 1 $ elements. Find the number of functions $ f: A \rightarrow A $ such that $ f(B) \subseteq B $.

Ceva's Here! Topic: Geometry/Inequalities. Level: Olympiad.

Problem: (1996 IMO Shortlist - #13) Let $ ABC $ be an equilateral triangle and let $ P $ be a point in its interior. Let the lines $ AP, BP, CP $ meet the sides $ BC, CA, AB $ at the points $ A_1, B_1, C_1 $, respectively. Prove that

$ A_1B_1 \cdot B_1C_1 \cdot C_1A_1 \ge A_1B \cdot B_1C \cdot C_1A $.



Solution: First thing to take into account is the fact that the triangle is equilateral. There is probably a good reason for this, so let's try and find it. Applying the Law of Cosines on triangle $ A_1B_1C $, we find

$ (A_1B_1)^2 = (A_1C)^2+(B_1C)^2-A_1C \cdot B_1C $.

But since $ (A_1C-B_1C)^2 \ge 0 \Rightarrow (A_1C)^2+(B_1C)^2-A_1C \cdot B_1C \ge A_1C \cdot B_1C $, we have

$ (A_1B_1)^2 \ge A_1C \cdot B_1C $.

Similarly, $ (B_1C_1)^2 \ge B_1A \cdot C_1A $ and $ (C_1A_1)^2 \ge C_1B \cdot A_1B $. Multiplying these three inequalities together, we obtain

$ (A_1B_1 \cdot B_1C_1 \cdot C_1A_1)^2 \ge (A_1B \cdot B_1C \cdot C_1A)(A_1C \cdot B_1A \cdot C_1B) $.

But by Ceva's, we know $ A_1B \cdot B_1C \cdot C_1A = A_1C \cdot B_1A \cdot C_1B $, so

$ (A_1B_1 \cdot B_1C_1 \cdot C_1A_1)^2 \ge (A_1B \cdot B_1C \cdot C_1A)^2 $

and

$ A_1B_1 \cdot B_1C_1 \cdot C_1A_1 \ge A_1B \cdot B_1C \cdot C_1A $

as desired. QED.

--------------------

Comment: After we were able to figure out an effective way to use the equilateral condition, it wasn't hard to see the inequality there. Then the problem just asks for Ceva, which fits in nicely at the end.

--------------------

Practice Problem: (1996 USAMO - #5) 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.

Yum! Topic: Inequalities. Level: Olympiad.

Problem: Let $ a,b,c $ be positive reals such that $ a^2+b^2+c^2 = 3 $. Prove that

$ \frac{a}{a^3+a^2+4}+\frac{b}{b^3+b^2+4}+\frac{c}{c^3+c^2+4} \le \frac{1}{2} $.

Solution: We will use a method of solving inequalities called "Isolated Fudging." Since the variables are separated we will prove an inequality for each individual term. We guess that there exists a real $ k $ such that

$ \frac{a}{a^3+a^2+4} \le \frac{1}{6}+ka^2-k $.

Doing the same for each variable and summing up, we see that this will prove the result. To find $ k $, we throw in some calculus (the part ensuing is not necessary in a formal solution write-up, so you don't need to include any calculus in the "official" solution).

Let $ f(a) = \frac{1}{6}+ka^2-k-\frac{a}{a^3+a^2+4} $. Differentiating with respect to $ a $, we have

$ f^{\prime}(a) = 2ak-\frac{(a^3+a^2+4)-a(3a^2+2a)}{(a^3+a^2+4)^2} $.

Looking at the equality case in the problem, we see that $ a = b = c = 1 $. So if our guess is correct, then $ f^{\prime}(1) = 0 $. So

$ f^{\prime}(1) = 2k-\frac{1}{36} = 0 \Rightarrow k = \frac{1}{72} $.


Now back to the solution. It remains to show that

$ \frac{a}{a^3+a^2+4} \le \frac{1}{6}+\frac{1}{72}a^2-\frac{1}{72} = \frac{11}{72}+\frac{1}{72}a^2 $,

which is equivalent to

$ 72a \le (a^3+a^2+4)(a^2+11) $,

or

$ 0 \le (a-1)^2(a^3+3a^2+16a+44) $.

Since $ a $ is a positive real, we have $ a^3+3a^2+16a+44 > 0 $ and $ (a-1)^2 \ge 0 $, so it is true. Hence

$ \frac{a}{a^3+a^2+4}+\frac{b}{b^3+b^2+4}+\frac{c}{c^3+c^2+4} \le \left(\frac{11}{72}+\frac{1}{72}a^2\right) + \left(\frac{11}{72}+\frac{1}{72}b^2\right) + \left(\frac{11}{72}+\frac{1}{72}c^2\right) = \frac{1}{2} $,

as desired. QED.

--------------------

Comment: Isolated Fudging is a pretty neat trick and there are many variations on it, which are nice to learn. It lets you come up with solutions that have extremely strange numbers but magically work out.

--------------------

Practice Problem: (2005 IMO - #3) Prove that for all positive $ a,b,c $ with product at least $ 1 $,

$ \frac{a^5-a^2}{a^5+b^2+c^2} + \frac{b^5-b^2}{b^5+c^2+a^2} + \frac{c^5-c^2}{c^5+a^2+b^2} \ge 0 $.

That's The Orthocenter! Topic: Geometry/Inequalities. Level: Olympiad.

Problem: (360 Problems For Mathematical Contests - 3.1.7) Let $ a,b,c $ and $ S $ be the side lengths and the area of triangle $ ABC $. Prove that if $ P $ is a point interior to triangle $ ABC $ such that

$ a \cdot PA+b \cdot PB+c \cdot PC = 4S $

then $ P $ is the orthocenter of the triangle.



Solution: Let $ D, E, F $ be the feet of the altitudes from $ A, B, C $ respectively. Denote $ P_1, P_2, P_3 $ the projections of $ P $ onto $ AD, BE, CF $, respectively. $ D $ and $ P_1 $ are shown in the picture above.

We know $ S = [PBC]+[PCA]+[PAB] $. And since the altitudes of these three smaller triangles from $ P $ are equal in length to $ P_1D = AD-AP_1 $, $P_2E = BE-BP_2 $, $ P_3F = CF-CP_3 $, respectively, we have

$ [PBC] = \frac{1}{2}a(AD-AP_1) $

$ [PCA] = \frac{1}{2}b(BE-BP_2) $

$ [PAB] = \frac{1}{2}c(CF-CP_2) $.

So $ S = \frac{1}{2}(a \cdot AD+ b \cdot BE+ c \cdot CF) - \frac{1}{2}(a \cdot AP_1 + b \cdot BP_2 + c \cdot CP_3) $, which rearranges to

$ a \cdot AP_1+ b \cdot BP_2 + c\cdot CP_3 = a \cdot AD+ b \cdot BE+ c \cdot CF - 2S $. (1)

But since $ \frac{1}{2} a \cdot AD = \frac{1}{2} b \cdot BE = \frac{1}{2} c \cdot CF = S $, we have

$ a \cdot AD + b \cdot BE + c \cdot CF = 6S $. (2)

Substituting (2) into (1), we obtain

$ a \cdot AP_1+ b \cdot BP_2 + c\cdot CP_3 = 6S-2S = 4S $.

However, we have $ AP \ge AP_1 $, $ BP \ge BP_2 $, and $ CP \ge CP_3 $ (since they are projections) so

$ a \cdot AP + b \cdot BP + c \cdot CP \ge a \cdot AP_1+ b \cdot BP_2 + c\cdot CP_3 = 4S $.

But since the given condition implies equality, we know that $ AP = AP_1 $, $ BP = BP_2 $, and $ CP = CP_3 $, or that $ P $ lies on all three altitudes it was projected on and hence is the orthocenter. QED.

--------------------

Comment: Many times geometric conditions often arise from inequalities that have a specific equality case. In this problem, we wanted to show something was the orthocenter so we related the given lengths to the altitudes, which worked.

--------------------

Practice Problem: (360 Problems For Mathematical Contests - 3.1.14) Let $ I $ be the incenter of an acute triangle $ ABC $. Prove that

$ AI \cdot BC + BI \cdot CA + CI \cdot AB = 4S_{ABC} $

if and only if triangle $ ABC $ is equilateral.

Integrate It. Topic: Calculus.

Problem: (2003 Mu Alpha Theta National Convention) Evaluate $ \displaystyle \int \cos{(\ln{x})} dx $.

Solution: Consider the substitution $ u = \ln{x} $. We than have $ du = \frac{1}{x}dx $ so $ dx = xdu = e^udu $. It remains to evaluate the integral

$ \displaystyle \int e^u(\cos{u}) du $.

We can evaluate this by parts (set $ v = \cos{u} $, $ dw = e^udu $); we find that

$ \displaystyle \int e^u(\cos{u}) du = e^u\cos{u}+\int e^u(\sin{u})du $.

Now evaluating $ \displaystyle \int e^u(\sin{u})du $ by parts as well ($ v = \sin{x} $, $ dw = e^udu $), we have

$ \displaystyle \int e^u(\sin{u})du = e^u\sin{u}-\int e^u(\cos{u})du $,

so

$ \displaystyle \int e^u(\cos{u})du = e^u\cos{u}+e^u\sin{u}-\int e^u(\cos{u})du $

and

$ \displaystyle \int e^u(\cos{u})du = \frac{e^u\cos{u}+e^u\sin{u}}{2} $.

Substituting $ u = \ln{x} $ back, we have

$ \displaystyle \int \cos{(\ln{x})}dx = \frac{x\cos{(\ln{x})}+x\sin{(\ln{x})}}{2} $. QED.

--------------------

Comment: At first glance, the integral doesn't suggest any direct way to proceed. After the substitution, we have a more familiar integral that we know how to evaluate by parts.

--------------------

Practice Problem: (2004 Mu Alpha Theta National Convention) Evaluate $ \displaystyle \int_0^1 \int_y^1 e^{-x^2}dx dy $.

Fibby Squares. Topic: NT/Sequences & Series. Level: Olympiad.

Problem: (360 Problems For Mathematical Contests - 2.1.54) Let $ (a_n)_{n \ge 0} $ be the sequence defined by $ a_0 = 0 $, $ a_1 = 1 $ and

$ \frac{a_{n+1}-3a_n+a_{n-1}}{2} = (-1)^n $

for all integers $ n > 0 $. Prove that $ a_n $ is a perfect square for all $ n \ge 0 $.

Solution: The condition doesn't give many clues, so we find a couple of values - we see that $ a_2 = 1 $, $ a_3 = 4 $, $ a_4 = 9 $, $ a_5 = 25 $, $ a_6 = 64 $, $ a_7 = 169 $. Taking the square roots, we have the sequence $ 0, 1, 1, 2, 3, 5, 8, 13 $ which looks suspiciously like the Fibonnaci Sequence.
We claim that $ a_n = F_n^2 $ for all $ n \ge 0 $ where $ F_0 = 0 $, $ F_1 = 1 $ and $ F_{n+1} = F_n+F_{n-1} $ for $ n > 0 $.

We will proceed by induction.

Base Case - $ a_0 = F_0^2 $, $ a_1 = F_1^2 $, $ a_2 = F_2^2 $

Induction Step - $ a_{n-2} = F_{n-2}^2 $, $ a_{n-1} = F_{n-1}^2 $, and $ a_n = F_n^2 $ imply that $ a_{n+1} = F_{n+1}^2 $

Consider the two relations

$ \frac{a_n-3a_{n-1}+a_{n-2}}{2} = (-1)^{n-1} $

$ \frac{a_{n+1}-3a_n+a_{n-1}}{2} = (-1)^n $.

Adding them up, we find that the RHS becomes zero, so

$ a_{n+1}-2a_n-2a_{n-1}+a_{n-2} = 0 $

$ a_{n+1} = 2a_n+2a_{n-1}-a_{n-2} $

By our inductive hypothesis, we may substitute to obtain

$ a_{n+1} = 2F_n^2+2F_{n-1}^2-F_{n-2}^2 $.

But recall that $ F_{n-2} = F_n-F_{n-1} $, so

$ a_{n+1} = 2F_n^2+2F_{n-1}^2-(F_n-F_{n-1})^2 $,

which simplifies to

$ a_{n+1} = F_n^2+F_{n-1}^2+2F_nF_{n-1} = (F_n+F_{n-1})^2 = F_{n+1}^2 $,

completing the induction. Hence we have $ a_n = F_n^2 $ for all $ n \ge 0 $, as claimed. QED.

--------------------

Comment: Looking for a pattern is often the way to go with these problems. Once you find one, you can try to prove it, but before you have something to prove you can't do much. The $ (-1)^n $ term was also rather annoying, and the addition of the equations allowed us to get rid of it. Lastly, induction is pretty much the simplest way to go, especially with the recursive definitions.

--------------------

Practice Problem: (360 Problems For Mathematical Contests - 2.1.57) Let $ a_0 = a_1 = 3 $ and $ a_{n+1} = 7a_n-a_{n-1} $ for $ n \ge 1 $. Prove that $ a_n-2 $ is a perfect square for all $ n \ge 1 $.

Now That's Efficient. Topic: Algebra/Complex Numbers/Polynomials. Level: Olympiad.

Problem: (360 Problems For Mathematical Contests - 1.1.53) Let

$ P(x) = a_0x^n+a_1x^{n-1}+\cdots+a_n $, $ a_n \neq 0 $,

be a polynomial with complex coefficients such that there is an integer $ m $ with

$ \left| \frac{a_m}{a_n} \right| > nCm $.

Prove that the polynomial $ P $ has at least a zero with absolute value less than $ 1 $.

Solution: We will prove the result by contradiction. Assume all the zeros have absolute value (modulus) at least $ 1 $. Let the zeros be $ z_1, z_2, \ldots, z_n $. Our assumption says that $ |z_i| \ge 1 $ for all $ z_i $.

By Vieta's Formulas, we have

$ (-1)^n z_1z_2 \cdots z_n = \frac{a_n}{a_0} $ so $ |z_1z_2 \cdots z_n| = \left| \frac{a_n}{a_0} \right| $.

Also,

$ \displaystyle (-1)^m\sum z_1z_2 \cdots z_m = \frac{a_m}{a_0} $,

where the summation is taken over all sets of $ m $ roots.

Then, by the Triangle Inequality for complex numbers,

$ \displaystyle \left|\frac{a_m}{a_0}\right| = \left| \sum z_1z_2 \cdots z_m \right| \le \sum |z_1z_2 \cdots z_m| $.

But since $ |z_i| \ge 1 $ for all $ z_i $ by our assumption, we know

$ |z_1z_2 \cdots z_n| = |z_1||z_2|\cdots|z_n| \ge |z_1||z_2|\cdots|z_m| = |z_1z_2 \cdots z_m| $

and similarly for all other sets of $ m $ roots. Since there are precisely $ nCm $ sets of $ m $ roots, we have

$ \displaystyle \sum |z_1z_2 \cdots z_m| \le nCm|z_1z_2 \cdots z_n| = nCm\left| \frac{a_n}{a_0} \right| $.

Connecting the inequalities, we find that

$ \left| \frac{a_m}{a_0} \right| \le nCm\left| \frac{a_n}{a_0} \right| $,

which means

$ \left| \frac{a_m}{a_n} \right| \le nCm $,

giving us a contradiction. Hence our original assumption is false and their exists a root $ z_i $ such that $ |z_i| < 1 $ as desired. QED.

--------------------

Comment: Once again, Vieta's Formulas are extremely important to know. Also, being able to manipulate the norms of complex numbers and knowing the general properties of them is essential to solving this problem.

---------------------

Practice Problem: (360 Problems For Mathematical Contests - 1.1.58) Consider the equation

$ a_0x^n+a_1x^{n-1}+\cdots+a_n = 0 $

with real coefficients $ a_i $. Prove that if the equation has all of its roots real, then $ (n-1)a_1^2 \ge 2na_0a_2 $. Is the reciprocal true?

Para-Para-Parameter. Topic: Algebra. Level: Olympiad.

Problem: (360 Problems For Mathematical Contests - 1.1.59) Solve the equation

$ x^4-(2m+1)x^3+(m-1)x^2+(2m^2+1)x+m = 0 $

where $ m $ is a real parameter.

Solution: Well, this equation just screams to be factored... but doing so is the challenge. Instead of a quartic in $ x $ let's write it as a quadratic in $ m $.

$ (2x)m^2-(x-1)(2x^2+x+1)m+x(x-1)^2(x+1) = 0 $

after everything is factored fully. Well this looks a little more manageable, so we guess for factors. Noticing the $ x-1 $ term on the $ m $, we can see that $ x-1 $ must appear in both factors, so the square must be split. After some work, we come up with

$ [2xm-(x+1)(x-1)][m-x(x-1)] = 0 $

$ (x^2-2mx-1)(x^2-x-m) = 0 $.

Solving this, we have either

$ x^2-2mx-1 = 0 \Rightarrow x = m \pm \sqrt{m^2+1} $

or

$ x^2-x-m = 0 \Rightarrow x = \frac{1 \pm \sqrt{1+4m}}{2} $,

both just from using the quadratic formula. Hence these are our solutions for $ x $ in terms of the parameter $ m $. QED.

--------------------

Comment: This technique of switching the variable is very useful because solving quadratics is much simpler than higher degree polynomials. Problems will often give the equation in a form like this one with one variable of a large degree and another of degree two. It's possible to discover the factorization by looking at the fourth degree polynomial, but much more difficult.

--------------------

Practice Problem: (360 Problems For Mathematical Contests - 1.1.60) Solve the equation

$ x^{2n}+a_1x^{2n-1}+\cdots+a_{2n-2}x^2-2nx+1 = 0 $

if all of its roots are positive reals. [Note: Original problem omitted positive, but I think it's necessary from looking at the solution.]

Square... From Nowhere! Topic: Complex Numbers/Geometry. Level: Olympiad.

Problem: (Problem-Solving Through Problems) On the sides of an arbitrary parallelogram $ ABCD $, squares are constructed lying exterior to it. Prove that their centers $ M_1, M_2, M_3, M_4 $ are themselves the vertices of a square.



Solution: We will show a solution using complex numbers. In general, the lower case of a letter that represents a point is the complex number it corresponds to. Assume WLOG that $ A $ is at the origin, or $ a = 0 $. Then $ b $ and $ d $ are arbitrary complex numbers. Since it is a parallelogram $ c = b+d $.

$ E,F,G,H $ are the midpoints of $ AB, BC, CD, DA $, respectively, so

$ e = \frac{b}{2} $, $ f = b+\frac{d}{2} $, $ g = d+\frac{b}{2} $, and $ h = \frac{d}{2} $.

$ M_1 $ is equivalent to $ A $ rotated $ \frac{\pi}{2} $ clockwise around $ E $. In complex numbers this translates to

$ m_1 = e+(a-e)i = \frac{b}{2}-\frac{b}{2}i $.

Similarly,

$ m_2 = f+(b-f)i = \left(b+\frac{d}{2}\right)-\frac{d}{2}i $
$ m_3 = g+(c-g)i = \left(d+\frac{b}{2}\right)+\frac{b}{2}i $
$ m_4 = h+(d-h)i = \frac{d}{2}+\frac{d}{2}i $.

We want to show that these form a square, so if we rotate $ M_1 $ clockwise $ \frac{\pi}{2} $ around $ M_4 $ we should end up with $ M_3 $, and similarly for the other sets of three vertices.

Verifying that

$ m_4+(m_1-m_4)i = m_3 $
$ m_1+(m_2-m_1)i = m_4 $
$ m_2+(m_3-m_2)i = m_1 $
$ m_3+(m_4-m_3)i = m_2 $,

we know that $ M_1M_2M_3M_4 $ is indeed a square. QED.

--------------------

Comment: Complex numbers are often useful when a problem involves showing something is a square or an equilateral triangle because those rotations in the complex plane come out nicely. Sometimes the calculations can be tedious, but if geometry isn't your strong point, complex numbers is an effective way of reducing a geometry problem to an algebra one.

--------------------

Problem: (Problem-Solving Through Problems) Let $ z_1, z_2, z_3 $ be complex numbers. Show that $ z_1, z_2, z_3 $ form an equilateral triangle if and only if

$ z_1^2+z_2^2+z_3^2 = z_1z_2+z_2z_3+z_3z_1 $.

Never Goes Away... Never Goes Away! Topic: Algebra/Sequences & Series. Level: AIME/Olympiad.

Problem: (Problem-Solving Through Problems) Let $ p $ and $ q $ be real numbers with $ \frac{1}{p}-\frac{1}{q} = 1 $, $ 0 < p \le \frac{1}{2} $. Show that

$ p+\frac{1}{2}p^2+\frac{1}{3}p^3+\cdots = q-\frac{1}{2}q^2+\frac{1}{3}q^3-\cdots $.

Solution: We're going to use a little bit of *gasp* calculus for this problem, because it's pretty nice. All we need is the following two facts:

$ -\ln{(1-x)} = x+\frac{1}{2}x^2+\frac{1}{3}x^3+\cdots $

and

$ \ln{(1+x)} = x-\frac{1}{2}x^2+\frac{1}{3}x^3-\cdots $,

which are simply Taylor Series centered at zero (Maclaurin Series).

We are given $ \frac{1}{p}-\frac{1}{q} = 1 $, which we can rewrite as $ (1+q)(1-p) = 1 $, or even better,

$ \ln{(1+q)}+\ln{(1-p)} = 0 $

$ -\ln{(1-p)} = \ln{(1+q)} $.

But by our infinite series representations above, we have

$ p+\frac{1}{2}p^2+\frac{1}{3}p^3+\cdots = q-\frac{1}{2}q^2+\frac{1}{3}q^3-\cdots $,

as desired. QED.

--------------------

Comment: It turns out that with the infinite series representations the problem is really simple, so the only real step is finding those. This is easily done by experimenting with the natural log function.

--------------------

Practice Problem: Prove that $ e^{i\theta} = \cos{\theta}+i\sin{\theta} $ using infinite series.

Unprimely Speaking. Topic: Number Theory. Level: Olympiad.

Problem: (1969 IMO - #1) Prove that there are infinitely many positive integers $m$, such that $n^4+m$ is not prime for any positive integer $n$.

Solution: Well, that $ n^4 $ sure reminds us of our good old factoring trick... setting $ m = 4k^4 $ for a positive integer $ k > 1 $, we have

$ n^4+4k^4 = (n^2-2kn+2k^2)(n^2+2kn+2k^2) $.

If this is ever prime, then $ n^2-2kn+2k^2 = 1 $ (since it's the smaller factor), but we have

$ n^2-2kn+2k^2 = (n-k)^2+k^2 \ge k^2 > 1 $,

so our number is always composite. Since there are infinitely many possible values for $ k $, there are infinitely many possible values of $ m $, as desired. QED.

--------------------

Comment: This problem is nearly trivialized if you know that factoring trick, and it's an IMO problem (an old one, but that's ok). This is definitely one of the tricks you should memorize (or know how to derive instantly) because it comes in handy a lot.

--------------------

Practice Problem: (Problem-Solving Through Problems) Show that $ n^4-20n^2+4 $ is composite when $ n $ is any integer.

Lotta Solutions. Topic: Number Theory. Level: Olympiad.

Problem: (1996 Italy - #2) Prove that the equation $ a^2+b^2 = c^2+3 $ has infinitely many integer solutions $ \{a,b,c\} $.

Solution: Let $ a $ be any even integer. Setting $ b = \frac{a^2-4}{2} $ and $ c = \frac{a^2-2}{2} $, we have

$ a^2+b^2 = a^2+\left(\frac{a^2-4}{2}\right)^2 = \frac{a^4-4a^2+16}{4} = \left(\frac{a^2-2}{2}\right)^2+3 = c^2+3 $,

as desired. Hence there are infinitely many integer solutions. QED.

--------------------

Comment: With these problems it's a good idea to find solutions for some small values. I found the solutions $ (2,0,1) $, $ (4,6,7) $, and $ (6,16,17) $ from which I guessed that if we set $ b = n $, $ c = n+1 $ for some integer $ n $ we might be able to generate some solutions. After writing $ n $ in terms of $ a $, this was easy.

--------------------

Practice Problem: Find all solutions to the equation $ x^3+y^3 = z^2 $ in the positive integers.

To Infinity... And Beyond! Topic: Algebra/Inequalities. Level: Olympiad.

Problem: (1996 Ireland - #7) Prove that for all positive integers $ n $,

$ 2^{\frac{1}{2}} \cdot 4^{\frac{1}{4}} \cdots (2^n)^{\frac{1}{2^n}} < 4 $.

Solution: Clearly, the product increases, so if we show that the infinite product is equivalent to $ 4 $, we know that the partial products must always be less than $ 4 $. Rewrite the infinite product as

$ 2^{\frac{1}{2}} \cdot 2^{\frac{2}{4}} \cdot 2^{\frac{3}{8}} \cdots $.

We wish to show that

$ \frac{1}{2}+\frac{2}{4}+\frac{3}{8} \cdots = 2 $.

We can rewrite it as the sum of an infinite number of infinite geometric series, or

$ \left(\frac{1}{2}+\frac{1}{4}+\cdots\right)+\left(\frac{1}{4}+\frac{1}{8}+\cdots\right)+\cdots $,

which becomes

$ 1+\frac{1}{2}+\frac{1}{4}+\cdots = 2 $.

Hence the infinite product is equivalent to $ 2^2 = 4 $ and the partial products are $ < 4 $ as desired. QED.

--------------------

Comment: With exponents, a lot of the time its a good idea to look at the exponents themselves because it usually reduces the problem to a sum instead of a product, which is easier to work with.

--------------------

Practice Problem: Evaluate $ n^{\frac{1}{n}} \cdot (n^2)^{\frac{1}{n^2}} \cdot (n^3)^{\frac{1}{n^3}} \cdots $.

Barycentric Coordinates. Topic: Analytic Geometry. Level: Olympiad.

Definition: We define barycentric coordinates (mass points) as follows. Given a triangle $ ABC $, we have $ A(1,0,0) $, $ B(0,1,0) $, and $ C(0,0,1) $.

Let $ d(P,l) $ denote the signed distance from a point $ P $ to a line $ l $.

A point $ Q(x,y,z) $ in the plane is represented by

$ \left(\frac{d(Q,BC)}{d(A,BC)}, \frac{d(Q,CA)}{d(B,CA)}, \frac{d(Q,AB)}{d(C,AB)}\right) $.

It's easy to show that all points $ Q(x,y,z) $ satisfy $ x+y+z = 1 $.

--------------------

Theorem: Three points $ P_i(x_i,y_i,z_i) $ for $ i = 1,2,3 $ are collinear iff

$ \left|\begin{array}{ccc} x_1 \quad y_1 \quad z_1 \\ x_2 \quad y_2 \quad z_2 \\ x_3 \quad y_3 \quad z_3 \end{array} \right| $ = 0.

--------------------

Comment: The proof of this is pretty standard. It works the same way as with Cartesian coordinates (you can use vectors and cross products).

--------------------

Problem: (WOOT Message Board) Let $D, E, F$ lie on sides $BC, CA, AB$, respectively, of triangle $ABC$. Suppose that $D, E, F$ are collinear. Prove that the midpoints of $AD, BE, CF$ are collinear.

Solution: We use barycentric coordinates with triangle $ ABC $.

Since $ D $ lies on $ BC $, we know $ d(D, BC) = 0 $ so the $ x $-coordinate will be zero. Hence the coordinates of $ D $ have the form $ (0,t_1,1-t_1) $ for some real $ t_1 $.

Similarly, $ E $ is of the form $ (1-t_2, 0, t_2) $ and $ F $ is $ (t_3, 1-t_3, 0) $ for real $ t_2, t_3 $.

Since $ D, E, F $ are collinear, we know the determinant of the matrix with the three points is zero. This comes out to be

$ t_1t_2t_3-(1-t_1)(1-t_2)(1-t_3) = 0 $. (1)

We can find the midpoints by simply averaging the points (work this out rigorously if you want). These are

$ \left(\frac{1}{2},\frac{t_1}{2},\frac{1-t_1}{2}\right) $, $ \left(\frac{1-t_2}{2},\frac{1}{2},\frac{t_2}{2}\right) $, and $ \left(\frac{t_3}{2},\frac{1-t_3}{2},\frac{1}{2}\right) $.

If we take the determinant of the matrix with these three points, we find that it is equivalent to

$ \frac{t_1t_2t_3-(1-t_1)(1-t_2)(1-t_3)}{4} $

after simplification. But by (1) we know that it zero as well, which means the midpoints are indeed collinear. QED.

--------------------

Comment: Barycentric coordinates are very powerful, and give easy proofs to some results which would be very difficult without them.

--------------------

Practice Problem: (Menelaus' Theorem) Let $ D, E, F $ be points on sides $ BC , CA, AB $ (possibly extended), respectively, of triangle $ ABC $. Prove that $ D,E,F $ are collinear iff $ BD \cdot CE \cdot AF = -DC \cdot AE \cdot BF $ with signed distances.

Degree Three. Topic: Algebra/Polynomials. Level: AIME/Olympiad.

Problem: (1992 Brazil National Olympiad - #1) The equation $ x^3+px+q = 0 $ has three distinct real roots. Show that $ p < 0 $.

Solution: Let $ a,b,c $ represent the roots of the equation. By Vieta's Formulas, we have

$ a+b+c = 0 $ and $ ab+bc+ca = p $.

But since $ (a-b)^2+(b-c)^2+(c-a)^2 > 0 \Rightarrow ab+bc+ca < \frac{(a+b+c)^2}{3} = 0 $, we have $ p < 0 $ as desired. QED.

--------------------

Comment: Not a difficult problem, but an interesting result (rather general). Manipulating Vieta's Formulas is often useful when dealing with polynomials (particularly with real roots).

--------------------

Practice Problem: Find a calculus proof of the above problem.

Where's Your Paddle? Sure Does! Topic: Space Geometry/Inequalities. Level: Olympiad.

Problem: (360 Problems for Mathematical Contests - 3.1.59) Let $ P $ be a point in the interior of a tetrahedron $ ABCD $ such that its projections $ A_1, B_1, C_1, D_1 $ onto the planes $ (BCD) $, $ (CDA) $, $ (DAB) $, $ (ABC) $, respectively, are all situated in the interior of the faces. If $ S $ is the total (surface) area and $ r $ the inradius of the tetrahedron, prove that

$ \frac{S_{BCD}}{PA_1} + \frac{S_{CDA}}{PB_1} + \frac{S_{DAB}}{PC_1} + \frac{S_{ABC}}{PD_1} \ge \frac{S}{r} $.

When does equality hold? (Note: $ S_{ABC} $ represents the area of the triangle $ ABC $)

Solution: We will use the following notation to simplify things.

$ \displaystyle \sum (S_{ABC}) = S $ denotes the sum of all triangular face areas.

$ \displaystyle \sum (PA_1 \cdot S_{BCD}) $ denotes the sum of the product of the area of each triangular face with the corresponding altitude from $ P $.

Let $ V_{ABCP} $ denote the volume of the tetrahedron $ ABCP $ and $ V = V_{ABCD} $.

We have

$ \displaystyle \sum (PA_1 \cdot S_{BCD}) = 3(V_{BCDP}+V_{CDAP}+V_{DABP}+V_{ABCP}) = 3V $, (1)

by the standard formula for the volume of a tetrahedron.

Similarly, we have

$ \displaystyle r \cdot (\sum (S_{ABC})) = rS = 3V $. (2)

Combining (1) and (2), we get

$ \displaystyle \sum (PA_1 \cdot S_{BCD}) = rS $. (3)

We apply Cauchy to get

$ \displaystyle \left(\sum (PA_1 \cdot S_{BCD})\right)\left(\frac{S_{BCD}}{PA_1} + \frac{S_{CDA}}{PB_1} + \frac{S_{DAB}}{PC_1} + \frac{S_{ABC}}{PD_1}\right) \ge \left(\sum S_{ABC}\right)^2 = S^2 $.

Substituting (3) and dividing through by $ rS $, we have

$ \frac{S_{BCD}}{PA_1} + \frac{S_{CDA}}{PB_1} + \frac{S_{DAB}}{PC_1} + \frac{S_{ABC}}{PD_1} \ge \frac{S}{r} $

as desired. Equality holds iff all the

$ \frac{PA_1 \cdot S_{BCD}}{\frac{S_BCD}{PA_1}} = (PA_1)^2 $

are equal, that is, $ P $ is the incenter of $ ABCD $. QED.

--------------------

Comment: Seeing the inequality with all the fractions should immediately make one think of Cauchy. After equating volumes in a few places, the result simply falls out.

--------------------

Practice Problem: Find the point in the tetrahedron $ ABCD $ such that $ PA_1+PB_1+PC_1+PD_1 $ is minimized.

Itty Bitty Intervals. Topic: Algebra/Sets. Level: Olympiad.

Problem: (1996 Germany - #2) Suppose $S$ is a union of finitely many disjoint subintervals of $ [0, 1] $ such that no two points in $S$ have distance $ \frac{1}{10} $. Show that the total length of the intervals comprising $S$ is at most $ \frac{1}{2} $.

Solution: Consider partitioning the interval $ [0,1] $ into the pairs

$ \{\alpha, \alpha+\frac{1}{10}\} $

for $ \frac{k}{5} \le \alpha \le \frac{k}{5}+\frac{1}{10} $ with $ 0 \le k \le 4 $. By the given condition, we can have at most one value from each of these pairs so at most half of the total length, and since the total length of the interval is $ 1 $, the maximum length of $ S $ is $ \frac{1}{2} $. QED.

--------------------

Comment: Sort of an easy problem for a national olympiad, but a good exercise in sets and intervals. The hardest part about these problems is usually finding a way to prove it rigorously, instead of intuitively.

--------------------

Practice Problem: Prove that given $ n $ real numbers in the interval $ [0,1) $, there exist two such that the absolute value of their difference is at most $ \frac{1}{n-1} $.

I See Double! Topic: Geometry. Level: AIME/Olympiad.

Problem: (Problem-Solving Through Problems) Triangles $ ABC $ and $ DEF $ are inscribed in the same circle. Prove that

$ \sin{A}+\sin{B}+\sin{C} = \sin{D}+\sin{E}+\sin{F} $

if and only if the perimeters of the given triangles are equal.

Solution: Let's make use of a common theorem, the Extended Law of Sines. This tells us that in a triangle $ XYZ $ circumscribed in a circle of radius $ R $, we have

$ \frac{\sin{X}}{x} = \frac{\sin{Y}}{y} = \frac{\sin{Z}}{z} = \frac{1}{2R} $

where $ x,y,z $ are the sides opposite angles $ X,Y,Z $ respectively. The proof of this is quite simple; try finding it.

So applying this to our triangles $ ABC $ and $ DEF $ with equal circumradii $ r $, we have

$ \sin{A} = \frac{a}{2r} $, $ \sin{B} = \frac{b}{2r} $, $ \sin{C} = \frac{c}{2r} $

and

$ \sin{D} = \frac{d}{2r} $, $ \sin{E} = \frac{e}{2r} $, $ \sin{F} = \frac{f}{2r} $,

where the sides are defined in the standard way. So

$ \sin{A}+\sin{B}+\sin{C} = \sin{D}+\sin{E}+\sin{F} $

if and only if

$ \frac{a}{2r}+\frac{b}{2r}+\frac{c}{2r} = \frac{d}{2r}+\frac{e}{2r}+\frac{f}{2r} $

$ a+b+c = d+e+f $,

which means their perimeters are equal, as desired. QED.

--------------------

Comment: Equating perimeters is often a strange thing, because the relationship of equivalent perimeters isn't particularly useful. In this case, however, noticing that their circumradii are the same immediately leads one to think of the Extended Law of Sines, which works out nicely with the trigonometry in the condition.

--------------------

Practice Problem: Prove the Extended Law of Sines.

Card Tricks. Topic: Logic. Level: Olympiad.

Problem: (2005 MOP Lecture, Reid Barton) A deck of $ 50 $ cards contains two cards labeled $ n $ for each $ n = 1, 2, . . . , 25 $. There are $ 25 $ people seated at a table, each holding two of the cards in this deck. Each minute every person passes the lower-numbered card of the two they are holding to the right. Prove that eventually someone has two cards of the same number.

Solution: This is an interesting problem, which requires a little more than just math to figure out; it's a lot more logic, in fact.

Consider the position of the cards numbered $ 25 $. If a single person holds both, we are done. Or else, they don't move at all (since they are the biggest).

Next consider the position of the cards numbered $ 24 $. Again a single person cannot hold them, or we're done. The only way these can be passed is if someone holds both $ 24 $ and $ 25 $. But then, after a finite number of passes, the cards numbered $ 24 $ will not be passed anymore (since there are only two cards bigger).

Similarly, the cards numbered $ 23, 22, \ldots, 14 $ will be stationary after a finite number of passes (since there are at most $ 22 $ cards bigger than any of them).

Clearly, once all $ 24 $ of these cards are stationary, they must be held by different people. Call the person without one of these cards $ P $.

Then we look at the cards numbered $ 13 $. They will be passed on every move unless person $ P $ obtains it, which must happen in a finite number of moves. After person $ P $ obtains one of the cards, he or she does not pass it because the bigger cards are already distributed among the other people. Hence the other card numbered $ 13 $ will eventually reach person $ P $ as well.

Thus eventually someone will be holding two cards of the same number. QED.

--------------------

Comment: We note that this problem can be extended from $ 25 $ to any odd integer by the same argument. The key to this problem was realizing that the big cards have a lot less possibility of moving (seems obvious) so it's not difficult to "monitor" them.

--------------------

Practice Problem: (2005 MOP Lecture, Reid Barton) A deck contains $n$ cards labeled $1, 2, . . . , n$. Starting with an arbitrary ordering of the cards, repeat the following operation: if the top card is labeled $k$, reverse the order of the top $k$ cards. Prove that eventually the top card will be labeled $1$.

It's Game Time! Topic: Algebra/Polynomials. Level: Olympiad.

Problem: (2002 MOP Homework - #7) Peter and Alex play a game starting with an ordered pair $ (a,b) $. On each turn, the current player increases or decreases either $ a $ or $ b $: Peter by $ 1 $, Alex by $ 1 $ or $ 3 $. Alex wins if at some point in the game the roots of $ x^2+ax+b $ are integers. Is it true that given any initial values of $ a $ and $ b $, Alex can guarantee that he wins?

Solution: We claim that Alex can guarantee that he wins for any initial values of $ a $ and $ b $. Call an ordered pair $ (a,b) $ "good" if Alex can win regardless of who starts.

We claim that if $ (a,b) $ is good, then $ (-a,b) $ is good as well. This is clear because $ (a,b) $ is good implies that $ x^2+ax+b = (x-r_1)(x-r_2) $ for integers $ r_1, r_2 $. Then $ x^2-ax+b = (x+r_1)(x+r_2) $ which also has integer roots. So it is sufficient to show that $ (a,b) $ is good for all $ a $ and $ b $ with the same sign.

First, we will show that if $ |a| \le 1 $ and $ |b| \le 1 $, then $ (a,b) $ is good.

Case 1. $ (0,0) $: $ x^2 $ has integer root $ 0 $. It is good.

Case 2. $ (1,0) $: $ x^2+x $ has integer roots $ 0, -1 $. It is good.

Case 3. $ (-1,0) $: $ x^2-x $ has integer roots $ 0, 1 $. It is good.

Case 4. $ (0,-1 $: $ x^2-1 $ has integer roots $ -1, 1 $. It is good.

Case 5. $ (0,1) $: $ x^2+1 $. If Peter starts, he must change $ b $ or Alex will decrease $ b $ to zero and the roots will be integral. But if he decreases $ b $, it becomes the same as Case 1, and if he increases it, Alex can decrease by $ 3 $ and it will become the same as Case 4. If Alex starts, he can decrease $ b $ by $ 1 $ to get Case 1. So it is good.

Case 6. $ (1,-1) $: $ x^2+x-1 $. If Peter starts, decreasing $ a $ or increasing $ b $ will result in Cases 4 and 2, respectively. If he does not change $ b $, Alex can increase $ b $ by $ 1 $ to get integer roots. And if he decreases $ b $ then $ x^2+x-2 $ has roots $ -2, 1 $. If Alex starts, he can increase $ b $ by $ 1 $ to get integer roots. So it is good.

Case 7. $ (1,1) $: $ x^2+x+1 $. If Peter starts, decreasing either $ a $ or $ b $ will reduce it to Cases 5 and 2, respectively. So he must increase one of them. If he increases $ a $, $ x^2+2x+1 $ has root $ -1 $, and if he increases $ b $, Alex may decrease $ b $ by $ 3 $ to get Case 6. So it is good.

Case 8. $ (-1,-1) $: $ x^2-x-1 $. Follows from Case 6. It is good.

Case 9: $ (-1,1) $: $ x^2-x+1 $. Follows from Case 7. It is good.

We claim that if the ordered pairs $ (x,y) $ for $ x,y \in \{0,1,2,\cdots,m\} $ (with $ m \ge 1 $) are good, then the ordered pairs containing $ m+1 $ are good as well. If this is true, then all ordered pairs $ (a,b) $ with $ a,b $ nonnegative are good. We will proceed by induction.

Base Case - We know $ (0,0) $, $ (0,1) $, $ (1,0) $, and $ (1,1) $ are good.

Induction Step - We have $ (x,y) $ for $ x,y \in \{0,1,2,\cdots,m\} $ good.

Take any ordered pair $ (m+1,n) $ or $ (n,m+1) $ for $ n \in \{0,1,2,\ldots,m\} $. If Peter goes first, then he must make one of the variables not be a member of the set $ \{0,1,2,\ldots,m\} $. But Alex can change it by either $ 1 $ or $ 3 $ such that it becomes a member of the set again (since the set has size at least $ 2 $). Then the case $ (m+1,m+1) $ can be reduced to one of the previous cases as well. If Alex goes first, he can also reduce it to $ (m,n) $ and then it's the same as if Peter went first with the ordered pair $ (m,n) $. This completes the induction.

Similarly, we can do this for all ordered pairs of negative numbers and show that they are good, and by an above claim all ordered pairs with integers of opposite sign are good as well. Hence all ordered pairs are good as desired. QED.

--------------------

Comment: There's probably a more straightforward solution to this problem, but basing it off an induction worked pretty well, because it's easy for Alex to reduce any ordered pair to a smaller one, hence the idea for induction.

--------------------

Practice Problem: Suppose Alex could only increase/decrease by $ 1 $ and $ 4 $. Can he still always win?

Schureal! Topic: Inequalities. Level: Olympiad.

Problem: (WOOT Message Board, Mildorf) Let $ a,b,c $ be arbitrary reals such that $ a \ge b \ge c $, and let $ x, y, z $ be nonnegative reals such that $ x+z \ge y $. Prove that

$ x^2(a-b)^k(a-c)^k+y^2(b-c)^k(b-a)^k+z^2(c-a)^k(c-b)^k \ge 0 $

where $ k $ is a positive integer.

Solution: Let's make a substitution which will help make things look a little nicer. Define $ a-b = d $ and $ b-c = e $, so $ a-c = d+e $ with $ d,e $ nonnegative reals.

For the case $ k = 1 $, we want to show that

$ x^2d(d+e)+z^2e(d+e) \ge y^2de $.

From the given condition, we have $ (x+z)^2de \ge y^2de $. (1)

Also, we know $ (xd-ze)^2 \ge 0 $. (2)

Adding up (1) and (2), we have

$ x^2d(d+e)+z^2e(d+e) \ge y^2de $

as desired.

Now we will induct on this base case. Assume for some positive integer $ n $ we have

$ x^2d^n(d+e)^n+z^2e^n(d+e)^n \ge y^2d^ne^n $. (3)

We clearly have

$ x^2d^{n+1}(d+e)^{n+1}+z^2e^{n+1}(d+e)^{n+1} = x^2d^n(d+e)^n \cdot [d(d+e)]+z^2e^n(d+e)^n \cdot [e(d+e)] $.

But since $ d(d+e) \ge de $ and $ e(d+e) \ge de $, we know that the above expression is at least

$ x^2d^n(d+e)^n \cdot (de)+z^2e^n(d+e)^n \cdot (de) \ge y^2d^ne^n (de) = y^2d^{n+1}e^{n+1} $

by (3), thus completing the induction. So the given inequality is true for all positive integers $ k $. QED.

--------------------

Comment: This is very similar to Schur's Inequality with more variables and some interesting conditions. The $ d, e $ substitution is very useful as it allows us to restrict ourselves to nonnegative reals, making multiplication on both sides of an inequality valid. We also had to find a good way to use the $ x+z \ge y $ condition, which is seen in the solution.

--------------------

Practice Problem:

Fig Newtons. Topic: Algebra/Polynomials. Level: AIME/Olympiad.

Problem: (2003 MOP Lecture, Reid Barton) If $ x < y < z $ are real numbers such that $ x+y+z = 5 $, $ x^2+y^2+z^2 = 11 $, and $ x^3+y^3+z^3 = 26 $, find $ y $.

Solution: Consider the monic polynomial $ P(a) $ of degree $ 3 $ with roots $ x,y,z $.

To find the coefficients, we use Newton Sums:

$ x+y+z = 5 $
$ xy+yz+zx = \frac{(x+y+z)^2-(x^2+y^2+z^2)}{2} = \frac{25-11}{2} = 7 $.
$ xyz = \frac{(x+y+z)^3-3(x+y+z)(x^2+y^2+z^2)+2(x^3+y^3+z^3)}{6} = \frac{125-3 \cdot 5 \cdot 11+2 \cdot 26}{6} = 2 $.

So $ P(a) = a^3-5a^2+7a-2 = (a-2)(a^2-3a+1) $. Since the roots of the quadratic are

$ a = \frac{3 \pm \sqrt{5}}{2} $,

we know that $ y = 2 $ because exactly one of the other roots is bigger than it and exactly one is smaller. QED.

--------------------

Comment: Newton Sums are a powerful idea and can help solve systems of equations very easily. Usually they are an intermediate step, but in the following USAMO problem Newton Sums give you the solution immediately.

--------------------

Practice Problem: (1973 USAMO - #4) Find all complex solutions to the system of equations

$ x+y+z = 3 $
$ x^2+y^2+z^2 = 3 $
$ x^3+y^3+z^3 = 3 $.

Cotangible. Topic: Geometry/Inequalities. Level: Olympiad

Problem: (2002 USAMO - #2) Let $ABC$ be a triangle such that

$\left( \cot \frac{A}{2} \right)^2 + \left( 2\cot \frac{B}{2} \right)^2 + \left( 3\cot \frac{C}{2} \right)^2 = \left( \frac{6s}{7r} \right)^2$,

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



Solution: At first glance, the condition seems extremely strange and convoluted, but remembering our basic triangle facts we can simplify it greatly.

First, recall that the intersection of the angle bisectors is the incenter, $ I $. Since we have a bunch of equivalent tangents (see picture), we can write $ a = x+y $, $ b = x+z $, and $ c = y+z $. Then $ s = \frac{a+b+c}{2} = x+y+z $.

Also, because radii make right angles with tangent lines, we have right triangles with which we can evaluate the cotangent terms:

$ \cot{\frac{A}{2}} = \frac{z}{r} $, $ \cot{\frac{B}{2}} = \frac{y}{r} $, $ \cot{\frac{C}{2}} = \frac{x}{r} $.

Notice that we have $ r^2 $ in the denominator of every term, so we can multiply through to get rid of it. Substituting everything in, we have

$ z^2+4y^2+9x^2 = \frac{36}{49}(x+y+z)^2 $.

To solve this, we use Cauchy to find

$ \left(1+\frac{1}{4}+\frac{1}{9}\right)(z^2+4y^2+9x^2) \ge (x+y+z)^2 $,

or

$ z^2+4y^2+9x^2 \ge \frac{36}{49}(x+y+z)^2 $.

That means the equality condition on Cauchy holds, that is

$ z = \frac{2y}{\frac{1}{2}} = \frac{3x}{\frac{1}{3}} $.

Setting this arbitrarily to $ 36k $, we have

$ z = 36k $, $ y = 9k $, $ x = 4k $.

Therefore our triangle has sides $ a = 13k $, $ b = 40k $, $ z = 45k $. So all such triangles are similar to the triangle $ T $ with side lengths $ 13, 40, 45 $. QED.

--------------------

Comment: This is actually a really cool problem and is good practice for converting geometric quantities into algebraic ones. Knowing the incircle relations is extremely useful and comes up often in olympiads.

--------------------

Practice Problem: (2000 USAMO - #2) Let $S$ be the set of all triangles ABC for which

$5 ( \frac{1}{AP} + \frac{1}{BQ} + \frac{1}{CR} ) - \frac{3}{\min\{ AP, BQ, CR \}} = \frac{6}{r}$,

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.

Back To The Coloring Books. Topic: Combinatorial Geometry. Level: Olympiad.

Problem: (1991 APMO - #2) Suppose there are $997$ points given in a plane. If every two points are joined by a line segment with its midpoint coloured in red, show that there are at least $1991$ red points in the plane. Can you find a special case with exactly $1991$ red points?

Solution: We will prove a generalization - that given any set of $ n $ points in a plane, there are at least $ 2n-3 $ distinct midpoints. We proceed by induction.

Base Case - $ n = 2 $. We have $ 2(2)-3 = 1 $ midpoint.

Induction Step - Consider one of the vertices of the convex hull of the $ k+1 $ points. Call it $ P $. Let $ C $ be the convex hull of the other $ n $ points. By our inductive hypothesis, there exist at least $ 2k-3 $ distinct midpoints in $ C $ (since any midpoint has to be inside the convex hull).

Then take the vertex of $ C $ closest to $ P $ and call it $ X $. Segment $ XP $ must be outside of the convex hull (or $ X $ would not be the closest vertex). Hence the midpoint of $ XP $ is outside of $ C $ and is distinct from any of the existing midpoints. Let $ Y $ and $ Z $ be the vertices of $ C $ consecutive with $ X $. Since $ \angle YXP+\angle ZXP < 360 $ (assume $ X, Y, Z $ not collinear and the angle outside of the convex hull is taken), one of the two is less than $ 180 $.

WLOG, assume $ \angle YXP < 180 $. Then $YP $ is not inside $ C $ either because $ \angle YXP < 180 < \angle YXZ $. Hence there exists a second midpoint outside of the convex hull and distinct from the first.

If $ C $ is a segment, take $ X, Y $ the two closest points in $ C $ to $ P $ such that $ XP < YP $. Clearly the midpoint of $ XP $ is outside of $ C $ and the midpoint of $ YP $ must lie between $ Y $ and $ P $. But then the midpoint of any two other points must be further from $ P $ than the midpoint of $ YP $, so it is distinct as well.

Therefore we have at least $ 2k-3+2 = 2(k+1)-3 $ distinct midpoints (red points), completing the induction.

Letting $ n = 997 $, we find that there must exist at least $ 2(997)-3 = 1991 $ red points, as desired.

Picking the points $ (0,0); (2,0); \ldots; (1992,0) $ gives us the midpoints $ (1,0); (2,0); \ldots; (1991,0) $ of which there are exactly $ 1991 $ of. QED.

--------------------

Comment: Combinatorial geometry is probably one of the most interesting and least-known areas of mathematics (to high school students). It showed up on last year's USAMO and most people were baffled that standard techniques didn't work (induction, pigeonhole, extremal, etc.). The idea of the convex hull is very powerful and generates many interesting results.

--------------------

Practice Problem: (2005 USAMO - #5) Let $n$ be an integer greater than $1$. Suppose $2n$ points are given in the plane, no three of which are collinear. Suppose $n$ of the given $2n$ points are colored blue and the other $n$ colored red. A line in the plane is called a balancing line if it passes through one blue and one red point and, for each side of the line, the number of blue points on that side is equal to the number of red points on the same side.

Prove that there exist at least two balancing lines.

Primessss... Topic: Number Theory. Level: Olympiad.

Problem: (1995 APMO - #2) Let$ a_1, a_2, \ldots, a_n$ be a sequence of integers with values between $2$ and $1995$ such that:

(i) Any two of the $a_i$'s are realtively prime,
(ii) Each $a_i$ is either a prime or a product of distinct primes.

Determine the smallest possible values of $n$ to make sure that the sequence will contain a prime number.

Solution: We claim that $ n = 14 $. A sequence with $ 13 $ values is

$ 41(43), 37(47), 31(53), 29(59), 23(61), 19(67), 17(71), 13(73), 11(79), 7(83), 5(89), 3(97), 2(101) $.

Suppose that there exist $ 14 $ composite numbers satisfying the given condition. Consider the smallest prime divisors of each of the $ 14 $ numbers. They must be distinct to fulfill the relatively prime condition. But since $ 41 $ is the $ 13 $th prime, one of the numbers must have smallest prime divisor $ \ge 43 $. Then that number is at least $ 43 \cdot 47 > 1995 $. Contradiction.

Hence $ n = 14 $, as claimed. QED.

Sum Big Stuff. Topic: Algebra/Sequences and Series. Level: Olympiad.

Problem: (1997 APMO - #1) Given

$ S = 1 + \frac{1}{1+\frac{1}{3}} + \frac{1}{1+\frac{1}{3}+\frac{1}{6}} + \cdots + \frac{1}{1+\frac{1}{3}+\frac{1}{6}+\cdots+\frac{1}{1993006}} $

where the denominators contain partial sums of the sequence of reciprocals of triangular numbers (i.e. $ k = \frac{n(n+1)}{2} $ for $ n = 1,2,\cdots,1996 $). Prove that $ S > 1001 $.

Solution: This is the original text; I don't know why they made it so ugly. Let's define $ S_n = \frac{1}{1+\frac{1}{3}+\cdots+\frac{2}{n(n+1)} $.

Note that $ \frac{1}{a(a+1)} = \frac{1}{a}-\frac{1}{a+1} $, so

$ 1+\frac{1}{3}+\cdots+\frac{2}{n(n+1)} = 2\left(1-\frac{1}{2}+\frac{1}{2}-\frac{1}{3}+\cdots+\frac{1}{n}-\frac{1}{n+1}\right) = \frac{2n}{n+1} $.

So $ S_n = \frac{1}{\frac{2n}{n+1}} = \frac{n+1}{2n} $. Since $ S = S_1+S_2+\cdots+S_{1996} $, we have

$ \displaystyle S = \sum_{i=1}^{1996} \frac{i+1}{2i} = \sum_{i=1}^{1996}\left(\frac{1}{2}+\frac{1}{2i}\right) = 998+\sum_{i=1}^{1996} \frac{1}{2i} $.

But we also know

$ \displaystyle \sum_{i=1}^{1996} \frac{1}{i} = 1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{1996} > 1+\frac{1}{2}+\left(\frac{1}{3}+\frac{1}{4}\right) + \left(\frac{1}{5}+\cdots+\frac{1}{8}\right) +\cdots+ \left(\frac{1}{513}+\cdots+\frac{1}{1024}\right) $.

Making all the terms in a set of parentheses equivalent to the smallest term, we have that our sum is greater than

$ 1 + \frac{1}{2} + \left(\frac{1}{4} + \frac{1}{4}\right) + \cdots+\left(\frac{1}{1024}+\cdots+\frac{1}{1024}\right) = 1+10 \cdot \frac{1}{2} = 6 $.

So

$ \displaystyle \sum_{i=1}^{1996} \frac{1}{2i} = \frac{1}{2}\sum_{i=1}^{1996} \frac{1}{i} > 3 $.

Hence

$ S > 998+3 = 1001 $ as desired. QED.

--------------------

Comment: This problem is standard in sequences and series. Telescoping sums and the harmonic series. Applying our regular ideas to it, we easily find the solution.

--------------------

Practice Problem: Prove that $ 1+\frac{1}{2}+\frac{1}{3}+\cdots $ diverges. (Hint: See the above solution)

It's The Real Deal. Topic: Algebra. Level: Olympiad.

Problem: (360 Problems for Mathematical Contests - 1.1.18) Find the real solutions to the system of equations

$ \frac{1}{x}+\frac{1}{y} = 9 $
$ \left(\frac{1}{\sqrt[3]{x}}+\frac{1}{\sqrt[3]{y}}\right) \left(1+\frac{1}{\sqrt[3]{x}}\right) \left(1+\frac{1}{\sqrt[3]{y}}\right) = 18 $.

Solution: To simplify things, make the substitution

$ a = \frac{1}{\sqrt[3]{x}} $, $ b = \frac{1}{\sqrt[3]{y}} $.

We now have the system

$ a^3+b^3 = (a+b)(a^2-ab+b^2) = 9 $
$ (a+b)(1+a)(1+b) = (a+b)(1+a+b+ab) = 18 $.

Letting $ p = a+b $, $ q = ab $, it becomes

$ p(p^2-3q) = 9 $ (1)
$ p(1+p+q) = 18 $ (2)

Adding three times (2) to (1), we have

$ p(p^2+3p+3) = 63 $,

or

$ (p-3)(p^2+6p+21) = 0 $ (3)

Since the discriminant of $ p^2+6p+21 $ is $ 6^2-4(21) < 0 $, the only real solution is $ p = 3 $. Then from (1), we have

$ 3(9-3q) = 9 \Rightarrow q = 2 $.

So $ ab = 2 \Rightarrow a = \frac{2}{b} $. So

$ p = \frac{2}{b}+b = 3 \Rightarrow b^2-3b+2 = (b-1)(b-2) = 0 $.

Then $ b = 1, 2 $ giving the solutions

$ (a,b) = (1,2); (2,1) $, which become

$ (x,y) = \left(1, \frac{1}{8}\right); \left(\frac{1}{8},1\right) $. QED.

--------------------

Comment: The only really hard part about this problem was the ugliness of the original problem. Making the right substitutions reduces it to simple algebra and solving a cubic (with an easy root if you saw it).

--------------------

Practice Problem: Prove that the equation $ a^2+4b^2+4ab+4a+8b+5 = 0 $ has no solution in the reals.

2006 AIME I.

Good luck to everyone on the AIME!

EDIT: Boo...

When, Oh When, Is It Divisible? Topic: Number Theory. Level: Olympiad.

Problem: (1998 IMO - #4) Determine all pairs $(x,y)$ of positive integers such that $x^{2}y+x+y$ is divisible by $xy^{2}+y+7$.

Solution: At first glance, this is a rather ugly problem... but the solution turns out to be not so bad. A little tedious, but that's ok!

If $ (xy^2+y+7)|(x^2y+x+y) $, then there exists a positive integer $ k $ such that $ k(xy^2+y+7) = x^2y+x+y $, or

$ 7k-y = (xy+1)(x-ky) $.

This form seems a little more useful, as factorizations usually are in divisibility problems. First we claim that all solutions have both sides nonnegative.

Suppose $ 7k-y < 0 $. But then we have

$ |7k-y| < |y| < |xy+1| < |xy+1||x-ky| $,

which is a contradiction. So both sides are nonnegative. Now consider the two cases: (1) both sides are zero, and (2) both sides are positive.

Case 1: Both sides are zero.

Then we have $ 7k-y = 0 \Rightarrow y = 7k $. And also $ (xy+1)(x-ky) = 0 $, but since $ xy+1 > 0 $ we know $ x-ky = 0 \Rightarrow x = ky = 7k^2 $. So we have all solutions of the form $ (x,y) = (7k^2, 7k) $.

Case 2: Both sides are positive.

Then $ x > ky $ so the RHS is positive. So we have

$ 7k > 7k-y = (xy+1)(x-ky) > (xy+1) > y^2k+1 $.

Hence $ y < 3 $. So we check $ y = 1, 2 $.

For $ y = 1 $, we have $ (x+8)|(x^2+x+1) $. Since

$ \frac{x^2+x+1}{x+8} = x-7+\frac{57}{x+8} $,

we have $ (x+8)|57 \Rightarrow x = 11, 49 $, giving the solutions $ (11,1) $ and $ (49,1) $.

For $ y = 2 $, we have $ (4x+9)|(2x^2+x+2) \Rightarrow (4x+9)|(4x^2+2x+4) $. Since

$ \frac{4x^2+2x+4}{4x+9} = x-\frac{7x-4}{4x+9} $,

so $ (4x+9)|(7x-4) $. But since $ 2(4x+9) > 7x-4 $, we must have $ 4x+9 = 7x-4 $, which does not have an integer solution.

Hence our only solutions are $ (x,y) = (11,1); (49,1); (7k^2, 7k) $ for positive integers $ k $. QED.

--------------------

Comment: Again, another divisibility problem in which it is very easy to overlook some solutions because they are very strange. But working through every case gives the desired solution.

--------------------

Practice Problem: (2003 IMO - #2) Determine all pairs of positive integers $(a,b)$ such that

$\frac{a^2}{2ab^2-b^3+1}$

is a positive integer.

Slickity. Topic: Inequalities. Level: Olympiad.

Problem: (2005 APMO - #2) Let $ a,b,c $ be positive reals with $ abc = 8 $. Prove that

$ \frac{a^2}{\sqrt{\left(a^3+1\right)\left(b^3+1\right)}} + \frac{b^2}{\sqrt{\left(b^3+1\right)\left(c^3+1\right)}} + \frac{c^2}{\sqrt{\left(c^3+1\right)\left(a^3+1\right)}} \ge \frac{4}{3} $.

Solution: This inequality is somewhat strange and ugly-looking with the cubes on the bottom and the square roots and the product condition. We consider the following interesting application of AM-GM:

$ a^3+1 = (a+1)(a^2-a+1) \le \left(\frac{a^2+2}{2}\right)^2 $,

since $ a+1 > 0 $ and $ a^2-a+1 > 0 $. Applying similar inequalities for $ b,c $, our inequality becomes

$ \displaystyle \sum_{cyc} \frac{4a^2}{(a^2+2)(b^2+2)} \ge \frac{4}{3} $.

Multiplying through by $ (a^2+2)(b^2+2)(c^2+2) $ and simplifying, we get

$ a^2c^2+b^2a^2+c^2b^2+2a^2+2b^2+2c^2 \ge 72 $.

Applying AM-GM again, we have

$ a^2c^2+b^2a^2+c^2b^2 \ge 3(abc)^{\frac{4}{3}} = 48 $

and

$ 2a^2+2b^2+2c^2 \ge 6(abc)^{\frac{2}{3}} = 24 $,

which sum up to the desired inequality. QED.

--------------------

Comment: The initial application of AM-GM required quite a bit of motivation to come up with. The idea was to sort of make the denominators look nicer. Noticing that $ a+1 = a^2-a+1 $ at the equality case $ a = 2 $ led to it as well.

--------------------

Practice Problem: (WOOT Message Board) Let $a, b, c$ be positive reals such that $a+b+c= 1$. Prove that

$\sqrt{ab+c} + \sqrt{bc+a} + \sqrt{ca+b} \ge 1 + \sqrt{ab} + \sqrt{bc} + \sqrt{ca} $.

AM to the GM. Topic: Inequalities. Level: Olympiad.

Problem: (2002 MOP Homework - #5) Let $ n \ge 2 $ be an integer. Show that

$ \displaystyle \sum_{i=1}^n kx_k \le nC2+\sum_{i=1}^n x_k^k $

for all nonnegative reals $ x_1, x_2, \ldots, x_n $.

Solution: The strange $ nC2 $ term bothers us. Consider rewriting it as $ nC2 = 1+2+\cdots+(n-1) $. Then the RHS becomes

$ \displaystyle nC2+\sum_{i=1}^n x_k^k = \sum_{i=1}^n (x_k^k+k-1) $.

We have

$ \displaystyle x_k^k+k-1 = x^k+1+1+\cdots+1 $ ($ k-1 $ times)

so by AM-GM,

$ x^k+1+1+\cdots+1 \ge kx_k $.

Thus

$ \displaystyle nC2+\sum_{i=1}^n x_k^k = \sum_{i=1}^n (x_k^k+k-1) \ge \sum_{i=1}^n kx_k $

as desired. QED.

--------------------

Comment: Really a pretty weak inequality because as $ n $ or any of the $ x_i $'s get big, the RHS is clearly larger than the left. But getting that constant term to go away was tricky. Oftentimes when you have big powers on one side you can AM-GM them with multiple $ 1 $'s to reduce it to a smaller power.

--------------------

Practice Problem: Given positive reals $ a,b,c $, prove that

$ a+b+c \ge 3\sqrt[3]{a\left(\frac{b+c}{2}\right)^2} $.

Function Conjunction. Topic: Number Theory. Level: Olympiad.

Problem: (2002 MOP Homework - #4) Given an odd prime $ p $, find all functions $ f: \mathbb{Z} \rightarrow \mathbb{Z} $ satisfying the following two conditions:

$ (i) $ $ f(m) = f(n) $ for all $ m, n \in \mathbb{Z} $ such that $ m \equiv n \pmod{p} $;
$ (ii) $ $ f(mn) = f(m)f(n) $ for all $ m, n \in \mathbb{Z} $.

Solution: We claim that the only such functions are $ f(n) = 0 $ for all $ n $, $ f(n) = 1 $ for all $ n $, or $ f(n) = 1 $ for $ n \not\equiv 0 \pmod{p} $ and $ f(n) = 0 $ for $ n \equiv 0 \pmod{p} $.

Note that by condition $ (i) $ it is sufficient to define $ f $ for one complete residue class modulo $ p $ (because all the other values are then determined).

Assume $ n \not\equiv 0 \pmod{p} $ for this. Let

$ k = max(|f(1)|, |f(2)|, \ldots, |f(p-1)|) $.

Since $ \{1, \ldots, p-1\} $ form a complete residue class modulo $ p $ (except $ 0 $), by condition $ (i) $ we know that $ f(n) $ takes only the values $ f(1), f(2), \ldots, f(p-1) $. Therefore

$ k = max(|f(n)|) $ for $ n \not\equiv 0 \pmod{p} $.

Suppose $ k > 1 $. Let $ a $ be the value for which $ |f(a)| = k $. Then we have

$ |f(a^2)| = |f(a)f(a)| = k^2 > k $

(and $ a^2 $ cannot be divisible by $ p $). But then $ k $ is not the maximum value as defined. Contradiction.

So $ k = 0, 1 $.

For the case $ k = 0 $, we simply have $ f(n) = 0 $ for all $ n \not\equiv 0 \pmod{p} $. Then $ f(0) = f(n)f(0) = 0 $ as well, giving us the solution $ f(n) = 0 $ for all $ n $.

For the case $ k = 1 $, there exists an $ a \not\equiv 0 \pmod{p} $ such that $ |f(a)| = 1 $. Then

$ f(a^2) = f(a)f(a) = 1 $.

But since $ (a^2,p) = 1 $, we have that $ a^2 $ is a primitive root modulo $ p $ and therefore the set $ \{a^2, a^4, \ldots, a^{2p-2}\} $ forms a complete residue class (except $ 0 $), but clearly all of these are $ 1 $ (by $ (ii) $) so $ f(n) = 1 $ for all $ n \not\equiv 0 \pmod{p} $. And

$ f(0) = f(0)f(0) \Rightarrow f(0) = 0,1 $,

both of which work. So our solutions are $ f(n) = 1 $ for all $ n $ or $ f(n) = 1 $ for $ n \not\equiv 0 \pmod{p} $ and $ f(n) = 0 $ for $ n \equiv 0 \pmod{p} $.

And the claim is proved. QED.

--------------------

Comment: The most fun part of this problem was getting it down to $ k = 0,1 $. Then it was just sort of tedious casework (though with some cool number theory) to find out all the possible functions.

--------------------

Practice Problem: (WOOT Test 7 - #4) Find all functions $f$ defined on the rational numbers such that $f(1) = 2$ and

$f(xy) = f(x)f(y) - f(x + y) + 1$

for all rational numbers $x$ and $y$.

Solve it. Topic: Number Theory. Level: Olympiad.

Problem: (WOOT Test 7 - #3) Find all ordered pairs $ (x,y) $ of positive integers such that $ 2^x = 3^y+7 $.

Solution: We claim that $ (x,y) = (4,2) $ is the only solution.

Clearly $ x = 1 $ does not work, so assume $ x>1 $.

Taking the equation $ \pmod{4} $, we have

$ 0 \equiv 3^y+3 \pmod{4} \Rightarrow y \equiv 0 \pmod{2} $.

Taking it $ \pmod{3} $, we have

$ 2^x \equiv 1 \pmod{3} \Rightarrow x \equiv 0 \pmod{2} $.

Let $ x = 2a, y = 2b $. Then

$ 2^{2a} = 3^{2b}+7 $, or

$ (2^a-3^b)(2^a+3^b) = 7 $.

Since $ 2^a+3^b > 0 $, we must have $ 2^a-3^b > 0 $ as well. But if $ a > 2 $ or $ b > 1 $, we have $ 2^a+3^b > 7 $, a contradiction. Checking $ a = 1,2 $; $ b = 1 $ we find $ (a,b) = (2,1) $ is the only solution.

Hence $ (x,y) = (2a, 2b) = (4,2) $ is the only solution, as claimed. QED.

--------------------

Comment: It's usually a good idea to work with mods in diophantine equations to reduce your possible answers. In this case, it worked out nicely because they were both even and we could factor the difference of two squares.

--------------------

Practice Problem: Go take the 2006 Mock AIME 5 below.