Monday, January 30, 2006

Not All Odd. Topic: Number Theory/Geometry. Level: AIME.

Problem: Show that there do not exist four lattice points such that the pairwise squares of the distances between the points are all odd integers.

Solution: WLOG, assume that one of the points is the origin. We can do so because it can just be translated to any other point in the plane. Let the other points be $ (x_1,y_1) $; $ (x_2,y_2) $; and $ (x_3,y_3) $.

Since the origin is one of our points, we know $ x_1^2+y_1^2 $, $ x_2^2+y_2^2 $, and $ x_3^2+y_3^2 $ are all odd. So each pair $ (x_i,y_i) $ for $ i= 1,2,3 $ must have one odd and one even (so that the sum of the squares will be odd). Then by Pigeonhole, we have two $ x $'s with the same parity. Then since the $ y $'s have the opposite parity as the $ x $'s, they are also the same.

Let $ (x_a,y_a) $ and $ (x_b,y_b) $ be the points with the same parity on both coordinates. Then $ x_a-x_b $ and $ y_a-y_b $ are both even. Hence the square of the distance between these two points is $ (x_a-x_b)^2+(y_a-y_b)^2 $, which is even because the sum of two even numbers is even. Therefore, not all the pairwise squares of distances can be odd. QED.

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

Comment: Originally came from a different problem, which I misread and came up with a solution for this problem instead. Well, anyway, it's not particularly difficult, but it's nice to WLOG a point to the origin and make things cleaner, as you can probably tell.

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

Practice Problem: (Olympiad Problem Solving MidTerm) Show that there do not exist four points in the Euclidean plane such that the pairwise distances between the points are all odd integers. (Note: They don't have to be lattice points; that's where I misread it.)

Saturday, January 28, 2006

A Bunch of Rectangles. Topic: Pigeonhole Principle. Level: Olympiad.

Problem: (Olympiad Problem Solving MidTerm) Suppose we have $101$ rectangles with sides of integer lengths not exceeding $100$. Prove that there exist three of these rectangles, which we call $A$, $B$, and $C$, such that $A$ fits wholly inside $B$ and $B$ fits wholly inside $C$. (Note: If two rectangles are identical, then each ‘fits’ inside the other.)

Solution: Well, again the numbers suggest Pigeonhole, so we get right to it. We want to construct sets of rectangles such that any three rectangles in each set would satisfy the condition. It might help to redefine the condition. Let $ l_X $ and $ w_X $ denote the length and width of rectangle $ X $, respectively. We may assume $ w_X \le l_X $ or we just switch the values for $ l_X $ and $ w_X $ to obtain the same rectangle. We want to find rectangles $ A,B,C $ such that $ w_A \le w_B \le w_C $ and $ l_A \le l_B \le l_C $.

Consider plotting rectangles on the coordinate plane with the axes equal to $ w_X $ and $ l_X $. All the rectangles lie below or on the line $ w_X = l_X $ (shown in blue below. We want to create fifty different holes to guarantee that three fall into a single one; all while keeping in mind that any three in a hole must satisfy our condition. Consider the following holes (shown in red):

OlyPS-19

If we continue these sets of red lines until the entire portion of the graph we want is full, we will have exactly fifty. Algebraically defined, we have

$ S_k = \{(w_X,l_X) | w_X = k, k \le l_X \le 101-k\} \cup \{(w_X, l_X) | l_X = 101-k, k \le w_X \le 101-k} $ for $ 1 \le k \le 50 $.

Since we have $ 50 $ holes and $ 101 $ pigeons, we know there are at least $ 3 $ pigeons in a single hole, or three rectangles in a single set. From the graph, it's easy to see that if three rectangles lie on either the vertical or horizontal line of any set, they fit within each other. They all have one equal dimension, so we just arrange the other dimension in nondecreasing order. If two lie on a vertical line and the third on the horizontal, the third is clearly the smallest and then arrange the other two in nondecreasing order by length. Similarly, if two lie on a horizontal line and a third on the vertical, the third is the largest and arrange the other two in nondecreasing order by width. Hence the problem is solved. QED.

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

Comment: More good Pigeonhole practice. Transfering the problem onto the graph and then determining the sets were the key steps, and the details pretty much worked themselves out from there. It's often a good idea to reduce things to algebra instead of geometry - in reality, this problem had nothing to do with geometry.

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

Practice Problem: If you wanted four rectangles that fit inside each other, how many total rectangles would you need? Five? $ n $?

Friday, January 27, 2006

Big-gon. Topic: Pigeonhole Principle. Level: Olympiad.

Problem: (Olympiad Problem Solving MidTerm) At each of the vertices of a regular $100$–gon one of the numbers $1, 2, \ldots , 49$ is written. Prove
that there are $4$ vertices $A,B,C,D$ of this polygon such that

(a) $AB \parallel CD$, and
(b) if the numbers written at $A,B,C,D$ are $a, b, c, d$, respectively, then $a + b = c + d$.

Solution: Well looking at the numbers given, it's not terribly difficult to guess that it is a Pigeonhole problem (the $100$ and the $49$ are pretty good indicators). But what are the pigeons and the holes?

Consider the longest diagonals (connecting two opposite vertices). There are $50$ of these, conveniently enough. Label each of these diagonals with the absolute value of their difference. These differences range from $ 0 $ to $ 48 $ because the maximal difference is $ 49-1 = 48 $ and the minimal is clearly zero from the absolute value.

Now let the possible differences be the holes and the diagonals be the pigeons; since we have $49$ holes and $50$ pigeons, there are two diagonals with equal differences. Let $x,y$ be the endpoints of the first and $z,w$ the endpoints of the second.

We know that $ |x-y| = |z-w| $. Also note that $ x,y,z,w $ form a rectangle because it has two diagonals of equal length which bisect each other. Thus the opposite sides are parallel. If $ x-y = z-w $, we have $ x+w = z+y $, but those are opposite sides and hence parallel and we are done. If $ x-y = w-z $, we have $ x+z = w+y $, which again are opposite sides so we are done here, too. Hence the problem is solved. QED.

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

Comment: Took a bit to realize how to set up the pigeons and the holes, but it worked out nicely. It's good practice to do a lot of Pigeonhole problems because when you see one you have more experience in determining the pigeons and the holes.

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

Practice Problem: Generalize the problem to a $2n$-gon with the numbers $ 1,2,\ldots, n-1 $.

Thursday, January 26, 2006

Nonnegativity. Topic: Algebra/Polynomials. Level: Olympiad.

Problem: (Olympiad Problem Solving MidTerm) Let $p(x)$ be a polynomial that is nonnegative for all real $x$. Prove that for some $k$, there are polynomials $f_1(x), . . . , f_k(x)$ such that

$ \displaystyle p(x) = \sum_{j=1}^k (f_j(x))^2 $.

Solution: First we will make some restrictions on $ p $, namely that it has an even degree and a positive coefficient on the highest-order term. If it has an odd degree take $ x \rightarrow \pm \infty $ and we get $ p(x) \rightarrow -\infty $ for one of the cases which is a contradiction. Similarly, if it has a negative coefficient on the highest-order term, take $ x \rightarrow \infty $ so again $ p(x) \rightarrow -\infty $. In both these cases, $ p $ cannot be nonnegative for all real $ x $.

Next, we will proceed by strong induction on the degree of $ p $.

Base case: $ deg(p) = 0 $. Then $ p(x) = a = (\sqrt{a})^2 $.

Then suppose the condition is satisfied for $ deg(p) = 0, \ldots, 2n $. We will show that it must also hold for $ deg(p) = 2n+2 $.

Denote $ m = min(p(x)) $ over all reals $ x $. Since $ p $ is nonnegative, $ m \ge 0 $.

Consider the polynomial $ f(x) = p(x)-m $, which is still nonnegative and of degree $ 2n+2 $. For some value of $ x $, $ f(x) = 0 $ because $ p(x) = m $ at some point. Let that value be $ x_0 $ (just take one of them; there might be more). The multiplicity at $ x_0 $ must be even because if it was odd then $ f $ would go negative for some $ x > x_0 $. Let the multiplicity at $ x_0 $ be $ 2b > 0$.

So we have $ f(x) = (x-x_0)^{2b}g(x) $ for some $ g(x) $. We note that $ g(x) $ is nonnegative as well because $ (x-x_0)^{2b} $ is nonnegative and $ f(x) $ would be negative if $ g(x) $ was negative anywhere, a contradiction. By our original restrictions, $ deg(g) $ is even. However, that means $ g(x) $ is a nonnegative polynomial with $ deg(g) < deg(f) = 2n+2 $ so $ g $ must be expressible in the form $ \displaystyle g(x) = \sum_{j=1}^{k_1} (f_j(x))^2 $ for some $ k_1 $ by our inductive hypothesis.

Then $ \displaystyle p(x) = f(x)+m = (x-x_0)^{2b}g(x)+m = \sum_{j=1}^{k_1} [(x-x_0)^bf_j(x)]^2 + (\sqrt{m})^2 $, completing the induction. QED.

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

Comment: A pretty fun, semi-difficult problem. I tried a few failed approaches before reaching this cool one, including getting rid of higher order terms first and reducing it to a lower degree polynomial which employs the same general idea but fails in some cases. Another way to do this problem (from the solutions guide) is simply to factor the polynomial into linear and quadratic terms, show that each linear term has even multiplicity and use the sum of squares product formula on the quadratic terms - $ (a^2+b^2)(c^2+d^2) = (ac+bd)^2+(ad-bc)^2 $. This actually proves a stronger result, that each nonnegative polynomial $ p $ can be written as the sum of the squares of two other polynomials.

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

Practice Problem: (Olympiad Problem Solving MidTerm) Find a polynomial in more than one variable that is always nonnegative that cannot be written as the sum of squares.

Wednesday, January 25, 2006

Lots of Terms. Topic: Number Theory. Level: Olympiad.

Problem: (1975 IMO - #2) Let $a_{1}, \ldots, a_{n}$ be an infinite sequence of strictly positive integers, so that $a_{k} < a_{k+1}$ for any $k$. Prove that there exists an infinity of terms $a_{m}$, which can be written like $a_m = x \cdot a_p + y \cdot a_q$ with $x,y$ strictly positive integers and $p \neq q$.

Solution: Let's take two cases - there exist $ a_i, a_j $ that are relatively prime and there don't exist such members of the sequence.

Well if $ (a_i, a_j) = 1 $, we can just use the Chicken McNugget Theorem and we can find $ x,y > 0 $ such that $ a_ix+a_jy = a_m $ for all $ a_m > a_ia_j-a_i-a_j $. There are an infinite number of such $ a_m $ because the sequence is strictly increasing.

Now suppose there don't exist such $ a_i,a_j $. Since $ a_1 $ is not relatively to any of the infinite other terms and it only has a finite number of divisors, at least one divisor $ d $ of $ a_1 $ divides an infinite number of other terms in the sequence by the Infinite Pigeonhole Principle. Then consider the sequence $ \left\{\frac{a_i}{d}\right\}_{d|a_i} $. We can then apply the same two cases on this sequence and keep going until the first condition holds true (this process terminates because $ a_1 $ only has a finite number of divisors - at some point it will either be relatively prime to another member of the sequence or equal $ 1 $ and be relatively prime anyway).

Therefore there always exist infinitely many $ a_m $ satisfying the condition. QED.

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

Comment: An interesting problem, more so the second case, though. Sort of like a recursive function with a terminating condition. In any case, in the recursion it's important to specify that it will eventually terminate, or it won't be a valid justification.

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

Practice Problem: Prove the Chicken McNugget Theorem - given two positive integers $ a,b $ such that $ (a,b) = 1 $, the largest value of $ n $ such that there do not exist positive integers $ x,y $ with $ ax+by = n $ is $ n = ab-a-b $.

Tuesday, January 24, 2006

Just Try and Reduce It. Topic: Number Theory. Level: AIME/Olympiad.

Problem: (1959 IMO - #1) Prove that the fraction $\frac{21n+4}{14n+3}$ is irreducible for every natural number $n$.

Solution: First, we're going to prove a very useful lemma.

**Lemma: For positive integers $a,b$, if there exist integers $x,y$ such that $ ax+by = 1 $ then $ gcd(a,b) = 1 $.

Proof: Let $ d = gcd(a,b) $. Then $ d|ax $ and $ d|by $ so $ d|(ax+by) \Rightarrow d|1 \Rightarrow gcd(a,b) = d = 1 $.**

Now, take $ a = 21n+4 $ and $ b = 14n+3 $. We find that $ (-2)(21n+4)+(3)(14n+3) = 1 $ so by Lemma, $ gcd(21n+4, 14n+3) = 1 $ and the fraction cannot be reduced. QED.

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

Comment: Note that the lemma can be extended to iff. However, the reverse is considerably more difficult to prove, but still a good exercise in number theory.

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

Practice Problem: Prove that for positive integers $ a,b $ such that $ gcd(a,b) = 1 $, there exist integers $ x,y $ such that $ ax+by = 1 $.

Monday, January 23, 2006

Digit Product. Topic: Number Theory. Level: AIME.

Problem: (1994 AIME - #5) Given a positive integer $n$, let $p(n)$ be the product of the non-zero digits of $n$. (If $n$ has only one digit, then $p(n)$ is equal to that digit.) Let

$S=p(1)+p(2)+p(3)+\cdots+p(999)$.

What is the largest prime factor of $S$?

Solution #1: At first glance, the product of the digits is really quite a nasty function... But some shrewd algebra skills can take it on without too much trouble.

Consider $p(k)$ for $ k = 1, 2, \ldots, 9 $.

We obviously get the values $ 1, 2, \ldots, 9 $. This sums to $ 45 $.

Consider $p(k)$ for $ k = d_1d_2 $, where the $d$'s are digits, for $ d_1 > 0 $ and $ d_2 = 0,1,2,\ldots,9 $.

It's easy to see that this gives $ d_1, 1 \cdot d_1, 2 \cdot d_1, \ldots, 9 \cdot d_1 $. This sums to $ d_1 \cdot (1+1+2+\cdots+9) = 46 \cdot d_1 $.

Now take $ d_1 = 1,2, \cdots, 9 $ to get a sum of $ 46(1+2+\cdots+9) = 46(45) $.

Consider the $p(k)$ for $ k = d_1d_2d_3 $ for $ d_1 > 0 $ and both $ d_2 $ and $ d_3 $ ranging from $ 0 $ to $ 9 $.

For any fixed $ d_1 $, we just have $ d_2d_3 $ ranging, which we know to have value (assume $ 00 $ gives $ 1 $) $ (1+1+\cdots+9)(1+1+\cdots+9) = 46^2 $.

And since $ d_1 $ ranges from $ 1 $ to $ 9 $, we get $ (1+2+\cdots+9)(46^2) = 45 \cdot 46^2 $.

Whew. Now sum everything up to get $ 45+45 \cdot 46+45 \cdot 46^2 = 45(1+46+46^2) = 45(2163) = 45 \cdot 21 \cdot 103 $.

Therefore the largest prime divisor is $ 103 $. QED.

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

Comment: That was a rather brute force solution, but it doesn't take much time on the test and works out pretty well. The following solution is more clever, but takes a little longer to work out logically.

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

Solution #2: We look at the numbers based on their place value.

Let $ p(0) = 1 $ for this, which has no effect on the product as given in the problem, except for the case $ n = 0 $ which we will discount later.

The required sum $ S+1 $ (we add one to account for the $ 0 $ term) can be rewritten as $ S+1 = [p(0)+\cdots+p(9)][p(0)+\cdots+p(9)][p(0)+\cdots+p(9)] = [p(0)+\cdots+p(9)]^3$. Why?

First notice that $ p(n) = \prod p(d) $ where $ d $ is a digit of $ n $. This is easy to show since multiplication is "multiplicative."

So consider any number $ p(n) = p(d_1d_2d_3) = p(d_1)p(d_2)p(d_3) $. We just need to take each $ d $ from $ 0 $ to $ 9 $ to find the desired sum $ S $. That means multiplying $ p(0)+p(1)+\cdots+p(9) $ for each digit, of which there are three, verifying the above formula.

Then $ p(0)+p(1)+\cdots+p(9) = 46 $ so $ S+1 = 46^3 \Rightarrow S = 46^3-1 = (46-1)(1+46+46^2) = 45 \cdot 21 \cdot 103 $ as before. QED.

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

Practice Problem: (1994 AIME - #1) The increasing sequence $3, 15, 24, 48, \ldots$ consists of those positive multiples of $3$ that are one less than a perfect square. What is the remainder when the $1994$th term of the sequence is divided by $1000$?

Sunday, January 22, 2006

Finished Product. Topic: Number Theory. Level: Olympiad.

Problem: (1970 IMO - #1) Find all positive integers $n$ such that the set $\{n,n+1,n+2,n+3,n+4,n+5\}$ can be partitioned into two subsets so that the product of the numbers in each subset is equal.

Solution: We claim that no such $n$ exists.

First, suppose one of the elements has a prime factor $ > 5 $. Then clearly none of the other elements has the same prime factor; therefore, any partition will create one set with that prime factor and one without it. Hence none of the elements has a prime factor $ > 5 $.

Now take the set modulo $ 5 $. By the same argument above, there must be two elements divisible by $ 5 $. But the first and last are the only two elements that differ by $ 5 $, so $ n \equiv n+5 \equiv 0 \pmod{5} $.

Consider the elements $n+1, n+2, n+3, n+4$. Two of them can be divisible by $ 2 $. Of the remaining two, however, only one can be divisible by $ 3 $ (since they differ by $ 2 $). Hence there exists an element that is divisible by neither $2, 3, $ nor $5$. Then it must have a prime factor $ > 5 $, which gives us a contradiction.

So no such $ n $ exist, as desired. QED.

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

Practice Problem: Find an $ n $ such that the above condition holds for the set $ \{n,n+1,\ldots,n+7\} $ or prove that none exist.

Saturday, January 21, 2006

It Only Matters In The End. Topic: Number Theory. Level: Olympiad.

Problem: (1978 IMO - #1) We consider all the pairs $(m,n)$ of integer numbers, so that $n>m \geq 1$ and so that their last three digits from the decimal writing of $1978^{m}$ are the same with those three last digits from the decimal writing of $1978^{n}$. Find all the pairs $(m,n)$ with these properties so that the sum $m+n$ is minimum.

Solution: Basically it's asking us to find the smallest $m$ and $n$ such that $ 1978^m \equiv 1978^n \pmod{1000} $ or $ 1978^n-1978^m \equiv 0 \pmod{1000} $. By the looks of this problem, Euler's Totient Theorem might come in handy again. But we have a small problem - $ (1978,1000) \neq 1 $.

So we try dividing out all the factors of $ 2 $ in $ 1000 $.

By the Totient Theorem, we find $ 1978^{\phi(125)} = 1978^{100} \equiv 1 \pmod{125} $ and that $100$ is also the smallest power for which this is true. This means $ 1978^{100} = 125k+1 $ for some positive integer $k$.

Hence $m$ and $n$ differ by at least $100$. Suppose $ n = m+100 $.

Then $ 1978^{m+100}-1978^m = 1978^m(1978^{100}-1) \equiv \pmod{1000} $. Since the second part is odd, all the powers of two, there must be at least three of them, come from $ 1978^m $. Hence $ m \ge 3 $. But since we know $ 1978^{100}-1 \equiv 0 \pmod{125} $, we have $ 1978^m(1978^{100}-1) $ divisible by both $ 8 $ and $ 125 $, which means it's divisible by $ 1000 $, so $ m = 3 $ is the smallest possible value that works, giving $ n = 103 $.

Therefore, our smallest $ m+ n = 106 $. QED.

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

Comment: Kind of a strange problem, with the minimum value, reminiscent of many AIME problems. Ultimately, not too difficult, though.

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

Practice Problem: Find the value of $ 10^{2006} \pmod{252} $.

Square Differences. Topic: Inequalities. Level: Olympiad.

Problem: (1975 IMO - #1) We consider two sequences of real numbers $x_{1} \geq x_{2} \geq \ldots \geq x_{n}$ and $\ y_{1} \geq y_{2} \geq \ldots \geq y_{n}$. Let $z_{1}, z_{2}, \ldots, z_{n}$ be a permutation of the numbers $y_{1}, y_{2}, \ldots, y_{n}$. Prove that $\displaystyle \sum \limits_{i=1}^{n} ( x_{i} -\ y_{i} )^{2} \leq \sum \limits_{i=1}^{n} ( x_{i} - z_{i})^{2}$.

Solution: Expanding both sides, we see that

$ \displaystyle \sum x_i^2 $ and $ \displaystyle \sum y_i^2 = \sum z_i^2 $ appear on both sides, so we can cancel them out, leaving

$ \displaystyle -2 \sum x_iy_i \le -2 \sum x_iz_i \Rightarrow \sum x_iy_i \ge \sum x_iz_i $ which is a direct result of the Rearrangement Inequality (easily extended to all reals). QED.

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

Comment: Well, I can't say this is the toughest IMO problem ever, but it does teach a few good lessons. One might be inclined to keep the squared differences there because they do look a bit nicer than after expansion. But getting a little messy can sometimes produce exactly the result you want, as it does here. Knowing the Rearrangement Inequality basically gives you the first ideas of an approach which is easy to finish.

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

Practice Problem: Extend the Rearrangement Inequality to all reals (i.e. show that the proof holds even when there are negative numbers).

Wednesday, January 18, 2006

unREAListic! Topic: Algebra. Level: AIME/Olympiad.

Problem: (WOOT Test 5 - #3) Find all non-empty sets $ A $ of real numbers satisfying the following property -

For all real numbers $ x,y $, if $ x+y \in A $ then $ xy \in A $.

Solution: We claim that $ A $ must be the set of all real numbers.

We will prove this by showing that
(1) $ 0 \in A $
(2) $ -n \in A $ for all positive reals $ n $
(3) $ m \in A $ for all positive reals $ m $

(1) Since $ A $ is non-empty, we know there exists at least one element $ a \in A $. Then take $ x = 0, y = a $, to get $ x+y = a \in A \Rightarrow xy = 0 \in A $.

(2) Take $ x = \sqrt{n}, y = -\sqrt{n} $, and we have, from (1), $ x+y = 0 \in A \Rightarrow xy = -n \in A $.

(3) Take $ x = -m, y = -1 $, and we have, from (2), $ x+y = -m-1 \in A \Rightarrow xy = m \in A $.

Hence all reals must be in $ A $. QED.

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

Comment: During the actual test, I had a slightly more convoluted solution, but the thought process was very much the same. I found that that given any element $ a $, I could take $ x,y $ such that one of them was very negative and the other very positive to get all the negative reals and obviously zero. From there, it's not a big step to see that all positive reals are in $ A $ as well.

Tuesday, January 17, 2006

One Big Set. Topic: Number Theory. Level: Olympiad.

Problem: (1971 IMO - #3) Prove that we can find an infinite set of positive integers of the form 2^n-3 (where n is a positive integer) every pair of which are relatively prime.

Solution: We will proceed by induction, stating that given any set $ A = \{a_1,a_2,\ldots,a_k\}$ of integers of the form $ 2^n-3 $ that are pairwise relatively prime, we can find a $ a_{k+1} $ such that $ (a_i, a_{k+1}) = 1 $ for all $ 1 \le i \le k $.

Consider the set $ A = \{a_1,a_2,\ldots,a_k\} $. Let $ S = \prod a_i = a_1a_2 \cdots a_k $. Since all $ a_i $ are odd, $ S $ is odd as well and $ (S,2) = 1 $.

Hence, by Euler's Totient Theorem, we must have $ 2^{\phi(S)} \equiv 1 \pmod{S} $. Which means $ 2^{\phi(S)}-3 = mS-2 $ for some positive integer $ m $. But since all $ a_i|S $, we know $ S = r_ia_i $ for some positive integers $ r_i $. So $ (a_i, mS-2) = (a_i, mr_ia_i-2) = d_i $. So $ d_i|a_i \Rightarrow d_i|mr_ia_i $ and $ d_i|(mr_ia_i-2) \Rightarrow d_i|(mr_ia_i-(mr_ia_i-2)) $ so $ d_i|2 $. But since $ a_i $ are all odd, $ d_i $ cannot be even so $ d_i = 1 $, which means $ a_{k+1} = 2^{\phi(S)}-3 $ is relatively prime to all $ a_i $.

Therefore, we can generate an infinite number of elements of the form $ 2^n-3 $ which are pairwise relatively prime. QED.

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

Comment: Euler's Totient Theorem is one of the most powerful tools in Number Theory and is a very handy thing to know for problem solving. It reduces exponents very quickly as well as having less direct applications such as in the above problem.

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

Practice Problem: Evaluate $ \phi(1000) $ and find the last three digits of $ 997^{2006} $.

Friday, January 13, 2006

Ratio This. Topic: Geometry/Inequalities. Level: Olympiad.

Problem: (1991 IMO - #1) Given a triangle $ ABC $, let $ I $ be the center of its inscribed circle. The internal bisectors of the angles $ A,B,C $ meet the opposite sides in $ A^{\prime },B^{\prime },C^{\prime } $ respectively. Prove that

$ \frac{1}{4} < \frac{AI\cdot BI\cdot CI}{AA^{\prime }\cdot BB^{\prime }\cdot CC^{\prime }} \leq \frac{8}{27} $.

1991IMO-1

Solution: We begin by changing the expression in the middle into something nicer to work with. First drop perpendiculars from the incenter $ I $ to each side, as in the diagram. Note that $ ID = IE = IF = r $ because they are all inradii. Also denote the side opposite angle $ A $ side $ a $ and similarly for $ b $ and $ c $.

Note that $ AI+IA^{\prime} = AA^{\prime} \Rightarrow \frac{AI}{AA^{\prime}} = 1-\frac{IA^{\prime}}{AA^{\prime}} $. However, we then have $ \frac{IA^{\prime}}{AA^{\prime}} = \frac{[IBC]}{[ABC]} $ because the two triangles share a base. Using the common formula of $ S = rs $, where $ S $ is the area of a triangle with inradius $ r $ and semiperimeter $ s $, we have $ \frac{[IBC]}{[ABC]} = \frac{\frac{1}{2}ra}{\frac{1}{2}r(a+b+c)} = \frac{a}{a+b+c} $. So $ 1-\frac{IA^{\prime}}{AA^{\prime}} = \frac{b+c}{a+b+c} $. Applying the same respective substitutions for $ \frac{BI}{BB^{\prime}} $ and $ \frac{CI}{CC^{\prime}} $, we have

$ \frac{AI\cdot BI\cdot CI}{AA^{\prime }\cdot BB^{\prime }\cdot CC^{\prime }} = \frac{(a+b)(b+c)(c+a)}{(a+b+c)^3} $.

Now, to simplify things, set $ a = x+y, b = x+z, c = y+z $, where $ x = CE = CD, y = BC = BD, z = AF = AE $. This gets rid of the triangle inequality condition. Set $ s = x+y+z $. Then

$ \frac{(a+b)(b+c)(c+a)}{(a+b+c)^3} = \frac{(s+x)(s+y)(s+z)}{8s^3} $.

We begin with the left inequality. We have

$ \frac{(s+x)(s+y)(s+z)}{8s^3} > \frac{s^3+s^2(x+y+z)}{8s^3} = \frac{2s^3}{8s^3} = \frac{1}{4} $.

For the right, we have

$ \sqrt[3]{(s+x)(s+y)(s+z)} \le \frac{3s+x+y+z}{3} = \frac{4s}{3} $ by AM-GM, so then

$ \frac{(s+x)(s+y)(s+z)}{8s^3} \le \frac{\frac{64s^3}{27}}{8s^3} = \frac{8}{27} $

as desired. QED.

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

Comment: This problem really isn't that hard if you see the ratios and make the right changes. As often happens in geometric inequalities involving triangles, substitution of $ x,y,z $ above for $ a,b,c $ works well in getting rid of the triangle inequality restraint.

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

Practice Problem #1: (1984 AIME - #3) A point $P$ is chosen in the interior of $\triangle ABC$ such that when lines are drawn through $P$ parallel to the sides of $\triangle ABC$, the resulting smaller triangles $t_1, t_2,$ and$ t_3$ in the figure, have areas $4, 9,$ and $49,$ respectively. Find the area of $\triangle ABC$.

Practice Problem #2: Find the area of a triangle in terms of $ x,y,z $ defined above.

Wednesday, January 11, 2006

No Way! Topic: Algebra/NT. Level: Olympiad.

Problem: (1987 IMO - #4) Prove that there is no function $f$ from the set of non-negative integers into itself such that $f(f(n))=n+1987$ for all $n$.

Solution: Suppose such a function does exist.

Note that $ f(f(n)) = n+1987 $, so $ f(n+1987) = f(f(f(n))) = f(n)+1987 $.

So given two integers $k_1 > k_2$, we have $ k_1 \equiv k_2 \pmod{1987} \Rightarrow k_1 = k_2+1987a $ for some positive integral $a$. $f(k_1) \equiv f(k_1-1987) \equiv f(k_1-2\cdot1987) \equiv \cdots \equiv f(k_1-a\cdot1987) = f(k_2) \pmod{1987} $.

Also note that $f$ is one-to-one. That is, given $x,y$ such that $ f(x) = f(y) $, we have $ f(f(x)) = f(f(y)) \Rightarrow x+1987 = y+1987 \Rightarrow x = y$.

Consider $ g(n) \equiv f(n) \pmod{1987} $ where $ 0 \le g(x) < 1986 $, $ 0 \le n < 1986 $. If we have $x \neq y$ such that $ g(x) = g(y) $, we have $ f(x) \equiv f(y) \Rightarrow x \equiv y $, but since the domain of $g$ is limited, we have a contradiction. Hence $g$ takes on all residues $ \pmod{1987} $.

Let $ f(n) = m $ where $n$ and $m$ have different residues $\pmod{1987}$. Then we have $ f(m) = f(f(n)) = n+1987 \equiv n \pmod{1987} $. So $ f(n) \equiv m, f(m) \equiv n \pmod{1987} $. Pairing up all values this way, we have an odd number (at least one) of remaining $n$ such that $ f(n) \equiv n \pmod{1987} $.

However, if $ f(n) \equiv n \pmod{1987} $, we have $ f(n) = n+1987t $ for some $ t \ge 0 $. Then $ f(n+1987t) = f(n+1987(t-1)) +1987 = \cdots = f(n)+1987t = n+1987(t+1) $, but $ f(f(n+1987t)) = n+1987(t+1) $ as well, so $ f(n+1987t) = n+1987t < n+1987(t+1) $, which clearly gives a contradiction.

Therefore no such functions $f$ exist. QED.

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

Practice Problem: Find all positive integrs $k$ such that there exists a function $f$ from the set of non-negative integers into itself such that $ f(f(n)) = n+k $.

Tuesday, January 10, 2006

Big Board. Topic: Combinatorics. Level: Olympiad.

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

Solution: We claim that $n = 1999$.

Suppose there are $1999$ colored squares on the board. On each row, let the colored square furthest to the left be the "main" square of the row. Let any other colored squares be "repeat" squares. If $x$ rows have colored squares, then there are $x$ main squares and $1999-x$ repeat squares.

Let the colored square furthest to the left be in the $y$th row. Then all repeat squares must exist in the columns to the right of $y$, of which there are $1000-y$.

Let $z$ be the number of columns with repeat squares. If $ z < 1999-x$, by the Pigeonhole Principle we must have at least two repeat squares $A$ and $B$ in the same column. But take a main square $C$ in the same row as $A$ or $B$ and we have $ABC$ a triangle. Contradiction.

Therefore $z \ge 1999-x$. But we also have $z \le 1000-y \le 999 \le 1999-x$, so the only case we have left is $z = 999 = 1999-x$. Then all rows have colored squares, the first column has a main square, and all of the other $999$ columns have repeat squares. If all the main squares are in the first column, we make a triangle with any of the repeat squares. So we must have some main squares in the $999$ remaining rows. Let $A$ be a main square not in the first column. We know there exists a repeat square $B$ in the same column as $A$. But then there is a main square $C$ in the same row as $B$, which means $ABC$ again forms a triangle. Contradiction.

Therefore $n = 1999$ has no coloring. The coloring for $n = 1998$ is the lower $999$ squares in the first column and the rightmost $999$ squares in the first row. Hence our answer is $n = 1999$. QED.

Monday, January 9, 2006

Symmetrific! Topic: Geometry/Inequalities. Level: Olympiad.

Problem: (2004 USAMO - #1) Let $ABCD$ be a quadrilateral circumscribed about a circle, whose interior and exterior angles are at least $60$ degrees. Prove that

$\frac{1}{3}|AB^3 - AD^3| \le |BC^3 - CD^3| \le 3|AB^3 - AD^3|$.

When does equality hold?

Solution: First of all, we notice conveniently enough that if the left inequality is true, the right is true by symmetry (just applying the same inequality cycled around the quadrilateral). Hence it is only necessary to prove the first inequality.

We establish two inequalities that we will use throughout the problem:

For $a,b, 60^{\circ} \le \theta \le 120^{\circ}$, we have $ -\frac{1}{2} \le \cos{\theta} \le \frac{1}{2} \Rightarrow -ab \le 2ab\cos{\theta} \le ab$ (1).

Also note that the interior angles and exterior angles $ \ge 60^{\circ}$ means all the angles of the quadrilateral will qualify as $\theta$ under the set conditions.

So we begin with the Trivial Inequality,

$ 0 \le (AB-AD)^2 $

$ (AB)(AD) \le AB^2+AD^2-(AB)(AD)$

$ (AB)(AD) \le AB^2+AD^2-2(AB)(AD)\cos{\angle BAD} = BD^2 $ by (1) and Law of Cosines.

Then we have

$ \frac{1}{3}(BD^2+2(AB)(AD)) \le BD^2 $

$ \frac{1}{3}(AB^2+AD^2-2(AB)(AD)\cos{\angle BAD}+2(AB)(AD)) \le BD^2 $ by Law of Cosines.

$ \frac{1}{3}(AB^2+AD^2+(AB)(AD)) \le BD^2 $ by (1).

So then we manipulate the RHS to find

$ \frac{1}{3}(AB^2+AD^2+(AB)(AD)) \le BC^2+CD^2-2(BC)(CD)\cos{\angle BCD} \le BC^2+CD^2+(BC)(CD) $ by Law of Cosines and (1).

Noticing that $ |AB-AD| = |BC-CD| = |y-w| $ in the diagram (true because of the inscribed circle), we multiply on both sides to get

$\frac{1}{3}|(AB-AD)(AB^2+AD^2+(AB)(AD))| \le |(BC-CD)(BC^2+CD^2+(BC)(CD))|$

$ \frac{1}{3}|AB^3-AD^3| \le |BC^3-CD^3| $

as desired. And the equality occurs whenever we have $ AB = AD, \angle BAD = 60^{\circ}, \angle BCD = 120^{\circ} $ for the first inequality or $ BC = CD, \angle BCD = 60^{\circ}, \angle BAD = 120^{\circ} $ for the second. QED.

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

Comment: A decent USAMO #1. Basically if you saw the factoring and noticed the similarity to the Law of Cosines, it just took a bit to work your way through the inequalities.

Saturday, January 7, 2006

Inductfully Done. Topic: Sets. Level: Olympiad.

Problem: (2002 USAMO - #1) Let $S$ be a set with $2002$ elements, and let $N$ be an integer with $0 \leq N \leq 2^{2002}$. Prove that it is possible to color every subset of $S$ either black or white so that the following conditions hold:

(a) the union of any two white subsets is white;
(b) the union of any two black subsets is black;
(c) there are exactly $N$ white subsets.

Solution: We apply induction on the $2002$, which we will call $k$, with $0 \le N \le 2^k$. Let the set be $S = \{a_1,\ldots,a_k\}$.

For $k = 1$, we have $S = \{a_1\}$.

If $N = 0$, we may color both $\{\emptyset\}, \{a_1\}$ black.
If $N = 1$, we may color $\{\emptyset\}$ black and $\{a_1\}$ white.
If $N = 2$, we may color both $\{\emptyset\}, \{a_1\}$ white.

So assume the condition is satisfied for some $k = n$. We wish to show the condition is also satisfied by $k = n+1$.

First consider the case $ 0 \le N \le 2^n$. There exists some coloring when $k = n$, so we take the same coloring for $k = n+1$ and color all the new sets black. Clearly all the new sets have the new element $a_{n+1}$ so the union of any of the old sets cannot be a new one and the union of any of the new sets cannot be an old one. And we preserve the number of white subsets, $N$.

Now consider the case $ 2^n+1 \le N \le 2^{n+1} $. Take the same coloring as $ M = 2^{n+1}-N$ except reverse white and black. The union condition obviously still holds by what was shown above and there are exactly $N$ white subsets now because there were originally $2^{n+1}-M = N$ black subsets for the $M$ case.

Hence the condition is true for all positive integral $k$, which means the case $k = 2002$ is true as well. QED.

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

Practice Problem #1: (2005 AMC-12A - #23) Two distinct numbers a and b are chosen randomly from the set $\{ 2, 2^2, 2^3, \ldots, 2^{25} \}$. What is the probability that $\log_{a} b$ is an integer?

Practice Problem #2: (1971 IMO - #3) Prove that we can find an infinite set of positive integers of the form $2^n-3$ (where n is a positive integer) every pair of which are relatively prime.

Friday, January 6, 2006

Colorful! Topic: Sets. Level: Olympiad.

Problem: (1985 IMO - #2) Let $n$ and $k$ be relatively prime positive integers with $k
Solution: We will start from some element $a$ and show that we can equate it with any other element in $M$.

First, we note that if $a \equiv b \pmod{k}$, $a$ and $b$ have the same color since they differ by a multiple of $k$, so it is only necessary to show that all residues modulo $k$ are the same color.

Also, $a \pmod{k}$ and $n-a \pmod{k}$ have the same color, as given. (1)

By the second condition, we can also infer that $a \pmod{k}$ and $ -a \pmod{k}$ are the same color (2) because we just take an element $x \equiv a \pmod{k}$ such that $x < k$ and we have $x \equiv a \pmod{k}$ and $|x-k| = k-x \equiv -x \equiv a \pmod{k}$ the same color.

So we generate residues $\pmod{k}$ as follows.

We have $a$ blue. If $mn+a$ is blue for some integer $m$, we have $ -mn-a$ is blue by (2) and $n-(-mn-a) = (m+1)n+a$ is blue by (1). Hence by induction all $mn+a$ are blue. But noting that $(n,k) = 1$, $mn+a$ clearly takes on all residues modulo $k$ and the proof is complete. QED.

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

Practice Problem: (2002 USAMO - #1) Let $S$ be a set with $2002$ elements, and let $N$ be an integer with $0 \leq N \leq 2^{2002}$. Prove that it is possible to color every subset of $S$ either black or white so that the following conditions hold:

(a) the union of any two white subsets is white;
(b) the union of any two black subsets is black;
(c) there are exactly $N$ white subsets.

Thursday, January 5, 2006

Dysfunctional. Topic: Algebra. Level: Olympiad.

Problem: (1983 IMO - #1) Find all functions $f$ defined on the set of positive reals which take positive real values and satisfy:$ f(xf(y))=yf(x)$ for all $x,y$; and $f(x)\to0$ as $x\to\infty$.

Solution: First, it would help a lot if we showed the function was one-to-one (that is, for each $y$ there is at most one $x$ such that $f(x) = y$).

So suppose $ f(a) = f(b) $.

Then $ f(af(b) = f(af(a)) = bf(a) $. But we also have $ f(af(a)) = af(a) $ so $ f(af(a)) = bf(a) = af(a)$. And since $f$ takes positive real values, we know can divide by $f(a)$ to get $a = b$. Hence $f$ is one-to-one and we take take its inverse.

Now let's experiment with some values.

Let $x = y = 1$. We have $ f(f(1)) = f(1) \Rightarrow f(1) = 1 $ (because we can take its inverse).

Now take $x = y$. We have $ f(xf(x)) = xf(x) $. Suppose $k = xf(x)$.

Assume $k > 1$. We have $ f(k) = k \Rightarrow f(kf(k)) = f(k^2) = k^2 $, and, repeating this process, we have $ f(k^{2n}) = k^{2n} $. Then if we take $ n \to \infty$, we have $ f(x) \to \infty $ as $x \to \infty $, which contradcits the given condition.

Now assume $k < 1$. We have $ f(k) = k \Rightarrow f\left(\frac{1}{k}f(k)\right) = f(1) = 1 = kf\left(\frac{1}{k}\right) \Rightarrow f\left(\frac{1}{k}\right) = \frac{1}{k} $. But again $ f\left(\frac{1}{k}\right) = \frac{1}{k} \Rightarrow f\left(\frac{1}{k}f\left(\frac{1}{k}\right)\right) = f\left(\frac{1}{k^2}\right) = \frac{1}{k^2} $ which, repeating the process, becomes $ f\left(\frac{1}{k^{2n}\right) = \frac{1}{k^{2n} $. Then if we take $ n \to \infty$, we have $ f(x) \to \infty $ as $ x \to \infty $, again giving a contradiction.

Therefore $k = 1 = xf(x) \Rightarrow f(x) = \frac{1}{x} $ is the only such function. QED.

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

Practice Problem: (1986 IMO - #5) Find all functions $f$ defined on the non-negative reals and taking non-negative real values such that: $f(2)=0,f(x) \neq 0$ for $0\le x<2$, and$ f(xf(y))f(y)=f(x+y)$ for all $x,y$.

Tuesday, January 3, 2006

Low as You Can Go. Topic: Geometry/Inequalities. Level: Olympiad.

SPECIAL POST! This problem was too cool and I couldn't wait another day to post it, so here you go.

Problem: (1981 IMO - #1) Consider a variable point $P$ inside a given triangle $ABC$. Let $D, E, F$ be the feet of the perpendiculars from the point $P$ to the lines $BC, CA, AB$, respectively. Find all points $P$ which minimize the sum

$\frac{BC}{PD}+\frac{CA}{PE}+\frac{AB}{PF}$.

1981IMO-1

Solution: So let's try to find some relationship with $PD, BC, PE, CA, PF, AB$. Area is a good bet. Let $S$ be the area of $ \triangle ABC$.

We have $S = \frac{1}{2}(PD \cdot BC+PE \cdot CA+PF \cdot AB)$.

We're looking for the minimum $ K = \frac{BC}{PD}+\frac{CA}{PE}+\frac{AB}{PF} $, which makes us think inequalities and the fractions make us think Cauchy.

Well, amazingly enough, by Cauchy we have

$ 2SK = (PD \cdot BC+PE \cdot CA+PF \cdot AB)\left(\frac{BC}{PD}+\frac{CA}{PE}+\frac{AB}{PF}\right) \ge (AB+BC+CA)^2 $.

So $K \ge \frac{(AB+BC+CA)^2}{2S} $, but the RHS is constant for a given triangle. Therefore the minimum is the equality condition on Cauchy, or

$ \frac{PD \cdot BC}{\frac{BC}{PD}} = \frac{PE \cdot CA}{\frac{CA}{PE}} = \frac{PF \cdot AB}{\frac{AB}{PF}}$,

which simplifies to

$ PD^2 = PE^2 = PF^2 \Rightarrow PD = PE = PF $.

Hence $K$ is minimized when $P$ is the incenter of $\triangle ABC$. QED.

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

Comment: If that's not a cool geometric inequality IMO problem, I don't know what is!

Subset It Up. Topic: Sets/Combinatorics. Level: Olympiad.

Problem: (1981 IMO - #2) Take $r$ such that $1\le r\le n$, and consider all subsets of r elements of the set $\{1,2,\ldots,n\}$. Each subset has a smallest element. Let $F(n,r)$ be the arithmetic mean of these smallest elements. Prove that:

$F(n,r)=\frac{n+1}{r+1}$.

Solution: So we first find out how many of these subsets there are. Well that's easy, just choose $r$ elements from $n$, or $nCr$.

So how many have smallest element $1$? Well, assume $1$ is in the set. Then we have to pick the other $r-1$ elements from the remaining $n-1$ elements. So we have $(n-1)C(r-1)$.

And $2$? By the same argument, we have $(n-2)C(r-1)$ (choosing $r-1$ elements from the numbers above $2$).

So for any $k$, we have $(n-k)C(r-1)$ ways to choose a subset of size $r$ that has minimum element $k$.

Since we are taking an arithmetic mean, we want the sum of ALL the minimum elements, meaning we take $k \cdot (n-k)C(r-1)$, added up to be

$ \displaystyle \sum_{i=1}^{n-r+1} [i \cdot (n-i)C(r-1)] = 1\cdot (n-1)C(r-1)+2 \cdot (n-2)C(r-1) + \cdots +(n-r+1)\cdot (r-1)C(r-1) $.

But remember by the above argument we have

$ \displaystyle \sum_{i=1}^{n-r+1} (n-i)C(r-1) = (n-1)C(r-1)+(n-2)C(r-1)+\cdots+rC(r-1)+(r-1)C(r-1) = nCr$.

Similarly

$ \displaystyle \sum_{i=2}^{n-r+1} (n-i)C(r-1) =(n-2)C(r-1)+\cdots+(r-1)C(r-1) = (n-1)Cr $.
$ \displaystyle \sum_{i=3}^{n-r+1} (n-i)C(r-1) = (n-3)C(r-1)+\cdots+(r-1)C(r-1) = (n-2)Cr $.
...
$ \displaystyle \sum_{i=n-r}^{n-r+1} (n-i)C(r-1) = rC(r-1)+(r-1)C(r-1) = (r+1)Cr$.
$ \displaystyle \sum_{i=n-r+1}^{n-r+1} (n-i)C(r-1) = (r-1)C(r-1) = rCr$.

Adding up all the equations, we have

$ \displaystyle \sum_{i=1}^{n-r+1} [i \cdot (n-i)C(r-1)] = \displaystyle \sum_{i=0}^{n-r} (n-i)Cr $.

Using again the same argument, we have

$ \displaystyle \sum_{i=0}^{n-r} (n-i)Cr = (n+1)C(r+1) $.

Then we divide by the total number of subsets, which we found earlier to be $nCr$ to get

$ F(n,r) = \frac{(n+1)C(r+1)}{nCr} = \frac{n+1}{r+1} $

as desired. QED.

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

Comment: Yay, first IMO problem posted here. Not a particularly difficult one, though somewhat time consuming to write out. But anyway, hopefully there will be more to come.

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

Practice Problem: (2001 AIME - #2) A finite set $S$ of distinct real numbers has the following properties: the mean of $S\cup\{1\}$ is $13$ less than the mean of $S$, and the mean of $S\cup\{2001\}$ is $27$ more than the mean of $S$. Find the mean of $S$.

Monday, January 2, 2006

United We Stand! Topic: Complex Numbers/Trigonometry. Level: AIME.

Problem: (2004 AIME1 - #13) The polynomial $P(x)=(1+x+x^2+\cdots+x^{17})^2-x^{17}$ has $34$ complex roots of the form $z_k=r_k[\cos(2\pi a_k)+i\sin(2\pi a_k)], k=1, 2, 3,\ldots, 34$, with $00$. Given that $a_1+a_2+a_3+a_4+a_5=m/n$, where $m$ and $n$ are relatively prime positive integers, find $m+n$.

Solution: Factor the first part as a finite geometric series to get

$P(x) = \left(\frac{x^{18}-1}{x-1}\right)^2-x^{17} = \frac{(x^{19}-1)(x^{17}-1)}{(x-1)^2}$.

So our roots are the $19$th and $17$th Roots of Unity except $x = 1$.

Knowing our complex number facts, we know the $n$th Roots of Unity appear in this form:

$ \cos{\frac{2\pi k}{n}}+i\sin{\frac{2\pi k}{n}} $.

Then, looking back at the problem, we know it's asking the sum of the first five $a$'s, which are actually just the $\frac{k}{n}$'s. So we have $n = 17,19$ so the smallest five should be

$\frac{1}{19}+\frac{1}{17}+\frac{2}{19}+\frac{2}{17}+\frac{3}{19} = \frac{159}{323}$

so the answer is $159+323 = 482$. QED.

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

Comment: Not too bad once you see the factorizations, but you have to remember those or else! And remember DeMoivre too. That's super handy.

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

Practice Problem: (2005 AIME2 - #9) For how many positive integers $n$ less than or equal to $1000$ is $(\sin t + i \cos t)^n=\sin (nt) + i \cos (nt)$ true for all real $t$?