Let's say I want to fill an $n \times n$ board with tiles that have the shape of a $3 \times 3$ square with the $4$ corners cut out (the tile makes a plus sign) such that the sides of each tile are parallel to the board. What makes this problem different from other tiling problems is that these tiles can be overlapped. Furthermore, it is fine if some parts of the outmost tiles are sticking out of the edges of the $nxn$ board because then, we can just cut out whatever parts are extra.

The question is to prove that the upper bound for the number of tiles needed to tile the board in such a manner is $\frac{(n+2)^2}{5}.$

I don't quite see how to prove such a thing. For example, I don't think that this bound is tight. When I tried smaller values of $n$, I got $1$ for $n=1$, $2$ for $n=2$, $3$ for $n=3$, $4$ for $n=4$, $7$ for $n=5$, $11$ for $n=6$, etc.

I haven't actually gotten a scenario where I met this upper bound. Does anyone have any ideas?

  • 1
    $\begingroup$ Didn't you mean to say a $3\times3$ square with the corners cut out? There are $5$ squares in a tile, right? $\endgroup$ – saulspatz Feb 19 at 5:12
  • $\begingroup$ @saulspatz yeah, sorry. you are absolutely right - I just fixed the error. $\endgroup$ – user884573 Feb 19 at 5:13
  • 1
    $\begingroup$ MathJax hint: use \times to get a multiplication sign, so 3 \times 3 gives $3 \times 3$. For basic multiplication, we prefer \cdot to get a centered dot, but for your tiles \times is the correct usage. $\endgroup$ – Ross Millikan Feb 19 at 5:14
  • $\begingroup$ The fact that for large $n$ you use not much more than $\frac {n^2}5$ tiles says you need to use all the squares of most of the tiles. That should lead you to look for a way to tile the plane with these tiles. Once you have that, you have to show that the excess is not too large for the formula you have. $\endgroup$ – Ross Millikan Feb 19 at 5:22
  • $\begingroup$ If the tiles can overlap, can't you place an infinite number of them in same spot? $\endgroup$ – Some Guy Feb 19 at 5:57