n+1 rows and columns

For discussing Olympiad Level Combinatorics problems
User avatar
asif e elahi
Posts:185
Joined:Mon Aug 05, 2013 12:36 pm
Location:Sylhet,Bangladesh
n+1 rows and columns

Unread post by asif e elahi » Sun Jan 04, 2015 7:10 pm

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.

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: n+1 rows and columns

Unread post by *Mahi* » Mon Jan 05, 2015 11:32 pm

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 explain.
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

User avatar
asif e elahi
Posts:185
Joined:Mon Aug 05, 2013 12:36 pm
Location:Sylhet,Bangladesh

Re: n+1 rows and columns

Unread post by asif e elahi » Tue Jan 06, 2015 12:32 pm

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.

User avatar
Samiun Fateeha Ira
Posts:23
Joined:Sat Aug 24, 2013 7:08 pm
Location:Dhaka, Bangladesh

Re: n+1 rows and columns

Unread post by Samiun Fateeha Ira » Sun Jan 11, 2015 11:08 pm

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. :?

User avatar
asif e elahi
Posts:185
Joined:Mon Aug 05, 2013 12:36 pm
Location:Sylhet,Bangladesh

Re: n+1 rows and columns

Unread post by asif e elahi » Tue Jan 13, 2015 12:22 am

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.
WHY??

User avatar
Samiun Fateeha Ira
Posts:23
Joined:Sat Aug 24, 2013 7:08 pm
Location:Dhaka, Bangladesh

Re: n+1 rows and columns

Unread post by Samiun Fateeha Ira » Tue Jan 13, 2015 10:50 pm

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.

Nirjhor
Posts:136
Joined:Thu Aug 29, 2013 11:21 pm
Location:Varies.

Re: n+1 rows and columns

Unread post by Nirjhor » Wed Jan 14, 2015 2:44 am

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.
- 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.

User avatar
asif e elahi
Posts:185
Joined:Mon Aug 05, 2013 12:36 pm
Location:Sylhet,Bangladesh

Re: n+1 rows and columns

Unread post by asif e elahi » Thu Jan 15, 2015 4:56 pm

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.
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.

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 .

Nirjhor
Posts:136
Joined:Thu Aug 29, 2013 11:21 pm
Location:Varies.

Re: n+1 rows and columns

Unread post by Nirjhor » Tue Jan 20, 2015 2:31 am

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.

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.

User avatar
asif e elahi
Posts:185
Joined:Mon Aug 05, 2013 12:36 pm
Location:Sylhet,Bangladesh

Re: n+1 rows and columns

Unread post by asif e elahi » Tue Jan 20, 2015 1:50 pm

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.
Please,explain this part.

Post Reply