Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

We want to tile $m\times m$-square using two types of tiles: $1 \times 1$-square tile and $2 \times 2$-square tile such that every underlying square is covered without overlapping. Let us define a function $f(n)$ that gives the size of largest uniquely tillable square using $n$ $1\times 1$-squares and any number of $2 \times 2$-squares.

Is this function computable? What is the algorithm?

EDIT1: Based on Steven's answer, unique tiling means that there is one way to place the $2 \times 2$-squares inside the $m \times m$-square with a unique configuration for the positions of the $n$ $1 \times 1$-squares inside the $m \times m$-square.

share|improve this question
1  
How is a unique tilling defined? For example, there could be 4 symmetric tillings. Would they be unique or not? –  Paresh Feb 9 '13 at 20:57
    
Symmetric tilings count as one configuration. –  Mohammad Al-Turkistany Feb 9 '13 at 21:43
1  
using $n$ 1-by-1 squares or using at most $n$? otherwise $f$ is not always defined: you cannot tile any square with 2 1-by-1 tiles and any number of 2-by-2 tiles, because the area would be $4x + 2$ and 2 is not a quadratic residue modulo 4. also by symmetries do you mean the dihedral group $D_4$? –  Sasho Nikolov Feb 9 '13 at 21:51
    
Ok. On those cases define $f(n)=0$. I'm not familiar with dihedral group D4. –  Mohammad Al-Turkistany Feb 9 '13 at 22:52
2  
I'm afraid I'm still at a loss - an example would go a long way towards helping understand, perhaps. How does the given answer not answer the question? –  Steven Stadnicki Feb 11 '13 at 5:43
show 9 more comments

1 Answer

up vote 7 down vote accepted

Here's an argument to prove my speculation in comments that no such unique tilings exist for any non-square $n\gt 5$. Firstly, as noted by Sasho in comments, $n$ must be restricted, because no such tilings exist if $n\equiv2$ or $3\pmod 4$. If $n$ is a perfect square $n=k^2$ then obviously the $k\times k$ square is uniquely tileable, so $f(n)$ is clearly defined and non-zero in these cases. To complete the argument, it just remains to show that no tiling involving $1$ or more $2\times 2$ tiles can be unique.

First, consider the case $n\equiv 0\pmod 4$, say $n=4k$. If we have a tiling of an $m\times m$ square using $n\ 1\times 1$ tiles, obviously $m$ must be even, say $m=2j$; then we can construct tilings by building a $j\times j$ tiling of $2\times2$ tiles and then replacing $k$ of these by 'blocks' of four $1\times 1$ tiles. It's clear that different replacements can always lead to distinct tilings except in the cases $m=4, n=12$ or $m=4, n=4$ where there's either a single $2\times 2$ tile or a single 'block of four' left over; in these cases, though, there's a different inequivalent tiling, one which puts a $2\times 2$ tile in the middle of an edge rather than in a corner.

Finally, suppose $n\equiv 1\pmod 4$, in particular presume $n=4t+1$ (and with $t\gt 1$ to prevent a slightly trivial case where there's simply 'not enough room' in the square for the following argument to go through). Then no square of size $(2t+1)^2$ or smaller can be uniquely tileable: consider a tiling with $1\times 1$ tiles across the top of the square and down the right of the square (with any extra $1\times 1$ tiles just tucked onto the right side — they can't affect the argument). Now the $2\times 3$ 'block' in the top-left of the square (consisting of the two $1\times 1$ tiles on the top and the $2\times 2$ tile beneath them) can be 'flipped' to produce a tiling that will necessarily be different from the tiling we've constructed. Finally, no square of size larger than $(2t+1)^2$ can be tileable at all: suppose we're trying to tile a square of size $(2s+1)^2$ for $s\gt t$; then by the pigeonhole principle we can't fit any more than $s^2\ 2\times 2$ tiles onto the square, which means that there are $(2s+1)^2-4s^2 = 4s^2+4s+1-4s^2=4s+1$ squares left over - but since $s\gt t$, $4s+1\gt 4t+1=n$, the number of $1\times 1$ tiles we have available.

Thus, the only unique tilings that exist for $n\gt 5$ are those that use no $2\times 2$ tiles at all, and $f(n)$ is only non-zero when $n$ is a square (in which case it equals $\sqrt{n}$).

share|improve this answer
    
since i was finding the part where you tuck leftover 1 by 1 tiles to the right iffy (maybe for no reason), here is a slightly different look at the case where $n = 4t + 1$ and the size of the square is $x^2 < (2t + 1)^2$. notice that $x \equiv 1$ or $x \equiv 3 \pmod 4$. in both cases it takes $2x - 1 \equiv 1 \pmod 4$ 1 by 1 tiles to build a border of thickness 1 for the square. then we're left with $n' \equiv 0 \pmod 4$ 1 by 1 tiles. in case $n' = 0$ we have $x = 2t + 1$ and you've dealt with that. otherwise we have reduced to the previous paragraph. –  Sasho Nikolov Feb 10 '13 at 7:03
    
Valid unique tiling must use both types of tiles. Sorry for not stating it clearly in my question. –  Mohammad Al-Turkistany Feb 10 '13 at 9:44
    
@MohammadAl-Turkistany Steven proves above that no such unique tilings exist for $n>5$. in fact the only "valid" unique tiling according to your definition is for $n=5$ (a single 2-by-2 tile and a "corner" of 5 1-by-1's). –  Sasho Nikolov Feb 10 '13 at 15:25
    
@Steven Thanks for your answer, my statment of the uniqueness requirement is not interesting since it leads to easily computable function. Do you think that it can be fixed by requiring that we pack the maximum number of $2 \times 2$-squares while posiblliy leaving some of the $m \times m$-squares uncovered? My motivation is to construct uncomputable function from a simple combainatorial problem. –  Mohammad Al-Turkistany Feb 11 '13 at 16:11
    
@Steven, your answer solves the orginal question but it is not exactly what motivated me to pose the question. I hope you are not bothered by modifying the question as I described it in the prevoius comment. –  Mohammad Al-Turkistany Feb 11 '13 at 16:27
show 5 more comments

Your Answer

 
discard

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.