5

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.

Herman Tulleken
  • 3,608
  • 2
    This is a consequence of the more general result found in the answers to https://math.stackexchange.com/questions/2482236/number-of-all-squares-placed-side-by-side-in-a-rectangle – David K Dec 23 '17 at 06:11

1 Answers1

10

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.

JimmyK4542
  • 54,331