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 »
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 »
A Bit Familiar. Topic: Algebra/NT. Level: Olympiad.	January 8th, 2007
Problem: (2002 Putnam – A5) Define a sequence by , together with the rules $a_{2n+1} = a_n$ and $a_{2n+2} = a_n+a_{n+1}$ for each integer $n \ge 0$ . Prove that every positive rational appears in the set $\left\{\frac{a_{n-1}}{a_n}: n \ge 1 \right} = \left{\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{3}{2}, \cdots \right\}$ . Solution: Consider the sequence $\displaystyle b_n = \frac{a_{n-1}}{a_n}$ . We know and we want to find a recursion for . We can see that $\displaystyle b_{2n+1} = \frac{a_{2n}}{a_{2n+1}} = \frac{a_{n-1}+a_n}{a_n} = 1+b_n$ (1) $\displaystyle b_{2n+2} = \frac{a_{2n+1}}{a_{2n+2}} = \frac{a_n}{a_n+a_{n+1}} = \frac{1}{1+\frac{1}{b_{n+1}}} = 1-\frac{1}{1+b_{n+1}}$ (2) . We will now prove the result by strong induction on the denominator of $\frac{p}{q}$ . We know that for , the term $\frac{1}{1}$ appears, so by applying (1) inductively we know $\frac{p}{1}$ appears for all . So suppose that all fractions of the form $\frac{p}{q}$ with appear in the set. We wish to show that all fractions $\frac{p}{q}$ with appear. We see that $\displaystyle \frac{1}{k-1} \rightarrow \frac{1}{k}$ by (2). In fact, since we know $\frac{m}{k-m}$ is in the set for already, we get $\displaystyle \frac{m}{k-m} \rightarrow \frac{m}{k}$ by (2). Hence we have found that $\frac{1}{k}, \frac{2}{k}, \cdots, \frac{k-1}{k}$ are all in the set. But then, by applying (1) inductively on each of the fractions, we know that $\frac{m}{k}+r = \frac{m+kr}{k}$ is in the set, for $m = 1, 2, \ldots, k-1$ and $r = 1, 2, \ldots$ , which easily gives us $\frac{s}{k}$ is in the set for any $s \not\equiv 0 \pmod{k}$ , but those are all integers, which are covered in the first base case. Hence we have shown that all positive rationals with denominator are in the set, completing the induction. QED. ——————– Comment: Not too hard for an A5 on the Putnam, especially if you’ve seen types of problems like this before. The crux step was probably getting the recursions for the sequence, which then allowed you to discover how the rationals are produced. As noted above, it seemed a bit familiar, and a very similar problem showed up on my blog before and a similar proof was given. This one was a little more complicated, but the main ideas are the same. ——————– Practice Problem: Can you modify the sequence in the problem to generate all negative rationals as well? Posted in Algebra, Number Theory, Olympiad \|\| No Comments »
Strikethrough. Topic: Geometry/NT. Level: AIME.	December 20th, 2006
Problem: (Stanford Putnam Practice) Let $P_1, P_2, \ldots , P_{2007}$ be distinct points in the plane. Connect the points with the line segments $P_1P_2, P_2P_3, \ldots, P_{2006}P_{2007}, P_{2007}P_1$ . Can one draw a line that passes through the interior of every one of these segments? Solution: Playing around with pictures for a while, our intuition says that since is odd, this is impossible. Now let’s try to prove it. Suppose there exists such a line . Then we know that the endpoints of each line segment lie on opposite sides of the line. So and lie on opposite sides of ; and lie on opposite sides of ; $\cdots$ $P_{2007}$ and lie on opposite sides of . But wait, by a simple induction we know that $P_1, P_3, P_5, \ldots, P_{2007}$ lie on the same side. That gives us the contradiction we seek. Thus does not exist, as desired. QED. ——————– Comment: Not a bad problem, though pretty simple after you realized that you could fix the line before the points. It’s easy to see that this generalizes to any set of an odd number of points (try the sides of a triangle, for example), so we have proven in fact a decently strong result. ——————– Practice Problem: (Stanford Putnam Practice) Show that if every room in a house has an even number of doors, then the number of outside entrance doors must be even as well. Posted in AIME, Geometry, Number Theory \|\| 3 Comments »
I Am The Greatest (Common Divisor)! Topic: Number Theory. Level: Olympiad.	December 19th, 2006
Problem: (Stanford Putnam Practice) Suppose $(a_i)_{i \ge 1}$ is a sequence of positive integers satisfying $\gcd(a_i, a_j) = \gcd(i, j)$ for $i \neq j$ . Show that for each . Solution: Let be an arbitrary positive integer. If we can show that we will be done. We have $\gcd(a_n, a_{2n}) = \gcd(n, 2n) = n$ so . Then for some positive integer . Similarly, we know $kn\|a_{kn}$ so $a_{kn} = ckn$ for some positive integer . Then, however, $\gcd(a_n, a_{kn}) = (kn, ckn) = kn$ and $\gcd(n, kn) = n$ so we must have $kn = n \Rightarrow k = 1$ . Thus . QED. ——————– Comment: At first, induction seemed the way to go, but after a while you realize that the induction step is, well, not very likely since $a_1 = 1, a_2 = 2, \ldots, a_k = k$ puts very few restrictions on $a_{k+1}$ . So then you look to a better option, trying to find the strongest use of $\gcd(i, j)$ . It turns out that this happens when is a multiple of , which is exactly how the above proof starts. ——————– Practice Problem: (Stanford Putnam Practice) Let be a prime number. Show that divides infinitely many of the numbers $1, 11, 111, 1111, \ldots$ . [Reworded] Posted in Number Theory, Olympiad \|\| No Comments »

free web counters