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.
Asked By : Mohammad Al-Turkistany
Answered By : Steven Stadnicki
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}$).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/9621
0 comments:
Post a Comment
Let us know your responses and feedback