BdMO National Secondary 2019#6

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

 Posts: 16
 Joined: Mon Dec 21, 2020 9:26 pm
Re: BdMO National Secondary 2019#6
The ans is $19$Ragib Farhat Hasan wrote: ↑Mon Sep 23, 2019 1:53 pmTake 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$.
Firstly note that the middle column and row must contain at least $4$ black squares to ensure there is no $4$ by $1$ array of white squares.
Now,note that the middle row and column divides the grid into $4$ squares of $4$ by $4$ and if any one of these squares contain less than $4$ black squares then there will be always an array of $4$ by $4$ white squares.
We have already taken at least $4$ white squares for the middle row and column.If $19 \geq n$ then there must be at least 1 $4$ by $4$ square which contains at most $3$ black squares.SO $n$ cannot be less than $20$.
And to see that for $n=20$ there must be a way to block $4$ by $4$ array of white squares,just follow the algorithm $\Longrightarrow$ block white array of squares in middle row and column and then place black squares in such a way that the divided $4$ $4$ by $4$ squares contain $4$ black squares.

 Posts: 16
 Joined: Mon Dec 21, 2020 9:26 pm
Re: BdMO National Secondary 2019#6
The ans is $19$
Call a $k\times k$ array of squares "$S(k)(k)$"
Consider the middle row and the middle column of $S(9)(9)$ of white squares..Note that they must contain at least $4$ black squares to block a $S(4)(1)$ of white squares.Also note that the middle row and column divides the $S(9)(9)$ into $4$ different $S(4)(4)$ of white squares
For $19\geq n$ There must be at most $15$ black squares for the $4$ different $S(4)(4)$ and at least $1$ $S(4)(4)$ must contain at most $3$ black squares and thus there will always be a $S(4)(1)$ of white squares.
Now,we will show that $19$ is indeed the max value for which this happens.
Follow the algorithm,
For $n>19$, at first block $S(4)(1)$ of white squares in the middle row and column with exactly $4$ black squares (This is possible).Then we still have at least $16$ black squares.Place the black squares in the $4$ $S(4)(4)$ in such a way that each $S(4)(4)$ contains at least $4$ black squares.It is easy to see that we can block $S(4)(1)$ of white squares in a $S(4)(4)$ of white squares with $4$ black squares.
(A.W.D)
Call a $k\times k$ array of squares "$S(k)(k)$"
Consider the middle row and the middle column of $S(9)(9)$ of white squares..Note that they must contain at least $4$ black squares to block a $S(4)(1)$ of white squares.Also note that the middle row and column divides the $S(9)(9)$ into $4$ different $S(4)(4)$ of white squares
For $19\geq n$ There must be at most $15$ black squares for the $4$ different $S(4)(4)$ and at least $1$ $S(4)(4)$ must contain at most $3$ black squares and thus there will always be a $S(4)(1)$ of white squares.
Now,we will show that $19$ is indeed the max value for which this happens.
Follow the algorithm,
For $n>19$, at first block $S(4)(1)$ of white squares in the middle row and column with exactly $4$ black squares (This is possible).Then we still have at least $16$ black squares.Place the black squares in the $4$ $S(4)(4)$ in such a way that each $S(4)(4)$ contains at least $4$ black squares.It is easy to see that we can block $S(4)(1)$ of white squares in a $S(4)(4)$ of white squares with $4$ black squares.
(A.W.D)

 Posts: 16
 Joined: Mon Dec 21, 2020 9:26 pm
Re: BdMO National Secondary 2019#6
actually the ans should be 19Ragib Farhat Hasan wrote: ↑Mon Sep 23, 2019 1:53 pmTake 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$.