# Mathematical Food for Thought

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

• ## Meta

 Eww… Topic: Algebra/Inequalties. Level: AIME/Olympiad. September 30th, 2006 Problem: Find the minimum value of for . Solution: Make a handy substitution , and . Then we want to minimize after cancelling . But we see that this evenly divides and becomes . But and by AM-GM and the same equality case, so with equality at . QED. ——————– Comment: It was very useful to make the substitution and then homogenize the numerator so you could cancel things out evenly. Then classical inequalities (AM-GM) helped us finish it. ——————– Practice Problem: Prove that . Posted in AIME, Algebra, Inequalities, Olympiad || 2 Comments » This Is Mental Math?!? Topic: Number Theory. Level: AIME. September 27th, 2006 Problem: (2006-2007 Warm-Up 2) Let be the sum of the digits of . Find . Solution: Let’s try bounding our quantity. We know because is the number of digits of (except when is a power of ten, but those are trivial) and the biggest digit is . So we can say that so and because the largest sum of digits of any number less than is . So we know our value is less than . But remember that the sum of the digits of a number is equal to itself (prove this!) and so our answer is also . But the only number less than that works is then . QED. ——————– Comment: Admittedly, this is not likely to show up on a mental math test, but it’s feasible to do in your head. The bounding is not horrific and taking the mod is also not bad. Of course, seconds is pretty quick, but if you knew how to approach the problem already, it was definitely possible (and done). ——————– Practice Problem: Show that the sum of the digits of a number is congruent to itself modulo nine. Posted in AIME, Number Theory || 3 Comments » Parity Check. Topic: Logic/NT. Level: AIME/Olympiad. September 25th, 2006 Problem: (2000 Putnam – B1) Let be integers for . Assume for each , at least one of is odd. Show that exist integers such that is odd for at least values of , . Solution: A pretty notation-heavy, strange, contrived problem. Let’s get started. Where do we get in the denominator? How about from the number of binary triples that contain at least one ? In fact we may simplify the problem so that are all in the set because we only care about even and odd. Cool. Now let’s see… for which binary triples and is odd? Try it out. We will list the binary triples and give them variable names to simplify our lives. . Now we will write as where and . We make the following table:  . A B C D E F G A X . X . X . X B . X X . . X X C X X . . X X . D . . . X X X X E X . X X . X . F . X X X X . . G X X . X . . X  where an X in the entry in row and column signifies that is odd. Notice that each choice of makes four odd and each choice of has four possible to make it odd. Let denote the number of times is odd for . We want to show that there exists a such that . We know is the number of times we have an odd sum if we apply every possible . But if we apply every we know from our table that each of the binary triples produces an odd for four of the seven . So in fact . But since the average of the ‘s is then , there must exist at least one such that , as desired. QED. ——————– Comment: IMO, a very cool problem. Something that at first glance you sort of stare blankly at how they got such a ridiculous problem but then you realize it is a Putnam B1 so it couldn’t possibly that bad, which is soon followed by your realization of the simplification to binary and finally the recognition of the seven as the number of binary triples with at least one . Yay! ——————– Practice Problem: I have seven light bulbs which are off and seven switches labeled with the binary triples above. A switch turns on a light bulb if the dot product (as above) of the number of the switch and the number of the light bulb is odd. Show that if I flip each switch once the light bulbs will still all be off. Posted in Logic, Number Theory || No Comments » Pell. Topic: NT. Level: AIME/Olympiad. September 23rd, 2006 Problem: (2000 Putnam – A2) Prove that there exist infinitely many integers such that are each the sum of the squares of two integers. [Example: , , .] Solution: Consider the Pell Equation . It is well-known that this equation has an infinite number of positive integer solutions . This can be derived using truncated continued fractions representation of (see here). So if we let , we have , completing the problem. QED. ——————– Comment: This was one of the official solutions to the problem, even though all you had to know was that Pell Equations have an infinite number of solutions. There is a constructive solution to the problem as well, based on choosing certain . ——————– Practice Problem: Find the constructive solution (i.e. all numbers of the form work for some function ). Posted in AIME, Number Theory, Olympiad || 2 Comments » Infinite… POWER! Topic: Algebra/Inequalities/S&S. Level: AIME/Olympiad. September 22nd, 2006 Problem: (2000 Putnam – A1) Let be a positive real number. What are the possible values of , given that are positive numbers such that ? Solution: First, we will try to guess what the range is using inequalities. We obviously have because all the are positive. Also, by “expansion” (infinitely, but that’s ok). So for now, our guess is the interval . We want to show that given any we can make a sequence such that and . Well, we like easy sequences so consider if is a geometric sequence with common ratio . Then . We want to show that given any , we can find a positive real satisfying , the above equation, and . Rewriting the two equations (and squaring the first), we have so . Since we want , we must use the second factor, which gives us . But if , clearly , so there exists some positive ratio such that and . Hence the possible values are . QED. ——————– Comment: A surprisingly difficult A1 problem on a Putnam; it had less perfect scores than A2, B1, and B2 (which will probably be posted over the next week or so). It required some experience with inequalities to guess the range and then a clever assumption of a geometric series to complete the proof. ——————– Practice Problem: What if the terms could be any nonzero real? What are the possible values of then? Posted in AIME, Algebra, Inequalities, Olympiad, Sequences & Series || 1 Comment »