n+1 rows and columns
- asif e elahi
- Posts:185
- Joined:Mon Aug 05, 2013 12:36 pm
- Location:Sylhet,Bangladesh
Some cells of a $n\times n$ board are coloured black so that any set of $n$ cells, no $2$ are on the same line or column contains at least one black cell. Prove there exists $i$ rows and $j$ columns with $i+j\geq n+1$,all of whose intersections are black.
Re: n+1 rows and columns
Please explain.asif e elahi wrote:... so that any set of $n$ cells, no $2$ are on the same line or column contains at least one black cell.
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
- asif e elahi
- Posts:185
- Joined:Mon Aug 05, 2013 12:36 pm
- Location:Sylhet,Bangladesh
Re: n+1 rows and columns
If a set of $n$ cells have the property that no $2$ cells are on the same row or column,then the set contains at least one black cell.
- Samiun Fateeha Ira
- Posts:23
- Joined:Sat Aug 24, 2013 7:08 pm
- Location:Dhaka, Bangladesh
Re: n+1 rows and columns
We want to colour the least possible cells in black so that all the $n!$ sets may have at least one black cell. And this is possible by colouring all the cells of a row/column black.
Now each cell can be described as the intersection of a row and a column. In the above case where we wanted to colour the least cells, we had coloured all the intersection of $n$ rows & $1$ column or $n$ columns & $1$ row.
So there exist at least $n+1$ rows & columns all of whose intersections are black.
Now each cell can be described as the intersection of a row and a column. In the above case where we wanted to colour the least cells, we had coloured all the intersection of $n$ rows & $1$ column or $n$ columns & $1$ row.
So there exist at least $n+1$ rows & columns all of whose intersections are black.
- asif e elahi
- Posts:185
- Joined:Mon Aug 05, 2013 12:36 pm
- Location:Sylhet,Bangladesh
Re: n+1 rows and columns
WHY??Samiun Fateeha Ira wrote:We want to colour the least possible cells in black so that all the $n!$ sets may have at least one black cell.
- Samiun Fateeha Ira
- Posts:23
- Joined:Sat Aug 24, 2013 7:08 pm
- Location:Dhaka, Bangladesh
Re: n+1 rows and columns
Actually I wanted to count the number of black cells we need "at least" & present them as the intersections so that i can prove there "always" exists $i$ rows & $j$ columns with given condition.
Re: n+1 rows and columns
Call the black coloring method described in the problem a good coloring, and call the set of cells described in the problem (no $2$ on same row/column) a good set.
Lemma: A good coloring is possible iff at least one row/column is completely black.
Proof: Suppose not, i.e. no row or column of the board is completely black. We consider the worst case, where we've colored exactly $n-1$ cells of each row black, such that no column is completely black. Clearly the other $n$ cells form a good set all of whose cells are white, a contradiction. Conversely, any coloring with at least one row/column completely black ensures the property that at least one cell of a good set is black, since a good set has cells on every row/column. $\square$
The rest is straight.
Lemma: A good coloring is possible iff at least one row/column is completely black.
Proof: Suppose not, i.e. no row or column of the board is completely black. We consider the worst case, where we've colored exactly $n-1$ cells of each row black, such that no column is completely black. Clearly the other $n$ cells form a good set all of whose cells are white, a contradiction. Conversely, any coloring with at least one row/column completely black ensures the property that at least one cell of a good set is black, since a good set has cells on every row/column. $\square$
The rest is straight.
- What is the value of the contour integral around Western Europe?
- Zero.
- Why?
- Because all the poles are in Eastern Europe.
Revive the IMO marathon.
- Zero.
- Why?
- Because all the poles are in Eastern Europe.
Revive the IMO marathon.
- asif e elahi
- Posts:185
- Joined:Mon Aug 05, 2013 12:36 pm
- Location:Sylhet,Bangladesh
Re: n+1 rows and columns
I think you misunderstood the problem.You have to prove that there exist $i$ rows and $j$ columns with $i+j\geq n+1$ for which ALL of whose intersections are black.Samiun Fateeha Ira wrote:Actually I wanted to count the number of black cells we need "at least" & present them as the intersections so that i can prove there "always" exists $i$ rows & $j$ columns with given condition.
And to nirjhor,your lemma is wrong.Colour the upper left $3\times 3$ black of a $5\times 5$ board.This is a good coloring .
Re: n+1 rows and columns
I considered the problem to be much trivial.
Call the cell on row $i$ and column $j$ by $(i,j)$. Consider a visual map (or relation) $F$ of two sets $\mathcal A,\mathcal B$ each containing the integers from $1$ to $n$. We connect two integers $a\in\mathcal A$ and $b\in \mathcal B$ by a segment iff the cell $(a,b)$ is white (not black).
Now the hypothesis, in language of our mapping, is that we can never achieve an injective map $f:\mathcal A\mapsto \mathcal B$ by removing some segments from the original map. So by the contrapositive of Hall's theorem, there exists $\mathcal S\subseteq \mathcal A$ so that $|\mathcal S| > |F(\mathcal S)|.~~ (*)$
Now we can take $i=|\mathcal S|$ and $j=|\mathcal B|-|F(\mathcal S)|$. As these elements are not connected, their intersections must be black, and we have $i+j=|\mathcal S|+|\mathcal B|-|F(\mathcal S)|>|\mathcal B|=n$ by $(*).~\square$
Illustration of the mapping for a case of $n=3$ is shown in the image.
Call the cell on row $i$ and column $j$ by $(i,j)$. Consider a visual map (or relation) $F$ of two sets $\mathcal A,\mathcal B$ each containing the integers from $1$ to $n$. We connect two integers $a\in\mathcal A$ and $b\in \mathcal B$ by a segment iff the cell $(a,b)$ is white (not black).
Now the hypothesis, in language of our mapping, is that we can never achieve an injective map $f:\mathcal A\mapsto \mathcal B$ by removing some segments from the original map. So by the contrapositive of Hall's theorem, there exists $\mathcal S\subseteq \mathcal A$ so that $|\mathcal S| > |F(\mathcal S)|.~~ (*)$
Now we can take $i=|\mathcal S|$ and $j=|\mathcal B|-|F(\mathcal S)|$. As these elements are not connected, their intersections must be black, and we have $i+j=|\mathcal S|+|\mathcal B|-|F(\mathcal S)|>|\mathcal B|=n$ by $(*).~\square$
Illustration of the mapping for a case of $n=3$ is shown in the image.
- What is the value of the contour integral around Western Europe?
- Zero.
- Why?
- Because all the poles are in Eastern Europe.
Revive the IMO marathon.
- Zero.
- Why?
- Because all the poles are in Eastern Europe.
Revive the IMO marathon.
- asif e elahi
- Posts:185
- Joined:Mon Aug 05, 2013 12:36 pm
- Location:Sylhet,Bangladesh
Re: n+1 rows and columns
Please,explain this part.Nirjhor wrote:I
Now the hypothesis, in language of our mapping, is that we can never achieve an injective map $f:\mathcal A\mapsto \mathcal B$ by removing some segments from the original map.