You say: (iii) marking with 0 all the UNMARKED squares which lie on the same line and column with a square marked with the number 1 (even if the square has been MARKED with 1 on another move). I see a contradiction between the two adjectives Can you explain it to me one more time?

I see no contradiction. You did not read carefully the problem's text (as some of the contestants did!). I shall give you an example: if at your first move you choose two different 1s, say the first two on the main diagonal (up-left corner, + one below right and down), then you mark with 0 the other 2 squares with which these 1s form a rectangle. then in your second move, if you choose only one unmarked square, say the one in the right-down corner, you have to mark with 0, the other two corners of the rectangle, because those squares lie on the intersection of the colum on which the last 1 chosen lies, and one of the first two 1s lies. So you must color in your second move exactly 4 squares (in this beginning of a game that I have chosen).

You mea what is the greter number of ones one can put in a m*n matrix s.t. for any 2 ones, there is no other 1 lying in a row with the first and in a column with another? It looks like some problem from USAMO

iura wrote: You mea what is the greter number of ones one can put in a m*n matrix s.t. for any 2 ones, there is no other 1 lying in a row with the first and in a column with another? It looks like some problem from USAMO yes I belive you can re-phrase the problem in this manner.

If the problem is so, I know the solution. Consider the sides of rectangle and consider the number of unit squares on border the 1's project to. If we can't take two squares lying in distinct columns and rows then all 1's lie in a row or column so we get at most max{m,n} 1's. If we can, this squares project into 4 unit squares. The next squares add at least 2 new squares on the border ( otherwise this 1 is in a row and column with anether 1's contradiction). As there are 2(m+n) squares in the border, we get at most m+n-2 squares. This bound is easily achieved so desired number is m+n-2

oh my god! this problem has been so confusing!!! let me explain what i've understood of it: at first the board has all the fields unmarked. step 1 choose some UNMARKED fields, any two not on the same line/column; step 2 consider ALL fields containing "1" and for any UNMARKED field that lies at intersection of a line that contains a "1" AND a column that contains a "1" mark that field with "0"... so the remark Quote: even if the square has been marked with 1 on another move simply specifies that we consider ALL the "1"'s... recent and old Iura, if you understand what i say you see that now you CAN have 3 fields that are verices of a right triangle... here are a series of moves for 2x2 put "1" in (1,1) ... no "0"'s put "1" in (2,1) ... no "0"'s (is it obvious?) put "1" in (1,2) ... field (2,2) is on the same line with (2,1) and on the same column with (1,2) so mark it with 0... that's the end.

Then I still don't understand the problem! What squares are MARKED?

Now I think MARKED squares are those in which there is written a 0 or 1. Then my answer is m+n-1. The proof is similar to my previous: Take projections on sides. First square projects on 4. Next squares add at least 2. So we get most m+n-1 which is achievable (Kappa's example for 2*2)

Yup... that's right! i forgot to mention that m+n-1 can be reached, so i got 6/7