Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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.

Unfortunately, there are no relatively 'simple' tiling problems that are known to be undecidable, and while I wouldn't say there can't be any, they seem unlikely to me - there's just too much structure in the space of solutions to allow for undecidability. (Of course, one can transcribe Wang tiles into polyominos and get undecidability of arbitrary polyomino tiling that way, but the tiles in question are much more complicated than it sounds like you're after.)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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