Saturday, December 31, 2005

Over and Over Again. Topic: Algebra. Level: Olympiad.

Problem: (1990 USAMO - #2) A sequence of functions $\{f_n(x) \}$, is defined recursively as follows:

$f_1(x) = \sqrt{x^2 + 48}, \quad \mbox{and} \\ f_{n+1}(x) = \sqrt{x^2 + 6f_n(x)} \quad \mbox{for } n \geq 1$

For each positive integer n, find all real solutions of the equation $f_n(x) = 2x$.

Solution: So $n$ can go to infinity, which means it's probably not going to be easy to go through each $n$ one by one.

Let's start with $n=1$: $\sqrt{x^2+48} = 2x \Rightarrow 3x^2 = 48 \Rightarrow x = 4$ (we ignore the negative solution because clearly a square root cannot be negative).

Moving on to $n=2$, we find $x=4$ again as the only solution.

Here we guess that $x = 4$ is a solution for all $n$. This can easily be shown by a quick induction with base case $n=1,2$.

If $x = 4$ is a solution for $n = k$, then $f_k(4) = 8 \Rightarrow f_{k+1}(4) = \sqrt{4^2+6f_k(4)} = \sqrt{4^2+6\cdot8} = 8$ so $4$ is a solution for $n = k+1$ as well. So $x = 4$ is always a solution.

Now we're like $x = 4$ is probably the only solution because it'd be too hard to find any other ones if they were out there. So we split into two cases ($x$ always positive because square roots are positive):

CASE 1: $x < 4$.

Then $f_1(x) = \sqrt{x^2+48} > 2x$. Inducting again, we have

$f_k(x) > 2x \Rightarrow f_{k+1}(x) = \sqrt{x^2+6f_k(x)} > \sqrt{x^2+12x} > 2x$ (last step using $x<4$). So there are no solutions.

CASE 2: $x > 4$.

Then $f_1(x) = \sqrt{x^2+48} < 2x$. Inducting, we have

$f_k(x) < 2x \Rightarrow f_{k+1}(x) = \sqrt{x^2+6f_k(x)} < \sqrt{x^2+12x} < 2x$ (last step using $x>4$). So there are no solutions here either.

Therefore, the only solution for all $n$ is $x = 4$. QED.

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

Comment: Don't think this was as easy as the previous problem, but still not difficult for USAMO, at least nowadays.

Friday, December 30, 2005

Pick one, any one! Topic: Algebra. Level: Olympiad

Problem: (1989 USAMO - #5) Let $u$ and $v$ be real numbers such that

$(u + u^2 + u^3 + \cdots + u^8) + 10u^9 = (v + v^2 + v^3 + \cdots + v^{10}) + 10v^{11} = 8$.

Determine, with proof, which of the two numbers, $u$ or $v$, is larger

Solution: Consider the functions

$f(x) = 1+x+\cdots+x^8+10x^9$ and $g(x) = 1+x+\cdots+x^{10}+10x^{11}$,

which are monotonically increasing on the interval $ (0,\infty)$.

We are given that $f(u) = g(v) = 9$.

We have $g(x)-f(x) = 10x^{11}+x^{10}-9x^9 = x^9(10x-9)(x+1)$.

$f\left(\frac{9}{10}\right) = 1+\frac{9}{10}+\cdots+\frac{9^8}{10^8}+10 \cdot \frac{9^9}{10^9}$.

By summing the geometric series,

$f\left(\frac{9}{10}\right) = \frac{1-\frac{9^9}{10^9}}{1-\frac{9}{10}} + 10 \cdot \frac{9^9}{10^9}= 10-10 \cdot \frac{9^9}{10^9}+10 \cdot \frac{9^9}{10^9} = 10 > 9$.

Since f is an increasing function, $f(u) < f\left(\frac{9}{10}\right) \Rightarrow u < \frac{9}{10}$.

Hence $g(u)-f(u) = u^9(10u-9)(u+1) < 0 \Rightarrow g(u) < f(u) = 9$.

But since $g$ is an increasing function as well, we know $g(u) < g(v) = 9 \Rightarrow u < v$. QED.

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

Comment: The last problem of the 1989 USAMO, so supposedly it is difficult, but that wasn't really the case. A simple analysis of $f$ and $g$ gives us the answer quickly.

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

Practice Problem: (2002 USAMO - #4) Let $\mathbb{R}$ be the set of real numbers. Determine all functions $f: \mathbb{R} \to \mathbb{R}$ such that

$f(x^2 - y^2) = x f(x) - y f(y)$

for all pairs of real numbers $x$ and $y$.

Wednesday, December 28, 2005

All Those Digits. Topic: Number Theory. Level: Olympiad.

Problem: (2003 USAMO - #1) Prove that for every positive integer $n$ there exists an $n$-digit number divisible by $5^n$ all of whose digits are odd.

Solution: We will prove the result by induction.

Base Case: $n=1$ - $5$ works.

Suppose there exists a $k$-digit positive integer with all odd digits that is divisible by $5^k$. Call this integer $x$.

Consider the following numbers:

$1(10^k)+x, 3(10^k)+x, 5(10^k)+x, 7(10^k)+x, 9(10^k)+x$, all of which have $k+1$ digits.

Let $x = 5^ky$.

Then the above numbers become

$5^k(1(2^k)+y), 5^k(3(2^k)+y), 5^k(5(2^k)+y), 5^k(7(2^k)+y), 5^k(9(2^k)+y)$.

Notice that $1(2^k)+y, 3(2^k)+y, 5(2^k)+y, 7(2^k)+y, 9(2^k)+y$ are all different modulo $5$ (since they are in an arithmetic sequence with difference $2^{k+1}$ and $(2^{k+1},5) = 1$).

Therefore one of the numbers must be divisible by $5$. Let that one be $a$.

So one of the original numbers is $5^ka$, where $a$ is divisible by $5$. Hence the number is divisible by $5^{k+1}$ and has $k+1$ digits, as desired. This completes the induction. QED.

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

Practice Problem: (1994 USAMO - #1) Let $ k_1 < k_2 < k_3 < \cdots$ , be positive integers, no two consecutive, and let $s_m = k_1 + k_2 + \cdots + k_m$ for $m = 1,2,3, \ldots $. Prove that, for each positive integer $n$, the interval $[s_n, s_{n+1}) $ contains at least one perfect square.

Friday, December 23, 2005

Rounding Time! Topic: Number Theory. Level: AIME.

Problem: (1995 AIME - #13) Let $f(n)$ be the integer closest to $\sqrt[4]{n}$. Find

$\displaystyle \sum_{k=1}^{1995} \frac{1}{f(k)}$.

Solution: So how can we best define "integer closest?" It basically means

$ f(n) = x$ iff $ x-\frac{1}{2} < \sqrt[4]{n} < x+\frac{1}{2}$.

Note we may use strict bounds because we know $\sqrt[4]{n}$ will not have fractional part $\frac{1}{2}$.

So we can find bounds for $n$ such that $f(n) = x$.

We must have $ \left(x-\frac{1}{2}\right)^4 < n < \left(x+\frac{1}{2}\right)^4$.

Expanding, we get

$ x^4-2x^3+\frac{3}{2}x^2-\frac{1}{2}x+\frac{1}{16} < n < x^4+2x^3+\frac{3}{2}x^2+\frac{1}{2}x+\frac{1}{16}$

from which we get $4x^3+x$ integral solutions (subtract lower bound from upper).

Thus the summation can be divided into separate cases based on the value of $f(n) = x$. Since there are $4x^3+x$ terms and each has value $\frac{1}{x}$, they sum to $\frac{1}{x}(4x^3+x) = 4x^2+1$.

Since $7^4 > 1995$, we may only take this from $x = 1$ to $x = 6$, giving

$\displaystyle \sum_{i=1}^6(4i^2+1) = 4 \cdot \frac{(6)(6+1)(2 \cdot 6+1)}{6}+6 = 370$.

But this only accounts for

$\displaystyle \sum_{i=1}^6(4i^3+i) = 4\left(\frac{(6)(6+1)}{2}\right)^2+\frac{(6)(6+1)}{2} = 1785 $ terms.

So we have $1995-1785 = 210$ remaining terms, all of which are $ \frac{1}{7}$, giving the new total of $370+\frac{1}{7}(210) = 400$. QED.

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

Comment: At this point, we're happy. Why? Because it's an AIME problem and we got an integer answer! And the chances of us doing it wrong and getting an integer answer is not too high, so we are probably right.

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

Practice Problem: Find the smallest $m$ such that

$\displaystyle \sum_{k=1}^m \frac{1}{f(k)}$ exceeds $600$.

Tuesday, December 20, 2005

Back Again? Topic: Inequalities. Level: Olympiad.

Problem: (2003 USAMO - #5) Let $a,b,c$ be positive real numbers. Prove that

$ \frac{(2a+b+c)^2}{2a^2+(b+c)^2}+\frac{(2b+c+a)^2}{2b^2+(c+a)^2}+\frac{(2c+a+b)^2}{2c^2+(a+b)^2} \le 8$.

Solution: Well first of all we notice that the inequality is homogeneous. Therefore, we can set $a+b+c$ to an arbitrary value. Note that using $a+b+c = 3$ works particularly well.

Then the inequality becomes

$ \displaystyle \sum \frac{(3+a)^2}{2a^2+(3-a)^2} = \sum \frac{a^2+6a+9}{3a^2-6a+9} = \sum \left(\frac{1}{3}+\frac{8a+6}{3(a-1)^2+6}\right) $.

Well, noticing that $ \frac{8a+6}{3(a-1)^2+6} \le \frac{8a+6}{6} = 1+\frac{4a}{3}$ we have

$ \displaystyle \sum \left(\frac{1}{3}+\frac{8a+6}{3(a-1)^2+6}\right) \le \sum \frac{4}{3}(1+a) = \frac{4}{3}(3+a+b+c) = \frac{4}{3}(6) = 8$

as desired. QED.

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

Comment: This was a pretty cool problem, too. The most important part was splitting the fraction and getting rid of the quadratic term. After both the squared terms are gone, it's pretty simple to finish off with only linear and constant terms.

Monday, December 19, 2005

See Through It. Topic: Inequalities. Level: Olympiad.

Problem: (2004 USAMO - #5) Let $a,b,c > 0$. Prove that

$(a^5-a^2+3)(b^5-b^2+3)(c^5-c^2+3) \ge (a+b+c)^3$.

Solution: Note that $a^2-1$ and $a^3-1$ always have the same sign. Therefore $(a^2-1)(a^3-1) \ge 0 \Rightarrow a^5-a^2+3 \ge a^3+2$.

Then $(a^5-a^2+3)(b^5-b^2+3)(c^5-c^2+3) \ge (a^3+1+1)(1+b^3+1)(1+1+c^3) \ge (a+b+c)^3$

by Holder. QED.

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

Comment: This is probably my favorite USAMO problem just because the solution is so short and simple. And the fact that I love inequalities. But honestly, can you get another USAMO problem (especially a #5) to give such a quick solution?

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

Practice Problem: (2003 USAMO - #5) Let $a,b,c$ be positive real numbers. Prove that

$ \frac{(2a+b+c)^2}{2a^2+(b+c)^2}+\frac{(2b+c+a)^2}{2b^2+(c+a)^2}+\frac{(2c+a+b)^2}{2c^2+(a+b)^2} \le 8$.

Sunday, December 18, 2005

Sum Differences. Topic: Algebra/NT. Level: Olympiad.

Problem: (USAMO 1998 - #1) Suppose that the set $\{1,2,\ldots, 1998\}$ has been partitioned into disjoint pairs $\{a_i,b_i\} (1\le i\le 999)$ so that for all $i$, $|a_i-b_i|$ equals $1$ or $6$. Prove that the sum

$|a_1-b_1|+|a_2-b_2|+\cdots +|a_{999}-b_{999}|$

ends in the digit $9$.

Solution: Let's make things simpler by first getting rid of the absolute values by assuming WLOG that $a_i > b_i$. If this is not true, we can simply switch the two and we have the same problem.

So the given sum becomes $\displaystyle \sum a_i-\sum b_i$ (all sums taken from $i = 1$ to $i = 999$).

But we also have $ \displaystyle \sum a_i+\sum b_i = 1+2+\cdots+1998 = \frac{(1998)(1999)}{2} = 999 \cdot 1999$, which is odd.

Hence $\displaystyle \sum a_i-\sum b_i$ is odd as well (since both sums have to be integers).

But $\displaystyle \sum a_i-\sum b_i$ is the sum of $999$ numbers, all of which are $1$ or $6$. Since it's odd, however, we know that there must be an even number of $6$'s. Let $2x$ be the number of $6$'s.

Then $\displaystyle \sum a_i-\sum b_i = 6(2x)+1(999-2x) = 10x+999 \equiv 9 \pmod{10}$ as desired. QED.

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

Comment: A pretty easy USAMO problem, but it is a #1, so yeah. And no practice problems for today since I can't think of any. I might add some later.

Saturday, December 17, 2005

Always Stays the Same. Topic: Invariants. Level: AIME.

Definition: An invariant, logically defined, is simply something that stays the same after any possible transition, or move.

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

Problem #1: (WOOT Lecture) $2005$ numbers are written on a board. On each move, two numbers are erased and the positive difference is written in place of them. Can the last remaining number be $2$?

Solution: What invariant can we find here? From any two numbers $a$ and $b$ with $a > b$, our move takes $(a,b)$ to $a-b$.

Let's try the parity of the sum of all the numbers on the board. Note that the parities of $a+b$ and $a-b$ are equivalent. Thus the parity of the sum of all numbers is invariant because our move does not change it.

Since the original sum is $1+2+\cdots+2005 = \frac{(2005)(2006)}{2} = 2005 \cdot 1003$ is odd and $2$ is even, it is impossible for the last number to be $2$. QED.

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

Problem #2: (WOOT Lecture) Suppose you have a heap of $1001$ stones. On each move, you remove one stone from a heap and divide the remaining number of stones in the heap between two new heaps. Prove that you can never make all heaps have $3$ stones.

Solution: Note that on each move the number of heaps increases by $1$ and the number of stones decreases by $1$. So let's try the invariant of $heaps+stones = 1002$.

If all the heaps have $3$ stones, then we have $heaps = 3(stones)$. So $3(stones)+stones = 4(stones) = 1002$, but $1002$ is not divisible by $4$ so it is impossible. QED.

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

Comment: Invariants are super cool and powerful; they just blow me away!

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

Practice Problem #1: (WOOT Message Board) You have a coin machine. When you put a penny in, you get five nickels. When you put a nickel in, you get five pennies. If you start out with one penny, can you ever get an equal number of pennies and nickels?

Practice Problem #2: (WOOT Message Board) Is it possible to cover a $10 \times 10$ square with $25$ rectangles of size $1 \times 4$?

Thursday, December 15, 2005

Coordinatize it! Topic: Geometry. Level: Olympiad.

Problem: (2001 USAMO - #4) 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.

Solution: Personally, I like to kill geometry problems by putting them on the coordinate plane, which can sometimes be an extremely effective way, as shown here.

WLOG, assume $A$ is the point $(0,0)$ and $B$ be $(1,0)$.

Let $C$ be $(x,y)$.

We want to show that $x > 0$ (then $\angle BAC < 90^{\circ}$).

Let $P$ be $(a,b)$.

By the given condition, we have $PA^2 > PB^2+PC^2$, giving

$a^2+b^2 > (a-1)^2+b^2+(a-x)^2+(b-y)^2$.
$0 > (a-1)^2+x(x-2a)+(b-y)^2$.

Now suppose $x \le 0$. The $(b-y)^2$ term can be arbitrarily small, so we have

$(a-1)^2+x(x-2a)+(b-y)^2 \ge (a-1)^2+x(x-2a) = a^2-(2+2x)a+(1+x^2)$.

The discriminant of this (as a quadratic in $a$) is $(2+2x)^2-4(1+x^2) = 8x \le 0$, so

$0 > (a-1)^2+x(x-2a)+(b-y)^2 \ge a^2-(2+2x)a+(1+x^2) \ge 0$

since it can have at most one root for $a$.

But that gives a contradiction, so $x > 0 \Rightarrow \angle BAC$ is acute.

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

Practice Problem: Do this problem geometrically.

Tuesday, December 13, 2005

Equilateralism. Topic: Geometry/Inequalities. Level: AIME.

Problem: Let $a,b,c$ be the side lengths of a triangle and $S$ be its area. Given that

$48S^2 = (a^2+b^2+c^2)^2$,

the triangle must be equilateral.

Solution: Well we have an annoying $S$ on the LHS, so how can we get rid of it... it's a good idea to get a few main formulas down for the area of a triangle, including Heron's:

$ [ABC] = \sqrt{s(s-a)(s-b)(s-c)} $

where $s = \frac{a+b+c}{2}$. So if we just plug that into our condition, we get

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

This is where some experience with inequalities comes in hand. Try applying AM-GM to get

$ (a+b-c)(a-b+c)(-a+b+c) \le \left(\frac{a+b+c}{3}\right)^3 $.

Multiply that by a factor of $3(a+b+c)$ to get

$ 3(a+b+c)(a+b-c)(a-b+c)(-a+b+c) \le \frac{1}{9}(a+b+c)^4 $.

By Cauchy or AM-QM, we have $ (a+b+c)^2 \le 3(a^2+b^2+c^2)^2 $, so

$ \frac{1}{9}(a+b+c)^4 \le (a^2+b^2+c^2)^2 $.

Then

$ 3(a+b+c)(a+b-c)(a-b+c)(-a+b+c) \le (a^2+b^2+c^2)^2$

with equality iff $ a = b = c $, but equality is the given condition, so the triangle is equilateral. QED.

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

Practice Problem #1: Prove Heron's Formula.

Practice Problem #2: Given a quadrilateral $ABCD$ with an inscribed circle of radius $r$, prove that $AB+BC+CD+DA \ge 8r$ and find the equality condition.

Sunday, December 11, 2005

A Little Logic Goes a Long Way. Topic: Logic/Sets. Level: AIME

Problem: (1983 AIME - #13) For each non-empty subset of $\{1, 2, 3, 4, 5, 6, 7\}$ arrange the members in decreasing order with alternating signs and take the sum. For example, for the subset $\{5\}$ we get $5$. For $\{6, 3, 1\}$ we get $6 - 3 + 1 = 4$. Find the sum of all the resulting numbers. [Source: http://www.kalva.demon.co.uk/aime/aime83.html]

Solution: Well, if you were really in a tenacious mood, you could take all $128$ of the subsets and add it all up. But I'm not, so we'll attack it with some logic.

Consider some subset $S$ of $\{1,2,3,4,5,6\}$. It has some value, call it $x$ when arranged in the given manner. What happens we you add $7$ to $S$? Clearly $7$ has to be the new biggest element. Thus the signs of each of the other elements switches, which means the new subset $S+\{7\}$ has value $7-x$. Adding up $S$ and $S+\{7\}$, we have $x+(7-x) = 7$.

And this works for ANY subset $S$, so if we pair the subsets of $\{1,2,3,4,5,6,7\}$ accordingly, we have the sum of the values of each pair to be $7$. And since there are $128$ total subsets, we have $64$ pairs and an answer of $(64)(7) = 448$. QED.

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

Comment: As you can see, this argument is pretty slick in killing off this problem in a few moments. Though a #13 on the 1983 AIME, it would be something like a #6 probably on an AIME now.

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

Practice Problem: Let $(x,y)$ be distinct, relatively prime elements of $\{1,2,\ldots,10\}$. Let $z = x+y$. Find the sum of all values of $z$.

Saturday, December 10, 2005

Broot Force. Topic: Polynomials. Level: AIME.

Problem: (2001 AIME1 - #3) Find the sum of the roots of the polynomial $x^{2001} + \left(\frac{1}{2} - x\right)^{2001}$. [Source: http://www.kalva.demon.co.uk/aime/aime01a.html]

Solution: So this isn't really brute force as the post title suggests, but it was a funny play on words so yeah.

We remember back here we used the one and only Vieta's Formulas, and we can do so again.

So let's check the biggest power, $2001$. We get coefficients of 1 from the first term and -1 from the second. But wait, that gives us $1+(-1) = 0$ as the coefficient of $x^{2001}$. What now?

In case you haven't figured out, the polynomial is actually of degree $2000$ instead, so we need to coefficients on $x^{2000}$ and $x^{1999}$. Expanding using the Binomial Theorem, we get

$ 2001C2000 \left(\frac{1}{2}\right)x^{2000} - 2001C1999 \left(\frac{1}{2}\right)^2x^{1999} = \frac{2001}{2}x^{2000}-(2001)(250)x^{1999}$,

which by Vieta's Formulas yields $ \frac{(2001)(250)}{\frac{2001}{2}} = 500 $ as the desired answer. QED.

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

Practice Problem #1: Prove Vieta's Formula for the sum of the roots of a polynomial.

Practice Problem #2: (1996 AIME - #5) The roots of $x^3+3x^2+4x-11$ are $a,b,c$. The equation with roots $a+b,b+c,c+a$ is $x^3+rx^2+sx+t$. Find $t$. [Source: http://www.kalva.demon.co.uk/aime/aime96.html]

Thursday, December 8, 2005

Connect the Dots. Topic: Space Geometry. Level: AMC/AIME.

Problem: (2004 AIME1 - #3) P is a convex polyhedron with $26$ vertices, $60$ edges and $36$ faces. $24$ of the faces are triangular and $12$ are quadrilaterals. A space diagonal is a line segment connecting two vertices which do not belong to the same face. How many space diagonals does P have? [Source: http://www.kalva.demon.co.uk/aime/aime04a.html]

Solution: What defines a space diagonal? The question tells us that "a space diagonal is a line segment connecting two vertices which do not belong to the same face." So we're basically choosing two points and connecting them, with several exceptions. Let's get the basics down first.

We have $26$ vertices. If we take any two at a time, there are $26C2 = 325$ ways of doing that.

But do we count anything we don't want? How about edges and the diagonals on the faces of the squares? We don't want those, but all of them are counted anyway. So we subtract away the number of edges and twice the number of squares ($2$ diagonals per square) to get $325 - 60 - 2(12) = 241$ space diagonals. QED.

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

Comment: A relatively easy AIME problem, requiring only basic counting and knowledge of a little space geometry. The AIME usually has a few space geometry problems so it's good to brush up on your 3-dimensional problem solving.

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

Practice Problem #1: Suppose in the above problem that the number of edges was not given. How would you solve the problem then?

Practice Problem #2: Suppose in the above problem that neither the number of edges nor the number of vertices were given. Is the problem still solvable?

Monday, December 5, 2005

The Stronger the Better. Topic: Inequalities. Level: Olympiad.

So for the next couple of days I'm just going to provide solutions to the problems I listed below, since I think they're pretty cool problems.

Problem: (2000 USA TST - #1) Given three non-negative reals $a,b,c$ prove that

$\frac{a+b+c}{3}-\sqrt[3]{abc} \le \max\{(\sqrt{a}-\sqrt{b})^2, (\sqrt{b}-\sqrt{c})^2, (\sqrt{c}-\sqrt{a})^2\}$.

Solution: Let's prove a stronger inequality, that

$a+b+c-3(\sqrt[3]{abc}) \le (\sqrt{a}-\sqrt{b})^2+(\sqrt{b}-\sqrt{c})^2+ (\sqrt{c}-\sqrt{a})^2$.

Make sure you understand why this is stronger (notice that the new RHS is less than three times the old RHS). So we have some ugly radicals here that we'd like to get rid of - try substituting $a = x^6, b = y^6, c = z^6$. Our inequality becomes

$x^6+y^6+z^6-3x^2y^2z^2 \le (x^3-y^3)^2+(y^3-z^3)^2+(z^3-x^3)^2$

which reduces down to

$2(x^3y^3+y^3z^3+z^3x^3) \le x^6+y^6+z^6+3x^2y^2z^2$.

But by Schur, we know

$\displaystyle \sum_{cyc} x^2(x^2-y^2)(x^2-z^2) \ge 0$

$ \displaystyle x^6+y^6+z^6 +3x^2y^2z^2 \ge \sum_{cyc} (x^4y^2+x^4z^2) $,

where a cyclic summation is taken over the variables "cycled" in order (e.g. $\displaystyle \sum_{cyc} x^2y = x^2y+y^2z+z^2x$).

Then, by AM-GM, we have $ \displaystyle \sum_{cyc} (x^4y^2+x^4z^2) = \sum_{cyc} (x^4y^2+y^4x^2) \ge \sum_{cyc} (2x^3y^3)$, so

$ \displaystyle x^6+y^6+z^6 +3x^2y^2z^2 \ge \sum_{cyc} (2x^3y^3) = 2(x^3y^3+y^3z^3+z^3x^3) $

as desired. QED.

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

Comment: This is pretty easy for a USA TST problem, even if it was a #1. The strongest inequality necessary was Schur and it was already all homogenized and everything.

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

Practice Problem: Prove the inequality by assuming WLOG $(\sqrt{a}-\sqrt{b})^2$ is the maximum of the three.

Sunday, December 4, 2005

Just Practice. Topic: All. Level: AIME/Olympiad.

Practice Problem #1: (2000 USA TST - #1) Given three non-negative reals $a,b,c$ prove that

$\frac{a+b+c}{3}-\sqrt[3]{abc} \le \max\{(\sqrt{a}-\sqrt{b})^2, (\sqrt{b}-\sqrt{c})^2, (\sqrt{c}-\sqrt{a})^2\}$

Practice Problem #2: (2004 AIME1 - #3) P is a convex polyhedron with $26$ vertices, $60$ edges and $36$ faces. $24$ of the faces are triangular and $12$ are quadrilaterals. A space diagonal is a line segment connecting two vertices which do not belong to the same face. How many space diagonals does P have? [Source: http://www.kalva.demon.co.uk/aime/aime04a.html]

Practice Problem #3: (2001 AIME1 - #12) Find the inradius of the tetrahedron with vertices $(6,0,0)$, $(0,4,0)$, $(0,0,2)$ and $(0,0,0)$. [Source: http://www.kalva.demon.co.uk/aime/aime01a.html]

Practice Problem #4: (2001 AIME1 - #3) Find the sum of the roots of the polynomial $x^{2001} + \left(\frac{1}{2} - x\right)^{2001}$. [Source: http://www.kalva.demon.co.uk/aime/aime01a.html]

Saturday, December 3, 2005

That 3rd Dimension. Topic: Space Geometry. Level: AIME.

Problem: (1983 AIME - #11) $ABCD$ is a square side $6\sqrt{2}$. $EF$ is parallel to the square and has length $12\sqrt{2}$. The faces $BCF$ and $ADE$ are equilateral. What is the volume of the solid $ABCDEF$? [Source: http://www.kalva.demon.co.uk/aime/aime83.html]

1983 AIME - #11

Solution #1: Here's the generic cut-it-up, add-it-up solution. Divide the solid into three pieces, a triangular prism in the middle plus two tetrahedrons on the ends. Use the Pythagorean Theorem to find the length of the edges of the triangles. We find that the area of the triangular face of the prism is $18\sqrt{2}$. So the volume of the prism is

$(18\sqrt{2})(6\sqrt{2}) = 216$.

Then we have the "height" of the tetrahedrons as the remaining portions of $EF$, or $3\sqrt{2}$ each. So the volume of each is

$ \frac{(18\sqrt{2})(3\sqrt{2})}{3} = 36 $.

But we have two, making a total volume of $216+36+36 = 288$. QED.

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

Comment: This solution is actually rather easy, especially when tackling an AIME #11. Simple applications of the Pythagorean Theorem and space geometry volume formulas kill it quickly. Consider the following solution - a more elegant approach to the problem.

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

Solution #2: Consider two of these solids, connected by the square base, but with the corresponding $EF$'s perpendicular (rotate $90^{\circ}$). What shape is this? It's actually a regular tetrahedron with edge length $EF = 12\sqrt{2}$.

Well, we know the formula for the volume of a tetrahedron is $\frac{s^3\sqrt{2}}{6}$ (derive this if you have not in the past), so the volume of the two combined shapes is

$\frac{(12\sqrt{2})^3\sqrt{2}}{6} = 576$.

But we want half of that, so we get $288$, confirming our previous answer. QED.

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

Practice Problem #1: Derive the formulas for the volumes of a regular tetrahedron and octahedron.

Practice Problem #2: Find the volume of the inscribed and circumscribed spheres of a regular tetrahedron of side length $1$.

Friday, December 2, 2005

Pigeon, I Choose You! Topic: Pigeonhole Principle. Level: AIME.

Problem: Prove that in an $(n+1)$-element subset of $\{1,2,\ldots, 2n\}$ for a positive integer $n$, there exists two numbers that divide one another.

Solution: Consider the greatest odd divisor of each element. We have $n+1$ of these, one from each of the elements. All the odd divisors are $ < 2n$. But there are only $n$ odd numbers $ < 2n$. So by the Pigeonhole Principle, we have that two of the greatest odd divisors are equal ($n+1$ Pigeons in $n$ Holes). Then the element with a smaller power of $2$ divides the element with a larger power of $2$. QED.

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

Comment: The problem at first probably doesn't look quite as easy as it turns out to be, thanks to our favorite Pigeonhole Principle. Problems involving sets and NT can many times be solved by the Pigeonhole Principle; it's only necessary to find out what the Pigeons are and what the Holes are. The Pigeonhole Principle can be generalized to the infinite case as well - given an infinite number of Pigeons and a finite number of Holes, there must be an infinite number of Pigeons in one Hole.

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

Practice Problem #1: Given $50$ points on a $7 \times 7$ square, prove that there exists two points that are within $\sqrt{2}$ units of each other. Generalize this for an $n \times n$ square.

Practice Problem #2: Given a set $S$ of $51$ integers, prove that there exist $a,b \in S$ such that $100|(a+b)$ or $100|(a-b)$. Generalize this for $n|(a+b)$ or $n|(a-b)$.

Thursday, December 1, 2005

Factor That! Topic: Factoring. Level: AMC/AIME/Olympiad.

Problem #1: Find all values for which we have $x^3+3x^2+3x+1$ a positive number.

Solution Consider rewriting $x^3+3x^2+3x+1 = (x+1)^3$. Then we know $x+1$ has to be positive so $x>-1$. QED.

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

Comment: This is a quite simple application of a very powerful technique, which we can derive some very cool inequalities from as well.

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

Problem #2: Prove that $ x^2y+x^2z+y^2z+y^2x+z^2x+z^2y \le x^3+y^3+z^3+3xyz $ for positive reals $x,y,z$.

Solution: Notice that something like Rearrangement doesn't quite cut it here because we have the $3xyz$ on the LHS. So we consider factoring this into

$ 0 \le x(x-y)(x-z)+y(y-z)(y-x)+z(z-x)(z-y) $.

Well this looks pretty good, all symmetric and stuff. But how do we prove it? Let's try first assuming WLOG that $ x \ge y \ge z$ because of symmetry. Then

$ x(x-y)(x-z)+y(y-z)(y-x) \ge 0 $

and

$ z(z-x)(z-y) \ge 0 $.

Add them up and we have our desired inequality. QED.

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

Comment: This is known as Schur's Inequality and can be generalized to $ x^n(x-y)(x-z)+y^n(y-z)(y-x)+z^n(z-x)(z-y) \ge 0$ for $n$ a positive integer with equality at $x=y=z$ or $x=0, y=z$ and permutations of that.

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

Practice Problem #1: Prove that, given three positive reals $a,b,c$, we have $ x^2y^2+x^2z^2+y^2z^2+y^2x^2+z^2x^2+z^2y^2 \le x^4+y^4+z^4+x^2yz+y^2zx+z^2xy$.

Practice Problem #2: Factor $ a^3+b^3+c^3-3abc $.

Wednesday, November 30, 2005

Can you count? Topic: Probability. Level: AMC/AIME.

Problem: (2005 AMC 12B - #25) Six ants are on the vertices of a regular octahedron - one on each vertex. Simultaneous and independently, they each traverse one edge and arrive at another vertex. What is the probability that no two ants arrive at the same vertex?

Solution: We wish to count the number of ways the ants can move such that no two arrive at the same vertex. Consider viewing the octahedron as two points with a square between them such that the square is perpendicular to the line containing the two points. Note that two of the ants on the square must move off and the two off the square must move on.
-----
CASE 1: Two ants opposite each other on the square move off.

There are two possible pairs of ants and each pair has two ways of moving off (each one can go to either point off the square). That's $4$ possibilities.

Now consider the remaining two ants on the square. There are two ways they can move such that they don't arrive at the same vertex. That's $2$ possibilities.

Now consider the two ants off the square. There are two ways they can move onto the square (each can go to either open point). That's $2$ possibilities.

So we have $4 \cdot 2 \cdot 2 = 16$ possibilities for the first case.
-----
CASE 2: Two ants adjacent to each other on the square move off.

There are four pairs of ants adjacent to each other on the square. Each pair can move off in two different ways (same argument as CASE 1). That's $8$ possibilities.

The remaining two ants can move anywhere on the square and not be at the same vertex, giving $4$ possibilities.

The two ants off the square can move onto the square in two different ways (same argument as CASE 1). That's $2$ possibilities.

So we have $8 \cdot 4\cdot 2 = 64$ possibilites for the second case.
-----
Now consider the total possible ways satisfying the condition: $16+64 = 80$. And the total number of ways the ants can move $4^6$ (each ant has $4$ places it can go). Thus our desired probability is

$\frac{80}{4^6} = \frac{5}{256} $.

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

Comment: Admittedly, the problem does look daunting when encountered at the end of the AMC-12, in your final minutes of the test, and I did not try very hard to solve the problem at the time, either. However, once you find a relatively simple method to analyze the number of ways (viewing it as two points and a square - consider the possible pairs on the square), the real counting process is quite simple. And the problem seems to just finish itself.

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

Practice Problem #1: Repeat the problem above, but use a tetrahedron instead of an octahedron.

Practice Problem #2: Consider a regular hexagon with all its diagonals drawn in. What is the probability that, given any two of the seven points (including the center - intersection of the diagonals), the line segment between the points is drawn?

Practice Problem #3: Four points are randomly chosen in the plane. What is the probability that the quadrilateral they form is convex?

Tuesday, November 29, 2005

Inequalities Revisited. Topic: Inequalities. Level: Olympiad.

Theorem: (Rearrangement Inequality) Given two nondecreasing sequences of positive reals $x_1 \le x_2 \le \cdots \le x_n$ and $y_1 \le y_2 \le \cdots \le y_n$,

$ \displaystyle \sum_{i=1}^n x_iy_i \ge \sum_{i=1}^n x_iy_{\delta(i)} $,

where $ \delta $ is some permutation of $1,2, \ldots, n $.

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

Comment: The Rearragement Inequality is extremely useful, and can quickly kill some inequalities that may be a hassle to AM-GM over and over again, as you'll see in the next example. The proof of the theorem simply requires considering a possible permutation, subtracting it away from the maximum, and showing that the difference is greater than zero.

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

Problem: (1999 United Kingdom - #7) Given three non-negative reals $p,q,r$ such that $p+q+r = 1$, prove that

$ 7(pq+qr+rp) \le 2+9pqr $.

Solution: We notice that the inequality we wish to prove is not homogenous - that is, the sums of the powers on the terms are not equal. Most of the classical inequalities require you to homogenize, and given our condition, we can do so (by multiplying by $p+q+r$ when necessary). After homogenizing, the inequality becomes

$ 7(pq+qr+rp)(p+q+r) \le 2(p+q+r)^3+9pqr $.

Now this may look uglier than before, but we notice a lot of terms cancel, leaving (you may do the algebra yourself if you wish)

$ p^2q+p^2r+q^2r+q^2p+r^2p+r^2q \le 2(p^3+q^3+r^3) $.

With enough experience, this will be an obvious direct result of Rearrangement, but to explicitly use it, we set (applied three times with $n = 2$ and WLOG assuming $p \le q \le r$):

$ x_1 = p^2 \le x_2 = q^2 $
$ y_1 = p \le y_2 = q $, from which we have

$ \displaystyle \sum_{i=1}^2 x_iy_i = p^3+q^3 \ge \sum_{i=1}^2 x_iy_{\delta(i)} = p^2q+q^2p $

where $ \delta = 2,1 $. As you can see applying this on the pairs $ (p,r); (q,r) $ the same way and summing them up, we get the desired result

$ p^2q+p^2r+q^2r+q^2p+r^2p+r^2q \le 2(p^3+q^3+r^3) $.

QED.

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

Comment: An "extension" of the Rearrangement Inequality, is the Muirhead Inequality, which effectively demolishes symmetric, homogenized inequalities.


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


Practice Problem #1: Prove, using Rearrangement, the Trivial Inequality:

$ (x-y)^2 \ge 0 $

for positive reals $x,y$.

Practice Problem #2: Prove, using Rearrangement, a special case of the Power-Mean Inequality:

$ \sqrt[n]{\frac{x^n+y^n+z^n}{3}} \ge \frac{x+y+z}{3} $

for a positive integer $n$ and positive reals $x,y,z$.

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

$ \frac{a}{b+c} + \frac{b}{a+c} + \frac{c}{a+b} \ge \frac{a}{a+b} + \frac{b}{b+c} + \frac{c}{c+a} $.

Monday, November 28, 2005

Add Them Up. Topic: Sequences & Series. Level: AIME/Olympiad.

Problem: (1989 USAMO - #1) For each positive integer $n$, let

$ S_n = 1+\frac{1}{2}+ \cdots + \frac{1}{n} $

$ T_n = S_1+S_2+ \cdots + S_n $

$ U_n = \frac{T_1}{2}+\frac{T_2}{3} +\cdots + \frac{T_n}{n+1} $

Find, with proof, integers $0 < a,b,c,d < 1000000 $ such that $T_{1988} = aS_{1989}-b $ and $ U_{1988} = cS_{1989}-d $.

Solution: Well let's start with the first condition - $T_{1988} = aS_{1989}-b $. We claim that

$ T_n = (n+1)(S_{n+1}-1) $.

Consider writing $T_n$ as sum of the following sequences:

$S_1 = 1$
$S_2 = 1+\frac{1}{2} $
...
$S_n = 1+\frac{1}{2}+ \cdots +\frac{1}{n} $.

Notice that $1$ appears $n$ times, $\frac{1}{2}$ appears $n-1$ times, and more generally $\frac{1}{i}$ appears $ n+1-i $ times. Then we can say

$\displaystyle T_n = \sum_{i=1}^n \frac{n+1-i}{i} = (n+1)\sum_{i=1}^n \frac{1}{i} - \sum_{i=1}^n 1 = (n+1)S_n-n = (n+1)\left(S_{n+1}-\frac{1}{n+1}\right)-n = (n+1)(S_{n+1}-1) $

as claimed. Also, save the fact that $ T_n = (n+1)S_n - n $.

So then $T_{1988} = 1989(S_{1989}-1) = 1989S_{1989}-1989 \Rightarrow a = b = 1989 $.

Now, using $ T_n = (n+1)(S_{n+1}-1) $, we substitute into the $ U_n $ equation to get

$ \displaystyle U_n = \sum_{i=1}^n \frac{T_n}{n+1} = \sum_{i=1}^n \frac{(n+1)(S_{n+1}-1)}{n+1} = \sum_{i=1}^n S_{n+1} - \sum_{i=1}^n 1 = \sum_{i=1}^n S_{n+1} - n $.

But recall that $\displaystyle \sum_{i=1}^n S_{n+1} = T_{n+1}-1 $ and remember the fact we saved back up there, so our final equation becomes

$ U_n = T_{n+1}-(n+1) = (n+2)S_{n+1}-(n+1)-(n+1) = (n+2)S_{n+1}-2(n+1)$.

So $ U_{1988} = 1990S_{1989}-3978 \Rightarrow c = 1990, d = 3978 $.

Thus our final answer is $ a = 1989, b = 1989, c = 1990, d = 3978 $. QED.

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

Comment: This was back in 1989, when the USAMO was a one-day, $ 3 \frac{1}{2} $ hour test with five problems. Not until 1996 did it become a two-day test.

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

Practice Problem #1: Do the problem again with $ T_{2005} $ and $ U_{2005} $ instead, to fully understand the solution.

Practice Problem #2: Show that $ T_n+\ln{(n+1)} > U_n+n $ for all positive integers $n$.

Sunday, November 27, 2005

Circular Reasoning. Topic: Geometry. Level: AMC/AIME.

Problem #1: (2006 Mock AIME 1 - #1) $2006$ points are evenly spaced on a circle. Given one point, find the number of other points that are less than one radius distance away from that point.

Solution: We know that one radius distance is equivalent to $ \frac{1}{6} $ of the circumference (by constructing an equilateral triangle with the center and two points on the circle).

We know each point is $\frac{1}{2006} $ of the circumference away from each other, so the $k$th point is $ \frac{k}{2006} $ arc distance away. We want $ \frac{k}{2006} < \frac{1}{6} \Rightarrow k \le 334 $. But since it can be on either side, we double that, to get $668.$. QED.

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

Comment: Note that this following AMC-12 problem is considerably more difficult than the preceding AIME problem, though it happens quite often that a AMC-12 #25 is more difficult than an AIME #1.

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

Problem #2: (2003 AMC 12B - #25) Three points are chosen randomly and independently on a circle. What is the probability that all 3 pairwise distances between the points are less than the radius of the circle?

Solution : Now on the surface it looks pretty easy, but remember, this is a #25 - chances are it won't come too quickly for an average problem-solver (it's easy to jump into a bunch of flawed arguments). First convert everything to arc lengths - one radius becomes $\frac{1}{6}$ circumference again. Consider the following argument:

2003 AMC-12B #25

The circumference is set to $1$. Let point $A$ be the "center" of the three points, the "center" being the point that both the other points are closest to (note that the existence of the "center" is guaranteed - think about it).

Call the shortest distance between two points to be $x$ (first assume $AB = x$) - we then have the other length $1-x$. Now think about the possibilities... we want to maintain

1. The minimum distance of $x$. So the arc $AC$ has to be greater than $x$ - $AC > x$.

2. The "center" status of $A$. So the arc $BC$ has to be greater than $AC$ so $ AC < \frac{1-x}{2} $ for a given $x$. Also, $ AB $ must be less than $ BC $ (which can be as small as $\frac{1-x}{2}$), so we have $ x < \frac{1-x}{2} \Rightarrow x < \frac{1}{3}$.

(1) We can graph this such that $AB$ is on the $x$-axis and $AC $ is on the $y$-axis following these rules: $ 0 < AB < \frac{1}{3} $ and $ AB < AC < \frac{1-AB}{2} $.

(2) Now recall that we assumed $AB = x$. But $ AC $ could be $x$ as well, so we apply the same argument, flipping $AB$ and $AC$. But the graph would be the same, only flipped over the line $y=x$, creating this:

2003 AMC-12B #25 Graph

where (1) creates the red region and (2) creates the blue region (both theoretically extending into the yellow region).

Those generate the total "number" of unique possibilites, denoted by the area beneath the graph. Now we have to find the ones that satisfy our given condition: the maximum arc length is less than $ \frac{1}{6} $.

However, we notice by introducing the center status of $A$ we automatically show that our maximum arc length is $AB+AC$ because it is always greater than the independent lengths ($AB+AC > AB$ and $AB+AC > AC$ - of course this is only when $AB$ and $AC$ are both less than $\frac{1}{6}$, which is all we care about). So we add to our graph the yellow region, $AB+AC < \frac{1}{6}$.

Thus the probability is (including the extensions of the red and blue regions into the yellow) $ \frac{[yellow]}{[red]+[blue]} = \frac{\frac{1}{72}}{\frac{1}{6}} = \frac{1}{12} $. QED.

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

Comment: On the actual contest, the argument would probably be loosely made in the interest of saving time and you could probably finish something like this in 5-10 minutes at most if you knew where you were headed. Of course, given that this is the last problem of an AMC-12, I wouldn't be surprised if most people didn't have those 5-10 minutes to spare.

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

Practice Problem #1: Find the probability that two points placed on a circle randomly and independently are within one radius distance of each other.

Practice Problem #2: In an acute angled triangle $ABC$, $\angle A = 30^{\circ}$. $H$ is the orthocenter and $M$ is the midpoint of $BC$. On the line $HM$, take point $T$ such that $HM=MT$. Show that $AT= 2BC$. (hint: Use complex numbers - see Post 13: November 24th, 2005).

Practice Problem #3: Three congruent circles of radius 1 intersect at a common point. A larger circle is circumscribed about them, tangent to each of them at one point. Consider the midpoint of one of the diameters of the smaller circles; call it $P$. What is the length of the arc along the bigger circle containing all the points that are within 2 units of $P$?

Saturday, November 26, 2005

Combina-WHAT? Topic: Combinatorics. Level: AMC/AIME.

Problem #1: Prove that $ nC0+nC1+\cdots+nCn = 2^n $ ($nCk$ denotes $n$ choose $k$).

Solution: Chances are you've seen this before, and there are many proofs to it (one of my favorites being the number of subsets of an $n$-element set... think about it).

But here's another cool proof, using our very own Binomial Theorem.

Consider $ (x+1)^n = (nC0)x^n+(nC1)x^{n-1}+\cdots+(nCn) $.

But upon setting $x = 1$, we immediately have $2^n = nC0+nC1+\cdots+nCn $ as desired. QED.

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

Problem #2: Prove that $ nC0-nC1+\cdots+(-1)^n(nCn) = 0 $.

Solution: Well if you understood the concept behind the first problem, this one should come very easily.

$ (x+1)^n = (nC0)x^n+(nC1)x^{n-1}+\cdots+(nCn) $ so for $ x = -1 $ we have

$ 0 = (-1)^n(nC0)+(-1)^{n-1}(nC1)+\cdots+(nCn) $ from which we can just flip the sign (if necessary) to get the desired result. QED.

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

Practice Problem #1: Prove $ nC0+nC1+\cdots+nCn = 2^n $ using the subsets argument.

Practice Problem #2: Show that $ nCr+nC(r+1) = (n+1)C(r+1)$.

Practice Problem #3: (1983 AIME #8) Find the largest two-digit prime that divides $200C100$.

Friday, November 25, 2005

Mix it Up. Topic: Polynomials/Inequalities. Level: Olympiad.

Problem #1: (ACoPS 5.5.22) Let $P$ be a polynomial with positive coefficients. Prove that if

$ P\left(\frac{1}{x}\right) \ge \frac{1}{P(x)} $

holds for $x=1$ then it holds for every $x > 0$.

Solution: Let $P(x) = a_nx^n+a_{n-1}x^{n-1}+ \cdots + a_0 $.

We have $ P(1) \ge \frac{1}{P(1)} \Rightarrow [P(1)]^2 = (a_n+a_{n-1}+\cdots+a_0)^2 \ge 1 $.

Then we have $ P(x) \cdot P\left(\frac{1}{x}\right) = (a_nx^n+a_{n-1}x^{n-1}+ \cdots + a_0)\left(a_n\frac{1}{x^n}+a_{n-1}\frac{1}{x^{n-1}}+ \cdots + a_0)$.

But $(a_nx^n+a_{n-1}x^{n-1}+ \cdots + a_0)\left(a_n\frac{1}{x^n}+a_{n-1}\frac{1}{x^{n-1}}+ \cdots + a_0) \ge (a_n+a_{n-1}+\cdots+a_0)^2 \ge 1 $

by Cauchy (see Post 12: November 24th, 2005). QED.

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

Problem #2: (USAMO 1983 #2) Prove that the zeros of

$ x^5+ax^4+bx^3+cx^2+dx+e = 0 $

cannot all be real if $ 2a^2 < 5b $.

Solution: Hmm... coefficients of polynomials... let's break out Vieta's Formulas !

So we have $ a = -(r_1+r_2+r_3+r_4+r_5) = -\sum r_i $ (for shorthand).

And $ b = r_1r_2+r_1r_3+r_1r_4+r_1r_5+r_2r_3+r_2r_4+r_2r_5+r_3r_4+r_3r_5+r_4r_5 = \sum r_ir_j$ (again, for shorthand).

So we have $ 2a^2<5b \Rightarrow 2\left(\sum r_i\right)^2 < 5\sum r_ir_j $.

Expanding and simplifying, we have $ 2\left(\sum r_i^2\right) < \sum r_ir_j $ which can be rearranged to

$ \sum (r_i-r_j)^2 < 0 $ which clearly cannot hold if all the roots are real. QED.

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

Practice Problem #1: Given the polynomial $ x^3+ax^2+bx+c $ with real coefficients, find the condition the polynomial must satisfy such that it has at least one nonreal root (based on $a,b,c$). And generalize for $a_nx^n+a_{n-1}x^{n-1}+ \cdots + a_0$.

Practice Problem #2: (ACoPS 5.5.36) Prove Cauchy-Schwarz using the polynomial

$ f(x) = (a_1x+b_1)^2+(a_2x+b_2)^2+\cdots+(a_nx+b_n)^2 $

by observing that $f$ has real zeros iff $ \frac{a_1}{b_1} = \frac{a_2}{b_2} = \cdots = \frac{a_n}{b_n} $.

Thursday, November 24, 2005

Simpler than it Sounds. Topic: Complex Numbers. Level: AMC/AIME.

Problem #1: Find the coordinates of the point $ (5,4) $ rotated around the point $ (2,1) $ by $ \frac{\pi}{4} $ radians counterclockwise.

Solution: Consider these points in the complex plane ($x$-axis becomes real part, $y$-axis becomes imaginary part).

We want to rotate $5+4i$ around $2+i$. Rewrite these in $ (r, \theta) $ form, where $ r$ is the magnitude and $\theta$ is the angle. We also have $ (r, \theta) = e^{i\theta} $ by the Euler Formula.

So, to simplify things, we shift $2+i$ to the origin, and now we want to rotate $ 3+3i = 3\sqrt{2}e^{i\frac{\pi}{4}} $. We notice that rotation by $ \frac{\pi}{4} $ simply adds $ \frac{\pi}{4} $ to the angle, resulting in $ 3\sqrt{2}e^{i\frac{\pi}{2}} = 3\sqrt{2}i$.

Shifting back to the "real" origin, our rotated point becomes $ 2+(1+3\sqrt{2})i $ in the complex plane and $ (2, 1+3\sqrt{2}) $ in the Cartesian plane. QED.

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

Problem #2: Given that $ A(x_1,y_1) $ and $ B(x_2,y_2) $ are two vertices of an equilateral triangle, find all possible values for the third point, $ C$.

Solution: Convert them to complex numbers - $ X = x_1+y_1i $ and $ Y = x_2+y_2i$.

Notice that if we rotate $X$ around $ Y $ by $ \frac{\pi}{3} $ or $ -\frac{\pi}{3} $ radians, we get the only two possible points for $ Z $ ($C$ as a complex number).

So applying the same rotation method as in the first problem, we have $ Z = Y + (X-Y)e^{i\frac{\pi}{3}} $ or $ Z = Y+(X-Y)e^{-i\frac{\pi}{3}}$. We can translate this back to the Cartesian plane, but it's just a mess of algebra, not essential to understanding the method of rotation in the complex plane. QED.

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

Practice Problem #1: Find the value of $ A = 3+i $ rotated by $ \frac{\pi}{2} $ radians counterclockwise.

Practice Problem #2: (WOOT Class) Show that, given three complex numbers $ A, B, C$ that lie on the unit circle, the orthocenter of the triangle formed by them is $ H = A+B+C $ (hint: If two complex numbers $X, Y$ are perpendicular, $\frac{X}{Y} $ is purely imaginary... prove it).

Practice Problem #3: (WOOT Message Board) Let $O$ be the center of a circle $\omega$. Points $A,B,C,D,E,F$ on $\omega$ are chosen such that the triangles $OAB,OCD,OEF$ are equilateral. Let $L,M,N$ be the midpoints of $BC,DE,FA$, respectively. Prove that triangle $LMN$ is equilateral.

Wednesday, November 23, 2005

To Equal or not to Equal. Topic: Inequalities. Level: AIME/Olympiad.

Problem #1: Prove that, given two positive reals $a$ and $b$, we have $\frac{a+b}{2} \ge \sqrt{ab}$.

Solution: Begin with the trivial inequality ($x^2 \ge 0$) applied on $a-b$. We have

$ (a-b)^2 \ge 0$
$ a^2-2ab+b^2 \ge 0$
$ a^2+2ab+b^2 \ge 4ab$
$ (a+b)^2 \ge 4ab$
$ a+b \ge 2\sqrt{ab}$
$\frac{a+b}{2} \ge \sqrt{ab}$

as desired. QED.

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

Comment: Note that we have just derived the Arithmetic Mean-Geometric Mean Inequality, more commonly referred to as just AM-GM. This can be generalized to $n$ variables by induction, that is, $\frac{a_1+a_2+\cdots+a_n}{n} \ge \sqrt[n]{a_1a_2 \cdots a_n}$.

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

Problem #2: Given two sequences of positive reals $ \{a_i\}$ and $ \{b_i\} $ for $ i = 1,2, \ldots, n$, prove that $ (a_1^2+a_2^2+\cdots+a_n^2)(b_1^2+b_2^2+\cdots+b_n^2) \ge (a_1b_1+a_2b_2+\cdots+a_nb_n)^2$.

Solution: We shall prove this with vectors (read the previous blog post to get some background information).

Consider the vector $A = (a_1,a_2,\ldots,a_n)$ and the vector $B = (b_1,b_2,\ldots,b_n)$ (in an $n$-space).

We have $|A||B| \ge |A||B|\cos{\theta} = A \cdot B$ since $ \cos{\theta} \le 1$.

But recall that $ A \cdot B = (a_1,a_2,\ldots,a_n) \cdot (b_1,b_2,\ldots,b_n) = (a_1b_1+a_2b_2+\cdots+a_nb_n) $.

Also, $ |A| = \sqrt{a_1^2+a_2^2+\cdots+a_n^2}$ and $ |B| = \sqrt{b_1^2+b_2^2+\cdots+b_n^2} $.

Combining them, we get $ \sqrt{a_1^2+a_2^2+\cdots++a_n^2} \cdot \sqrt{b_1^2+b_2^2+\cdots+b_n^2} \ge (a_1b_1+a_2b_2+\cdots+a_nb_n) $, from which our result follows directly upon squaring both sides:

$ (a_1^2+a_2^2+\cdots+a_n^2)(b_1^2+b_2^2+\cdots+b_n^2) \ge (a_1b_1+a_2b_2+\cdots+a_nb_n)^2 $. QED.

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

Comment: This is known as Cauchy's Inequality, or the Cauchy-Schwarz Inequality. It is one of the most useful inequalities to know and can be generalized (see Holder's Inequality).

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

Problem #3: Given three positive reals $a$, $b$, and $c$, prove that $\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b} \ge \frac{3}{2}$.

Solution: Let's put our newly-learned inequalities in action!

By AM-GM, we have $a^2+b^2 \ge 2ab$. Applying this to the two other pairs and summing them up, we get

$a^2+b^2+c^2 \ge ab+bc+ca$.

Adding $2(ab+bc+ca)$ to both sides, we have

$ a^2+b^2+c^2+2(ab+bc+ca) = (a+b+c)^2 \ge 3(ab+bc+ca) \Rightarrow \frac{(a+b+c)^2}{2(ab+bc+ca)} \ge \frac{3}{2} $.

Rewrite the original LHS (left hand side) as $ \frac{a^2}{ab+ac}+\frac{b^2}{bc+ba}+\frac{c^2}{ca+cb}$. By Cauchy, we have

$ (ab+bc+bc+ba+ca+cb)\left(\frac{a^2}{ab+bc}+\frac{b^2}{bc+ba}+\frac{c^2}{ca+cb}\right) \ge (a+b+c)^2 $

with $ a_1^2 = ab+bc $, $ b_1^2 = \frac{a^2}{ab+bc}$, and similarly define $ a_2, a_3, b_2, b_3$.

So then dividing by $2(ab+bc+ca)$ and combining it with the previous inequality, we find

$ \frac{a^2}{ab+bc}+\frac{b^2}{bc+ba}+\frac{c^2}{ca+cb} \ge \frac{(a+b+c)^2}{2(ab+bc+ca)} \ge \frac{3}{2} $

as desired. QED.

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

Comment: This is known as Nesbitt's Inequality, and many of the classical inequalities can be applied to prove it.

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

Practice Problem #1: Prove the Root-Mean-Square - Arithmetic Mean Inequality - $ \sqrt{\frac{a_1^2+a_2^2+\cdots+a_n^2}{n}} \ge \frac{a_1+a_2+\cdots+a_n}{n} $.

Practice Problem #2: (IMO 1995 #A2) Given positive reals $a, b, c$ such that $abc = 1$, prove that $ \frac{1}{a^3(b+c)}+\frac{1}{b^3(c+a)}+\frac{1}{c^3(a+b)} \ge \frac{3}{2} $.

Tuesday, November 22, 2005

Vectors... wow! Topic: Vector Geometry. Level: AMC/AIME.

Problem #1: Find the area of the triangle formed by the heads of two vectors, $A = (5, 67^{\circ})$ and $B = (4, 37^{\circ})$, and the origin.

Solution: So, we have two vectors with pretty ugly angles, but we do notice that they differ by exactly $30^{\circ}$! Hmm, then we know two sides and the angle between them...

And consequently we remember the formula $ [ABC] = \frac{1}{2}ab\sin{\angle C} $, which makes us happy.

Hence the area of the triangle is $ \frac{1}{2}(5)(4)(\sin{30^{\circ}}) = 5$. QED.

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

Comment: Notice that the formula $ \frac{|A||B|\sin{\theta}}{2} = \frac{|A \times B|}{2}$, where $ A \times B $ is the cross product of $A$ and $B$.

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

Problem #2: Show that the vectors $A = (3, 4, 5)$ and $B = (2, -4, 2) $ are perpendicular.

Solution: Consider the dot product of $A$ and $B$, $ A \cdot B$. The general definition of this is $A \cdot B = |A||B|\cos{\theta}$, where $\theta$ is the angle between the two vectors. Notice that if two vectors are perpendicular to each other, the angle $\theta = 90^{\circ} \Rightarrow \cos{\theta} = 0 \Rightarrow A \cdot B = 0$.

We can easily show that the dot product is distributive (left as an exercise to the reader), that is, $A \cdot (B+C) = A \cdot B + A \cdot C$.

Thus $A \cdot B = [(3, 0, 0)+(0, 4, 0)+(0, 0, 5)] \cdot [(2, 0, 0)+(0, -4, 0)+(0, 0, 2)]$. Distributing this, we see that only the terms that are parallel remain because all the axes are perpendicular to each other ($\theta = 90^{\circ}$ between any two axes).

So $ A \cdot B = (3, 0, 0) \cdot (2, 0, 0)+(0, 4, 0) \cdot (0, -4, 0)+(0, 0, 5) \cdot (0, 0, 2) = 6 +(-16)+10 = 0$. So $A$ is perpendicular to $B$. QED.

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

Comment: In effect, we have just shown that given any two vectors $ X = (x_1, x_2, \ldots, x_n)$ and $ Y = (y_1, y_2, \ldots, y_n)$, we have $ X \cdot Y = x_1y_1+x_2y_2+\cdots+x_ny_n$, an interesting and useful result (these are all in $n$-spaces, where there actually exist $n$ dimensions).

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

Practice Problem #1: Show that the dot product is distributive: $ A \cdot (B+C) = A \cdot B+ A \cdot C$.

Practice Problem #2: Find the area of the triangle formed by the points $(5,2)$, $(7,8)$, and $(2,1)$.

Practice Problem #3: Show that, given three vectors of equal magnitude $A$, $B$, and $C$, the orthocenter of the triangle formed by the heads of each of the vectors is $A+B+C$.

Practice Problem #4: Using Practice Problem #3, show that the centroid ($G$), circumcenter ($O$), and orthocenter ($H$) of a triangle are collinear and that $ OG:GH = 1:2$.

Monday, November 21, 2005

Polynomial Power. Topic: Algebra/Polynomials. Level: AIME.

Problem: (2006 Mock AIME 1 - #14) Let $P(x)$ be a monic polynomial of degree $n \ge 1$ such that

$ [P(x)]^3 = [P(x)]^2-P(x)+6$

for $x = 1, 2, \ldots , n$. Let $n_0$ be the smallest $n$ such that $P(0) > (P(1)+P(2)+ \cdots +P(n))^3$.
Find the remainder when $P(0)$ is divided by $1000$ given $n = n_0$.

Solution: Well the condition we're given as it is doesn't look particularly helpful in defining the polynomial, especially with the cube. So we try and factor it (almost always a safe bet) and we find

$ (P(x)-2)([P(x)]^2+P(x)+3) = 0$.

But we notice that $ [P(x)]^2+P(x)+3 = \left(P(x)+\frac{1}{2}\right)^2 + \frac{11}{4} > 0$. So then we must have $ P(x)-2 = 0 $ for $x = 1, 2, \ldots, n$.

Consider the polynomial $H(x) = P(x)-2$. It has zeros at $x = 1, 2, \ldots, n$ and is also monic with degree $n$. Hence $H(x) = (x-1)(x-2)\cdots(x-n) \Rightarrow P(x) = (x-1)(x-2)\cdots(x-n)+2$.

Then we have $P(0) = (-1)^n\cdot n!+2 > (P(1)+P(2)+\cdots+P(n))^3 = (2n)^3 = 8n^3$. Checking, we find the first $n$ such that this is true is $n = 8$. Therefore, $P(0) = (-1)^8 \cdot 8!+2 = 40322$. So our answer is $322$. QED.

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

Pracitice Problem #1: Factor $ x^4+64 $.

Practice Problem #2: Let $P(x)$ be a monic polynomial of degree $n$ such that $P(x) = x$ for $x = 1,2,\ldots,n$. Find a closed expression for $P(n+1)$.

Sunday, November 20, 2005

Go Go Geometry! Topic: Geometry/Trigonometry. Level: AIME.

Problem: (2006 Mock AIME 1 - #15) Let $ABCD$ be a rectangle and $AB = 24$. Let $E$ be a point on $BC$ (between $B$ and $C$) such that $DE = 25$ and $\tan{\angle BDE} = 3$. Let $F$ be the foot of the perpendicular from $A$ to $BD$. Extend $AF$ to intersect $DC$ at $G$. Extend $DE$ to intersect $AG$ at $H$. Let $I$ be the foot of the perpendicular from $H$ to $DG$. The length of $IG$ is $\displaystyle \frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Suppose $\alpha$ is the sum of the distinct prime factors of $m$ and $\beta$ is the sum of the distinct prime factors of $n$. Find $\alpha + \beta$.

Diagram

Solution: We begin by solving for $EC = \sqrt{25^2-24^2} = 7$. Then $\tan{EDC} = \frac{7}{24}$.

By the tangent addition formula, we have

$\tan{BDC} = \tan{(BDE+EDC)} = \frac{\tan{BDE}+\tan{EDC}}{1-\tan{BDE}\tan{EDC}} = \frac{3+\frac{7}{24}}{1-3\left(\frac{7}{24}\right)} = \frac{79}{3} $.

Since $\tan{BDC} = \frac{BC}{CD}$, we have $\displaystyle BC = (CD)\tan{BDC} = 24\left(\frac{79}{3}\right) = 632$.

Notice that $\angle AGD = 90 - \angle BDC \Rightarrow \tan{AGD} = \frac{1}{\tan{BDC}} = \frac{3}{79}$.

Then $\tan{AGD} = \frac{AD}{DG} \Rightarrow DG = \frac{AD}{\tan{AGD}} = \frac{632}{\frac{3}{79}} = \frac{2^3 \cdot 79}{3}$.

Consider $\triangle HIG$. We have $\tan{HGI} = \frac{HI}{IG} \Rightarrow HI = (IG)\tan{HGI} = \frac{3}{79}(IG)$.

Notice that $\triangle EDC$ is similar to $\triangle HDI$, so $\frac{HI}{ID} = \frac{EC}{CD} = \frac{7}{24} \Rightarrow HI = \frac{7}{24}(ID) = \frac{7}{24}(DG-IG)$.

Combining our two expressions for $HI$, we get

$ HI = \frac{3}{79}(IG) = \frac{7}{24}(DG-IG)$.

Solving this for $IG$, we get

$IG = \frac{\frac{7}{24}(DG)}{\frac{3}{79}+\frac{7}{24}$.

But we calculated $DG = \frac{2^3 \cdot 79}{3}$ above, so upon substitution we get

$IG = \frac{\frac{7}{24}\left(\frac{2^3 \cdot 79}{3}\right)}{\frac{3 \cdot 24 + 7 \cdot 79}{24 \cdot 79}} = \frac{2^3 \cdot 7 \cdot 79^3}{3 \cdot 5^4} $.

Summing the distinct prime factors, we have $2+7+79+3+5 = 96$.

Thursday, November 17, 2005

2006 Mock AIME 1.

Here is the first AoPS Mock AIME of the 2005-2006 year, written by yours truly. If you wish to participate officially, please create an AoPS account at the AoPS forum.

2006 Mock AIME 1

Date: Friday, Nov. 18th to Sunday, Nov. 20th, 2005
Time: 3 hours, self-timed
Format: 15 questions, Free Response (ALL answers are integers from 000 to 999, inclusive)
Scoring: 1 point per correct answer (No guessing penalty)
Submitting Answers: PM the answers to me, paladin8.
Answer Format: (As follows)

1. Answer to #1
2. Answer to #2
...
15. Answer to #15

2006 Mock AIME 1 Questions

P.S. I'll be gone the next two days, so don't expect blog posts.

EDIT: Ack, #14 should be taken mod 1000, to get an AIME answer, my mistake to anyone who has taken it already. I'll modify the actual PDF file when I get home.

EDIT 2: All better.

EDIT 3: #15 was also written incorrectly (hey, it's not that easy to write hard AIME problems); fixed now.

Wednesday, November 16, 2005

Modular Math. Topic: Number Theory. Level: AMC/AIME.

Problem: What is the remainder when you divide $6^{2005}+8^{2005}$ by $49$?

Solution Modular arithmetic is a useful tool for this problem. The concept is really quite simple:

We state that $a \equiv b \pmod{c} \Rightarrow c|(a-b)$,

that is, $a$ and $b$ leave the same remainder upon division by $c$.

We rewrite the problem as evaluating $6^{2005}+8^{2005} \pmod{49}$.

The key to this problem is noticing that $6 = 7-1$ and $8 = 7+1$. Rewrite them as such:

$(7-1)^{2005}+(7+1)^{2005}$.

Applying our handy Binomial Theorem, we see that

$\displaystyle (7-1)^{2005} = (2005C0)(7^{2005}) - (2005C1)(7^{2004}) + \ldots +(2005C2004)(7)-(2005C2005)$.

Consider this $\pmod{49}$ or $\pmod{7^2}$. We note that any term with a power of $7$ greater than or equal to $2$ is $0 \pmod{49}$ (make sure you get this, review the definition of mod if you don't). Thus the only terms that we need to consider are the last two: $\displaystyle (2005C2004)(7)-(2005C2005) = 2005(7)-1$.

Similarly, the only two terms of $(7+1)^{2005}$ we need to consider are $\displaystyle (2005C2004)(7)+(2005C2005) = 2005(7)+1$.

Summing the two, we have $(2005(7)-1)+(2005(7)-1) = 4010(7) \equiv 42 \pmod{49}$ (you can work out the details yourself). Hence our answer is $42$. QED.

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

Comment: Modular arithmetic has extremely wide applications in Number Theory, including a number of important theorems you should be familiar with (e.g. Fermat's Little Theorem). Learning this concept will increase your ability to solve NT problems dramatically. If you just love Number Theory and want to learn more about it, check out the PROMYS website; it's a summer camp devoted entirely to NT.

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

Practice Problem: Find the remainder when $1+10+10^2+\ldots+10^{2005}$ is divided by $9$.

Tuesday, November 15, 2005

Power of a Point. Topic: Geometry. Level: AMC/AIME.

Problem: Given a circle that passes through the points $(3,4)$ and $(6,8)$, find the length of a tangent to the circle from the origin.

Solution: Consider Power of a Point, which states that

Power of a Point

$a^2 = b(b+c) = d(d+e)$, all of which are equal to the power of the point at which they intersect.

Now consider the tangent from the origin in the problem (call this length $x$) and notice that the secant from the origin through $(3,4)$ passes through $(6,8)$ as well.

Then by Power of a Point applied to the origin, we have $x^2 = (\sqrt{3^2+4^2})(\sqrt{6^2+8^2}) = (5)(10) = 50 \Rightarrow x = \sqrt{50}$. QED.

Note: On the actual contest (ARML) a third point was provided to define the circle. We notice, however, that this third point is not necessary and was thus omitted in this rewording of the problem.

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

Practice Problem: Given two circles, find all points $P$ such that the power of point $P$ with respect to both circles is equal.

Monday, November 14, 2005

Diophantine Fun. Topic: Number Theory. Level: AIME.

Problem: Find all integer solutions $(m,n)$ to the equation

$n^4+n^3+2n^2+2n+1 = m^2$.

Solution: Let me introduce a technique used to solve diophantine equations with a power (square in this case) on one side and a multiple of that power (fourth power) on the other: Bounding.

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

Example - Suppose you had the equation $n^2+3n+3 = m^2$ (assume positive integers for the example; it is not necessary for the actual problem though). We can say

$(n+1)^2 < n^2+3n+3 < (n+2)^2$ which can be verified by expanding.

The LHS becomes $0 < n+2$ and the RHS becomes $0 < n+1$.

But there are no integer squares between $(n+1)^2$ and $(n+2)^2$ so we can conclude that there are no solutions.

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

Now back to the problem... we look for bounding squares; however, this requires some experimenting and matching coefficients. We want to match at least the first two terms - $n^4+n^3$.

After playing around with squares, we find a pretty good bound that works for $n \ge 4$ and $n \le 0$:

$\displaystyle \left(n^2+\frac{n}{2}+\frac{1}{2}\right)^2 \le n^4+n^3+2n^2+2n+1 \le \left(n^2+\frac{n}{2}+1\right)^2$.

The LHS becomes $\displaystyle 0 \le \frac{3}{4}(n+1)^2$ and the RHS $\displaystyle 0 \le n\left(\frac{n}{4}-1\right)$ (hence the restrictions on $n$).

Since there are no squares between $\displaystyle \left(n^2+\frac{n}{2}+\frac{1}{2}\right)^2$ and $\displaystyle \left(n^2+\frac{n}{2}+1\right)^2$, the only possible solutions are the equality conditions and $n=1,2,3$.

Checking those three, we find nothing, so we move to the equality conditions.

As noted above, the equality conditions are $\displaystyle 0 = \frac{3}{4}(n+1)^2$ and $\displaystyle 0 = n\left(\frac{n}{4}-1\right)$, giving the solutoins $n=-1, 0, 4$. Then $m = \pm 1, \pm 1, \pm 19$, respectively.

Hence our solutions are: $(m,n) = (-1, \pm 1); (0, \pm 1); (4, \pm 19)$. QED.

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

Practice Problem: Find all nonnegative integer solutions $(a,b)$ to the equation

$a^6+2a^4+2a^2+2a+1 = b^2$.

Hello!

Welcome to my blog! This will be an ongoing journal of mathematical problems and problem solving techniques, targetted at high school students like myself aiming to do well on the American Math Competitions. The difficulty will range from mostly difficult AMC problems to USAMO problems. Enjoy!