# Mathematical Food for Thought

• ## About

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

• ## Meta

 Break Time. August 25th, 2006 I’ll be gone for the next week on a cruise, so… no math! Posted in Announcements || No Comments » Add Some Numbahs. Topic: Number Theory. Level: AIME/Olympiad. August 24th, 2006 Problem: (2003 Putnam – A1) Let be a fixed positive integer. How many ways are there to write as a sum of positive integers with an arbitrary positive integer and ? Solution: So that strange inequality condition basically says that all the numbers are within one of each other. Easy enough. Let’s take this approach; for any , run through each from to (if there are clearly no solutions). Let . Then . Essentially, this says that all of the 's are close to . We claim that in fact or for all and a fixed . Suppose for some . Then since the maximum is within of the minimum, impossible. Similarly, suppose for some . Then since the minimum is within of the maximum, again impossible. This proves the claim. Now we claim that there is exactly one solution for any fixed . Suppose are all and are all . Then the sum is . At , all the ‘s are and the sum is . But notice that decreasing by increases the LHS by . So if we keep incrementing , we will eventually get to (if we go all the way to we reach , so we must’ve passed somewhere in there). It’s easy to see that we can’t get twice because the LHS only increases. Hence for each there is exactly one solution for . Since are all possible values for , there are exactly ways to write as a sum of the desired form. QED. ——————– Comment: Another Putnam problem; they aren’t too bad, right? Considering a large percentage of students who take it get zero points out of , anyway. The solution above would probably have to be rigorized immensely before actually being called a proof, but that would be no fun to read and stuff. ——————– Practice Problem: (2003 Putnam – B1) Do there exists polynomials such that holds identically? Posted in AIME, Number Theory, Olympiad || 7 Comments » Function + Equation = ?? Topic: Algebra. Level: AIME/Olympiad. August 22nd, 2006 Problem: Find all functions that satisfy for all reals . Solution: Let’s start by plugging in something easy, like . We get so . Hmm, make it a little more complicated then and try just . Then . But wait, we already know so we can just plug this in. Thus we have or . We check by plugging each in: (this works) (this doesn’t). That means only works. QED. ——————– Comment: Functional equations are pretty strange as far as problems go. Basically you go around plugging random things in until you find something useful. Then you work it all out and you usually get an interesting result. ——————– Practice Problem: (360 Mathematical Contests – 1.1.49) Find all polynomials with integral coefficients such that for all real numbers . Posted in AIME, Algebra, Olympiad || 5 Comments » Ex-ex-exponents! Topic: Inequalities. Level: AIME. August 20th, 2006 Problem: Let be positive reals. Prove that . Solution: How do you get rid of exponents? Well, take the log of course! Logging both sides and using log rules (multiplication to addition and bringing the power down), the inequality becomes . We will prove that and . If we add those together, we get the inequality above. But we note that and are similarly sorted, we can apply the Rearrangement Inequality (see here), which tells us that and , exactly what we needed. Thus the inequality is proven. QED. ——————– Comment: Classic way of proving inequalities with exponents; many times, after you take the log, you can apply Jensen’s (log is concave) to get some interesting results as well. ——————– Practice Problem: Prove AM-GM. For positive reals , . Posted in AIME, Inequalities || 7 Comments » Effuvay. Topic: Algebra/NT/Polynomials. Level: AIME. August 18th, 2006 Problem: Let be a polynomial with integer coefficients. Show that divides . Solution: Note that means divides . Let’s prove a more general result, that . Write . We want to show that . But since , it’s clear that divides each and thus their sum. Applying this result to and , we get , which implies that , as desired. QED. ——————– Comment: The general result is a very useful fact about polynomials with integer coefficients that shows up often; problems can be written based on many variations of it. Writing out the terms of the polynomial is also a good strategy whenever you’re stuck. ——————– Practice Problem: Let be a polynomial with integer coefficients. If are distinct integers such that , show that there cannot exist an integer such that . Posted in AIME, Algebra, Number Theory, Polynomials || 10 Comments »