Tuesday, February 27, 2007

Recurrences Are Cool. Topic: Probability/S&S. Level: AIME.

Problem: Let $ p_k $ be the probability of choosing a positive integer $ n $ from the interval $ [2^{k-1}, 2^k-1] $ such that the binary representation of $ n $ does not contain three consecutive $ 1 $'s. Evaluate the infinite summation $ p_1+p_2+\cdots $.

Solution: First, let $ S_k $ be the number of positive integers $ n $ in the interval $ [2^{k-1}, 2^k-1] $ that do not contain three consecutive $ 1 $'s in their binary representations - note that it is equivalent to the number of binary strings of length $ k $ starting with a $ 1 $ that satisfy that property. By testing, we have $ S_1 = 1 $, $ S_2 = 2 $, $ S_3 = 3 $, $ S_4 = 6 $, $ S_5 = 11 $, $ S_6 = 20 $. You can construct a certain type of table to make these calculations easier. We notice that the recurrence $ S_{k+3} = S_{k+2}+S_{k+1}+S_k $ seems to hold, so we want to try and prove this.

We categorize the strings of length $ k+3 $ based on the last occurence of $ 0 $. It must either be in the last, second to last, or third to last spots. If it is in the last spot, the string is $ \text{blah}0 $ where $ \text{blah} $ has length $ k+2 $ so there are $ S_{k+2} $ of those. Similarly, the other possibilities are $ \text{blah}01 $ or $ \text{blah}001 $, where the $ \text{blah} $'s have length $ k+1 $ and $ k $, respectively, giving the recurrence. Now it remains to sum it.

We want to evaluate $ \displaystyle \sum_{k=1}^{\infty} p_k = \sum_{k=1}^{\infty} \frac{S_k}{2^{k-1}} $ since there are $ 2^{k-1} $ binary strings of length $ k $ that begin with $ 1 $.

Luckily, we know a cool way to evaluate recurrences over a geometric sequence. Let $ \displaystyle S = \sum_{k=1}^{\infty} \frac{S_k}{2^{k-1}} $. Then

$ \displaystyle 2S = 2S_1+\sum_{k=1}^{\infty} \frac{S_{k+1}}{2^{k-1}} $

$ \displaystyle 4S = 4S_1+2S_2+\sum_{k=1}^{\infty} \frac{S_{k+2}}{2^{k-1}} $

$ \displaystyle 8S = 8S_1+4S_2+2S_3+\sum_{k=1}^{\infty} \frac{S_{k+3}}{2^{k-1}} $.

Notice, now that if we take $ S = 8S-4S-2S-S $ a lot of terms cancel due to the recurrence. In fact, all of the summations do! So

$ \displaystyle S = (8S_1+4S_2+2S_3)-(4S_1+2S_2)-2S_1+ \sum_{k=1}^{\infty} \frac{S_{k+3}-S_{k+2}-S_{k+1}-S_k}{2^{k-1}} $

$ S = 2S_1+2S_2+2S_3 = 12 $.

QED.

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

Comment: Both parts of this problem are pretty classical. The first, finding a recurrence for a string satisfying a certain property, and the second, evaluating an infinite summation of the terms of a sequence divided by a geometric series. These two techniques are very useful, however, in approaching many problems. It would not be fun to solve a problem and get to the last step only to find that you do not know how to evaluate the summation to get the final answer.

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

Practice Problem: Evaluate $ \displaystyle \sum_{k=1}^{\infty} \frac{F_k}{n^k} $, where $ n > 1 $ is a positive integer and $ F_k $ is the Fibonacci sequence (i.e. $ F_0 = F_1 = 1 $ and $ F_{k+1} = F_k+F_{k-1} $ for all positive integers $ k $).

Friday, February 23, 2007

2007 Mock AIME 6.

The 2007 Mock AIME 6 is underway! The test can be found here and more information can be found at the AoPS Forum.

Thursday, February 22, 2007

Pythagorean x3. Topic: Geometry/NT. Level: AMC.

Problem: (2007 AMC12B - #23) How many non-congruent right triangles with positive integer leg lengths have areas that are numerically equal to $ 3 $ times their perimeters?

Solution: Well, basically, you should know the Pythagorean triple generating formula, i.e. $ a = k(u^2-v^2) $, $ b = 2kuv $, $ c = k(u^2+v^2) $. Substitute accordingly and we have to solve the diophantine equation

$ \frac{1}{2} \cdot k(u^2-v^2) \cdot 2kuv = 3 \cdot (k(u^2-v^2)+2kuv+k(u^2+v^2)) $

which conveniently simplifies to

$ kv(u-v) = 6 $.

Obviously then $ k = 1, 2, 3, 6 $ so look at these cases:

$ k = 1 $: We can take $ v = 1, 2, 3, 6 $ to get the triples $ (14, 48, 50); (20, 21, 29); (16, 30, 34); (13, 84, 85) $.

$ k = 2 $: We can take $ v = 1, 3 $ to get the triples $ (16, 30, 34); (14, 48, 50) $ both of which are already counted.

$ k = 3 $: We can take $ v = 1, 2 $ to get the triples $ (18, 24, 30); (15, 24, 39) $.

$ k = 6 $: We can take $ v = 1 $ to get the triple $ (18, 24, 30) $, which is already counted.

So we have $ 4+2 = 6 $ triangles. QED.

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

Comment: Not too hard if you knew the generating formula for Pythagorean triples. It was a little annoying having to check for repeated triples, but at least there weren't that many.

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

Practice Problem: (2007 AMC 12B - #24) How many pairs of positive integers $ (a, b) $ are there such that $ \text{gcd}(a, b) = 1 $ and

$ \frac{a}{b}+\frac{14b}{9a} $

is an integer?

Sunday, February 18, 2007

Mu Alpha Practice Tests.

There are so many, so I'm not going to bother putting links to them all. You can reach any test by going to the URL "http://wangsblog.com/jeffrey/TestName.pdf" where TestName may be replaced by any of the following:

ABTest
Algebra34
AlphaIndividual
Answers (for all tests)
BCTest
Cipher2003_16ques
Cipher2003Alpha17
Cipher2003Mu15
Cipher2003Theta17
CirclesAreaVolume
Gemini
GeometryClass
LimDeriv2003
MuIndividual
MuS&S
NumberTheory
ProbAlpha
ProbilityTheta
S&SAlpha
TheNumber_e
ThetaIndividual
ThetaLogsExps
TrigClassTest

So, for example, if I wanted the Number Theory test I would go to "http://wangsblog.com/jeffrey/NumberTheory.pdf". Not all of these tests are around, but this should give you some idea of what to expect.

Currently...

Writing a Mock AIME. Stay tuned!

Friday, February 16, 2007

Common Law. Topic: Geometry/Trigonometry. Level: AIME.

Problem: (2003 AIME1 - #12) In convex quadrilateral $ ABCD $, $ \angle A = \angle C $, $ AB = CD = 180 $, and $ AD \neq BC $. The perimeter of $ ABCD $ is $ 640 $. Find $ \lfloor 1000 \cos{\angle A} \rfloor $.

Solution: Well, let's say that $ BC = x $ and $ AD = y $. We know $ x+y+180+180 = 640 \Rightarrow x+y = 280 $. Consider the two triangles $ ABD $ and $ CBD $. Using the Law of Cosines on $ \angle A $ and $ \angle C $, which we know are equal (let them both equal $ \theta $), we have

$ BD^2 = AB^2+AD^2-2 \cdot AB \cdot AD \cos{\theta} $

$ BD^2 = CB^2+CD^2-2 \cdot CB \cdot CD \cos{\theta} $.

Substituting $ AB = CD = 180 $ and $ BC = x $, $ AD = y $, it becomes

$ BD^2 = 180^2+y^2-360y \cos{\theta} $

$ BD^2 = x^2+180^2-360x \cos{\theta} $.

Equating the two,

$ 180^2+y^2-360y \cos{\theta} = x^2+180^2-360x \cos{\theta} \Rightarrow x^2-y^2 = 360(x-y)\cos{\theta} $.

Recall that $ x+y = 280 $, so

$ x^2-y^2 = (x+y)(x-y) = 280(x-y) = 360(x-y)\cos{\theta} $.

Finally, since $ x \neq y \Rightarrow x-y \neq 0 $, we divide through to get

$ \cos{\theta} = \frac{280}{360} = \frac{7}{9} \Rightarrow \lfloor 1000 \cos{\theta} \rfloor = 777 $.

QED.

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

Comment: This is a demonstration of the power of something as simple as the Law of Cosines. Never underestimate what a little experimentation can do for you on the AIME; play around with equations. If at first you do not see an approach, look at the question itself for hints. Since you have to find the cosine, it should immediately trigger the Law of Cosines because it relates sides and angles. Then apply the Law of Cosines to the important angles (the ones you know something about), in this case $ \angle A $ and $ \angle C $, from which the result falls quite nicely.

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

Practice Problem: (2003 AIMEI - #6) The sum of the areas of all triangles whose vertices are also vertices of a $ 1\times 1 \times 1 $ cube is $m+\sqrt{n}+\sqrt{p}$, where $m$, $n$, and $p$ are integers. Find $m+n+p$.

Tuesday, February 13, 2007

Lots of Fn. Topic: Algebra/S&S. Level: AIME.

Problem: Let $ F_n $ be the Fibonnaci sequence that begins with $ F_1 = 1 $, $ F_2 = 1 $, etc. Show that

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

Solution: We will use induction (as expected). First, rewrite the equality as

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

The base case is easy, since we have $ F_4 = 3 = 2^2-1^2 = F_3^2-F_1^2 $. Now we will show that it is true for $ n = k+1 $ assuming it is true for $ n \le k $. We have

$ F_{2k+2} = F_{2k+1}+F_{2k} = 3F_{2k}-F_{2k-2} $.

Now we apply the inductive hypothesis to get

$ F_{2k+2} = 3F_k(2F_{k+1}-F_k)-F_{k-1}(2F_k-F_{k-1}) $,

which we can simplify with the substitution $ F_{k-1} = F_{k+1}-F_k $ to get

$ F_{2k+2} = 3F_k(2F_{k+1}-F_k)-(F_{k+1}-F_k)(3F_k-F_{k+1}) = 2F_kF_{k+1}+F_{k+1}^2 $

and finally from $ F_k = F_{k+2}-F_{k+1} $ we get

$ F_{2k+2} = F_{k+1}(2F_{k+2}-F_k) $

as desired. QED.

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

Comment: Not a particularly insightful problem, but admittedly a pretty neat identity. Standard substitution/induction method, which you should all be familiar with right now since I use it all the time here. Maybe there's some cool combinatorics argument that I can't see...

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

Practice Problem: Show $ F_{2n} = F_n^2+F_{n-1}^2 $ through a combinatorics argument, where $ F_0 = 1 $, $ F_1 = 1 $, etc. is the Fibonnaci sequence.

[Hint: $ F_n $ is the number of ways to tile a $ 2 \times n $ board with $ 1 \times 2 $ tiles.]

Sunday, February 11, 2007

Return Of The Triangle. Topic: Geometry/Inequalities/Trigonometry. Level: AIME.

Problem: (1961 IMO - #2) Let $ a, b, c $ be the sides of a triangle, and $ T $ its area. Prove:

$ a^2+b^2+c^2 \ge 4T\sqrt{3} $.

In what case does equality hold?

Solution: We begin with the trivial inequality, $ (a-b)^2 \ge 0 $, which has equality at $ a = b $. Rearrange to get

$ a^2+b^2 \ge 2ab $.

Let $ \theta $ be the angle between the sides with lengths $ a, b $. Since $ 2 \ge \cos{\theta}+\sqrt{3}\sin{\theta} $ (can be proved by combining RHS) with equality at $ \theta = \frac{\pi}{3} $, we know

$ a^2+b^2 \ge ab(\cos{\theta}+\sqrt{3}\sin{\theta}) $

$ 2(a^2+b^2) \ge 2ab(\cos{\theta}+\sqrt{3}\sin{\theta}) $

$ a^2+b^2+(a^2+b^2-2ab\cos{\theta}) \ge 2\sqrt{3} \cdot ab\sin{\theta} $.

Recalling the Law of Cosines, we know $ c^2 = a^2+b^2-2ab\cos{\theta} $. Also, $ T = \frac{1}{2}ab\sin{\theta} $, so substituting we obtain

$ a^2+b^2+c^2 \ge 4T\sqrt{3} $

as desired. Equality holds when $ a = b $ and $ \theta = \frac{\pi}{3} $, which means the triangle must be equilateral. QED.

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

Comment: There are lots of ways to prove this, but this is one of the more elementary ones, requiring only basic knowledge of inequalities and trigonometry. Which is always good because I don't know any geometry. We see that this inequality is in general pretty weak, with equality only when the triangle is equilateral - there is a stronger version that states

$ a^2+b^2+c^2 \ge 4T\sqrt{3}+(a-b)^2+(b-c)^2+(c-a)^2 $.

See if you can prove that...

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

Practice Problem: Let $ a, b, c $ be the sides of a triangle, and $ T $ its area. Prove:

$ a^2+b^2+c^2 \ge 4T\sqrt{3}+(a-b)^2+(b-c)^2+(c-a)^2 $.

Friday, February 9, 2007

Don't You Wish You Remembered Those Trig Identities. Topic: Trigonometry. Level: AMC/AIME.

Problem: (1962 IMO - #4) Solve the equation $ \cos^2{(x)}+\cos^2{(2x)}+\cos^2{(3x)} = 1 $.

Solution: Subtract the $ \cos^2{(3x)} $ from both sides, and replace the LHS by $ \sin^2{(3x)} $, so we now have

$ \cos^2{(x)}+\cos^2{(2x)} = \sin^2{(3x)} $.

Recalling the sine angle addition identity, we write

$ \sin{(3x)} = \sin{(2x+x)} = \sin{(2x)}\cos{(x)}+\sin{(x)}\cos{(2x)} $.

So our equation is

$ \cos^2{(x)}+\cos^2{(2x)} = [\sin{(2x)}\cos{(x)}+\sin{(x)}\cos{(2x)}]^2 $.

Expanding, collecting terms, and simplifying using $ 1-\sin^2{(2x)} = \cos^2{(2x)} $ and $ 1-\sin^2{(x)} = \cos^2{(x)} $, we get

$ 2\cos^2{(x)} \cos^2{(2x)} = 2\sin{(x)}\cos{(x)}\sin{(2x)}\cos{(2x)} $.

Divide by $ 2 $, rearrange, and factor:

$ \cos{(x)}\cos{(2x)}[\cos{(x)}\cos{(2x)}-\sin{(x)}\sin{(2x)}] = 0 $.

Substitute using the double-angle identities $ \cos{(2x)} = 1-2\sin^2{(x)} $ and $ \sin{(2x)} = 2\sin{(x)}\cos{(x)} $ to finally find

$ \cos^2{(x)} \cos{(2x)} [1-4\sin^2{(x)}] = 0 $.

Solving yields

$ x = \frac{\pi}{2}+k\pi \mbox{ ; } \frac{\pi}{4}+\frac{k \pi}{2} \mbox{ ; } \frac{\pi}{6}+k\pi \mbox{ ; } \frac{5 \pi}{6}+k \pi $

for all integers $ k $. QED.

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

Comment: Pretty standard and slightly ugly manipulation of trig identities, but overall not too bad. Considering you get like an hour or more to do this, I don't feel too bad about it. Other solutions taking into account symmetry or using DeMoivre's and stuff are also out there, but this seemed much more straightforward and easier to develop.

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

Practice Problem: (2007 AMC 12A - #24) For each integer $ n > 1 $, let $ F(n) $ be the number of solutions of the equation $ \sin{(x)} = \sin{(nx)} $ on the interval $ [0, \pi] $. What is $ \displaystyle \sum_{n=2}^{2007} F(n) $?

Wednesday, February 7, 2007

Spacy. Topic: S&S/Sets. Level: AMC.

Problem: (2007 AMC 12A - #25) Call a set of integers spacy if it contains no more than one out of any three consecutive integers. How many subsets of $ \{1, 2, 3, \ldots, 12\} $, including the empty set, are spacy?

Solution: We will solve this problem with a recursion on $ S_n $, which we will define as the number of spacy subsets of $ \{1, 2, 3, \ldots, n\} $. We can easily calculate

$ S_0 = 1 $, $ S_1 = 2 $, $ S_2 = 3 $, and $ S_3 = 4 $.

Now we will think about how to evaluate $ S_n $ in terms of previous terms. Obviously, we can keep all the subsets in $ S_{n-1} $. These will account for any space subsets that don't contain the element $ n $. Now we just need to count the ones that do contain the element $ n $.

If a spacy subset contains $ n $, it cannot have $ n-1 $ or $ n-2 $. So take all the spacy subsets of $ \{1, 2, \ldots, n-3\} $ and add the element $ n $ to them to get all the spacy subsets that contain $ n $. Since these are both of the cases, we obtain

$ S_n = S_{n-1}+S_{n-3} $.

Some calculations yield $ S_{12} = 129 $. QED.

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

Comment: In all honesty, a pretty standard recursion problem, which is probably better off on an easy olympiad-style contest because it's too easy to guess on the AMC. After just calculating a few terms, it wasn't hard to see the recursion and assume its validity. A more interesting problem would be to find the closed form for that recursion (eww?). Maybe generating functions will save the day.

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

Practice Problem: Can you find a closed form for $ S_n $?

Tuesday, February 6, 2007

Sunday, February 4, 2007

Mean. Topic: Algebra/Probability & Combinatorics/Calculus. Level: Olympiad.

Problem: (1983 Canada - #5) Show that the geometric mean of a set $ S $ of positive numbers equals the geometric mean of the geometric means of all non-empty subsets of $ S $. [Reworded]

Solution: Let $ S = \{a_1, a_2, \ldots, a_n\} $, so the geometric mean is $ (a_1a_2 \cdots a_n)^{\frac{1}{n}} $. We will show that the geometric mean of the geometric means of all non-empty subsets of $ S $ is equivalent to this. It suffices to show it is true for an arbitrary $ a_i $. Consider dividing the subsets of $ S $ that contain $ a_i $ into groups based on the number of elements it contains. We will count how many of them there are:

$ 1 $-element subsets containing $ a_i $ - clearly just the set $ \{a_i\} $. There is only $ 1 $;

$ 2 $-element subsets containing $ a_i $ - the set $ \{a_i, a_j\} $ for any $ j \neq i $. There are $ (n-1)C1 $ of these;

$ 3 $-element subsets containing $ a_i $ - there are $ (n-1)C2 $ of these.

It's pretty clear that if we want a $ k $-element subset containing $ a_i $ we are free to choose the other $ k-1 $ elements from the remaining $ n-1 $ elements of $ S $. If we take the geometric mean of these subsets, however, we find that

$ 1 $-element subsets give a full power of $ a_i $;

$ 2 $-element subsets give a $ \frac{1}{2} $ power of $ a_i $;

$ 3 $-element subsets give a $ \frac{1}{3} $ power of $ a_i $;

and so on. So when we multiply these all together, we get an exponent of

$ \displaystyle 1+(n-1)C1 \cdot \frac{1}{2}+(n-1)C2 \cdot \frac{1}{3}+ \cdots +(n-1)C(n-1) \cdot \frac{1}{n} = \sum_{k=1}^n \frac{1}{k} \cdot (n-1)C(k-1) $.

It remains to evaluate this sum, but we can do that through generating functions. Since $ \displaystyle (1+x)^{n-1} = \sum_{k=1}^n (n-1)C(k-1) \cdot x^{k-1} $, we integrate both sides to get

$ \displaystyle \frac{(1+x)^n}{n} = C+\sum_{k=1}^n \frac{1}{k}(n-1)C(k-1) \cdot x^k $.

Using $ x = 0 $, we obtain $ C = \frac{1}{n} $, so $ \displaystyle \frac{(1+x)^n-1}{n} = \sum_{k=1}^n \frac{1}{k}(n-1)C(k-1) \cdot x^k $.

Finally, by the substitution $ x = 1 $, we get the desired summation:

$ \displaystyle \sum_{k=1}^n \frac{1}{n} \cdot (n-1)C(k-1) = \frac{2^n-1}{n} $.

So prior to the last geometric mean, we have $ (a_i)^{\frac{2^n-1}{n}} $, but we know that there are $ 2^n-1 $ non-empty subsets of $ S $, which means the last geometric mean is a power of $ \frac{1}{2^n-1} $, and we have

$ \left(a_i^{\frac{2^n-1}{n}}\right)^{\frac{1}{2^n-1}} = (a_i)^{\frac{1}{n}} $,

the same power as the original geometric mean we computed. QED.

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

Comment: A very nice problem because it branched together several aspects of mathematics all into a single problem, which is always cool. There is probably a non-calculus method of evaluating that sum, but basically any time you see a sum like that you can use generating functions and then apply derivatives/integrals to make it what you want. Apparantly a symmetry argument can also be made, but that's probably just the lazy way to do this problem...

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

Practice Problem: (1983 Canada - #4) Given an arbitrary prime $ p $, show that we can find infinitely many positive integers $ n $ such that $ 2^n-n $ is a multiple of $ p $.

Saturday, February 3, 2007

2007 Northwest Math Championships.

Good job Bellevue today at the 2007 NWMC! We did amazing!

3rd Place 9/10 Team

1st Place 11/12 Team