0

If I have a $n\times m$ rectangular floor completely tessellated with $2\times 2 $ and $1 \times 4$ tiles and it now happens that I accidentally break one of those (no matter which one)- Can I then fix my misfortune if I only have one tile of the other kind left? (supposed that it is no problem to rearrange the remaining tiles) Any help would be appreciated.

Edit: Sorry for my bad wording.

  • 1
    I've never had an $n$ by $m$ floor, myself. – Will Jagy Sep 10 '14 at 21:42
  • @WillJagy what are you trying to say? –  Sep 10 '14 at 21:52
  • Which one is the one broken and which is the 'other kind'? – Steven Stadnicki Sep 10 '14 at 21:55
  • I suppose this: if you actually had a floor with this problem, you would likely be more specific. I suggest that this is a contest or homework question, which is largely alright on MSE. – Will Jagy Sep 10 '14 at 21:55
  • @WillJagy Ok I can understand why you think that. I'll fix my question to make it more fitting. –  Sep 10 '14 at 22:01
  • Something is likely wrong with the question. If the floor dimensions are $m\times n$, and the two sizes of tile available are $2m\times2m$ and $1m\times4m$, not even one of the $2m\times2m$ tiles will fit. – Steve Kass Sep 10 '14 at 22:14
  • (My earlier comment can no longer be edited, but the question has now been modified, so the question is okay now.) – Steve Kass Sep 10 '14 at 22:20

3 Answers3

5

Draw a grid of $1 \times 1$ squares on the floor and number them as follows:

\begin{bmatrix}1&i&-1&-i&1&i&-1&-i& \cdots \\ i&-1&-i&1&i&-1&-i&1& \cdots \\ -1&-i&1&i&-1&-i&1&i& \cdots \\ -i&1&i&-1&-i&1&i&-1& \cdots \\ 1&i&-1&-i&1&i&-1&-i& \cdots \\ i&-1&-i&1&i&-1&-i&1& \cdots \\ -1&-i&1&i&-1&-i&1&i& \cdots \\ -i&1&i&-1&-i&1&i&-1& \cdots \\ \vdots & \vdots & \vdots& \vdots& \vdots& \vdots& \vdots& \vdots & \ddots\end{bmatrix}

Define a tile's "tile-sum" as the sum of the numbers it covers.

Each $1 \times 4$ tile has a tile-sum of $0$ no matter how it is placed.

Each $2 \times 2$ tile can have a tile-sum of $2$, $2i$, $-2$, or $-2i$ depending on where it is placed.

The sum of the tile-sums of all the tiles is $(1+i+\cdots+i^{m-1})(1+i+\cdots+i^{n-1}) = \dfrac{(1-i^m)(1-i^n)}{(1-i)^2} = \dfrac{i}{2}(1-i^m)(1-i^n)$

If $m$ or $n$ is a multiple of $4$, then the sum of tile-sums is $0$. Thus, we need $a$ tiles with tile-sum $2$, $a$ tiles with tile-sum $-2$, $b$ tiles with tile-sum $2i$, and $b$ tiles with tile-sum $-2i$. Thus, the total number of $2 \times 2$ tiles is $2(a+b)$ which is even.

If $m$ and $n$ are both $2 \pmod 4$, then the sum of tile-sums is $2i$. Thus, we need $a$ tiles with tile-sum $2$, $a$ tiles with tile-sum $-2$, $b+1$ tiles with tile-sum $2i$, and $b$ tiles with tile-sum $-2i$. Thus, the total number of $2 \times 2$ tiles is $2(a+b)+1$ which is odd.

If $m$ and $n$ are both not multiples of $4$ and only one is a multiple of $2$, then you can't tile the floor.

Therefore, given an $m \times n$ floor, the pairity of the number of $2 \times 2$ tiles needed is constant. Do you see the problem?

JimmyK4542
  • 54,331
2

Not in general. Say you had a $2 \times 2$ floor tessellated by a single $2 \times 2$ tile. If you broke that tile you'd be SOL, since your $1 \times 4$ tile would be too long. Similar situations could occur for a $1 \times n$ floor.

genisage
  • 427
  • In fact. I suspect but don't have a proof, that it will never work out. Since m and n must both be even, so you need an even number of both vertical and horizontal skinny tiles (if you had an odd number the squares wouldn't be able to cover the rest). So adding or subtracting just one from a tiling should never work. – genisage Sep 10 '14 at 22:06
  • Your example doesn’t meet the specifications in the question. If $m=n=2$, there is no tiling with $4\times4$ and $2\times8$ tiles to begin with. ($2\times2$ tiles are not one of the choices in the case of a $2\times2$ floor.) – Steve Kass Sep 10 '14 at 22:12
  • huh? the question doesn't say anything about $4 \times 4$ tiles and I don't anything about the available tiles depending on the dimensions of the floor. – genisage Sep 10 '14 at 22:17
  • The question has been changed. When I commented, it gave the available tile sizes as $m\times4m$ and $2m\times2m$. – Steve Kass Sep 10 '14 at 22:18
  • @SteveKass you are right. But by $2m \times 2m$ I meant to say 2 meter by 2 meter tile etc. sorry. My fault. –  Sep 10 '14 at 22:22
  • 1
    In the case that one suspects such a situation can never exist, the question may be formulated as follows: "Show that there are no positive integers $m, n$ such that there simultaneously exist tilings of a $m \times n$ rectangle with $a-1$ $2\times 2$ and $b$ $1 \times 4$ tiles, and $a$ $2 \times 2$ and $b-1$ $1 \times 4$ tiles." – heropup Sep 10 '14 at 23:32
0

So you break $1\times 4$ and then take the broken piece out. Take $3$ more of the $1\times 4$ pieces out and then you should have enough room for a $4\times 4$ depending on the arrangement. If you break the $4\times 4$ you will never have enough pieces because all you have left is a $1\times 4$. So your mistake is there.

k170
  • 9,045
Josh Little
  • 1