Consider a $n\times n$ checkerboard. Each cell can be colored white or black. $n$ is even. How many configurations are there so that each row and each column have an odd number of white cells?


Fill the $(n-1)\times(n-1)$ board arbitrary with the black and white.now you should just set the parity with the last row and column. the last cell($a_{n,n}$) will be same color for both last row and last column because of the parity of the $n-1$ first row is equal to parity of the $n-1$ first column and that is because your board is $n\times n$ and $n\equiv n \bmod{2}$ and if rows parity differ from column parity it is contradiction.

Finally the total answer is $2^{(n-1)\times (n-1)} $.

Update I asked generalized version of this question before.


Coloring the entire board with the parity constraint is equivalent to arbitrary coloring a sub-board with one row and one column removed. The first restricts to the second and can be uniquely reconstructed from it given the parity condition.

You can predict without going through the complete analysis that the number of solutions is a power of 2. This is because the problem can be phrased as a system of linear equations mod 2 and the number of colorings will be $2^t$ where $t$ is the dimension of the solution space. For example, the way I found the answer in the first paragraph is to think in terms of the linear equations and afterward recognize that they can be removed.

The $(m-1)(n-1)$ as dimension of solution space occurs constantly in statistics as the number of degrees of freedom in contingency tables. In that generality there is a $m$ by $n$ matrix with specified row and column sums and, exactly as in the case of the checkerboard, one can uniquely fill the whole table from any filling of the subtable with one row and one column removed.

  • $\begingroup$ The element at the intersection of the removed row and column might be impossible to color in this case, I think. $\endgroup$ – user16367 Apr 11 '12 at 20:44
  • $\begingroup$ @user16367, it is always possible, because the parity at the intersection is equal to the sum of the the whole (n-1)x(n-1) sub-board. The "row" and "column" constraints on that square turn out to be identical so there is no additional condition to satisfy. But as you point out, one has to check this as part of the statement that a coloring of the sub-board extends uniquely to a coloring of the whole board of size n. $\endgroup$ – zyx Apr 11 '12 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.