Problem:
A table with rows and columns is given. At any move one chooses some empty cells such that any two of them lie in different rows and columns, puts a white piece in any of these cells and then puts a black piece in the cells whose lines and columns contain white pieces. The game is over if it is not possible to make a move. Find the maximum possible number of the white pieces that can be put on the table.
Solution
Solution:
We put white pieces by moves consecutively in the cells .
We shall call a closed chain of cells such that at least two numbers of rows and columns change alternatively a zig-zag cycle.
Note that there is at least one black piece in the cells of a zig-zag cycle. Indeed, assume the contrary and consider the last white piece. Its neighbors (in the zig-zag cycle) are white pieces that have been put before it. Then the last piece must be black, a contradiction.
Assume now that the game is over and there are more than pieces. Remove a row or a column with at most one white piece, repeat the same operation, etc. Since such a removing can be done at most times, any row and column in the new table will contain at least two white pieces. This new table, and hence the given table, has a zig-zag cycle, a contradiction to the proved above.