There is a 4 x 4 grid. In each cell of the grid, you are allowed to put either a 1 or a -1. The sum of the numbers of each column and each row must equal 0. How many such configurations of the grid are there?
Put into each cell one number 1 or one number -1 that the sums of number in each coloums each rows is 0.
-
0I'm deleting my answer for now since I forgot about rowsum zero. Thanks to Arthur for pointing that out. – 2012-12-05
2 Answers
I'm going to write + for $+1$ and - for $-1$ in what follows, to save space. I also advice you to draw diagrams to follow my reasoning.
The first row can have sum $0$ in six different ways. I am going to assume that it is done one specific way, and count the ways rows 2-4 can be written. Afterwards, if I multiply that answer with $6$, I get the total number of ways for the entire grid.
For the second row, we can split into 3 cases:
1) It is exactly the same as row 1. This can be done in one way, and if this is the case, then the last two rows can only be done in one way, since each column now has either two + or two -. So this case contributes one way to the total.
2) It is exactly the opposite of row 1. This can be done in one way, and if this is the case, then the third row can be whatever (6 ways), and the last row can only be the opposite of row 3. This case contributes with 6 to the total.
3) It differs from row 1 in exactly two places. This can be done in four ways. It has to have different values in the two columns where they differ, and in the two columns where they are the same, the values for row 3 and 4 are determined. The four cells left in row 3 and 4 are uniquely determined by what you put into one of them, but that can be whatever. In total, 8 ways for case 3.
We sum the contributions from the cases to $15$, so there are a total of $6\cdot 15 = 90$ ways to fill the whole grid.
You can to start completing the first line of the square \begin{array}{|c|c|c|c|} \hline .& . & .&. \\ \hline .& .&. & .\\ \hline . & . & .& .\\ \hline .& . & .& .\\ \hline \end{array}
And you can do this of $ 6 = \binom{4}{2} $ ways because you need to choose the 2 places between the 4 to put the numbers 1. For exemplo, \begin{array}{|c|c|c|c|} \hline 1& -1 & 1 & -1 \\ \hline . & .&.& .\\ \hline . & .& .&.\\ \hline .&.&. &.\\ \hline \end{array}.
Then you can complete the fisrt column choosing one of the three places to put the number 1 . For exemplo, \begin{array}{|c|c|c|c|} \hline 1& -1 & 1 &-1 \\ \hline 1 & & &\\ \hline . & . & .&.\\ \hline .& .& .&.\\ \hline \end{array}. Then, after you do this, your table must be \begin{array}{|c|c|c|c|} \hline 1& -1 & 1 &-1 \\ \hline 1 & & &\\ \hline -1 & & &\\ \hline -1 & & &\\ \hline \end{array}. You can complete the column that contains the number 1. There are two signicant ways to do this. You can to put the 1 in the column that already countains the 1 or no. These cases are respectively of this forms \begin{array}{|c|c|c|c|} \hline 1& -1 & 1 &-1 \\ \hline 1 & -1&1 &-1\\ \hline -1 & & &\\ \hline -1 & & &\\ \hline \end{array}. or for examplo \begin{array}{|c|c|c|c|} \hline 1& -1 & 1 &-1 \\ \hline 1 & 1& -1&-1\\ \hline -1 & & &\\ \hline -1 & & &\\ \hline \end{array}.
Notice that there are another way to do the second case, namely \begin{array}{|c|c|c|c|} \hline 1& -1 & 1 &-1 \\ \hline 1 & -1& -1&1\\ \hline -1 & & &\\ \hline -1 & & &\\ \hline \end{array}.
The case \begin{array}{|c|c|c|c|} \hline 1& -1 & 1 &-1 \\ \hline 1 & -1&1 &-1\\ \hline -1 & & &\\ \hline -1 & & &\\ \hline \end{array} is determined to be \begin{array}{|c|c|c|c|} \hline 1& -1 & 1 &-1 \\ \hline 1 & -1&1 &-1\\ \hline -1 &1 &-1 &1\\ \hline -1 &1 &-1 &1\\ \hline \end{array}. And the second case \begin{array}{|c|c|c|c|} \hline 1& -1 & 1 &-1 \\ \hline 1 &- 1&-1 &1\\ \hline -1 & & &\\ \hline -1 & & &\\ \hline \end{array} and \begin{array}{|c|c|c|c|} \hline 1& -1 & 1 &-1 \\ \hline 1 & 1& -1&-1\\ \hline -1 & & &\\ \hline -1 & & &\\ \hline \end{array}.
also are to be determined by respectvely \begin{array}{|c|c|c|c|} \hline 1& -1 & 1 &-1 \\ \hline 1 &- 1&-1 &1\\ \hline -1 & 1 & &\\ \hline -1 & 1 & &\\ \hline \end{array} and \begin{array}{|c|c|c|c|} \hline 1& -1 & 1 &-1 \\ \hline 1 & 1& -1&-1\\ \hline -1 & & &1\\ \hline -1 & & &1\\ \hline \end{array}. Then you need to choose the polace where you put the number 1 on the third and this determines the table. This can be done of 2 ways. Then the answer is $ 6 \cdot 3(1 + 2 \cdot 2) = 90 \quad \mbox{ways.} $
-
0Ok, thank you. I will corret this. – 2012-12-05