Mathematical Food for Thought


			Mathematical Food for Thought

google
yahoo
bing

About
Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.

Meta
- Register
- Log in
- Valid XHTML
- XFN
- WordPress

Credits
- Design by Stacee Leung
- Coded by Daynah Nguyen
- Powered by Wordpress

Recurrences Are Cool. Topic: Probability/S&S. Level: AIME.	February 27th, 2007
Problem: Let be the probability of choosing a positive integer from the interval $[2^{k-1}, 2^k-1]$ such that the binary representation of does not contain three consecutive ’s. Evaluate the infinite summation $p_1+p_2+\cdots$ . Solution: First, let be the number of positive integers in the interval $[2^{k-1}, 2^k-1]$ that do not contain three consecutive ’s in their binary representations – note that it is equivalent to the number of binary strings of length starting with a that satisfy that property. By testing, we have , , , , , . 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 based on the last occurence of . 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 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 and , 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 that begin with . 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 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}}$ . 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 is a positive integer and is the Fibonacci sequence (i.e. and $F_{k+1} = F_k+F_{k-1}$ for all positive integers ). Posted in AIME, Probability & Combinatorics, Sequences & Series \|\| 1 Comment »
2007 Mock AIME 6.	February 24th, 2007
The 2007 Mock AIME 6 is underway! The test can be found here and more information can be found at the AoPS Forum. Posted in AIME, Announcements \|\| 3 Comments »
Pythagorean x3. Topic: Geometry/NT. Level: AMC.	February 22nd, 2007
Problem: (2007 AMC12B – #23) How many non-congruent right triangles with positive integer leg lengths have areas that are numerically equal to times their perimeters? Solution: Well, basically, you should know the Pythagorean triple generating formula, i.e. , , . 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 . Obviously then so look at these cases: : We can take to get the triples . : We can take to get the triples both of which are already counted. : We can take to get the triples . : We can take to get the triple , which is already counted. So we have 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 are there such that $\text{gcd}(a, b) = 1$ and $\frac{a}{b}+\frac{14b}{9a}$ is an integer? Posted in AMC, Geometry, Number Theory \|\| 2 Comments »
Mu Alpha Practice Tests.	February 18th, 2007
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. Posted in Announcements \|\| 8 Comments »
Currently…	February 18th, 2007
Writing a Mock AIME. Stay tuned! Posted in AIME, Announcements \|\| No Comments »

free web counters