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

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 »
A Square of Divisors. Topic: Number Theory. Level: AIME/Olympiad.	May 8th, 2007
Problem: (1999 Canada – #3) Determine all positive integers with the property that . Here denotes the number of positive divisors of . Solution: So, testing some small numbers yields as a solution. We claim that this is the only such solution. Clearly, since is a square, we can use a variant of the usual prime decomposition and say that $n = p_1^{2e_1} p_2^{2e_2} \cdots p_k^{2e_k}$ . Furthermore, again since is a square, we know $d(n) = (2e_1+1)(2e_2+1) \cdots (2e_k+1)$ is odd, so must be odd as well, i.e. is not one of the . Then we use the equation given to us to get $p_1^{2e_1} p_2^{2e_2} \cdots p_k^{2e_k} = (2e_1+1)^2(2e_2+1)^2 \cdots (2e_k+1)^2$ $p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} = (2e_1+1)(2e_2+1) \cdots (2e_k+1)$ . Note, however, that by Bernoulli’s Inequality (overkill, I know) we have for $i = 1, 2, \ldots, k$ $(1+(p_i-1))^{e_i} \ge 1+(p_i-1)e_i \ge 2e_i+1$ with equality iff and . So $p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \ge (2e_1+1)(2e_2+1) \cdots (2e_k+1)$ . Since we want equality, we must have and for all . But since the primes are supposed to be distinct we can have exactly one prime so that is the only solution. QED. ——————– Comment: Another one of those problems that you kind of look at the result and you’re like huh, that’s interesting. But anyway, just throwing in some weak inequalities led to a pretty straightforward solution. As long as you know how to find the number of divisors of a positive integer it isn’t too much of a stretch to figure the rest out, though it make take some time to get in the right direction since the problem is quite open-ended. ——————– Practice Problem: (1999 Canada – #4) Suppose $a_1,a_2,\cdots,a_8$ are eight distinct integers from $\{1,2,\ldots,16,17\}$ . Show that there is an integer such that the equation has at least three different solutions. Also, find a specific set of distinct integers from $\{1,2,\ldots,16,17\}$ such that the equation does not have three distinct solutions for any . Posted in AIME, Number Theory, Olympiad \|\| 6 Comments »
Ready For AP Calculus? Topic: Calculus/S&S. Level: AIME/Olympiad.	May 5th, 2007
Problem: Evaluate $\displaystyle \sum_{n=1}^{\infty} \frac{1}{n^2 \cdot 2^n}$ . Solution: Let $\displaystyle f(x) = \sum_{n=1}^{\infty} \frac{x^n}{n^2}$ . Then $\displaystyle f^{\prime}(x) = \sum_{n=1}^{\infty} \frac{x^{n-1}}{n} = -\frac{\ln{(1-x)}}{x}$ , a well-known Taylor series. So we want to integrate this: $\displaystyle \int \frac{\ln{(1-x)}}{x}dx = \ln{x} \ln{(1-x)}-\int \frac{\ln{x}}{x-1}dx$ by parts using $u = \ln{(1-x)}$ and . Substituting in the last integral, we have $\displaystyle \int \frac{\ln{(1-x)}}{x}dx = \ln{x} \ln{(1-x)}-\int \frac{\ln{(1-t)}}{t}dt$ . So $-f(x) = \ln{x} \ln{(1-x)}+f(t)+C = \ln{x} \ln{(1-x)}+f(1-x)+C$ . Thus $f(x)+f(1-x) = C-\ln{x} \ln{(1-x)}$ for some constant . Using our knowledge that , $\displaystyle f(1) = \frac{\pi^2}{6}$ , and $\displaystyle \lim_{x \rightarrow 1} \ln{x} \ln{(1-x)}= 0$ by L’Hopital twice, we see that $f(0)+f(1) = C \Rightarrow C = \frac{\pi^2}{6}$ Then setting $x = \frac{1}{2}$ we obtain $\displaystyle 2f\left(\frac{1}{2}\right) = \frac{\pi^2}{6}-\ln{\frac{1}{2}} \ln{\frac{1}{2}}$ and $\displaystyle \sum_{n=1}^{\infty} \frac{1}{n^2 \cdot 2^n} = f\left(\frac{1}{2}\right) = \frac{\pi^2}{12}-\frac{\ln^2{(2)}}{2}$ . QED. ——————– Comment: This was a pretty tough problem that required you to compound a lot of calculus knowledge all into a single problem – series, integration by parts, limits. Recognizing all the steps was the first part; following through with the right computations was another. Still, there weren’t really any super clever tricks, mostly just standard substitutions and approaches applied in a somewhat non-standard way. Makes for a very nice problem. ——————– Practice Problem #1: Show that $\displaystyle \lim_{x \rightarrow 1} \ln{x} \ln{(1-x)} = 0$ . Practice Problem #2: Evaluate $\displaystyle \sum_{n=1}^{\infty} \frac{x^n}{n}$ . Can you also find $\displaystyle \sum_{n=1}^{\infty} \frac{x^n}{n^3}$ ? Posted in AIME, Calculus, Olympiad, Sequences & Series \|\| No 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 »

free web counters