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 be a class of functions from to , satisfying the following properties:
- The functions and are in ;
- If and are in , then and are in ;
- If and are in and for all , then is in .
Prove that, if and are in , then is also in .
Spoiler alert: the solution is below Nyan Cat.
Even though this superficially looks like an analysis problem, it’s really more of an algebra problem. You’re given that the set 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 for all , then is in . Since the “universe” of functions in this problem go from to , 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 to .
If and are in , then:
- You can compose the functions with to get and are in .
- You can add to get is in .
- You can compose with to get is in .
- Finally, you can subtract to get is in (and this is okay since always holds).
In my first attempt at this problem, I exponentiated first, which gave me . I figured I could split up the first term as , 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.