43rd Putnam 1982 Problem B3 Let p n be the probability that two numbers selected independently and randomly from {1, 2, 3, ... , n} have a sum which is a square. Find lim n→∞ p n √n. Solution
: 4(√2 - 1)/3. There are m 2 - 1 ordered pairs with sum m 2 for m 2  n (and ≤ 2n). Hence the total number of ordered pairs taken from {1, 2, ... , n} which sum to a square is ∑ 1 [√n] (m 2 - 1) + ∑ [√n + 1] [√(2n)] (2n - m 2 + 1). Now ∑ 1 N m 2 = 1/3 N 3 + O(N 2 ). Also removing the [ ] from the limits gives an error of O(n). So we get: 1/3 n 3/2 + 2(√2 - 1)n 3/2 - 1/3 ( √(2n) 3 - √n 3 ) + O(n). p n = 1/n 2 x no. of pairs which sum to a square. So p n √n = (1/3 + 2(√2 - 1) - 1/3 ( 2√2 - 1) ) + O(n)/n 3/2 which tends to the limit (1/3 + 2(√2 - 1) - 1/3 ( 2√2 - 1) ) = 4(√2 - 1)/3. 43rd Putnam 1982 © John Scholes jscholes@kalva.demon.co.uk 16 Jan 2002