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 sup S g(S)/f(S). Solution
: 1/n! For any n elements a, b, ... , w of S, the coefficient of a 1 b 1 ...w 1 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) = m n 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 jscholes@kalva.demon.co.uk 27 Jan 2001