## BdMO National Secondary 2019#6

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

### BdMO National Secondary 2019#6

Consider a $9\times 9$ array of white squares.Fond the largest $n\in \mathbb N$ with the property:no matter how one choice $n$ out of $81$ white squares and colour in black,there always remains a $1\times 4$ array of white squares(either vertical or horizontal).

Ragib Farhat Hasan
Posts: 62
Joined: Sun Mar 30, 2014 10:40 pm

### Re: BdMO National Secondary 2019#6

Take one major diagonal and color the squares in black.
Take the other two corners and color them in black.
Take the diagonals consisting of 5 squares each (parallel to the colored major diagonal on either side) and color them in black.

Therefore, total number of colored squares are $9+2+5+5=21$.

It can be seen that under this formation, there is no $1\times4$ array of white squares on the board.

Therefore, the largest value of $n$, where $n\in \mathbb N$, is $20$.

Now, this is a constructed solution. What about general proof? Well, we can use PHP for that.

Say that we want to cover the board using blocks of the shape of $1\times4$ array.

Now, since $81\div4=20.25$, then there is at least one block which is $1\times5$. Which in turn means that the entire board cannot be covered with twenty $1\times4$ blocks.

Hence, $20$ is the largest value for $n$.