### 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.

**Solution**

*Easy.*

We have a square array of numbers a_{ij} = 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

jscholes@kalva.demon.co.uk

14 Nov 1999