Mathematical Food for Thought

I’ll be gone for the next week on a cruise, so… no math!

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?

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 .

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 ,

.

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 .