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