9
$\begingroup$

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.

$\endgroup$
14
  • 1
    $\begingroup$ How is a unique tilling defined? For example, there could be 4 symmetric tillings. Would they be unique or not? $\endgroup$
    – Paresh
    Commented Feb 9, 2013 at 20:57
  • $\begingroup$ Symmetric tilings count as one configuration. $\endgroup$ Commented Feb 9, 2013 at 21:43
  • 1
    $\begingroup$ 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$? $\endgroup$ Commented Feb 9, 2013 at 21:51
  • $\begingroup$ Ok. On those cases define $f(n)=0$. I'm not familiar with dihedral group D4. $\endgroup$ Commented Feb 9, 2013 at 22:52
  • 2
    $\begingroup$ 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? $\endgroup$ Commented Feb 11, 2013 at 5:43

1 Answer 1

7
$\begingroup$

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}$).

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$ Commented Feb 10, 2013 at 7:03
  • $\begingroup$ Valid unique tiling must use both types of tiles. Sorry for not stating it clearly in my question. $\endgroup$ Commented Feb 10, 2013 at 9:44
  • $\begingroup$ @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). $\endgroup$ Commented Feb 10, 2013 at 15:25
  • $\begingroup$ @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. $\endgroup$ Commented Feb 11, 2013 at 16:11
  • $\begingroup$ @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. $\endgroup$ Commented Feb 11, 2013 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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