47th Putnam 1986 Problem A4 Let r(n) be the number of n x n matrices A = (a ij ) such that: (1) each a ij = -1, 0, or 1; and (2) if we take any n elements a ij , no two in the same row or column, then their sum is the same. Find rational numbers a, b, c, d, u, v, w such that r(n) = a u n + b v n + c w n + d. Solution
: r(n) = 2.3 n + 4 n - 4.2 n + 1. Moderately hard. The key insight is that the elements in any two rows have a fixed difference between corresponding elements. In other words, if the first row is a 1 , a 2 , ... , a n , then the ith row is a 1 + b, a 2 + b, ... , a n + b for some b (*). Indeed, a little thought shows that this is a necessary and sufficient condition for (2) to hold. Because if we have r ≠ s and c ≠ d, then given a sum involving a rc and a sd , we have another sum which is identical except that these two elements are replaced by a rd and a sc . Hence a rc - a sc = a rd - a sd . So as we vary d the difference a rd - a sd remains fixed. We now examine the following disjoint cases: (A) all elements of the first row are the same; (B) both -1 and 1 appear somewhere in the first row; (C) 1 and 0, but not -1, appear in the first row; (D) -1 and 0, but not 1, appear in the first row. In case (A), (*) implies that the same must be true for the other rows, and then (1) is automatically satisfied. We have 3 choices for each row, so 3 n possibilities in all. In case (B), the other rows must all be identical to the first, because if the difference b in (*) is non-zero then we get an element that does not satisfy (1). In other words each column has all elements the same. So we have to find the number of possibilities for the first row. The total number of possibilities is 3 n . There are 2 n possibilities where 1 is not present, 2 n where -1 is not present, and 1 where neither 1 nor -1 is present. Hence the required number is 3 n - 2.2 n + 1. In case (C), b in (*) must be 0 or -1. There are 2 n - 2 ways of choosing the first row so that it includes 1 or 0, but not -1. We then have 2 choices for the difference b for each of the other n-1 rows, or 2 n-1 difference choices in all, giving a total of 2 2n-1 - 2 n possibilities in total. Similarly, for case (D). So in (C) and (D) together there are 4 n - 2.2 n possibilities. Adding up, we get 4 n + 2.3 n - 4.2 n + 1. As a check, this is correct for n = 1. In a sense, everything after the first paragraph above is fairly routine (once you grasp that the small number of available values for the elements places severe restrictions on b). But care is needed to avoid double counting. Notice also the typical Putnam misdirection of rational values. Finally, a formula of this type should instantly suggest recurrence relations. But I did not find that a productive approach. Does anyone else have a solution of that type? 47th Putnam 1986 © John Scholes jscholes@kalva.demon.co.uk 2 Oct 1999