36th Putnam 1975

Problem B3

Let n be a fixed positive integer. Let S be any finite collection of at least n positive reals (not necessarily all distinct). Let f(S) = (∑a∈S a)n, and let g(S) = the sum of all n-fold products of the elements of S (in other words, the nth symmetric function). Find supS g(S)/f(S).



Answer: 1/n!

For any n elements a, b, ... , w of S, the coefficient of a1b1...w1 in the multinomial expansion of f(s) is just n!/(1! 1! ... 1!) = n!. In other words, f(S) = n! g(S) + other terms. But the other terms are all positive, so f(S) > n! g(S). Hence g(S)/f(S) < 1/n! . This establishes that 1/n! is an upper bound.

Take S to be m elements all 1. Then f(S) = mn and g(S) = mCn. Hence g(S)/f(S) = (m/m) ( (m-1)/m) ( (m-2)/m) ... ( (m-n)/m) 1/n! . As m tends to infinity, each of the n terms (m-r)/m tends to 1 and hence g(S)/f(S) tends to 1/n! . Hence 1/n! is the least upper bound.



36th Putnam 1975

© John Scholes
27 Jan 2001