Re: n+1 rows and columns
Posted: Tue Jan 20, 2015 2:02 pm
If there existed an injective map, subset of the original map, that would mean there are $n$ cells none of which lies on same row/column, are all white. For example, consider the following.
Here we have an injective map in the left, showing the cells $(1, 1), (2,3), (3,2)$ are all white (that's why they're connected), contradicting the hypothesis that at least one cell among them is black. So no injection exists.
Here we have an injective map in the left, showing the cells $(1, 1), (2,3), (3,2)$ are all white (that's why they're connected), contradicting the hypothesis that at least one cell among them is black. So no injection exists.