Ivan has a $m \times n$ board, and he color some squares black, so that no three black squares form a L-triomino up to rotations and reflections. What is the maximal number of black squares that Ivan can color? Proposed by Ivan Chan Kai Chin
Problem
Source: Own. Malaysian SST 2023 P1
Tags: combinatorics
31.08.2023 16:09
Answer:$2(\lceil \frac{m}{2} \rceil.\lceil \frac{n}{2} \rceil-a)$ where $mn \equiv a (mod 2)$ and $a=0,1.$
There are at most $2$ black squares in a $2x2$. $i)$ If $m,n$ are even, we can divide the board into $2x2$ squares. So there are at most $\boxed{\frac{mn}{2}}$ black squares. $ii)$ If one of $m,n$ is even, one of $m,n$ is odd. $WLOG,m$ is even, $n$ is odd and there are $m$ columns, $n$ rows. We can divide the board into $2x2$ squares and the last row. There are at most $\frac{m(n-1)}{2}+m$ black squares which is equal to $\boxed{\frac{m(n+1)}{2}}$. $iii)$ If both $m,n$ are odd. There are at most $6$ black squares on a $3x3$ board.
We can divide the board into $3x3$ at left lower part, $3x(m-3)$ and $3x(n-3)$ at left higher part and right lower part, $(m-3)(n-3)$ at right higher part. We know that $m-3$ and $n-3$ are even. Then there are at most \[6+2(n-3)+2(m-3)+\frac{(m-3)(n-3)}{2}=\boxed{\frac{(m+1)(n+1)}{2}-2}\]black squares.
05.09.2023 17:54
A first observation is that in a $2 \times 2$ board, Ivan can color at most $2$ squares. Now we have the following cases based on the parity of $m$ and $n$: 1st case: $m,n$ are even ($m=2a, n=2b$) In this case we divide the board into $ab$ $2 \times 2$ squares and from the above observation we can color at most $2ab$ squares. This value is achievable by coloring fully the columns $2,4,...n$, hence it is indeed the maximum. 2nd case: $m$ is even, $n$ is odd ($m=2a, n=2b+1)$. Then we divide the board into $2a \times 2b$ and $2a \times 1$ and from case 1 we can color at most $2ab+2a=2a(b+1)$ squares. This value is achievable by coloring fully the columns $1,3,...n$, hence it is indeed the maximum. 3rd case: $m$ is odd, $n$ is even $m=2a+1,n=2b$ Following the same procedure as the 2nd case, the maximum in this case is $2b(a+1)$ 4th case: $m,n$ are odd $(m=2a+1, n=2b+1)$ Let WLOG $m\geq n $. I will prove that the maximum is $(b+1)(2a+1)$. This value is achievable by coloring the columns $1,3...n$. Now, I will prove that Ivan cannot color more than that. If $m=1$ it is obvious, so suppose that $m>1$. I will prove the following claim, which proves what we want: Claim: Let $m=2a+1>1$ be a positive integer. Then for all $n=2b+1 \leq m$ we can color at most $(b+1)(2a+1)$. Proof: With induction on $n$. For $n=1$ it is obvious. Suppose that it holds for all odd $k<n=2b+1$ and I will prove it for $n=2b+1$, where $n \leq m$. I divide the $m \times n$ board into $m \times (n-2)$ and $m \times 2$ (the $m \times 2$ board is in the columns $1,2$). If in the $m \times 2$ board we have $ \leq m$ colored squares, applying the inductive ypothesis we can color at most $b(2a+1)+m=(b+1)(2a+1)$. Also, from case 2, we cannot color more than $m+1$. Hence it remains to check the cases, in which we have exactly $m+1$. Then (using that in a $2 \times 2$ board, Ivan can color at most $2$ squares), Ivan must color fully the rows $1,3,...,m$ of the $m \times 2$ board. If the 3rd column had more than $a+1$ colored squares then there would exist two consecutive colored squares, and therefore an $L$ triomino would occur with these 2 squares and a square of the $m \times 2$ board (which neighbors to one of them). Hence, it can have at most $a+1$ colored squares. Finally, the remaining $m \times (n-3)$ board can have (using case 3, as $n-3$ is even) at most $(a+1)(n-3)$ colored squares. So totally the board can have at most : $ (m+1)+ (a+1) + (n-3)(a+1)$ colored squares, which is trivially $ \leq (b+1)(2a+1)$ (it is equivalent to $ a \geq b$). Hence, the induction is completed and the problem is solved.