Or more generally, is it true that to tile a $(2k+1) \times (2k + 1)$ square with square tetrominoes and monominoes, we need at least $4k + 1$ monominoes?

Each row (having an odd number of cells) need at least one monomino in each row, and similarly we need one in each column. So we need at least $2k + 1$. At least some monominoes can be placed so that they are the only ones in their row and columns (this would be necessary for obtaining that lower bound), as is shown in the tiling below. However, it seems that we cannot do better than $4k + 1$, but I also cannot prove this.

Tiling of a odd square with square tetrominoes and monominoes.


Let $(m,n)$ denote the square in the $m$-th row and $n$-th column where $1 \le m \le 2k+1$ and $1 \le n \le 2k+1$. Consider the set subset of squares $$S = \{(m,n) | m \ \text{and} \ n \ \text{are both even}\}.$$

Each blue tile covers exactly one of the squares in $S$. Thus, there are at most $|S| = k^2$ blue tiles, and thus, at least $(2k+1)^2-4k^2 = 4k+1$ pink tiles.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.