42nd Putnam 1981 Problem A1 Let the largest power of 5 dividing 1 1 2 2 3 3 ... n n be 5 f(n) . What is lim n→∞ f(n)/n 2 ? Solution
: 1/8. Let 5 k be the largest power of 5 not exceeding n. We proceed by looking first at the contribution of the single power of 5 in all multiples of 5, then at the additional contribution from the second power of 5 in all multiples of 25 and so on. A single power of 5 in m appears m times in m m , so the first power of 5 in 5, 10, 15, 20, ... contributes to f(n): 5 + 10 + 20 + ... + 5[n/5] = 5( 1 + 2 + ... + [n/5] ) = 1/2 5 ( [n/5] 2 + [n/5] ). Similarly, the second power of 5 in 25, 50, 75, ... contributes an additional 1/2 5 2 ( [n/5 2 ] 2 + [n/5 2 ] ). And so on. Hence 2 f(n) = 5 ( [n/5] 2 + [n/5] ) + 5 2 ( [n/5 2 ] 2 + [n/5 2 ] ) + ... + 5 k ( [n/5 k ] 2 + [n/5 k ]). Let [n/5 i ] = n/5 i + δ i . Then 5 i ( [n/5 i ] 2 + [n/5 i ] ) = 5 i ( (n/5 i - δ i ) 2 + (n/5 i - δ i ) = n 2 /5 i - 2n δ i + 5 i δ i 2 + n - 5 i δ i . Hence 2 f(n) = n 2 ∑1/5 i - 2n ∑ δ i + ∑ 5 i (δ i 2 - δ i ) + nk. Now k = [log 5 n], so k/n → 0 as n → ∞. Also |δ i | and |δ i 2 - δ i | < 1. Hence lim 1/n 2 |- 2n ∑ δ i + ∑ 5 i (δ i 2 - δ i ) + nk| <= lim 2k/n + lim k/n + lim 1/n 2 ∑ 5 i = 0 + 0 + lim 1/n 2 (1/4 (5 k+1 + 1) = 0 (since the last term is less than 5/4n). Hence lim f(n)/n 2 = 1/2 (1/5 + 1/5 2 + ... ) = 1/2 1/5 1/(1 - 1/5) = 1/8. 42nd Putnam 1981 © John Scholes jscholes@kalva.demon.co.uk 3 Nov 1999