Monday, October 30, 2006

Symmetry For The Win. Topic: Calculus.

Problem: Evaluate the improper integral $ I = \displaystyle \int_0^{\pi} \ln{(\sin{x})} dx $.

Solution: As the topic suggests, we will look for a symmetry to simplify the problem. Notice the identity $ \displaystyle \int_0^a f(x) dx = \int_0^a f(a-x) dx $ (since we're just integrating across the interval from different "directions." Using this, we have

$ \displaystyle I = \int_{0}^{\frac{\pi}{2}}\ln{(\sin{x})}dx = \int_{0}^{\frac{\pi}{2}}\ln{\left(\sin{\left(\frac{\pi}{2}-x\right)}\right)}dx = \int_{0}^{\frac{\pi}{2}}\ln{(\cos{x})}dx $.

Adding the old integral to the new one, we have

$ \displaystyle 2I = \int_{0}^{\frac{\pi}{2}}\ln{(\sin{x})}dx+\int_{0}^{\frac{\pi}{2}}\ln{(\cos{x})}dx = \int_{0}^{\frac{\pi}{2}}\ln{\left(\frac{1}{2}\sin{2x}\right)}dx $

from the property of logs and the double-angle identity (here it is again!). But in fact this expression is simply

$ \displaystyle 2I =-\frac{\pi}{2}\ln{2}+\frac{1}{2}\int_{0}^{\pi}\ln{(\sin{u})}du $ (*)

by the substitution $ u = 2x $. Taking into the account of the symmetry of $ \sin{x} $ from $ 0 $ to $ \pi $, we get $ \sin{x} = \sin{(\pi-x)} $ so

$ \displaystyle \frac{1}{2}\int_{0}^{\pi}\ln{(\sin{u})}du = \int_{0}^{\frac{\pi}{2}}\ln{(\sin{u})}du = I $.

Plugging back into (*) we obtain $ \displaystyle 2I =-\frac{\pi}{2}\ln{2}+I $ so we get $ I = -\frac{\pi}{2}\ln{2} $. QED.

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

Comment: The function is not nice to actually integrate; it involves the polylogarithm function if you try here. This is an important example of how symmetry can help a ton in integration because there are so many functions that cannot be integrated with elementary functions but can be evaluated over an interval through different techniques.

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

Practice Problem: Evaluate $ \displaystyle \int_0^{\frac{\pi}{2}} \sin^4{x} dx $ without actually finding the antiderivative.

Sunday, October 29, 2006

Out Of Place Trig. Topic: Geometry/Trigonometry. Level: AMC/AIME.

Problem: (2006-2007 Warm-Up 4) Two sides of a triangle are $ 4 $ and $ |\cos{\theta}| $ and the angle between them is $ \theta $. If $ 0 < \theta < \pi $, what is the maximum area of the triangle?

Solution: Well, given two sides and the angle between them, there is only one formula for the area of a triangle that comes to mind. $ [ABC] = \frac{1}{2}ab \sin{(\angle C)} $. So plugging this in, we get the area to be

$ \frac{1}{2} (4) |\cos{\theta}| \sin{\theta} = 2 \sin{\theta} |\cos{\theta}| $.

By the double-angle identity, this is equal to

$ |\sin{(2\theta)}| $

for $ 0 < \theta < \pi $. But the maximum of this is clearly $ 1 $ and it is obtained when $ \theta = \frac{\pi}{4}, \frac{3 \pi}{4} $. QED.

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

Comment: This problem shouldn't have been too hard; finding that specific formula for the area of the triangle could have been derived by drawing an altitude. And the double-angle identity should always be known. Lastly, maximizing the sine function is a given.

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

Practice Problem: (2006 Skyview) If $ \sin{x} = \frac{3}{5} $ and $ \cos{x} = \frac{4}{5} $, what is $ \sin{(3x)} $?

Friday, October 27, 2006

Square Sum Stuff. Topic: Polynomials/S&S. Level: AMC/AIME.

Problem: Evaluate the summation

$ \displaystyle \sum_{k=1}^{\infty} \frac{k^2}{2^k} = \frac{1^2}{2^1}+\frac{2^2}{2^2}+\frac{3^2}{2^3}+\frac{4^2}{2^4}+\cdots $.

Solution: Here's a technique that will help you evaluate infinite series that are of the form polynomial over exponential. It's based on the idea of finite differences:

If $ P $ is a polynomial with integer coefficients of degree $ n $ then

$ P(x+1)-P(x) $

is a polynomial of degree $ n-1 $ (not hard to show; just think about it).

So let

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

Then consider $ 2S $ by simply multiplying each term by $ 2 $:

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

And now find the difference $ 2S-S = S $ by subtracting the terms with equal denominators. We get

$ S = 2S-S = 1+\frac{2^2-1^2}{2^1}+\frac{3^2-2^2}{2^2}+\frac{4^2-3^2}{2^3}+\cdots $

$ S = 1+\frac{3}{2^1}+\frac{5}{2^2}+\frac{7}{2^3}+\cdots $.

Notice that the numerator is now a polynomial of degree $ 1 $ instead of $ 2 $. Repeating this, we have

$ 2S = 2+3+\frac{5}{2^1}+\frac{7}{2^2}+\cdots $

and

$ S = 2S-S = 2 + 2 + \frac{5-3}{2^1}+\frac{7-5}{2^2}+\cdots $

$ S = 2 + (2 + 1+\frac{1}{2}+\cdots) $.

Notice that the latter part is just a geometric series which sums to

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

so $ S = 2+4 = 6 $. QED.

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

Comment: The method of finite differences is extremely useful and is basically a simplified version of calculus - $ P(x+1)-P(x) \approx P^{\prime}(x) $ in a very approximating sense. It's a good thing to know, though, because then you have a better understanding of how polynomials work.

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

Practice Problem: Let $ P $ be a polynomial with integer coefficients. Using the method of finite differences, predict the degree of $ P $.

$ P(1) = 1 \mbox{ } P(2) = 9 \mbox{ } P(3) = 20 \mbox{ } P(4) = 36 \mbox{ } P(5) = 59 \mbox{ } P(6) = 91 $.

Wednesday, October 25, 2006

Serious Substitution. Topic: Calculus.

Problem: Use the substitution $ z = \sqrt{x} $ to solve the differential equation $ 4x \frac{d^2y}{dx^2}+2 \frac{dy}{dx}+y = 0 $.

Solution: Well, let's do what it says. From the chain rule, we have

$ \displaystyle \frac{dy}{dz} = \frac{dy}{dx} \cdot \frac{dx}{dz} = 2z \frac{dy}{dx} $.

Then we also have by the product rule and chain rule again

$ \displaystyle \frac{d^2y}{dz^2} = 2 \frac{dy}{dx}+2z \frac{d^2y}{dx^2} \cdot \frac{dx}{dz} = \frac{1}{z} \cdot \frac{dy}{dz}+4z^2 \frac{d^2y}{dx^2} $.

So we can make the substitutions

$ \displaystyle 4x \frac{d^2y}{dx^2} = 4z^2 \frac{d^2y}{dx^2} = \frac{d^2y}{dz^2}-\frac{1}{z} \cdot \frac{dy}{dz} $

and

$ \displaystyle \frac{dy}{dx} = \frac{1}{2z} \cdot \frac{dy}{dz} $

to obtain the differential equation

$ \frac{d^2y}{dz^2}-\frac{1}{z} \cdot \frac{dy}{dz} + 2 \cdot \frac{1}{2z} \cdot \frac{dy}{dz}+y = \frac{d^2y}{dz^2}+y = 0 $.

But we know the solution to this is $ y = C_1 \cos{z}+C_2 \sin{z} $ so our final solution is

$ y = C_1 \cos{\sqrt{x}}+C_2 \sin{\sqrt{x}} $.

QED.

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

Comment: This substitution is, of course, not really natural but was actually found after solving the ODE in another way. Fortunately, it simplifies the problem rather greatly and seems to be a useful technique to look out for.

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

Practice Problem: Find another way to solve the differential equation.

New Stuff!

My Tests:

2006-2007 Warm-Up 4

Tuesday, October 24, 2006

Everything You Ever Wanted To Know About Mods...

Tutorials:

Modular Arithmetic

As It Goes. Topic: Sets. Level: AIME.

Problem: (1992 Putnam - B1) Let $ S $ be a set of $ n $ distinct real numbers. Let $ A_s $ be the set of numbers that occur as averages of two distinct elements of $ S $. For a given $ n \ge 2 $, what is the smallest possible number of elements in $ A_s $?

Solution: We claim that $ |A_s| \ge 2n-3 $. To show this, let the elements of $ S $ be $ a_1 < a_2 < \cdots < a_n $. We can easily see that

$ \frac{a_1+a_2}{2} < \frac{a_1+a_3}{2} < \cdots < \frac{a_1+a_n}{2} $,

giving us $ n-1 $ distinct elements of $ A_s $. Furthermore,

$ \frac{a_1+a_n}{2} < \frac{a_2+a_n}{2} < \cdots < \frac{a_{n-1}+a_n}{2} $,

giving us an additional $ n-2 $ distinct elements of $ A_s $ for a total of $ 2n-3 $ elements. For any $ n \ge 2 $, the set $ S = \{1, 2, \ldots, n\} $ gives $ A_s = \{1.5, 2, 2.5, \ldots, n-0.5\} $, which has precisely $ 2n-3 $ elements. QED.

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

Comment: A good strategy for solving minima/maxima problems (inequalities, too) is to find a case which you think may be a minimum/maximum and try to prove it. In this case, you can guess that the set $ \{1, 2, \ldots, n\} $ gives the minimum number of distinct average elements and try to find that many distinct elements in an arbitrary set, as shown above through ordering.

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

Practice Problem: What if you consider the average of three elements?

Sunday, October 22, 2006

Integrrr... Topic: Algebra. Level: AIME.

Problem: (1992 Putnam - A1) Prove that $ f(n) = 1-n $ is the only integer-valued function defined on the integers that satisfies the following conditions.

(i) $ f(f(n)) = n $;
(ii) $ f(f(n+2)+2) = n $;
(iii) $ f(0) = 1 $.

Solution: We will use induction to prove the claim for $ -k \le n \le k+1 $ where $ k $ is a nonnegative integer.

Base Case: $ k = 0 \Rightarrow f(0) = 1, f(1) = 0 $ which are true from (iii) and (i).

Induction Step: Assume that $ f(n) = 1-n $ for $ -k \le n \le k+1 $.

Then $ f(k+2) = f(f(-k+1)+2) = -k-1 = 1-(k+2) $ by our induction hypothesis and (ii). Also, $ f(-(k+1)) = k+2 = 1-(-(k+1)) $ by (i), completing the induction.

Hence $ f(n) = 1-n $ for all integers. QED.

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

Comment: Functional equations over the integers are not usually too hard to handle; induction is usually a good way to handle them, strong induction in particular. Most of the time you just need to find out what set to induct on, in this case $ [-k,k+1] $.

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

Practice Problem: Find all functions $ f: \mathbb{N} \rightarrow \mathbb{N} $ such that

(1) $ f(f(n)+n) = f(n) $;
(2) There exists a $ n_0 $ such that $ f(n_0) = 1 $.

Saturday, October 21, 2006

Practice Makes Perfect. Topic: All. Level: AIME/Olympiad.

Some problems that I have done and not felt like writing solutions to...

Practice Problem #1: (2004 Putnam - A2) For $ i = 1, 2 $ let $ T_i $ be a triangle with side lengths $ a_i, b_i, c_i $, and area $ A_i $. Suppose that $ a_1 \le a_2 $, $ b_1 \le b_2 $, $ c_1 \le c_2 $ and that $ T_2 $ is an acute triangle. Does it follow that $ A_1 \le A_2 $?

Practice Problem #2: (2001 Putnam - B3) For any positive integer $ n $, let $ \langle n \rangle $ denote the integer closest to $ \sqrt{n} $. Evaluate

$ \displaystyle \sum_{n=1}^{\infty} \frac{2^{\langle n \rangle}+2^{-\langle n \rangle}}{2^n} $.

Practice Problem #3: (2000 Putnam - B2) Prove that the expression

$ \frac{gcd(m,n)}{n} (nCm) $

is an integer for all pairs of integers $ n \ge m \ge 1 $.

Wednesday, October 18, 2006

Dattebayo... Topic: Algebra/NT/Polynomials. Level: AIME/Olympiad.

Problem: (2004 Putnam - B1) Let $ P(x) = c_nx^n+c_{n-1}x^{n-1}+\cdots+c_0 $ be a polynomial with integer coefficients. Suppose that $ r $ is a rational number such that $ P(r) = 0 $. Show that the $ n $ numbers

$ c_nr, c_nr^2+c_{n-1}r, c_nr^3+c_{n-1}r^2+c_{n-2}r, \ldots, c_nr^n+c_{n-1}r^{n-1}+\cdots+c_1r $

are integers.

Solution: Well rational numbers only really have one good way of being handled - rewrite $ r $ as $ \frac{p}{q} $ for relatively prime integers $ p, q $. We then know that

$ P(r) = \frac{c_np^n+c_{n-1}p^{n-1}q+\cdots+c_0q^n}{q^n} = 0 $

so the numerator is zero. Also, we may write the $ n $ integers as

$ \frac{c_np^n+c_{n-1}p^{n-1}q+\cdots+c_{k+1}p^{k+1}q^{n-(k+1)}}{p^kq^{n-k} $

for $ k = 0, 1, \ldots, n-1 $ (from substituting $ r = \frac{p}{q} $ and finding a common denominator). Notice that

$ c_np^n+c_{n-1}p^{n-1}q+\cdots+c_{k+1}p^{k+1}q^{n-(k+1)} \\ = -(c_kp^kq^{n-k}+c_{k-1}p^{k-1}q^{n-(k-1)}+\cdots+c_0q^n) $

from $ P(r) = 0 $. The LHS gives us that the quantity is divisible by $ p^k $ (since every term has a power of $ p $ greater than or equal to $ k $) and the RHS gives us that the quantity is divisible by $ q^{n-k} $ (since every term has power of $ q $ greater than or equal to $ n-k $). Since $ p $ and $ q $ are relatively prime, however, we must have

$ (p^kq^{n-k}) | (c_np^n+c_{n-1}p^{n-1}q+\cdots+c_{k+1}p^{k+1}q^{n-(k+1)}) $

or

$ \frac{c_np^n+c_{n-1}p^{n-1}q+\cdots+c_{k+1}p^{k+1}q^{n-(k+1)}}{p^kq^{n-k} $

is an integer for $ k = 0, 1, \ldots, n-1 $, as desired. QED.

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

Comment: Actually more difficult than I expected from a B1 on the Putnam; it required solid knowledge of how to deal with rational numbers and roots of polynomials. That said, a good number of people got it right, so maybe I just messed around for a bit too long. In any case, this is a problem worth learning how to do.

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

Practice Problem: Prove that the remainder of $ P(x) $ when divided by $ x-r $ is $ P(r) $.

Tuesday, October 17, 2006

Fraction Faction. Topic: Inequalities/NT. Level: AIME/Olympiad.

Problem: (2005 Putnam - B2) Find all positive integers $ n, k_1, \ldots, k_n $ such that $ k_1+\cdots+k_n = 5n-4 $ and

$ \frac{1}{k_1}+\cdots+\frac{1}{k_n} = 1 $.

Solution: First, by the Cauchy-Schwarz Inequality, we find that

$ \displaystyle \left(\sum k_i \right)\left(\sum \frac{1}{k_i}\right) \ge n^2 \Rightarrow \sum \frac{1}{k_i} \ge \frac{n^2}{5n-4} $.

For $ n > 4 $, however, $ n^2 > 5n-4 \Rightarrow \sum \frac{1}{k_i} > 1 $, which is a contradiction. Hence $ n \le 4 $. Then we proceed by cases:

CASE 1: $ n = 1 $

Clearly $ k_1 = 1 $ is the only solution.

CASE 2: $ n = 2 $

We have $ k_1+k_2 = 6 $ so our possible pairs are $ (1,5); (2,4); (3,3) $ (and permutations), none of which work.

CASE 3: $ n = 3 $

We have $ k_1+k_2+k_3 = 11 $. Notice that $ k_i \neq 1 $ or the sum of the reciprocals will exceed $ 1 $. So our possible triplets are $ (2, 2, 7); (2, 3, 6); (2, 4, 5); (3, 3, 5); (3, 4, 4) $ (and permutations), of which only $ (2, 3, 6) $ works.

CASE 4: $ n = 4 $

Notice that with our use of Cauchy Schwarz above at $ n = 4 $ we have $ \sum \frac{1}{k_i} \ge \frac{n^2}{5n-4} = \frac{16}{16} = 1 $, so equality must hold. Hence $ k_1 = k_2 = k_3 = k_4 = 4 $ is the only solution.

In summary, our solutions are

$ n = 1 $: $ \{1\} $
$ n = 3 $: $ \{2,3,6\} $
$ n = 4 $: $ \{4, 4, 4, 4\} $.

QED.

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

Comment: The only really interesting part of this problem was bounding with Cauchy. After that, it's just manual counting to figure out the solutions. But overall this is a good test of using inequalities to simplify number theory problems.

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

Practice Problem: What if $ k_1+\cdots+k_n = 4n-3 $?

Sunday, October 15, 2006

Great Expectations. Topic: Probability. Level: AMC/AIME.

Definition: The expected value of a random variable $ X $ is $ \displaystyle \sum_x x \cdot p(x) $, where the summation is taken over all possible values $ x $ of $ X $ and $ p(x) $ is the probability that $ X = x $. For example, the expected value of a die roll is

$ 1 \cdot \frac{1}{6}+ 2\cdot \frac{1}{6}+ \cdots + 6 \cdot \frac{1}{6} = \frac{7}{2} $.

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

Problem: What is the expected number of rolls on a standard die that you need to make before every number shows up at least once?

Solution: Let $ E_n $ be the expected number of rolls before $ n $ of the numbers shows up at least once. Clearly, $ E_1 = 1 $. Then

$ E_2 = \frac{5}{6}(E_1+1)+\frac{1}{6}(E_2+1) $

because there is a $ \frac{5}{6} $ probability that it will take exactly one more than $ E_1 $ (if we roll a new number) and a $ \frac{1}{6} $ probability that it will result in the same number as before and we start from the same situation again. Using this same argument, we deduce that

$ E_{n+1} = \frac{6-n}{6}(E_n+1)+\frac{n}{6}(E_{n+1}+1) $,

which is equivalent to

$ E_{n+1} = E_n+\frac{6}{6-n} $.

Since we want to find $ E_6 $, we just apply this recursion $ 6 $ times to get

$ E_6 = 6\left(1+\frac{1}{2}+\cdots+\frac{1}{6}\right) = 14.7 $.

QED.

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

Comment: Expected value is an interesting topic and can result in a bunch of strange recursions, but it's quite cool in that respect. It's "possible" to solve this problem using only probability, but that would get very ugly very quickly.

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

Practice Problem: Generalize this to a die with $ 8 $, $ 12 $, or $ 20 $ sides (the three bigger regular die which exist).

Saturday, October 14, 2006

Sumthing's Up. Topic: Algebra/S&S. Level: AIME.

Problem: (1994 Putnam - A1) Suppose that a sequence $ a_1, a_2, a_3, \ldots $ satisfies $ 0 < a_n \le a_{2n}+a_{2n+1} $ for all $ n \ge 1 $. Prove that the series $ \displaystyle \sum_{n=1}^{\infty} a_n $ diverges.

Solution: Well, let's see. $ a_1 $ is an arbitrary constant. Then

$ a_2+a_3 \ge a_1 $

$ (a_4+a_5)+(a_6+a_7) \ge a_2+a_3 \ge a_1 $.

Whoa, that looks like a pattern... Indeed, by induction we can show that

$ S_k = (a_{2^k}+a_{2^k+1})+(a_{2^k+2}+a_{2^k+3})+\cdots+(a_{2^{k+1}-2}+a_{2^{k+1}-1}) \ge S_{k-1} $

for $ k \ge 1 $ and $ S_0 = a_1 $, so

$ \displaystyle \sum_{n=1}^{\infty} a_n = \sum_{k=1}^{\infty} S_k \ge \sum_{k=1}^{\infty} a_1 $,

which clearly diverges. QED.

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

Comment: Pretty interesting and easy problem, though from the scores evidently a lot of people missed some minor error in rigor (59 people got 9/10, and also 59 people got a full score). In any case, this is a good concept for infinite series, and should be familiar to most people who do math a lot (a.k.a. if you are familiar with the following practice problem).

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

Practice Problem: Without calculus, show that $ \displaystyle \sum_{n=1}^{\infty} \frac{1}{n} $ diverges.

Prime Factorizations... With A Twist!

Tutorials:

Prime Factor Bar Graphs

Thursday, October 12, 2006

Divvy It Up. Topic: Number Theory. Level: AMC.

Problem: Find the number of divisors of a postive integers.

Solution: For all you people at math club who didn't understand it... here it is. Suppose our number is $ n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k} $, where the $ p $'s are the prime divisors of $ n $ and the $ e $'s are the number of times (power) each $ p $ divides $ n $. For example, $ 36 = 2^2 \cdot 3^2 $.

We will show that the number of divisors is $ (e_1+1)(e_2+1) \cdots (e_k+1) $. Let $ d $ be a divisor of $ n $. Write $ d $ as

$ d = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k} $.

We know that $ d $ can only have the prime divisors of $ n $ or it obviously won't divide $ n $. So now it remains to choose the $ a $'s. Well, what can $ a_1 $ be? It can be $ 0, 1, 2, \ldots, e_1 $ but if $ a_1 > e_1 $ then $ d $ will have more $ p_1 $'s than $ n $ and won't divide it. So there are $ e_1+1 $ choices there. Similarly, $ a_2 $ can be $ 0, 1, 2, \ldots, e_2 $ and $ a_j $ can be $ 0, 1, 2, \ldots, e_j $ for $ j = 3, 4, \ldots, k $.

So if we just multiply the number of ways we can pick the power on each prime factor, we get the total number of divisors, i.e. $ (e_1+1)(e_2+1) \cdots (e_k+1) $. QED.

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

Comment: This is very important for general number theory; it is one of the fundamental ideas. Plus, it's logical and easy to remember so it should always be accessible during competitions.

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

Practice Problem: (2002-2003 MIC Championships Team Test - #2) How many natural numbers less than $ 50,000 $ have exactly $ 35 $ positive integer factors?

Wednesday, October 11, 2006

Tuesday, October 10, 2006

We're Closed. Topic: Algebra/Sets. Level: AIME.

Problem: (1995 Putnam - A1) Let $ S $ be a set of real numbers which is closed under multiplication (that is, if $ a $ and $ b $ are in $ S $, then so is $ ab $). Let $ T $ and $ U $ be disjoint subsets of $ S $ whose union is $ S $. Given that the product of any three (not necessarily distinct) elements of $ T $ is in $ T $ and that the product of any three elements of $ U $ is in $ U $, show that at least one of the two subsets $ T, U $ is closed under multiplication.

Solution: Let's attack this problem using contradiction. Suppose that both $ T $ and $ U $ are NOT closed under multiplication. What happens? Well, we then know that there are $ a, b \in T $ such that $ ab \in U $ (since $ ab \in S $ and $ ab \not\in T $) and $ c, d \in U $ such that $ cd \in T $. However, we then have

$ abcd = a \cdot b \cdot (cd) \in T $ (three elements in $ T $)

$ abcd = (ab) \cdot c \cdot d \in U $ (three elements in $ U $),

which is a contradiction since $ T $ and $ U $ are disjoint. Hence at least one of them must be closed under multiplication. QED.

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

Comment: Ha, that wasn't so bad was it. Well it took a bit to come up with, but after just realizing contradiction was an easy way to do it and listing out what you knew, putting everything together was pretty quick. Working with sets is a good way to develop your thinking skills since it's quite theoretical.

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

Practice Problem: Which of the standard operations (addition, subtraction, multiplication, division) are the following sets closed under: (a) the reals, (b) the rationals, (c) the integers, (d) the odd integers, (e) the natural numbers, and (f) powers of $ 2 $. Exclude zero from all of these sets.

Sunday, October 8, 2006

New Stuff!

Tutorials:

Triangle Ratios (Advanced)

Think Rationally. Topic: Algebra/NT/Polynomials. Level: AIME/Olympiad.

Problem: (2003 Putnam - B4) Let

$ f(z) = az^4+bz^3+cz^2+dz+e = a(z-r_1)(z-r_2)(z-r_3)(z-r_4) $

where $ a, b, c, d, e $ are integers, $ a \neq 0 $. Show that if $ r_1+r_2 $ is a rational number and $ r_1+r_2 \neq r_3+r_4 $, then $ r_1r_2 $ is a rational number.

Solution: Some important results that you don't need to prove - if $ x $ and $ y $ are rational, then

$ x+y $, $ x-y $, $ xy $, and $ \frac{x}{y} $

are rational (note the last one is only true for $ y \neq 0 $).

We start of by using Vieta's Formulas, which tells us that

$ S_1 = r_1+r_2+r_3+r_4 $

$ S_2 = r_1r_2+r_1r_3+r_1r_4+r_2r_3+r_2r_4+r_3r_4 = (r_1+r_2)(r_3+r_4)+r_1r_2 $

$ S_3 = r_1r_2r_3+r_1r_2r_4+r_1r_3r_4+r_2r_3r_4 = r_1r_2(r_3+r_4)+r_3r_4(r_1+r_2) $

are all rational. But since we know $ r_1+r_2 $ is rational, we must have $ r_3+r_4 = S_1-(r_1+r_2) $ be rational as well. Then

$ (r_1+r_2)(r_3+r_4) $

and

$ r_1r_2+r_3r_4 = S_2-(r_1+r_2)(r_3+r_4) $

are rational. Let $ k = r_3+r_4-r_1+r_2 \neq 0 $, which we know is rational. Then

$ S_3 = r_1r_2(r_1+r_2+k)+r_3r_4(r_1+r_2) = (r_1r_2+r_3r_4)(r_1+r_2)+r_1r_2k $,

but $ (r_1r_2+r_3r_4)(r_1+r_2) $ is rational, so $ r_1r_2k $ must be rational as well. Finally, since $ k $ is rational and nonzero, we have $ r_1r_2 $ rational. QED.

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

Comment: This problem required slugging through some rational/irrational arguments, but turned out to be not so bad. As long as you recognized the use of Vieta's Formulas, you should have been able to work out the details to get to the solution.

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

Practice Problem: Find a polynomial $ p(z) $ with $ r_1+r_2 = r_3+r_4 $ such that the above argument does not hold.

Thursday, October 5, 2006

Binary Soup. Topic: Number Theory. Level: AIME/Olympiad.

Problem: (1998 Putnam - A4) Let $ A_1 = 0 $ and $ A_2 = 1 $. For $ n > 2 $, the number $ A_n $ is defined by concatenating the decimal expansions of $ A_{n-1} $ and $ A_{n-2} $ from left to right. For example $ A_3 = A_2A_1 = 10 $, $ A_4 = A_3A_2 = 101 $, $ A_5 = A_4A_3 = 10110 $, and so forth. Determine all $ n $ such that $ 11 $ divides $ A_n $.

Solution: A recursively defined sequence divisibility problem. Not too uncommon; we use our usual strategy and apply $ \pmod{11} $ and find the recursive relation $ \pmod{11} $. First define $ B_n $ to be the number of digits in $ A_n $; notice, however, that $ B_n = B_{n-1}+B_{n-2} $ and $ B_1 = B_2 = 1 $, meaning that $ B_n $ is simply the Fibonnaci sequence.

We can see that $ A_n $ is just $ A_{n-1} $ followed by $ B_{n-2} $ zeros and then added to $ A_{n-2} $. Translated into math, this is

$ A_n = 10^{B_{n-2}} A_{n-1}+A_{n-2} $.

But we only care about this $ \pmod{11} $, so

$ A_n \equiv (-1)^{B_{n-2}} A_{n-1}+A_{n-2} \pmod{11} $.

Well let's start writing out terms for $ B_n \pmod{2} $ (since that's all we care about) and $ A_n \pmod{11} $.

$ B_n: 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0 \ldots $

$ A_n: 0, 1, 10, 2, 1, 1, 0, 1, 10, 2, 1, 1 \ldots $

We see that every six, both sequences repeat and since they only depend on the two terms before them, we know they will repeat infinitely. Hence our answers are all positive integers $ n \equiv 1 \pmod{6} $. QED.

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

Comment: This problem really wasn't all that hard for an A4; it only required a little sequence construction to find out what the answer was and a rigorous proof even wouldn't be too much of a challenge. It's a good exercise in converting a word problem to something you can work with mathematically and applying mods effectively.

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

Practice Problem: The Fibonnaci sequence is defined by $ F_0 = F_1 = 1 $ and $ F_n = F_{n-1}+F_{n-2} $ for $ n > 1 $. Prove that if $ a|b $ then $ F_a|F_b $.

New Stuff!

Practice Tests:

2003 MIC Ch. Individual
2003 MIC Ch. Individual MC

Tutorials:

Logarithms

Wednesday, October 4, 2006

So Complex, Yet So Plain. Topic: Complex Numbers/Polynomials. Level: AMC/AIME.

Problem: (2006-2007 Warm-Up 3 - #13) What is the area of the shape formed by connecting the solutions to $ x^3-5x+12x-7 = 0 $ in the complex plane?

Solution: Well, let's start off by finding those solutions. It's not hard to guess that $ x= 1 $ is a solution, so we have

$ (x-1)(x^2-4x+7) = 0 $.

Using the quadratic formula, we get the other two solutions to be

$ x = 2 \pm i \sqrt{3} $.

So our points are $ 1, 2+i\sqrt{3}, 2-i\sqrt{3} $. This makes an isosceles triangle with base $ 2 \sqrt{3} $ and height $ 1 $ in the complex plane, which has area $ \sqrt{3} $. QED.

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

Comment: Pretty easy after we guessed that $ x = 1 $ was a solution; a general formula for the area probably gets ugly when the polynomial is irreducible. But in this case, we can draw the triangle and figure out the area without too many tricks.

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

Practice Problem: What is the area of the shape formed by connecting the solutions to $ x^3 = 1 $ in the complex plane?

New Stuff!

My Tests:

2006-2007 Warm-Up 3

Practice Tests:

2002 MIC Ch. Individual
2002 MIC Ch. Individual MC

Tutorials:

Combinatorics

Tuesday, October 3, 2006

Conehead. Topic: Geometry. Level: AMC.

Problem: (1998 Putnam - A1) A right circular cone has base of radius $1$ and height $3$. A cube is inscribed in the cone so that one face of the cube is contained in the base of the cone. What is the side length of the cube?

Solution: Suppose the cube has side length $ s $. Then the top face of the cube has to fit into a circle of radius

$ 1-\frac{s}{3} $

by proportions ($ 3-s $ of the total height of $ 3 $ will still be above the cube). So its side length can be at most

$ \left(1-\frac{s}{3}\right)\sqrt{2} $

since a square with $ \sqrt{2} $ times the radius of a circle is perfectly inscribed. Then we have

$ \left(1-\frac{s}{3}\right)\sqrt{2} \ge s \Rightarrow s \le \frac{9\sqrt{2}-6}{7} $,

so the side length must be the maximum $ \frac{9\sqrt{2}-6}{7} $ in order to be inscribed. QED.

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

Comment: This problem was not difficult at all. Just drawing a picture and using some ratios it's easy to find the inequality and then solve for $ s $ knowing that equality must hold for inscribed things.

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

Practice Problem: Can you do this for a general cone with base radius $ a $ and height $ b $?