Rectangle exclusion by monominoes

70 Views Asked by At

Here is the question: Given an $m\times n$ chessboard, what is the least number of monominoes can be placed on it so that the rectangle of shape $a\times b$ (or $b\times a$) can no longer be fitted onto the board? Here $a,b,m,n$ are positive integers and we assume that $a\leq m,b\leq n$.

Since the question seems quite classical, I wonder if it has already been (at least partially) solved somewhere, but unfortunately I can't find any reference.

Up to now, the following cases are known to me:

  1. Either $a$ or $b$ is equal to $1$;
  2. $a=b$.

It is likely that things would be easier if both $m$ and $n$ are multiples of $ab$, but I'm not sure to which extent does this assumption simplify the problem.

Any advice or hint is appreciated.

1

There are 1 best solutions below

0
On

A key search term is "blocking set." Here is one paper whose references and citations might lead you to useful literature.

Cano, J., García, A., Hurtado, F., Sakai, T., Tejel, J., & Urrutia, J. (2015). Blocking the $k$-holes of point sets in the plane. Graphs and combinatorics, 31(5), 1271-1287.