On 2012 Putnam Problem B1

This post continues my effort to write solutions, aimed at students, to the problems on this year’s Putnam exam. Here is problem B1:

Let S be a class of functions from [0,\infty) to [0,\infty), satisfying the following properties:

  1. The functions f_1(x) = e^x - 1 and f_2(x) = \ln(x+1) are in S;
  2. If f(x) and g(x) are in S, then f(x) + g(x) and f(g(x)) are in S;
  3. If f(x) and g(x) are in S and f(x) \geq g(x) for all x \geq 0, then f(x) - g(x) is in S.

Prove that, if f(x) and g(x) are in S, then f(x)g(x) is also in S.

Spoiler alert: the solution is below Nyan Cat.

poptart1red1

Initial comments

Even though this superficially looks like an analysis problem, it’s really more of an algebra problem. You’re given that the set S is closed under addition, composition, and (when possible) subtraction, and you’re asked to prove that the set will necessarily be closed under multiplication as well. The key insight here is that the exponential and logarithmic functions should allow you to “turn addition into multiplication” and vice versa. And that one idea really does form a sketch of the proof, and all that’s left is to carry the idea out in detail.

A remark about the subtraction condition: I would slightly rephrase it to say that, if f(x) - g(x) \geq 0 for all x \geq 0, then f(x) - g(x) is in S. Since the “universe” of functions in this problem go from [0,\infty) to [0,\infty), it’s worth recognizing that the inequality really is the weakest possible thing you could require; it simply says that subtraction is okay, as long you still get something that goes from [0,\infty) to [0,\infty).

Solution

If f(x) and g(x) are in S, then:

  • You can compose the functions with \ln(x+1) to get \ln(f(x)+1) and \ln(g(x)+1) are in S.
  • You can add to get \ln(f(x)+1) + \ln(g(x)+1) = \ln(f(x)g(x) + f(x) + g(x) + 1) is in S.
  • You can compose with e^x - 1 to get f(x)g(x) + f(x) + g(x) is in S.
  • Finally, you can subtract to get f(x)g(x) is in S (and this is okay since f(x)g(x) \geq 0 always holds).

QED

Closing remarks

In my first attempt at this problem, I exponentiated first, which gave me e^{f(x) + g(x)} - 1. I figured I could split up the first term as e^{f(x)}e^{g(x)}, and then…I don’t know. This approach wasn’t going anywhere.

I could explain why that approach was doomed to failure, but the moral of the story is that things like this are going to happen. It’s important to be able to recognize when you’re headed toward a dead end, and to go back as far as necessary to try something different. Putnam problems aren’t supposed to be easy, and they often require a few rounds of starting over before you get things right.

Advertisements
Tagged , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: