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

Even, Odd, Even, Odd… Topic: Algebra/S&S. Level: AMC/AIME.	January 30th, 2007
Problem: Show that the sequence $\lfloor \sqrt{2} \rfloor, \lfloor 2\sqrt{2} \rfloor, \lfloor 3\sqrt{2} \rfloor, \ldots$ contains an infinte number of both even and odd integers. Furthermore, show that there can be at most two consecutive integers of the same parity. Solution: Suppose their exists a finite number of either even or odd integers. Then we definitely have three integers of the same parity in a row. But since $1 < \sqrt{2} < 2$ , they must each differ by . Hence $\lfloor k\sqrt{2}\rfloor+2 = \lfloor (k+1)\sqrt{2} \rfloor$ $\lfloor (k+1)\sqrt{2}\rfloor+2 = \lfloor (k+2)\sqrt{2} \rfloor$ . Adding the equalities together, we get $\lfloor k\sqrt{2} \rfloor+4 = \lfloor (k+2)\sqrt{2}\rfloor$ . By the standard floor function inequalities, however, we know that $x-1 < \lfloor x \rfloor < x$ when is not an integer. Hence $\lfloor k\sqrt{2}\rfloor+4 > k\sqrt{2}+3 > k\sqrt{2}+2\sqrt{2} > \lfloor (k+2)\sqrt{2} \rfloor$ , a contradiction. Hence we have proved both of the desired results. QED. ——————– Comment: An interesting result which can be simply generalized to any irrational $1 < \alpha < 2$ and probably any positive irrational $\alpha$ at all (see if you can prove this). It wasn't hard to reason out that because $\sqrt{2} < 1.5$ we really cannot have three integers of the same parity in a row in that sequence. Adding a touch of rigor to the proof turned out to be quite easy as well. -------------------- Practice Problem: Prove or disprove that, given a positive irrational $\alpha > 0$ , the sequence $\lfloor \alpha \rfloor, \lfloor 2\alpha \rfloor, \lfloor 3\alpha \rfloor, \ldots$ contains an infinite number of both even and odd integers. Posted in AIME, AMC, Algebra, Sequences & Series \|\| 3 Comments »
Distasteful Distance. Topic: Sequences & Series. Level: AIME.	January 28th, 2007
Problem: (1997 Putnam – B1) Let $\{x\}$ denote the distance between the real number and the nearest integer. For each positive integer , evaluate $\displaystyle F_n = \sum_{m=1}^{6n-1} \min(\{\frac{m}{6n}\}, \{\frac{m}{3n}\})$ . Solution: Well since $\frac{m}{6n}$ lies in the interval , we can just characterize $\min(\{x\}, \{2x\})$ for all $x \in (0, 1)$ . We split it up into three intervals: If $0 < x \le \frac{1}{3}$ , we have $\{x\} \le \{2x\}$ because $2x \ge x$ and $1-2x \ge x$ . If $\frac{1}{3} < x \le \frac{2}{3}$ , we have $\{2x\} \le \{x\}$ because $x \ge \|1-2x\|$ and $1-x \ge \|1-2x\|$ . If $\frac{2}{3} < x < 1$ , we again have $\{x\} \le \{2x\}$ because $2x-1 \ge 1-x$ and $2-2x \ge 1-x$ . This translates to $1 \le m \le 2n$ , $2n+1 \le m \le 4n$ , and $4n+1 \le m \le 6n-1$ , so we sum the intervals separately (note that we split the middle interval again into two parts to avoid absolute values): $\displaystyle \sum_{m=1}^{2n} \frac{m}{6n} = \frac{1}{6n} \cdot \frac{2n(2n+1)}{2} = \frac{2n+1}{6}$ $\displaystyle \sum_{m=2n+1}^{3n} \left(1-\frac{m}{3n}\right) = \sum_{m=0}^{n-1} \frac{m}{3n} = \frac{1}{3n} \cdot \frac{(n-1)n}{2} = \frac{n-1}{6}$ $\displaystyle \sum_{m=3n+1}^{4n} \left(\frac{m}{3n}-1\right) = \sum_{m=1}^n \frac{m}{3n} = \frac{1}{3n} \cdot \frac{n(n+1)}{2} = \frac{n+1}{6}$ $\displaystyle \sum_{m=4n+1}^{6n-1} \left(1-\frac{m}{6n}\right) = \sum_{m=1}^{2n-1} \frac{m}{6n} = \frac{1}{6n} \cdot \frac{(2n-1)2n}{2} = \frac{2n-1}{6}$ . Summing them together we have $F_n = \frac{2n+1}{6}+\frac{n-1}{6}+\frac{n+1}{6}+\frac{2n-1}{6} = n$ . QED. ——————– Comment: A pretty neat, although contrived, summation to just get simply to . The key was splitting the summation up; without doing that, it’s really not possible to evaluate the sum in easy ways (like summing the first positive integers multiple times). Figuring out how the function $\{x\}$ worked helped a lot in determining the behavior of $\min(\{x}, \{2x\})$ . ——————– Practice Problem: Evaluate the sum $\displaystyle \sum_{i=1}^{\infty} \lfloor \frac{n+2^{i-1}}{2^i} \rfloor = \lfloor \frac{n+1}{2} \rfloor+\lfloor \frac{n+2}{4} \rfloor+\lfloor \frac{n+4}{8} \rfloor+\cdots$ . Posted in AIME, Sequences & Series \|\| 4 Comments »
Vector Magic. Topic: Geometry. Level: AIME.	January 27th, 2007
Problem: (1997 Putnam – A1) A rectangle, , has sides and . A triangle has as the intersection of its altitudes, the center of its circumscribed circle, the midpoint of , and the foot of the altitude from . What is the length of ? Solution: Since everyone loves algebra and hates geometry, let’s use the standard algebrization of a triangle problem: vectors. Set to be the origin, to , from which we automatically obtain and . Let be the vectors from to points , respectively. We know and from here, so we’ll use these results. Also, by the definition of a midpoint. Using these three equations, we can solve for . and implies that . Also, the -coordinates of and are the same value with opposite signs. So if , where and , we must have $11^2+10^2 = x^2+5^2 \Rightarrow x^2 = 196 \Rightarrow x = 14$ . So . QED. ——————– Comment: There are various other synthetic ways to approach this problem, but using vectors seems to make life really easy as we know lots of relationships about the circumcenter, orthocenter, and midpoints. See if you can convince me that there is a simpler way to do it without vectors. ——————– Practice Problem: “Prove” that the vector representation of the orthocenter has to be symmetric in (i.e. explain why you know is wrong). Posted in AIME, Geometry \|\| No Comments »
Log Rolling. Topic: Inequalities. Level: AIME.	January 24th, 2007
Problem: Given reals $a, b, c \ge 2$ , show that $\log_{a+b}(c)+\log_{b+c}(a)+\log_{c+a}(b) \ge \frac{3}{2}$ . Solution: Recall the change-of-base identity for logs. We can rewrite the LHS as $\frac{\log{c}}{\log{(a+b)}}+\frac{\log{a}}{\log{(b+c)}}+\frac{\log{b}}{\log{(c+a)}}$ . Note, however that $(a-1)(b-1) \ge 1 \Rightarrow ab \ge a+b \Rightarrow \log{a}+\log{b} = \log{(ab)} \ge \log{(a+b)}$ , so it remains to show that $\frac{\log{c}}{\log{a}+\log{b}}+\frac{\log{a}}{\log{b}+\log{c}}+\frac{\log{b}}{\log{c}+\log{a}} \ge \frac{3}{2}$ , which is true by Nesbitt’s Inequality. QED. ——————– Comment: A good exercise in using log identities and properties to achieve a relatively simple result. Once we made the change-of-base substitution, seeing the $\frac{3}{2}$ should clue you in to Nesbitt’s. That led to the inequality $\log{a}+\log{b} \ge \log{(a+b)}$ , which was easily proven given the conditions of the problem. ——————– Practice Problem: Given reals $a, b, c \ge 2$ , find the best constant such that $\log_{a+b+c}(a)+\log_{a+b+c}(b)+\log_{a+b+c}(c) \ge k$ . Posted in AIME, Inequalities \|\| 3 Comments »
Who Loves Algebra? Topic: Algebra. Level: AIME/Olympiad.	January 21st, 2007
Problem: (1999 Putnam – A3) Consider the power series expansion $\displaystyle \frac{1}{1-2x-x^2} = \sum_{n=0}^{\infty} a_nx^n$ . Prove that, for each integer $n \ge 0$ , there is an integer such that $a_n^2+a_{n+1}^2 = a_m$ . Solution: Playing around with the expansion for a bit (using geometric series or otherwise), we find that , , so . Realizing that the calculation gets uglier and uglier, we decide to go for the general case right now. Now we need to find a good expansion. Try partial fractions. $\displaystyle \frac{1}{1-2x-x^2} = \frac{1}{2\sqrt{2}}\left(\frac{1}{\sqrt{2}-1-x}+\frac{1}{\sqrt{2}+1+x}\right)$ . Now, to simplify our lives, we let $\alpha = \sqrt{2}+1$ . Note that $\frac{1}{\alpha} = \sqrt{2}-1$ , so this may turn out to be a key substitution. We get $\displaystyle \frac{1}{2\sqrt{2}}\left(\frac{1}{\sqrt{2}-1-x}+\frac{1}{\sqrt{2}+1+x}\right) = \frac{1}{2\sqrt{2}}\left(\frac{\alpha}{1-\alpha x}+\frac{1}{\alpha} \cdot \frac{1}{1+\frac{x}{\alpha}}\right)$ . Expanding both fractions using a geometric series, we obtain $\frac{1}{2\sqrt{2}}\displaystyle \sum_{n=0}^{\infty} x^n \cdot \left(\alpha^{n+1}+\frac{(-1)^n}{\alpha^{n+1}}\right)$ , a remarkably simple expression given what we had up there. It remains to show that $a_n^2+a_{n+1}^2$ also has the form of one of those. So, plugging the appropriate values, we see that $\displaystyle \frac{1}{8}\left[\left(\alpha^{n+1}+\frac{(-1)^n}{\alpha^{n+1}}\right)^2+\left(\alpha^{n+2}+\frac{(-1)^{n+1}}{\alpha^{n+2}}\right)^2\right] = \frac{1}{8} \left(\alpha^{2n+4}+\alpha^{2n+2}+\frac{1}{\alpha^{2n+2}}+\frac{1}{\alpha^{2n+4}}\right)$ because the middle terms in the squaring cancel out nicely (and the $\frac{1}{8}$ came from the squaring of the constant $\frac{1}{2\sqrt{2}}$ ). So, recalling that when , we had $a_n^2+a_{n+1}^2 = a_{2n+2}$ , we want to make that last expression look like $a_{2n+2}$ . A clever factorization yields $\displaystyle \frac{1}{8} \left[ \alpha^{2n+3}\left(\alpha+\frac{1}{\alpha}\right)+\frac{1}{\alpha^{2n+3}} \left(\alpha+\frac{1}{\alpha}\right) \right] = \frac{\alpha+\frac{1}{\alpha}}{8} \left( \alpha^{2n+3}+\frac{1}{\alpha^{2n+3}} \right)$ . Note, however, that $\alpha+\frac{1}{\alpha} = (\sqrt{2}+1)+(\sqrt{2}-1) = 2\sqrt{2}$ , so the result is $\frac{1}{2\sqrt{2}} \left( \alpha^{2n+3}+\frac{(-1)^{2n+2}}{\alpha^{2n+3}} \right) = a_{2n+2}$ by the expansion we found earlier. QED. ——————– Comment: That looked like a lot of work, and it was. The hardest parts were definitely (1) finding out that using the partial fraction decomposition was the best way to go, (2) making the substitution that allowed things to cancel nicely, and (3) keeping track of my work. This is a pretty cool result, which you can usually expect from Putnam problems that have large amounts of algebraic manipulation (you’d hope so, anyway). But in the end, we are left with a satisfactory feeling, so it’s all good. ——————– Practice Problem: (1999 Putnam – B2) Let be a polynomial of degree such that $P(x) = Q(x)P^{\prime\prime}(x)$ , where is a quadratic polynomial and $P^{\prime\prime}(x)$ is the second derivative of . Show that if has at least two distinct roots then it must have distinct roots. Posted in AIME, Algebra, Olympiad \|\| No Comments »

free web counters