বিয়ে

For discussing Olympiad Level Combinatorics problems
User avatar
ahmedittihad
Posts:181
Joined:Mon Mar 28, 2016 6:21 pm
বিয়ে

Unread post by ahmedittihad » Tue Apr 11, 2017 4:21 pm

You are given a $10$*$10$ grid with the property that in every row, exactly three squares are shaded, and in every column, exactly 3 squares are shaded. Prove that you can select 10 if these shaded squares so that each of them are in different rows and columns.
Frankly, my dear, I don't give a damn.

SN.Pushpita
Posts:11
Joined:Thu Aug 10, 2017 1:44 pm

Re: বিয়ে

Unread post by SN.Pushpita » Thu Feb 15, 2018 1:38 pm

Are you proud of your knowledge regarding Hall's Marriage Lemma?:p

samiul_samin
Posts:1007
Joined:Sat Dec 09, 2017 1:32 pm

Re: বিয়ে

Unread post by samiul_samin » Thu Feb 15, 2018 9:04 pm

Partial Solution
Just think it as a $10*10$ Chessboard and the shaded squares are the squares with ROOK (It makes the problem more realistic!) Now ,we have to place $10×3=30$ ROOKS in the board and make sure that if we take any 10 ROOKS,we wiil get no ROOKS which are attacked by each other.
So,if we put the rooks in all the diagonals square we will easily get it!So,we need to put more ROOKS in a row or in a column side by side to get the worst case.
In $9×9$ Chessboard we can place highest 27 ROOKS under this condition.[it can be proved by using PHP].So,if we place the next ROOK at a different row and column,we will get the situation stated above.So, we are done(not really :| :| :| :cry: ).
I don't know how to use Hall's Marriage Lemma and I can't prove this completely. Please,any one help to solve this.

User avatar
ahmedittihad
Posts:181
Joined:Mon Mar 28, 2016 6:21 pm

Re: বিয়ে

Unread post by ahmedittihad » Sat Feb 17, 2018 1:41 am

SN.Pushpita wrote:
Thu Feb 15, 2018 1:38 pm
Are you proud of your knowledge regarding Hall's Marriage Lemma?:p
Yes, yes I am proud of my knowledge of marriage procedures.
Frankly, my dear, I don't give a damn.

SN.Pushpita
Posts:11
Joined:Thu Aug 10, 2017 1:44 pm

Re: বিয়ে

Unread post by SN.Pushpita » Mon Feb 19, 2018 12:45 pm

ahmedittihad wrote:
Sat Feb 17, 2018 1:41 am
SN.Pushpita wrote:
Thu Feb 15, 2018 1:38 pm
Are you proud of your knowledge regarding Hall's Marriage Lemma?:p
Yes, yes I am proud of my knowledge of marriage procedures.
Dude, it isn't mathoscope :D

User avatar
ahmedittihad
Posts:181
Joined:Mon Mar 28, 2016 6:21 pm

Re: বিয়ে

Unread post by ahmedittihad » Tue Feb 20, 2018 7:13 am

SN.Pushpita wrote:
Mon Feb 19, 2018 12:45 pm
Dude, it isn't mathoscope :D
But I'm still the same guy.
Frankly, my dear, I don't give a damn.

samiul_samin
Posts:1007
Joined:Sat Dec 09, 2017 1:32 pm

Re: বিয়ে

Unread post by samiul_samin » Sun Mar 10, 2019 3:49 pm

SN.Pushpita wrote:
Mon Feb 19, 2018 12:45 pm


Dude, it isn't mathoscope :D
What is mathoscope?

Post Reply