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 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.
© John Scholes
jscholes@kalva.demon.co.uk
14 Nov 1999