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

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