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

What’s Your Function? Topic: Algebra. Level: AMC/AIME.	July 7th, 2007
Problem: Given two positive reals $\alpha$ and $\beta$ , show that there is a continuous function that satisfies $f(x) = f(x+\alpha)+f(x+\beta)$ . Solution: There are several special cases that are interesting to look at before we make a guess as to what type of function will be. First we consider the case $\alpha = \beta = 1$ . This immediately gives . It should not be too difficult to guess that $f(x) = 2^{-x}$ is a solution to this, as well as any constant multiple of it. Now try $\alpha = -1$ and $\beta = -2$ , resulting in . Looks a lot like Fibonacci, right? In fact, one possible function is just $f(x) = \phi^x$ . That’s pretty convenient. Notice how both of these illuminating examples are exponential functions, which leads us to guess that our function will be exponential as well. So, following this track, we set so we simply need to solve $a^x = a^{x+\alpha}+a^{x+\beta}$ $a^x = a^x\left(a^{\alpha}+a^{\beta}\right)$ . Unfortunately, the equation $a^{\alpha}+a^{\beta} = 1$ does not always have a solution (take $\alpha = 1$ and $\beta = -1$ for example). But that’s ok and I’ll worry about it some other time. In any case we have found a function for whenever the equation $a^{\alpha}+a^{\beta} = 1$ has a solution in the reals. Posted in Algebra \|\| 5 Comments »
Bigger Means Better. Topic: Algebra/Inequalities/Sets. Level: Olympiad.	May 12th, 2007
Definition: A set is said to be convex if, for any $X, Y \in S$ and $\lambda \in [0,1]$ , we have $\lambda X+(1-\lambda)Y \in S$ . ——————– Definition: Let $f: D \rightarrow \mathbb{R}$ be a real-valued function defined on a convex set . We say that is convex if, for all $X, Y \in D$ and $\lambda \in [0, 1]$ , we have $\lambda f(X) + (1-\lambda) f(Y) \ge f(\lambda X+(1-\lambda)Y)$ . ——————– Theorem: (Jensen’s Inequality) Let be a real-valued, convex function defined on a convex set . Given $x_1, x_2, \ldots, x_n \in D$ and nonnegative reals $w_1, w_2, \ldots, w_n$ such that $w_1+w_2+\cdots+w_n = 1$ , we have $w_1f(x_1)+w_2f(x_2)+\cdots+w_nf(x_n) \ge f(w_1x_1+w_2x_2+\cdots+w_nx_n)$ or, more concisely, $\displaystyle \sum_{i=1}^n w_if(x_i) \ge f\left(\sum_{i=1}^n w_ix_i\right)$ . Proof: We proceed by induction on . Base Case – , we have $f(x_1) \ge f(x_1)$ which is trivially true. , we have $\lambda_1 f(x_1)+\lambda_2 f(x_2) \ge f(\lambda_1 x_1+\lambda_2 x_2)$ with $\lambda_1+\lambda_2 = 1$ which is true by the definition of convexity. Induction Step – Suppose $\displaystyle \sum_{i=1}^k w_if(x_i) \ge f\left(\sum_{i=1}^k w_ix_i\right)$ . We wish to show $\displaystyle \sum_{i=1}^{k+1} u_if(x_i) \ge f\left(\sum_{i=1}^{k+1} u_ix_i\right)$ for nonnegative reals $u_1, u_2, \ldots, u_{k+1}$ that sum to . Well, $\displaystyle f\left(\sum_{i=1}^{k+1} u_ix_i\right) \le u_{k+1}f(x_{k+1})+(1-u_{k+1})f\left(\frac{1}{1-u_{k+1}} \sum_{i=1}^k u_ix_i\right)$ by the definition of convexity. But since $\displaystyle \frac{1}{1-u_{k+1}} \sum_{i=1}^k u_i = \sum_{i=1}^k \frac{u_i}{1-u_{k+1}} = 1$ , by our inductive hypothesis (the term case) we must have $\displaystyle f\left(\frac{1}{1-u_{k+1}} \sum_{i=1}^k u_ix_i\right) \le \sum_{i=1}^k \frac{u_i}{1-u_{k+1}} f(x_i)$ . Combining this into the above inequality, we obtain $\displaystyle f\left(\sum_{i=1}^{k+1} u_ix_i\right) \le u_{k+1}f(x_{k+1})+(1-u_{k+1})\sum_{i=1}^k \frac{u_i}{1-u_{k+1}} f(x_i) = \sum_{i=1}^{k+1} u_if(x_i)$ as desired, completing the induction. QED. ——————– Definition: The convex hull of a set is defined to be the smallest convex set containing . It is the set of all points that can be written as $\displaystyle \sum_{i=1}^n a_ix_i$ , where is a natural number, $a_1, a_2, \ldots, a_n$ are nonnegative reals that sum to , and $x_1, x_2, \ldots, x_n \in S$ . ——————– Definition: A vertex of a set is a point $v \in D$ such that for all $x \in D$ not equal to and $\lambda > 1$ we have $\lambda v+(1-\lambda)x \not\in D$ . ——————– Theorem: Let $V_D = \{v_1, v_2, \ldots, v_k\}$ be the set of vertices of a compact convex set . The convex hull of is . Example: The set of vertices of a convex polygon is, in fact, its vertices as traditionally defined in geometry. Any point inside the polygon can be written as a convex combination of its vertices. ——————– Theorem: If is a real-valued, convex function defined on a compact convex set , then $\displaystyle \max_{x \in D} f(x) = \max_{x \in V_D} f(x)$ , where is the set of vertices of . Proof: We will show that $\displaystyle f(x) \le \max_{x \in V_D} f(x)$ for all $x \in D$ . Let $\displaystyle x = \sum_{i=1}^k \lambda_i v_i$ where $\lambda_1, \lambda_2, \ldots, \lambda_k$ are nonnegative reals that sum to and $V_D = \{v_1, v_2, \ldots, v_k\}$ . This is possible by the preceding theorem. Then by Jensen’s Inequality we get $\displaystyle \sum_{i=1}^k \lambda_i f(v_i) \ge f\left(\sum_{i=1}^k \lambda_i v_i\right) = f(x)$ . And since $\displaystyle \max_{x \in V_D} f(x) \ge \sum_{i=1}^k \lambda_i f(v_i)$ , we have $\displaystyle \max_{x \in V_D} f(x) \ge f(x)$ for all $x \in D$ . Furthermore, since is a subset of , we know that this maximum is attained, thus $\displaystyle \max_{x \in D} f(x) = \max_{x \in V_D} f(x)$ as desired. QED. ——————– Comment: This is a very useful result, as it allows us to limit our search for the maximum of a function to its set of vertices, which is usually a considerably smaller set, though it may still be infinite (think sphere). In any case, this works well for constrained optimization problems in which the domain is limited to a polygon, the easiest application of this theorem. ——————– Practice Problem: Let and be real numbers satisfying $\|2x-y\| \le 3$ and $\|y-3x\| \le 1$ . Find the maximum value of . Posted in Algebra, Inequalities, Olympiad, Sets \|\| 3 Comments »
Just A “Natural” Thing. Topic: Algebra. Level: AIME/Olympiad.	April 28th, 2007
Problem: Factor $7^{6(2k-1)}-7^{5(2k-1)}+7^{4(2k-1)}-7^{3(2k-1)}+7^{2(2k-1)}-7^{2k-1}+1$ . Solution: Consider the polynomial . We have , so we want to factor the second term when $x = 7^{2k-1}$ . Call it so that $P(x) = \frac{x^7+1}{x+1}$ . Consider the relation . Since is a root of the LHS, we factor it out of the RHS as well to get . Dividing through by and rearranging, we obtain the nice expression . Letting $x = 7^{2k-1}$ , this becomes $P(7^{2k-1}) = (7^{3(2k-1)}+3 \cdot 7^{2(2k-1)}+3 \cdot 7^{2k-1}+1)^2-7^{2k}(7^{2(2k-1)}+7^{2k-1}+1)^2$ which is conveniently enough a difference of two squares. And we’ll leave it as this because the factors are not particularly nice or anything. QED. ——————– Comment: This “natural” factorization was basically the one crucial step to solving the USAMO #5 this year and most people did not see it, unsurprisingly. Taking the difference was the trickiest/cleverest part, and there were definitely a limited number of approaches to this factorization. Oh well, at least it seems sort of cool after you know about it. ——————– Practice Problem: (2007 USAMO – #5) Prove that for every nonnegative integer n, the number $7^{7^{n}}+1$ is the product of at least (not necessarily distinct) primes. Posted in AIME, Algebra, Olympiad \|\| 1 Comment »
Sense Of Poise And Rationality. Topic: Algebra. Level: AIME/Olympiad.	April 15th, 2007
Problem: (1993 Canada National Olympiad – #2) Show that is rational if and only if three distinct terms that form a geometric progression can be chosen from the sequence $x, x+1, x+2, x+3, \ldots$ . Solution: We will prove the “if” statement first, i.e. is rational implies we can find the geometric progression. Let $x = \frac{p}{q}$ . The terms of the sequence are then $\frac{p}{q}$ , $\frac{p+q}{q}$ , $\frac{p+2q}{q}$ , $\frac{p+3q}{q}, \ldots$ . We simply choose the terms $\frac{p}{q}$ , $\frac{p+pq}{q}$ , $\frac{p+(2p+pq)q}{q}$ which are the same as $\frac{p}{q}$ , $\frac{p(1+q)}{q}$ , $\frac{p(1+q)^2}{q}$ , clearly a geometric progression. Now for the other direction, assume are a geometric progression with positive integers. Then $\frac{x+a}{x+b} = \frac{x+b}{x+c} \Rightarrow x^2+(a+c)x+ac = x^2+2bx+b^2 \Rightarrow (a+c)x+ac = 2bx+b^2$ . Solving for yields $x = \frac{b^2-ac}{a+c-2b}$ which is clearly rational, as desired. QED. ——————– Comment: An interesting “definition” of a rational number, pretty neat in fact. Though it may not seem so at first, the “if” direction was actually considerably harder than the “only if” direction because the approach was not as straightforward. The “only if” proof required simple algebra, while the “if” proof needed a little creative picking and choosing. Another approach for the “if” direction is to set $x = \frac{p}{q}$ and try to find corresponding but that makes it a little more difficult than necessary. ——————– Practice Problem: (1993 Canada National Olympiad – #3) In triangle , medians to the sides $\overline{AB}$ and $\overline{AC}$ are perpendicular. Show that $\cot{B}+\cot{C} \ge \frac{2}{3}$ . Posted in AIME, Algebra, Olympiad \|\| 2 Comments »
Da Roots. Topic: Algebra/Complex Numbers Level: AIME.	March 11th, 2007
Problem: (2007 Mock AIME 6 – #7) Let $P_n(x) = 1+x+x^2+\cdots+x^n$ and $Q_n(x) = P_1 \cdot P_2 \cdots P_n$ for all integers $n \ge 1$ . How many more distinct complex roots does $Q_{1004}$ have than $Q_{1003}$ ? Solution: Well, is familiar. Rewrite as $P_n(x) = \frac{x^{n+1}-1}{x-1}$ , i.e. the th roots of unity except . Since $Q_{1004}$ just contains a $P_{1004}$ term that $Q_{1003}$ doesn’t have, we only need to think about that term in relation to the previous ones. So we want to find out how many of the th roots of unity are not -th roots of unity for any . Well, recalling that any -th root of unity can be written as $e^{2 \pi i \frac{p}{k}} = \cos{\left(2 \pi \frac{p}{k}\right)}+i \sin{\left(2 \pi \frac{p}{k}\right)}$ for $p = 0, 1, \ldots, k-1$ , it remains to find the number of such that $\frac{p}{1005}$ does not reduce. But this, of course, is simply $\phi(1005) = 1005\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)\left(1-\frac{1}{67}\right) = 2 \cdot 4 \cdot 66 = 528$ . QED. ——————– Comment: Definitely one of my favorite problems on the test because it has a really nice and clean solution once you see it. And it wasn’t too difficult to see either; combining a little knowledge of roots of unity with a little knowledge of the $\phi$ function made it a good problem. Furthermore, it offers the nice generalization that has $\phi(n+1)$ more distinct roots than $Q_{n-1}$ . ——————– Practice Problem: (2007 Mock AIME 6 – #8) A sequence of positive reals is defined by , , and $a_n \cdot a_{n+2} = a_{n+1}$ for all integers $n \ge 0$ . Given that $a_{2007}+a_{2008} = 3$ and $a_{2007} \cdot a_{2008} = \frac{1}{3}$ , find . Posted in AIME, Algebra, Complex Numbers \|\| 1 Comment »

free web counters