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

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 »
Something To Think About. Topic: Probability. Level: AMC/AIME.	April 18th, 2007
Problem: A coin is repeatedly flipped. What is the expected number of flips to get two heads in a row? heads in a row? ——————– I will be out of town for the next four days, so have fun with the problem! Posted in AIME, AMC, Probability & Combinatorics \|\| 4 Comments »
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