46th Putnam 1985

a_{i j} is a positive integer for i, j = 1, 2, 3, ... and for each positive integer we can find exactly eight a_{i j} equal to it. Prove that a_{i j} > ij for some i, j.

Solution

The idea is to show that for some N there are more than 8N pairs (i, j) with ij ≤ N. For then if we always had a_{i j} ≤ ij we would have a_{i j} ≤ N for more than 8N pairs (i, j) and hence some value in {1, 2, ... , N} would be shared by more than 8 a_{i j}, contradicting the premise.

The number of pairs (i, j) with ij ≤ N is [N/1] + [N/2] + ... + [N/N] = N(1 + 1/2 + 1/3 + ... + 1/N) - N. But ∑ 1/n diverges, so it is certainly greater than 9 for N sufficiently large.

46th Putnam 1985

© John Scholes
jscholes@kalva.demon.co.uk
7 Jan 2001