In a table some of the cells are black and the rest of them are white. Alice and Bob each have a copy of this table and trying to make the whole table red in the following ways:
If Alice finds a cell that is the only black cell in its row, She changes the color of all the cells in its column to red. If Bob finds a cell that is the only black cell in its column, He changes the color of all the cells in its row to red.
Prove that Alice can make the whole table red if and only if Bob can.
Solution
If a cell is the only black cell in its row and Alice uses it to make its column red we call that cell special. Because after using a special set every cell in its column becomes red, now two special cells are in a column. On the other hand, no two special cells are in a row. Therefore, if Alice can make the table red, the special cells form a transversal.
Note that swapping the rows with each other or columns with each other does not affect the ability of Alice and Bob to make the table red. So we can assume that the first special cell that Alice choose is , the second is , and so on. This means that all the cells above the diagonal were white at the beginning. Now Bob can start from , then and so on until the whole table becomes red. Conversely, by symmetry, if Bob can make the table red Alice can also make the table red.
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.