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 $.