বিয়ে

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

[SN.Pushpita]

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

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

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.

[ahmedittihad]

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

Yes, yes I am proud of my knowledge of marriage procedures.

[SN.Pushpita]

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

[ahmedittihad]

Dude, it isn't mathoscope

But I'm still the same guy.

[samiul_samin]

Dude, it isn't mathoscope

What is mathoscope?