Page 1 of 1

বিয়ে

Posted: Tue Apr 11, 2017 4:21 pm
by ahmedittihad
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.

Re: বিয়ে

Posted: Thu Feb 15, 2018 1:38 pm
by SN.Pushpita
Are you proud of your knowledge regarding Hall's Marriage Lemma?:p

Re: বিয়ে

Posted: Thu Feb 15, 2018 9:04 pm
by samiul_samin
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.

Re: বিয়ে

Posted: Sat Feb 17, 2018 1:41 am
by ahmedittihad
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.

Re: বিয়ে

Posted: Mon Feb 19, 2018 12:45 pm
by SN.Pushpita
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

Re: বিয়ে

Posted: Tue Feb 20, 2018 7:13 am
by ahmedittihad
SN.Pushpita wrote:
Mon Feb 19, 2018 12:45 pm
Dude, it isn't mathoscope :D
But I'm still the same guy.

Re: বিয়ে

Posted: Sun Mar 10, 2019 3:49 pm
by samiul_samin
SN.Pushpita wrote:
Mon Feb 19, 2018 12:45 pm


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