(10/5/98) Let n be an odd integer greater than 1. Let A be an nxn symmetric matrix such that each row and each column of A consists of some permutation of 1,2, ..., n. Show that each of the integers 1,2, ..., n must appear on the main diagonal.
(This was Problem 1 from Part A of the 1954 Putnam Exam.)

Solution:

Let k be an integer between 1 and n. Since A is symmetric, k must appear the same number of times above the diagonal as below; therefore k appears an even number of times off of the main diagonal. Since k appears once in each row, it must appear n times in A; since n is odd, k must appear at least once on the main diagonal. This is true for all k from 1 to n.