Putnam 2003, Problem A-1

Let \( n \) be a fixed positive integer. How many ways are there to write \( n \) as a sum of positive integers,
\[
n = a_1 + a_2 + \cdots + a_k,
\]
with \( k \) an arbitrary positive integer and \( a_1 \leq a_2 \leq \cdots \leq a_k \leq a_1 + 1 \)? For example, with \( n = 4 \) there are four ways: \( 4 \), \( 2+2 \), \( 1+1+2 \), \( 1+1+1+1 \).

Solution:
There are \( n \) such sums. More precisely, there is exactly one such sum with \( k \) terms for each of \( k = 1, \ldots, n \) (and clearly no others). To see this, note that if \( n = a_1 + a_2 + \cdots + a_k \) with \( a_1 \leq a_2 \leq \cdots \leq a_k \leq a_1 + 1 \), then  
\[
ka_1 = a_1 + a_1 + \cdots + a_1 \leq n \leq a_1 + (a_1 + 1) + \cdots + (a_1 + 1) = ka_1 + k - 1.
\]  
However, there is a unique integer \( a_1 \) satisfying these inequalities, namely \( a_1 = \lfloor n/k \rfloor \). Moreover, once \( a_1 \) is fixed, there are \( k \) different possibilities for the sum \( a_1 + a_2 + \cdots + a_k \): if \( i \) is the last integer such that \( a_i = a_1 \), then the sum equals \( ka_1 + (i - 1) \). The possible values of \( i \) are \( 1, \ldots, k \), and exactly one of these sums comes out equal to \( n \), proving our claim.  

**Note:** In summary, there is a unique partition of \( n \) with \( k \) terms that is "as equally spaced as possible". One can also obtain essentially the same construction inductively: except for the all-ones sum, each partition of \( n \) is obtained by "augmenting" a unique partition of \( n - 1 \).  


### Third solution:  
Since both sides are continuous in each \( a_i \), it is sufficient to prove the claim with \( a_1, \ldots, a_n \) all positive (the general case follows by taking limits as some of the \( a_i \) tend to zero). Put \( r_i = b_i/a_i \); then the given inequality is equivalent to  
\[
(1 + r_1)^{1/n} \cdots (1 + r_n)^{1/n} \geq 1 + (r_1 \cdots r_n)^{1/n}.
\]  
In terms of the function  
\[
f(x) = \log(1 + e^x)
\]  
and the quantities \( s_i = \log r_i \), we can rewrite the desired inequality as  
\[
\frac{1}{n} \left( f(s_1) + \cdots + f(s_n) \right) \geq f\left( \frac{s_1 + \cdots + s_n}{n} \right).
\]  
This will follow from Jensen’s inequality if we can verify that \( f \) is a convex function; it is enough to check that \( f''(x) > 0 \) for all \( x \). In fact,  
\[
f'(x) = \frac{e^x}{1 + e^x} = 1 - \frac{1}{1 + e^x}
\]  
is an increasing function of \( x \), so \( f''(x) > 0 \) and Jensen’s inequality thus yields the desired result. (As long as the \( a_i \) are all positive, equality holds when \( s_1 = \cdots = s_n \), i.e., when the vectors \( (a_1, \ldots, a_n) \) and \( (b_1, \ldots, b_n) \) are proportional. Of course other equality cases crop up if some of the \( a_i \) vanish, i.e., if \( a_1 = b_1 = 0 \).)