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.
Problem
Source: Iran MO 2nd round 2022 , P4
Tags: combinatorics
13.05.2022 11:16
We'll use induction on $n$. $n=1$ is clear. Assume Amin can color all cells red. Lemma. There exists a column with exactly one black cell. Proof. We'll use induction on $n$. for $n=1$ , lemma holds. Assume WLOG Amin's first move , is to consider the up-most - left-most cell and he colored all cells in the left-most column red(Here we assumed WLOG the left-most - up-most cell is the only black cell in the up-most row). Now since he can color the remaining $(n-1)*(n-1)$ table with black cells in that table(since all other cells in the up-most row are white(except the left-most one) and all in the left-most column are red). So by induction hypothesis , there exists a column with exactly one black cell in the $(n-1)*(n-1)$ table and clearly that column works in the main $n*n$ table too. So we're done. Note that the lemma , implies that Ali has a move. Assume Ali has done a move and give the colored table to Amin . This table has one row red and a column with all cells white , except one which is red.Assume WLOG the red row is the up-most row and the mentioned column is the left-most one. We shall prove that Amin can color the remaining $(n-1)*(n-1)$ table red . Note that Amin could color the first $n*n$ table. Now , in the left-most column there exists only one red cell and the others are white. So Amin couldn't use that column's cell except the up-most one. And clearly he couldn't use the up-most row's cells except the left-most one since that up-most - left-most cell was black. So he should apply his moves on the remaining $(n-1)*(n-1)$ table and the up-most - left-most cell. So by the induction hypothesis Ali can color the remaining $(n-1)*(n-1)$ table and clearly his moves , cover the hole left-most column so the hole table would be red and we're done.
17.11.2024 21:48
Can anyone give me a solution by rotating the board 90 degree?