2

Question: A 2018 x 2018 square is tiles with some 4 x 1 rectangles and some 2 x 2 squares. One of the 4 x 1 rectangles is removes and replaced with a 2 x 2 square. Is it still possible to tile the original 2018 x 2018 square with the new set of tiles? Justify your answer.

For this question I thought I could maybe start with simplifying the problem and using a smaller square to begin with but then ran into the problem of how I could simplify it in a relevant way. I thought if it were 2048 x 2048 it would be an easy simplification with it being a power of 2 and could hope to find a link between increasing powers of 2 but for this, I'm not sure how to simplify it or if that would even help draw to a solution. And especially as 2018 only has factors of 1, 2, 1009 and 2018)

Can someone please help with how to attack this question and how to then get to the solution, thanks in advance.

EricGunter7055
  • 105

2 Answers2

7

Colouring proofs are often nice when proving things about tilings. Exactly what coloring to use depends on the grid and the tiles you're using.

In this case, it works to colour the grid using three colours the following way:

enter image description here

The first, third, fifth (and so on) rows are red, blue, red, blue, etc. The second, fourth, sixth (and so on) rows are blue, green, blue, green, etc. (The blue ones are irrelevant.)

In your original tiling, any $1\times 4$ tile will cover either two red squares or two green squares. Any $2\times 2$ tile will cover one red square and one green square. (The two tiles behave differently with respect to the two colourings, which is nice)

Because there are an equal number of red and green squares ($1009^2$ of each), the number of $1\times 4$ tiles that cover two red squares must be equal to the number of $1\times 4$ tiles that cover green squares. In particular, there needs to be an even number of $1\times 4$ tiles. So tiling the grid after swapping out one is impossible.

Arthur
  • 199,419
1

There must be $pairs$ of both tiles to make up a larger even-numbered square. You can move one-or-more of one tile to fit the other but it is impossible to $replace$ one without turning a $pair$ of $4\times1$s into a $2\times2$. enter image description here

poetasis
  • 6,338
  • Sure, it turns out that this is the case. But it is not immediately obvious (and there is no reason for the pairings to be this clear). Just because your two tilings happen to have nice pairs, that doesn't show that it is necessary, and especially because your board isn't the same size as the one in the problem. – Arthur Aug 11 '19 at 19:11
  • You gave a very good answer, one I never would have thought about and I gave it one of the upvotes once I studied it. As for my tilings, they are large enough to demonstrate the pairing requirement of any even numbered $space\ge4\times4$. Note the $C$-shape in the middle bottom of the right pic. It was transformed from the $4\times6$ on the left. No matter how you shuffle any $other$ tiles on the even-square plane, you cannot make room for another $2\times2$ by removing a $4times1$. Both tiles must always come in pairs. – poetasis Aug 12 '19 at 16:45