Monochrome Matrix


একটি $9 \times 9$ সাদা বর্গের বোর্ড আছে। এমন সর্বোচ্চ $n \in \mathbb{N}$ বের কর যাতে যে কোনভাবে $n$ টি বর্গ কালো করে দিলেও সবসময় একটি $1 \times 4$ সাদা বর্গের অংশ থাকে (খাড়া অথবা শোয়ানোভাবে)।



Proof Based Problems  


  1 Upvote                    0 Downvote


Solution

Disclaimer: The solutions we've shared are just one exciting approach, and there are surely many other wonderful methods out there. We’d love to hear your alternative solutions in the community thread below, so let's keep the creativity flowing!

For the sake of contradiction, assume that there is a configuration of $19$ black squares such that there is no place for $1\times4$ white rectangle.

In any $1\times4$ rectangle, there is at least $1$ black cell.

So, in any $1\times8$ rectangle, there is at least $2$ black cells.

Now, in the first leftmost $9\times8$ rectangle, dividing it into $9$ rectangle of size $1x8$, we see that each of them has at least $2$ black cells. So, this $9x8$ area has at least 18 black squares.

There is a $9x1$ area remaining. Taking the top $8$ cells, we see there is also at least $2$ black cells.

So, the board has at least $20$ black cells. Contradiction.


Now, we need to show that there is a configuration of $20$ black cells that resists all $1x4$ white rectangles. So, the answer is $19$.


This is a proof based problem added for learning purposes and does not accept submissions.

You can view the solution by clicking on the solution tab.

Editorial



Need a hint? Checkout the editorial.

View Editorial