Problem

Source: Iran MO 2nd round 2022 , P4

Tags: combinatorics



There is an $n*n$ table with some unit cells colored black and the others are white. In each step , Amin takes a $row$ with exactly one black cell in it , and color all cells in that black cell's $column$ red. While Ali , takes a $column$ with exactly one black cell in it , and color all cells in that black cell's $row$ red. Prove that Amin can color all the cells red , iff Ali can do so.