7th Irish 1994 Problem A4 An n x n array of integers has each entry 0 or 1. Find the number of arrays with an even number of 1s in every row and column.
2 (n-1) 2 Solution Suppose A is an arbitrary n-1 x n-1 array of 0s and 1s. Then we can extend A to an n x n array by adding an extra row and an extra column. For i = 1, 2, ... , n-1, we choose the i,n entry to make the number of 1s in row i even. Similarly, we choose the n,j entry to make the number of 1s in column j even. Suppose we put an odd number of i,n entries equal to 1. Then an odd number of rows in A had an odd number of 1s, and the rest had an even number of 1s, so in total A had an odd number of 1s. Similarly, if we put an even number of i,n entries equal to 1, then A has an even number of 1s. Similarly for the entries in n,j. Thus if we choose the final entry in n,n to make the nth column have an even number of 1s, then it will also make the nth row have an even number of 1s. Thus each array for n-1 x n-1 gives rise to a unique n x n array with the required property. Hence the number is 2 (n-1) 2 . 7th Irish 1994 © John Scholes jscholes@kalva.demon.co.uk 17 Dec 2003 Last updated/corrected 17 Dec 03