BdMO National Secondary 2019#6

Discussion on Bangladesh Mathematical Olympiad (BdMO) National
samiul_samin
Posts:1007
Joined:Sat Dec 09, 2017 1:32 pm
BdMO National Secondary 2019#6

Unread post by samiul_samin » Thu Mar 14, 2019 10:59 am

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

Unread post by Ragib Farhat Hasan » Mon Sep 23, 2019 1:53 pm

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

Nayer_Sharar
Posts:16
Joined:Mon Dec 21, 2020 9:26 pm

Re: BdMO National Secondary 2019#6

Unread post by Nayer_Sharar » Sun Dec 27, 2020 11:34 am

Ragib Farhat Hasan wrote:
Mon Sep 23, 2019 1:53 pm
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$.
The ans is $19$
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.

Nayer_Sharar
Posts:16
Joined:Mon Dec 21, 2020 9:26 pm

Re: BdMO National Secondary 2019#6

Unread post by Nayer_Sharar » Sun Dec 27, 2020 1:11 pm

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)

Nayer_Sharar
Posts:16
Joined:Mon Dec 21, 2020 9:26 pm

Re: BdMO National Secondary 2019#6

Unread post by Nayer_Sharar » Mon Dec 28, 2020 7:22 pm

Ragib Farhat Hasan wrote:
Mon Sep 23, 2019 1:53 pm
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$.
actually the ans should be 19

Post Reply