# Mathematical Food for Thought

Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.

• ## Meta

 Toast To Euclid. Topic: Number Theory. Level: AMC/AIME. December 17th, 2006 Introduction: (Euclid’s Algorithm) Given two positive integers , we can determine through the following algorithm. Let , where are positive integers such that . If , then . Otherwise, let , , and repeat. For example, if we wanted to find , we would do so . A proof of this result is left to the reader. -------------------- Problem: (Stanford Putnam Practice) Prove that consecutive Fibonacci numbers are always relatively prime. Solution: Well, since we had a handy introduction to Euclid's Algorithm up there, let's try to use it. We want to calculate . Executing the algorithm, we get . Hmm, is there a pattern? I think so! We eventually get . So , as desired. QED. -------------------- Comment: Euclid's Algorithm is an extremely powerful tool for computing greatest common divisors. It even comes in handy in computer science, where we can write a very simple recursive method to compute . For example int gcd(int a, int b) { if(b > a) swap(a,b); if(b == 0) return a; a %= b; return gcd(b, a); } Posted in AIME, AMC, Number Theory || No Comments » Complexity. Topic: Complex Numbers/Polynomials. Level: AIME/Olympiad. December 12th, 2006 Problem: Let . If and , find the remainder when is divided . [Reworded] Solution: Well is pretty ugly looking at the moment, let’s fix that. We can write it as the sum of the following series: , since all of them are geometric series with common ratio . Summing these up, we have . The top is again a geometric series with common ratio (without that part) so we can write it ias . But wait, if then , so in fact we have . Then so it remains the evaluate the denominator of that. Considering we are like whoa, has the th roots of unity for its roots except and it has leading coefficient so it must be . Hence . By Euler’s Totient Theorem, . QED. ——————– Comment: It didn’t take too much “insight” to reduce to the nicer expression, more like just tedious evaluation of geometric series galore. Seeing the product in the denominator should have been pretty familiar (though I admit I forgot what it came out to at first) and a standard argument allowed you to evaluate it. Possibly the hardest part was Euler’s Totient Theorem, which is invaluable to carry around for the AIME. Also knowing that . ——————– Practice Problem: Do there exist polynomials and such that ? If so, find them. Posted in AIME, Complex Numbers, Olympiad, Polynomials || 1 Comment » Just… Right. Topic: Calculus/Inequalities. Level: AIME/Olympiad. December 10th, 2006 Problem: (Stanford Putnam Practice) Let be continuous and monotonically increasing, with and . Prove that . Solution: We can easily generalize this to , so we will prove this instead. Consider the value of . This integrates across the area of the unit square with opposite vertices and so the integral is . Visualize this with a picture. Now we use a left-hand Riemann sum approximation on both and with subdivisions from to to get . Then it remains to show that . But from the argument above we know covers at least the square with opposite vertices and , which has area . Again, draw a picture (it’s the same as before except without the endpoint restriction). Hence we have shown that , as desired. QED. ——————– Comment: This was a pretty interesting problem; it was pretty clear from the beginning that you were approximating some kind of interval and it looked a lot like Riemann sums so that seemed to be the method of choice. After that, a little knowledge about function inverses and a couple of nice pictures gave the rest of the solution. ——————– Practice Problem: (Stanford Putnam Practice) Let be an arbitrary positive integer and let for . Determine if exists and if so, evaluate it. [Reworded] Posted in AIME, Calculus, Inequalities, Olympiad || No Comments » eek! Topic: Calculus/S&S. Level: AIME/Olympiad. December 9th, 2006 Problem: (Problem-Solving Through Problems – 5.4.15) Let and for . Show that . Solution: Well, the LHS looks suspiciously like a Taylor series, so maybe we can find a function. A good choice is . Notice that . Testing a few derivatives, we hypothesize that . By induction, we easily have , which exactly satisfies so we indeed have . Then and the Taylor series of centered at zero is . Hence our desired sum is the above series evaluated at , which is simply . QED. ——————– Comment: A neat problem resulting from Taylor series. They are useful in all sorts of ways, especially evaluating other series. If we can reduce a given series to the Taylor series of a function like we did in this problem, evaluating it becomes plugging in a point. ——————– Practice Problem: (Problem-Solving Through Problems – 5.4.17) Show that the functional equation is satisfied by with . Posted in AIME, Calculus, Olympiad, Sequences & Series || 2 Comments » Digit To The Unit. Topic: Algebra. Level: AIME. December 6th, 2006 Problem: (2006-2007 Warm-Up 5 – #13) Determine the units digit in the decimal expansion of . Solution: Well, in its current form it is quite an ugly expression, with half of the terms involving a radical. Maybe we can simplify this, a.k.a. get rid of the radicals. Consider . Since we know , then (it’s really small). The above expression is an integer because all of the radical terms cancel out. So if we find the units digit of this, we simply subtract one away and get the units digit of our original number. But this number is just , where every term in between is divisible by . That means they all have a units digit of zero, so we only need to look at the last term. Since powers of repeat the sequence , we know . So twice of this would give a units digit of . Subtracting one away as we mentioned above gives us a units digit of . QED. ——————– Comment: This is an excellent application of the binomial theorem and a good test of your intuition, which basically consisted of noticing . The power was an arbitrary even number; in fact, for smaller powers we notice the exact same thing: . ——————– Practice Problem: Determine how many elements of the th row of Pascal’s Triangle are odd. Posted in AIME, Algebra || 2 Comments »