Problem:
A grid with rows and columns has each cell colored either white or black in such a way as to satisfy the following two conditions:
a. each row contains as many white cells as black cells;
b. if a row meets a column in a black cell, then that row and that column have the same number of black cells; likewise, if a row intersects a column in a white cell, then that row and that column have the same number of white cells.
Find all possible pairs for which such a coloring can exist.
Solution:
From the first condition we have that the number of columns is necessarily even. In general, the rows, of length , have white cells and black cells. For every row there will be at least one column that intersects it in a white cell and at least one that intersects it in a black cell. Let us consider the one that intersects it in a white cell. It has exactly white cells. Hence one possible solution is given by the pairs , in which half of the columns are entirely white and half entirely black. A possible realization of such a solution is a board in which the first columns are white and the following are black.
If instead they are not monochromatic, this means that there exists at least one black cell, but then in that cell the column intersects a row with black cells, so the column too must have black cells in addition to the white cells. The second family of possible solutions is therefore given by the pairs . A possible realization in this case is a board colored in the canonical way.