Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
The element at the intersection of the removed row and column might be impossible to color in this case, I think. –  user16367 Apr 11 '12 at 20:44
    
@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. –  zyx Apr 11 '12 at 20:49
    
Thank you. Wish I could accept 2 answers :) –  user16367 Apr 11 '12 at 22:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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