Problem 12. A table with $m$ rows and $n$ 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.

## Bulgarian Mathematical Competitions 2005
12. We put $m+n-1$ white pieces by $m+n-1$ movies consecutively in the cells $(1,1),(2,1), \ldots,(m, 1),(1,2),(1,3), \ldots,(1, n)$.

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 $m+n-1$ 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 $m+n-1$ 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.

## Bulgarian Mathematical Competitions 2005