1

I'm having trouble fully understanding this introductory combinatorics problem; this is all that's provided, so it's most likely me not fully comprehending the question.

Any help is appreciated.

The problem is this:

Each square of a 1998 by 2002 chess board contains either 0 or 1 such that the total number of squares containing 1 is odd in each row and each column. Prove that the number of white unit squares containing 1 is even.

I have discovered that this is a legitimate question and has been copied out of a book entitled 102 Combinatorial Problems where the problem and solution are clearly stated here.

Thank you and apologies for the ambiguity.

Gauss
  • 395

2 Answers2

2

Firstly, we show that one exists: take $$L_{1,1}=L_{2,2}=\cdots=L_{1998,1998}=L_{1998,1999}=L_{1998,2000}=L_{1998,2001}=L_{1998,2002}=1$$ and $0$s elsewhere. (We can inspect the properties hold.)

Next, observe that toggling the $0$s and $1$s in any $2 \times 2$ submatrix does not alter either the property (a) there's an odd number of $1$s in each row and column, and (b) the number of white-squared $1$s is even.

Finally, we will show that any matrix $M$ (with an odd number of $1$s in each row and column) can be realized from the above construction by a sequence of switches described above.

We use this algorithm:

  • We proceed row-by-row then column-by-column. In the $i$-th row, suppose column $j$ disagrees with the goal matrix $M$. Then we toggle some $2 \times 2$ submatrix that contains cell $(i,j)$ in its top-left corner. (This means we don't affect previous switches.)

We will never reach a situation where $i$ is the $1998$-th row or $j$ is the $2002$-th column, otherwise $M$ would not satisfy the property that there's an odd number of $1$s in each row and column.

So the algorithm terminates and returns $M$.

Rebecca J. Stones
  • 26,845
0

The whole chessboard can be cut into $2 \times 2$ blocks which contain two black and two white squares. Let TL be the number of 1's in all the top-left squares of these blocks, and similarl TR, BL and BR are the number of 1's in all the top-right, bottom-left and bottom-right squares.

Now all the top-left squares and all the top-right squares together make every second row on the chessboard. So they are 999 rows, each with an odd number of 1's. Hence together they contain an odd number of 1's. This number of 1's is TL + TR.

All the top-left squares and all the bottom-left squares together make every second column on the chessboard. So they are 1001 rows, each with an odd number of 1's. Hence together they contain an odd number of 1's. This number of 1's is TL + BL.

Since TL + TR and TL + BL are both odd, their sum must be even. So TR + 2TL + BL is even. Since 2TL is even, this means that TR + BL is even.

Now the top-right and bottom-left squares are either both white or both black in each block. In fact, if they are both black/white in one block they will both be black/white in all blocks and will together constitute all the black/white squares.

Since TR+BL and TL + BR are both even, we have that the number of black squares with a 1, and also the number of white squares with a 1 are both even.

DavidButlerUofA
  • 3,364