How many ways can one fill a square grid with nonnegative integers such that no nonzero integer appears more than once in the same row or column and the sum of the numbers in every row and column equals 7 ?
Solution
In what ways could we potentially fill a single row? The only possibilities are if it contains the numbers or or or or . Notice that if we write these numbers in binary, in any choices for how to fill the row, there will be exactly one number with a 1 in its rightmost digit, exactly one number with a 1 in the second digit from the right, and exactly exactly one number with a 1 in the third digit from the right. Thus, consider the following operation: start with every unit square filled with the number 0 . Add 1 to three unit squares, no two in the same row or column. Then add 2 to three unit squares, no two in the same row or column. Finally, add 4 to three unit squares, no two in the same row or column. There are clearly ways to perform this operation and every such operation results in a unique, suitably filled-in 3 by 3 square. Hence the answer is 216.