Maths Olympiad Prep

Library / /102 of 104

Combinatorics Difficulty 7.2 National Olympiad, round 2 Prove it Bulgaria

Problem:
A table with mm rows and nn 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 m+n1m+n-1 white pieces by m+n1m+n-1 moves consecutively in the cells (1,1),(2,1),,(m,1),(1,2),(1,3),,(1,n)(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+n1m+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+n1m+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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.