14th Putnam 1954

Problem A1

Let N be the set {1, 2, ... , n}, where n is an odd integer. Let f : N x N → N satisfy: (1) f(r, s) = f(s, r) for all r, s; (2) {f(r, s) : s ∈ N} = N for each r. Show that {f(r, r) : r ∈ N} = N.




We have a square array of numbers aij = f(i, j). Each member of N occurs just once in each row (by (2) ), so it occurs n times in all. But the array is symmetric (by (1) ), so each member occurs an even number of times off the main diagonal. Hence it must occur an odd number of times, and hence at least once, on the main diagonal. But the main diagonal only has n entries, so if each of n numbers occurs at least once, then each must occur exactly once.



14th Putnam 1954

© John Scholes
14 Nov 1999