# Tiling of squares

Motivation: This question is motivated by my previous question . In that question, my statment of the uniqueness requirement is not interesting since it leads to easily computable function. I am interested in constructing uncomputable function from a simple combainatorial problem.

We want to tile $m\times m$-square using two types of tiles: $1 \times 1$-square tile and $2 \times 2$-square tile without overlapping. We require packing the maximum number of $2 \times 2$-squares while posiblliy leaving some of the $m \times m$-squares uncovered?

Let us define a function $f(n)$ that gives the size of largest tillable square using $n$ $1\times 1$-squares and maximum number of $2 \times 2$-squares.

Is this function computable? Is it computable if we use Trominos instead of $2 \times 2$-squares?

-
What are the values of $f(n)$ for $n=4k,\; k\geq 0$? (i.e. if you can arrange the 1x1 squares like a set of 2x2 squares, $f(n)$ is infinite?) –  Vor Feb 11 '13 at 18:39

This function is (still) computable, by a subset of the reasoning in the previous question: No squares are tileable using $n=4k+2$ or $4k+3\ 1\times 1$ tiles; arbitrarily large squares are tileable using $n=4k\ 1\times 1$ tiles, and using $n=4k+1\ 1\times 1$ tiles and an arbitrary number of $2\times 2$ tiles, one can cover a $(2k+1)\times(2k+1)$ square but none larger. The results for $n\equiv 2,3\pmod 4$ are because no square can be congruent to those numbers mod 4; the result for $n\equiv 0\pmod 4$ is essentially trivial (pack the $1\times1$ tiles 4 at a time into $2\times2$ tiles). For the final case, just note that any tiling of a $(2t+1)\times (2t+1)$ square can only use $t^2\ 2\times2$ tiles, meaning that at least $4t+1$ squares are left over for the $1\times 1$ tiles - in other words, $n\geq 4t+1$, or seen the other way around, $f(n)\leq \frac{n+1}{2}$. Since this bound is acheivable, then the value is exactly $f(n)=\frac{n+1}{2}$.
For the case of trominos, either L or straight, your function $f()$ is ill-defined; the squares mod 6 are exactly 0, 1, 3, 4 so the number of $1\times 1$ blocks will have to be the same, but for any $n$ in the appropriate residue classes, arbitrarily large squares can be tiled. The core reason is simple: unlike the case where the 'extra' tiles are $2\times 2$, there's no 'squareness' or evenness constraint here on the number of extra tiles that can be placed. This means that from e.g. a tiling of a $5\times 5$ square one can then generate an $11\times 11$ square by abutting two edges with $5\times 6$ rectangles (made up of $2\times 3$ bricks, which are then made up of either the straight or ell pieces) and then putting a $6\times 6$ rectangle in the remaining corner; from this one can go on to build a $17\times 17$ square, etc. Since $6\times n$ rectangles are constructable for all $n\gt1$, any $k\times k$ square can be 'amplified' this way to get a $(k+6)\times(k+6)$ square. What's more, trying to force the tilings to be 'fault-free' probably won't be any help - it should be possible to use local changes to modify any of these tilings so there are no global faults.