Page 1 of 1

BdMO National Secondary 2019#6

Posted: Thu Mar 14, 2019 10:59 am
by samiul_samin
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).

Re: BdMO National Secondary 2019#6

Posted: Mon Sep 23, 2019 1:53 pm
by Ragib Farhat Hasan
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$.