You can view the solution by clicking on the solution tab.
Editorial
Need a hint? Checkout the editorial.
View Editorial
একটি $9 \times 9$ সাদা বর্গের বোর্ড আছে। এমন সর্বোচ্চ $n \in \mathbb{N}$ বের কর যাতে যে কোনভাবে $n$ টি বর্গ কালো করে দিলেও সবসময় একটি $1 \times 4$ সাদা বর্গের অংশ থাকে (খাড়া অথবা শোয়ানোভাবে)।
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$.